基于社群挖掘的用户个性化信息推荐方法研究-余以胜.pdf

《基于社群挖掘的用户个性化信息推荐方法研究-余以胜.pdf》由会员分享，可在线阅读，更多相关《基于社群挖掘的用户个性化信息推荐方法研究-余以胜.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、情报学报 2017年10月 第36卷 第10期 Journal of the China Society for Scientific and Technical Information, Oct. 2017, 36(10): 1093-1098 收稿日期: 2017-03-25; 修回日期: 2017-07-01 基金项目: 广东省公益研究与能力建设专项“基于社会网络分析的区域协同创新体系研究” ( 2014B0714021388) 。 作者简介: 余以胜,男, 1975 生,博士,副教授,主要研究方向为电子商务与信息经济;徐剑彬,男, 1991 年生,硕士,主要研究方向为商务智能、社会化网

2、络、个性化推荐;刘鑫艳,女, 1992 年生,硕士,主要研究方向为个性化推荐、文献计量学, E-mail: 。 基于社群挖掘的用户个性化信息推荐方法研究 余以胜1,徐剑彬2,刘鑫艳1( 1. 华南师范大学经济与管理学院,广州 510006; 2. 顺丰控股(集团)股份有限公司,深圳 518000) 摘 要 当前情报学科的发展目前呈现出多维度、跨学科等特点,而结合个性化信息推荐算法,可为其注入新活力。本文的研究是为了提高个性化信息推荐的效果,解决个性化信息推荐的稀疏性问题,以期可以促进情报学科的新发展,为此,我们引入了社群挖掘概念,得到 TO 算法,在协同过滤或关联规则推荐之前先对数据进行社团划

3、分,通过对 Book-crossing 公开数据集的验证分析,并与对照算法相比,我们发现 TO 算法的准确率和调和度都最佳。 关键词 社群挖掘;个性化推荐;情报学科建设 Research on Personalized Information Recommendation Based on Community Structure Mining Yu Yisheng1, Xu Jianbin2and Liu Xinyan1(1. Department of Economics and Management, South China Normal University, Guangzhou 510

4、006; 2. S.F. Express, Shenzhen 518000) Abstract: The development of information science is characterized by its multi-dimensional, interdisciplinary nature, and a personalized recommendation algorithm will inject new vitality into it. The research presented in this paper aims to improve the effect o

5、f personalized recommendation and to solve the sparseness problem of individual rec-ommendations, to promote new developments in information science. To this end, we import community structure mining into personalized recommendation, which is called the TO algorithm. We mine the community structure

6、of users and items before performing association rule exploration and collaborative filtering. The empirical test based on the Book-Crossing open dataset proves that the precision and F of the proposed algorithm is the best among com-parison algorithms. Key words: community structure mining; persona

7、lized recommendation; information science construction 1 引 言 随着互联网技术的迅速发展,情报学在方法移植、学科交叉的学术背景下呈现出跨领域、多维度的发展态势,情报信息也展示出爆炸式的发展趋势,那么该领域的学者如何能全面、精准、便捷的获取所需信息,减少信息冗余,这成为研究者要深入研究的一个重要课题。因此,作为解决信息过载最有效的手段之一的用户个性化信息推荐方法应运而生,学术圈对其认可程度也正在快速提升。我们将基于社群挖掘的用户个性化信息推荐方法进一步应用在网络信息资源管理、企业竞争情报、信息传播等领域,希望个性化信息推荐方法为情报学带来

8、新的研究思路和方法,促进情报学的发展1。 万方数据1094 情 报 学 报 第 36 卷 目前为用户提供个性化信息推荐服务已经成为众多网络平台的发展方向,然而我们也清楚地认识到,虽然个性化信息推荐在情报学研究上有一定的优势,但是将不同的个性化推荐算法运用到信息服务中去,或多或少都会存在数据稀疏性问题、冷启动问题以及系统扩展性问题等关键性问题。因此本文结合之前学者对个性化信息推荐算法的相关研究,引入社群挖掘的思想,以解决个性化信息推荐算法存在的问题,以期可以提升个性化信息推荐算法的效果。 2 研究综述 2.1 社群挖掘算法研究综述 互联网上的信息纷繁复杂,学者在进行学术研究时需要花费大量时间进行

9、筛选,那么如何对其信息内容进行分析,挖掘出人们所需的内容就成为一个学术界研究热点。社群挖掘是解决这一问题的有效途径之一,它不仅可以节省学者和用户的时间,而且可以提高他们分析的效率。当然,社群挖掘的使用,也可以帮助学者发现和自己有相同研究方向的“学术社群” ,积极开展学术交流和资源共享,共同促进情报学科的发展。 网络中的社群挖掘是指在复杂网络中找到那些社群内部有紧密联系,社群之间联系尽可能少的部分结构,其中,社群挖掘算法多年来一直是研究热点。社群挖掘从原理上讲,就是将网络结构中联系较为紧密的节点聚集成为一类,从而得到社群结构,这本质上也是数据挖掘中的聚类算法的思想,因而社群挖掘也可以采用聚类算法

10、。 按照刘大有等2的观点, 可以按照采用的基本原理归纳为五种:基于划分、基于模块性优化、基于标签传播、基于动力学和基于仿生计算的方法。根据本文需要,主要对划分法和基于模块度优化的方法进行总结。 划分法的基本原理是通过删除网络中的社群之间的链接,得到剩余的结构即为社群,其代表算法是著名的 GN 算法3, 发表者是著名的社群结构挖掘大师 Newman。其次是由 Duch 等4提出的 EO 算法。Newman5还提出了重要的概念模块度 Q,基于模块性优化的算法就是把 Q 作为目标函数进行优化得到社群的算法,代表算法是 Newman 提出的 FN 算法6和在 FN 算法基础上改进得到的 CNM 算法7

11、。 2.2 个性化推荐算法研究综述 近几年,学者对推荐系统的研究热情不减,但是已有的推荐系统并没有考虑到在情报领域应用的特殊性,比如,信息热度、实时性问题,最终导致了对情报信息推荐的效果不佳8。 个性化推荐是近几年信息检索、信息系统和人工智能领域关注的热点,个性化推荐的出现,将信息推送的精准度大大提升。情报学科近几年的发展特点越来越趋向于跨学科,多领域,如果将二者结合,为学者进行个性化情报信息推荐服务,相信可以大大提大科研效率,促进科研水平的提升。 推荐算法是个性化推荐系统设计中的核心,也是个性化推荐中的研究热点。不同的推荐算法拥有不同的优缺点,没有任何一种算法能适用所有情况,因此根据不同的条

12、件选择适应的算法或者其变形就成为了个性化推荐算法的重点。目前,推荐算法主要有基于内容的个性化推荐算法,基于协同过滤算法、基于关联规则的算法,基于组合模型的个性化推荐算法、基于社交网络的推荐算法、基于网络结构的推荐算法等类别。根据本文的研究需要,主要对基于关联规则、基于内容的推荐算法和协同过滤算法进行简单的总结。 基于关联规则的推荐就是利用关联规则进行推荐,而关联规则最经典的例子就是沃尔玛的“啤酒与尿布”的故事,类似沃尔玛这样,当有顾客购买啤酒时,就向其推荐尿布就是基于关联规则的个性化推荐。 关联规则挖掘的代表算法有由 Agrawal 等9提出的 Apriori 算法, 以及 Han 等10提出

13、的 FP-Growth算法。 Apriori 算法是一种迭代算法,其核心思想是通过生成候选集和向下封闭检测两个阶段来挖掘频繁项集。缺点是每次迭代都需要扫描一次数据,较为繁琐,当数据量极大时运算量容易超负荷,但Apriori 算法拓展性比较好,也容易实现分布式计算从而极大提高运算能力。 FP-Growth 算法则相反,其基于大型树形结构的计算过程有效减少了运算的负荷,但是相应的拓展性能明显弱于 Apriori。 基于内容的推荐算法最大的优势在于没有冷启动问题,即不需要用户及物品的原始数据积累,特别适合进入推荐的新用户及新物品。基于内容的推荐系统中,有三部分主要算法:物品的特征提取算法、建立用户模

14、型算法、对象特征和用户模型相似度算法。基于内容的推荐主要是根据用户的喜好和对物品的评分进行推荐,其中的重点是物品的特征提取,一般采用 TF-IDF 算法,其中 Salton 等11和林万方数据第 10 期 余以胜等:基于社群挖掘的用户个性化信息推荐方法研究 1095 霜梅等12都提出了经典的采用向量空间模型进行描述;建立用户模型会采用的算法主要有决策树分类算法,贝叶斯分类算法,基于概率模型的方法和线性分类器,神经网络;而对象特征和用户模型相似度算法一般则会采用向量夹角余弦法计算。郝水龙等13提出了经典的用层次向量空间模型对用户兴趣特征进行表示。 协同过滤技术是由 D. Goldberg 等在

15、1992 年首次提出的 , 是一种根据用户的评价信息来选择信息的一种信息过滤技术14。基于协同过滤算法的主要思想是计算物品或者用户的相似度进行推荐,因此需要考虑用户的购物数据积累。协同过滤算法的核心算法在于相似矩阵,根据相似矩阵建立的对象分为用户协同过滤和物品协同过滤。其中基于用户协同过滤算法是由 Breese 等15提出,随后 Chen 等16则提出了通过不同产品在用户的列表次序来计算用户与用户的相似度, Yang 等17则提出建立用户的兴趣点,从而得出用户间的相似程度。而最早提出可 靠的基于项目的协同过滤算法的有 Yang 等18、Sarwar19、邓爱林等20,其中提出经典的利用夹角余弦

16、来计算产品的相似程度的是 Sarwar 等19。 近年来,针对基于 Web2.0 环境下的个性化信息推荐方法研究很多,社会化标注系统就是典型的应用,这种系统允许用户对其所关注的资源进行关键字标识,同时为用户共享资源提供了一个开放的社会化环境21。将用户社群划分的思想运用于此,将会更好的优化社会化标注系统的效率。 3 推荐方法设计及评测指标 3.1 推荐方法设计 上文提到,个性化信息推荐方法目前存在的问题主要是数据稀疏性问题,冷启动问题、扩展性问题以及推荐准确性等问题。以解决其中几个问题作为目标,本文在个性化信息推荐流程中引入社群挖掘的思想,将目标用户网络细分成不同的子社群,在兴趣相近的子社群中

17、进行推荐,此外,运用基于内容的个性化信息推荐方法,可以很好地解决物品冷启动和用户冷启动的关键问题,具体推荐系统流程设计如图 1 所示。 图 1 推荐系统流程设图 上文提到基于用户的协同过滤算法,而协同过滤算法主要通过用户的行为的相似度计算兴趣的相似度。给定用户 U1和用户 U2,令 N(U1)为用户 U1有过购买行为的产品集合,令 N(U2)表示用户 U2有过购买行为的产品集合。通过 Jaccard 公式,可以计算 U1和 U2的兴趣相似度,表示如下: ( ) ( )() ()121212UUNU NUwNU NU=( 1) 余弦相似度计算法方法,表示如下: ( ) ( )()()121212

18、UUNU NUwNU NU=( 2) 自 Newman 提出社团结构的概念以来,社会网络的划分算法很多,具有代表性的有 Newman 快速算法、 CNM 算法、 EO 算法等, Newman 快速算法是一种凝聚算法, 给定初始网络有 n 个社群,即一个节点就是一个社群,给定初万方数据1096 情 报 学 报 第 36 卷 始值 eij和 ai,表示如下: ()()1/20ijijme=如果节点 与 之间有边则否连接( 3) /2iiak m= ( 4) 其中, ki是节点 i 的度, m 为社群的总边数。 EO 算法的提出是在 Newman 算法的基础进行优化,它基于 Newman 定义的全局

19、模块 Q 值来定义局部模块 q 值, q 值是全局 Q 值在局部模块的反映,局部模块的 q 值可以用i 来表示,一般定义如下: ,igigea =- ( 5) 其中,g ie 是顶点 i 与社群 g 内部连接的边占全部边的比例, ag是指社群 g 所有的边占整个网络边的比例, 局部模块 q 值是用来表示节点 i 对社群 g 的隶属程度。 EO 算法在实现不知道社群数目的情况下,它能自动根据 q 值的优化确定社群的数量。 考虑式( 2)和式( 5)两组公式进行社群划分,给定一个值 , 用来衡量节点之间的关系度,表示如下: 2w += ( 6) 给定一个阈值区间,只有符合预先设置阈值的节点才能归入

20、到一个社群当中,本文也采取以上方式实现购买图书用户细分社团的划分。 3.2 评测指标 社会网络社群计算精度对比常用的指标是NMI,可以定义为: ,2logNMIlog logijijijijjiijNNNNNNNNNNN- |=+|( 7) 其中, N 表示由两种不同算法所计算出来的社群对应的混合矩阵; Nij表示同时包含在社团 ci和 cj中的节点数; Ni表示 N 的第 i 行元素之和。 NMI 的取值范围为 0,1,其 中 0 表示两个社群集合完全不同, 1 表示两个社群集合完全相同。显然, NMI 值越大,网络社团精度更高。本文将 NMI 值与上文提到的 Q 值作为社群划分的两个评价指

21、标。 个性化推荐系统最终一般是给用户生成一个推荐列表,这种推荐方式称之为 Top-N 推荐。 Top-N推荐的预测准确率一般通过准确率( Precision)和 召回率( Recall)度量。 给定 R(u)根据训练集产生的推荐列表, T(u)是测试集上的用户行为列表。推荐结果的召回率可以表示为: ( ) ( )()RecalluUuURu TuTu=( 8) 推荐结果的准确率可以表示为: ( ) ( )()PrecisionuUuURu TuRu=( 9) 因准确率和召回率两者具有一定的矛盾性,因此前人提出一个综合的评价指标 F,称之为调和度,一般来说调和度越大,则推荐效果越好,调和度 F定

22、义如下: ( )()2 Precision RecallPrecision RecallF=+( 10) 4 数据处理及结果分析 本章采用 Book-crossing 公开数据集。该数据集包含 278858 位用户对 271379 本书籍的 1149780 条评分,此数据集是一个评分数据集,因本文着重研究隐反馈数据集中的 Top-N 推荐问题,因此忽略了数据集中的评分记录。随机从以上筛选出的 970 位用户对 322 本书籍的行为数据,随机选取 100 位用户作为网络节点。分别运行 Newman 算法、 EO 算法以及 TO 算法,在运算节点间是否属于同一社团时,看节点与节点之间是否有边连接,

23、因此假定节点之间有联系为 1,节点之间没有关联为 0,因此可以设定阈值区间为 0,1,得到的社团划分结果与精度都是一样的,此处拟定初始阈值为 0.1,密度为 0.001(即迭代运算 1000 次) ,得到的运行结果如表 1 所示。 表 1 社群挖掘算法结果评价 算法名称 Newman EO TO 社团数量 5 5 6 Q 值 0.727 0.712 0.786 NMI 值 0.87 0.84 0.92 从表 1 不难看出, TO 算法舍弃了一些离异节点后,无论在社群模块度还是社群划分精度都有更好的表现。为了更好地体现社群划分结果,图 2 为运用 TO 算法运行后产生的社群划分图,图中可以看出,

24、社群结构划分明显,不同的社群结构体现出不同的细分用户群体。 万方数据第 10 期 余以胜等:基于社群挖掘的用户个性化信息推荐方法研究 1097 根据实验设计,我们选取用户评分的最后一本书作为预测的目标,因此每个用户的测试集大小为1, TOP-N 推荐中将 N 取值为 10,15,20,25,30,支 持度预设为 0.05,0.10,0.15,0.20,0.25,0.30,0.35, 选取个性化推荐中的 F 值调和度作为推荐系统的评测指标,实验结果如表 2 所示。 图 2 本文算法社群划分结果图 表 2 个性化推荐指标测试结果 N/min_sup 0.05 0.10 0.15 0.20 0.25

25、 0.30 0.35 10 0.315 0.323 0.338 0.346 0.359 0.354 0.353 15 0.327 0.337 0.344 0.357 0.364 0.357 0.354 20 0.333 0.347 0.356 0.368 0.393 0.383 0.379 25 0.346 0.355 0.367 0.373 0.388 0.376 0.364 30 0.348 0.353 0.364 0.373 0.386 0.374 0.361 从表 2 可以看出,当最小支持度选择 25,TOP-N 推荐选择 20 的时候,推荐系统的调和度表现最佳,选择此规则作为标准,给

26、定传统推荐算法基于内容的推荐算法( CBF) 、基于用户的协同过滤推荐算法( UserCF) 、基于项目的协同过滤推荐算法( ItemCF) 、基于关联规则的推荐算法( AF) 、基于社群挖掘的关联规则算法( TAF) ,详细指标如表 3所示。 由表 3 可以看出,在给定推荐列表数量为 20 的情况下,对比准确率和调和度, TAF 效果最佳;召回率方面 CBF 表现最好,而 TAF 也有相当不错的数据表现。 综上所述,本文提出的将社群挖掘思想融入到基于用户的协同过滤推荐中,将兴趣相近的用户进行了社团细分,同时在社团细分的基础之上对再寻找更相似的用户,传统的推荐步骤往往只通过一个指标去衡量用户之

27、间的相似性,而本文结合了用户相似度以及社团划分的 q 值i 两者进行用户细分社团的划分,可以更加准确地划分用户社团,从而在一定程度提升个性化信息推荐方法的准确度,并解决目前存在的一些数据稀疏性、准确率不高等问题。 表 3 各算法个性化推荐对比 准确率( Precision) 召回率( Recall) 调和度 F CBF 0.454 0.363 0.403432069UserCF 0.487 0.349 0.406610048ItemCF 0.466 0.361 0.406834341AF 0.473 0.344 0.398315789TAF 0.523 0.347 0.417197701万方数

28、据1098 情 报 学 报 第 36 卷 5 总 结 本文将社群挖掘的思想引入到个性化情报信息推荐方法当中,将社会化网络中的用户细分成不同的用户社群,在不同的兴趣细分社群中进行用户相似性的计算,并在细分社群中计算推荐算法的准确度,一定程度上缓解了数据稀疏性的问题,而同时在缓解数据稀疏性的同时,推荐算法的准确度得到了提升,调和度也表现不错。在实际运用中,以此方法作为情报推荐系统的基准,而当系统中出现新用户和新物品时同样可以采用基于内容的个性化信息推荐方法,将其划分至不同的物品或用户社群中,能够解决个性化信息推荐系统冷启动的问题。这种情报信息推荐方法在现实生活中也适用于大多数需要个性化推荐的应用场

29、景,如购物、交友、新闻、图书推荐等。 此外,网络时代用户的兴趣点是变化很快的,用户的兴趣也是随着时间而发生漂移的,未来的研究工作可以将兴趣漂移考虑进来。 参 考 文 献 1 刘小玲 , 谭宗颖 . 复杂网络社团结构划分算法的情报学应用研究 J.图书馆学研究 , 2011(8): 20-25. 2 刘大有 , 金弟 , 何东晓 , 等 . 复杂网络社区挖掘综述 J. 计算机研究与发展 , 2013, 50(10): 2140-2154. 3 Girvan M, Newman M E J. Community structure in social and biological networksJ

30、. Proceedings of the National Academy of Science of the United States of America, 2002, 99(12): 7821- 7826. 4 Duch J, Arenas A. Community detection in complex networks u-sing extremal optimizationJ. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2005, 72: 027104 5 Newman M E, Gi

31、rvan M. Finding and evaluating community structure in networksJ. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2004, 69: 026113. 6 Newman M E J. Fast algorithm for detecting community structure in networksJ. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 20

32、04, 69: 066133. 7 Clauset A, Newman M E J, Moore C. Finding community struc-ture in very large networksEB/OL. 2008-12-20. http: /www. ece.unm.edu/ifis/papers/community-moore.pdf. 8 王星星 . 基于网络热点的个性化情报推荐系统设计与实现 D. 上海 : 华中师范大学 , 2014. 9 Agrawal R, Srikant R. Fast algorithms for mining association rules

33、 in large databasesC/ Proceedings of the 20th International Conference on Very Large Data Bases. San Francisco: Morgan Kaufmann Publishers, 1994: 487-499. 10 Han J W, Pei J, Yin Y W. Mining frequent patterns without can-didate generationC/ Proceedings of the 2000 ACM SIGMOD International Conference

34、on Management of Data. New York: ACM Press, 2000: 1-12. 11 Salton G, Buckley C. Term-weighting approaches in automatic text retrievalJ. Information Processing & Management, 1988, 24(5): 513-523. 12 林霜梅 , 汪更生 , 陈弈秋 . 个性化推荐系统中的用户建模及特征选择 J. 计算机工程 , 2007, 33(17): 196-198. 13 郝水龙 , 吴共庆 , 胡学钢 . 基于层次向量空间模型

35、的用户兴趣表示及更新 J.南京大学学报 (自然科学版 ), 2012, 48(2): 190-197. 14 马文峰 , 高凤荣 , 王珊 . 论数字图书馆个性化信息推荐系统 J. 现代图书情报技术 , 2003(2): 16-18. 15 Breese J S, Heckerman D, Kadie C. Empirical analysis of predic-tive algorithms for collaborative filteringC/ Proceedings of the Fourteenth Conference on Uncertainty in Artificial

36、Intelli-gence.San Francisco: Morgan Kaufmann Publishers, 1998: 43-52. 16 Chen Y L, Cheng L C. A novel collaborative filtering approach for recommending ranked itemsJ. Expert Systems with Applica-tions, 2008, 34(4): 2396-2405. 17 Yang M H, Gu Z M. Personalized recommendation based on partial similari

37、ty of interestsJ. Advanced Data Mining and Ap-plications Proceedings, 2006, 4093: 509-516. 18 Yang W S, Cheng H C, Dia J B. A location-aware recom-mender system for mobile shopping environmentsJ. Expert Systems with Applications, 2008, 34(1): 437-445. 19 Sarwar B, Karypis G, Konstan J, et al. Item-b

38、ased collaborative filtering recommendation algorithmsC/ Proceedings of the 10th International Conference on World Wide Web. New York: ACM Press, 2001: 285-295. 20 邓爱林 , 朱扬勇 , 施伯乐 . 基于项目评分预测的协同过滤推荐算法 J. 软件学报 , 2003, 14(9): 1621-1628. 21 吴克文 , 朱庆华 , 赵翔宇 , 等 . 社会化标注系统中标签检索质量模拟研究 J. 情报学报 , 2011, 30(1): 29-36. (责任编辑 车 尧) 万方数据