基于用户邻域和主题的新颖性web社区推荐方法-余骞.pdf

《基于用户邻域和主题的新颖性web社区推荐方法-余骞.pdf》由会员分享，可在线阅读，更多相关《基于用户邻域和主题的新颖性web社区推荐方法-余骞.pdf（19页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、 软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: Journal of Software,2016,27(5):12661284 doi: 10.13328/ki.jos.004882 http:/ 中国科学院软件研究所版权所有 . Tel: +86-10-62562563 基于用户邻域和主题的新颖性 Web 社区推荐方法余 骞2, 彭智勇1,2, 洪 亮3, 万言历21(软件工程国家重点实验室 (武汉大学 ),湖北 武汉 430072) 2(武汉大学 计算机学院 ,湖北 武汉 430072) 3(武汉大学 信息管理学院 ,湖北 武汉 430072) 通讯

2、作者 : 彭智勇 , E-mail: ; 洪亮 , E-mail: 摘 要 : 社区推荐从海量社区中为用户过滤出有价值的社区 ,变得越来越重要 .新颖性推荐逐渐得到关注 ,因为单纯追求准确度的推荐结果存在局限性 .已有新颖性推荐方法不适用于社区推荐 ,因其无法处理 Web 社区特性 ,包括社区成员用户通过交互形成的关系网络以及社区主题 .提出了一种新颖性社区推荐方法 NovelRec,向用户推荐其有潜在兴趣但不知道的社区 ,旨在拓展用户视野和推动社区发展 .NovelRec 基于用户交互网络中的邻域关系 ,利用用户之间在主题上的关联 ,计算候选社区对用户的准确度 ;根据用户与社区在邻域和主题

3、上的关联 ,提出一种用户社区距离度量方式 ,并利用该距离计算候选社区的新颖度 .在此基础上 ,NovelRec 最终进行新颖性社区推荐 ,并兼顾推荐结果的准确性 .真实数据集上的对比实验结果表明 ,NovelRec 方法在新颖性上优于现有方法 ,同时能够保证推荐结果的准确性 . 关键词 : 网络社区 ;新颖性推荐 ;用户邻域 ;主题分类 中图法分类号 : TP311 中文引用格式 : 余骞 ,彭智勇 ,洪亮 ,万言历 .基于用户邻域和主题的新颖性 Web 社区推荐方法 .软件学报 ,2016,27(5):1266 1284. http:/ 英文引用格式 : Yu Q, Peng ZY, Hon

4、g L, Wan YL. Novel Web community recommendation based on user neighborhood and topic. Ruan Jian Xue Bao/Journal of Software, 2016,27(5):12661284 (in Chinese). http:/ Novel Web Community Recommendation Based on User Neighborhood and Topic YU Qian2, PENG Zhi-Yong1,2, HONG Liang3, WAN Yan-Li2 1(State K

5、ey Laboratory of Software Engineering (Wuhan University), Wuhan 430072, China) 2(School of Computer, Wuhan University, Wuhan 430072, China) 3(School of Information Management, Wuhan University, Wuhan 430072, China) Abstract: Community recommendation has become increasingly important in sifting valua

6、ble communities from massive amounts of communities on the Internet. In recent years novel recommendation is attracting attention, because of the limitation of accurate recommendation which purely pursues accuracy. Existing novel recommendation methods are not suitable for Web community as they fail

7、 to utilize unique features of Web community, including the social network established by interactions between users, and the topics of Web community. In this paper, a novel recommendation method, NovelRec, is proposed to suggest communities that users have not seen but are potentially interested in

8、, in order to better broaden users horizons and improve the development of communities. Specifically, the method explores neighborhood relationships and topical associations from the aforementioned features. First, NovelRec identifies 基金项目 : 国家自然科学基金 (61232002, 61303025); 武汉科技局高新技术产业科技创新团队培养计划 (2014

9、070504020237) Foundation item: National Natural Science Foundation of China (61232002, 61303025); Program for Innovative Research Team of Wuhan of China (2014070504020237) 收稿时间 : 2015-01-09; 修改时间 : 2015-03-18; 采用时间 : 2015-08-05; jos 在线出版时间 : 2016-01-11 CNKI 网络优先出版 : 2016-01-12 11:22:18, http:/ 余骞 等

10、:基于用户邻域和主题的新颖性 Web 社区推荐方法 1267 candidate communities for users based on neighborhood relationships between users, and computes accuracy of the candidates using topical associations between users. Next, NovelRec computes novelty of the candidates based on a new metric of user-community distance, and

11、the distance metric is defined by associations between users and communities on both user neighborhood and topic taxonomy. Finally, NovelRec balances novelty with accuracy for the candidates to improve the overall recommendation quality. Experimental results on a real data set of Douban communities

12、show that the proposed method outperforms competitors on the recommendation novelty, and guarantees the recommendation accuracy. Key words: Web community; novel recommendation; user neighborhood; topic taxonomy Web 社区作为社交网络的重要组成部分正持续高速增长 (http:/ 2011/social-media-report-q3.html).为解决海量 Web 社区带来的信息过载问

13、题 ,社区推荐通过信息过滤帮助用户选择有价值的社区加入 .已有大多数推荐方法属于准确性推荐16,该类方法旨在提高推荐准确度 ,认为推荐结果与用户历史偏好越接近 ,准确度越高、推荐效果越好 .然而单纯追求高准确度会降低推荐系统质量7.在社区推荐场景下 ,准确性方法存在以下两个方面的问题 :(1) 用户可能对准确性推荐结果不满 :准确性方法旨在推荐与用户历史偏好接近的社区 ,同时倾向于推荐大众流行的社区8,则用户可能因为已知被推荐的社区而产生不满 .(2) 社区提供商可能对准确性推荐结果不满 :准确性推荐对大众流行社区的倾向 ,会产生 “穷者越穷富者越富 ”的马太效应 ,使得小众不流行的社区很难被

14、推荐 ,而占大多数的小众社区 (帕累托法则 ,即 80/20 法则 )却有能力吸引大量用户加入9,则社区提供商可能因为小众社区很难进入推荐列表而不满 .鉴于准确性推荐方法存在的问题 ,新颖性推荐方法逐渐得到关注8,1015.新颖性社区是指用户有潜在兴趣但不知道的社区16.图 1 通过从豆瓣社区 (http:/ ,比较了准确性与新颖性社区推荐 . qu1c2c3c12,cc1c3c23,cc3,quc1u2u3uFig.1 Illustration: Accurate vs. novel community recommendation 图 1 准确性 vs. 新颖性社区推荐示例 图 1 中目标

15、用户 uq加入的社区 c2为其历史偏好 .准确性社区推荐更可能向 uq推荐社区 c1:c1与 uq的历史偏好 c2接近 ,在主题上两者同为情景喜剧 .新颖性社区推荐则更可能向 uq推荐社区 c3:uq对 c3有潜在兴趣 ,因与uq存在间接交互的用户加入了该社区 ;uq可能不知道该社区 ,因 c3在主题上距离 c1较远 ,且在交互关系上距离 uq较远 .图示新颖性社区推荐利用了 Web 社区特性 ,包括社区成员用户交互所形成的网络以及社区主题 .新颖性社区距离目标用户历史偏好较远 ,更有利于拓展用户视野 ;新颖性社区推荐更有利于推动社区发展 ,因其能更多地覆盖占大多数的小众社区 ,而大量的小众社

16、区有能力吸引大量用户加入 . 近年来提出的新颖性推荐方法8,1015利用用户与推荐项的交互 ,即用户 -项评分矩阵进行新颖性推荐 .然而已有新颖性方法不适用于 Web 社区推荐 ,原因如下 :(1) 已有新颖性方法不能将用户交互网络用于推荐社区 ,而存在交互关系的用户其行为会相互影响17,18;如图 1 中 u2和 u3加入 c3会对 uq选择社区产生影响 .(2) 已有新颖性方法不能利用用户、 社区通过社区主题产生的关联 ,而这些关联会影响用户对社区的选择19;如图 1 和图 2(见第 2 节 )所示 ,uq通过 c2以及社区主题 (分类 )与 c1和 c3产生间接关联 ,该关联会影响 uq

17、对 c1和 c3的选择 .(3) 已有方法缺少合理的新颖度定义 ,从而无法客观衡量项的新颖度 (详见第 1.2 节 ). 在真实社会网络中 ,存在邻域关系 (即 1 跳或多跳的社会关系 )的用户 ,其行为会相互影响 ;而且 Web 社区之间存在主题上的关联 .因此 ,为了进行高质量的新颖性社区推荐 ,本文提出基于用户邻域和主题的新颖性推荐方法 NovelRec.该方法从用户交互网络中建模用户邻域 ;利用社区分类和用户 -社区交互建模用户之间、用户与社 1268 Journal of Software 软件学报 Vol.27, No.5, May 2016 区之间的主题关联 .NovelRec

18、将邻域用户 (与目标用户有邻域关系 )加入的社区 ,作为目标用户的候选社区 ;通过衡量目标用户与候选社区的距离 ,计算候选社区的新颖度 ;根据目标用户与其邻域用户的主题关联 ,计算候选社区的准确度 .在此基础上 ,该方法最终进行新颖性社区推荐 ,同时兼顾推荐结果的准确性 .本文主要贡献如下 : 提出新颖性社区推荐方法 NovelRec,通过多阶邻域交互计算 ,确定目标用户对候选社区的潜在兴趣 ,并使候选社区尽可能地远离目标用户 ,从而提高推荐的新颖性 ;同时利用邻域用户的行为及其与目标用户在主题上的关联 ,兼顾推荐的准确性 . 提出一种用户社区距离度量方式 ,在该距离基础上定义并计算社区的新颖

19、度 ;该距离考虑用户与社区间的邻域关系和主题关联 ,能够客观地衡量社区对用户的新颖程度 . 提出将用户之间在邻域和主题上的关联 ,离线建模到邻域用户相似度矩阵 ,旨在减少在线推荐的计算量 ,并保证在线计算的低复杂度 . 豆瓣社区数据上的实验结果表明 ,NovelRec 在新颖性度量标准、包括覆盖率和流行度上均优于已有方法 ;验证了高质量新颖性推荐需要考虑 “三度影响理论 ”;表明 NovelRec 能够保证推荐结果的准确性 . 1 相关工作 大部分已有推荐方法为准确性推荐 ,而单纯追求推荐准确度会降低推荐系统质量7,近年来国内外研究者开始关注新颖性推荐 ,因此本节从准确性推荐和新颖性推荐两个方

20、面阐述相关工作 . 1.1 准确性推荐 准确性推荐方法旨在提高推荐准确度 ,认为推荐结果与用户历史偏好越接近 ,准确度越高、推荐效果越好 .已有大多数推荐方法属于准确性推荐 ,其中最具代表性的是协同过滤 CF(collaborative filtering).协同过滤一般分为基于记忆 (memory-based)13和基于模型 (model-based)4两种20.基于记忆协同过滤分为 3 类 :(1) 基于推荐项的协同过滤 (item-based CF)向目标用户推荐与其历史偏好相似的项 (item)1;(2) 基于用户的协同过滤(user-based CF)向目标用户推荐其相似用户选择的项

21、2;(3) 混合型 CF 结合以上两类 CF 思想 ,向目标用户推荐其相似用户选择的 ,同时与其历史偏好相似的项3.基于记忆协同过滤的关键是利用用户 -项评分矩阵计算用户相似度或项相似度 .基于模型的 CF 在模型计算过程中融入 CF 思想 ,如文献 4利用 LDA 模型从用户 -社区评分矩阵中计算出用户与社区基于潜在主题的关联 ,并向目标用户推荐关联度高的社区 ;此外 ,该方法从用户 -社区评分矩阵中挖掘出社区间关联规则 ,将与目标用户已评分的社区存在关联的其他社区 ,根据置信度推荐给目标用户 ;该方法验证了 LDA 相对于关联规则挖掘能够达到更好的推荐准确性 . 社会化推荐利用社会化关系进

22、行准确性推荐 ,该类方法将 CF中基于相似度的关联 ,替代为社会化关系以降低数据稀疏产生的影响21,从而提高推荐准确度 .社会化推荐基本思想是 ,目标用户会对与其有社会化关系的用户所选择的项感兴趣 .文献 5将推荐数据建模为图 :用户、推荐项以及用户为项加的标签均建模为图中节点 ,节点间相应关联建模为边 ,利用随机游走算法得到该图上所有节点间的关联度 ,依据关联度值进行推荐 .文献 6提出将目标用户历史偏好、用户之间的社会化影响两个因素统一建模 ,基于该模型提出一套矩阵运算方法 ,旨在融合上述两个因素并进行推荐 .孟祥武等人22提出使用推土机距离实现跨推荐项的用户相似度计算 ,并提出融合用户信

23、任关系和项特征的社会化推荐方法 .Ma 等人在用户 -项评分矩阵基础上加入显式的用户信任关系提高推荐准确度21,并通过大量实验23比较了分别利用显式和隐式社会化关联进行推荐对准确度的影响 . McNee 等人7指出 ,高准确度的推荐结果可能对用户没有用处 .推荐结果准确度越高 ,反映其与目标用户的历史偏好越接近 ;推荐结果中远离其历史偏好 ,即对目标用户 “新颖 ”的项 ,会降低推荐的准确度 ,但新颖的项可能对用户更有用 .Herlocker 等人16也提出了新颖性推荐的概念和一些度量标准 .准确性推荐方法的目标 ,即单纯提高推荐准确度可能存在不足 ,因此近年来国内外研究者开始关注新颖性推荐

24、. 1.2 新颖性推荐 新颖性推荐的概念由 Herlocker 等人16首次提出 :向目标用户推荐其有潜在兴趣但不知道的项 .相对于准确 余骞 等 :基于用户邻域和主题的新颖性 Web 社区推荐方法 1269 性推荐 ,新颖性推荐能够更好地拓展用户兴趣 ,并使得相对小众不流行却能创造巨大价值的项更多地被推荐 .近几年国内外研究者提出了一些新颖性推荐方法 .Oh 等人8提出将用户 -项评分矩阵中用户的评分模式建模为PPT(personal popularity tendency),同时为项建立相应的被评分模式 ;该方法设计了一个 PPT 匹配算法 ,项的被评分模式与目标用户的 PPT 差别越大

25、,则该项的新颖度越高 .Onuma 等人10将用户 -项评分矩阵建模为二分图 ,用户和项为节点 ,评分关联为边 ;该方法利用随机游走方法计算出所有节点之间的关联度 ,基于该关联度定义项节点的 “TANGENT”值 ,该值越高则项的新颖度越高 .Nakatsuji 等人11结合用户 -项评分矩阵和项的分类信息 ,将项所属分类与用户已评分的分类之间的距离 ,定义为该项对目标用户的新颖度 ;该方法根据项的新颖度排序生成推荐列表 .文献 14,15利用项的流行度衡量其新颖度 :一个项越流行 ,用户知道该项的可能性越大 ,该项的新颖度越低 .文献 12在用户 -项评分矩阵中引入评分时间 ,将较早评分某项

26、的用户视为革新者 (innovator),尚未评分该项的用户为其潜在跟随者 (follower),认为革新者评分的项对跟随者有高新颖度 ;该方法视目标用户为跟随者 ,计算其他用户为其革新者的概率 ,并根据该概率值将革新者评分的项推荐给目标用户 .Zhang 等人13构建以项为节点、项相似度为边的图 ,则用户已评分的项对应该图的子图 ;该方法将特定项节点加入目标用户的子图 ,计算该项的聚集因子 ,该因子值越大 ,则该项对目标用户的新颖度越高 .文献 12,13所提出的 “惊喜性 ”推荐方法没有体现 “用户反馈 ”,而 “推荐惊喜度 =新颖度 +用户反馈 ”7,因此仍被归类为新颖性推荐方法 . 上

27、述新颖性推荐方法忽略了 Web 社区的特性 :(1) 社区成员用户通过交互形成的社会关系网络 ;(2) 社区的主题特性以及用户、 社区基于主题的关联 .此外 ,上述方法都没有合理的新颖度定义 :其中文献 8,10,12没有定义项的新颖度 ,因此无法针对性衡量新颖度 ,而文献 11,13,14对新颖度的定义存在缺陷 .Vargas 等人14提出单纯用项的流行度衡量其新颖度 ,会导致每个项对所有用户的新颖度相同 ,而这种全局值不适用于个性化推荐 ; Nakatsuji 等人11提出的定义 ,使得属于相同分类的项对目标用户的新颖度相同 ,导致无法对这些项进行新颖度排序 ;Zhang 等人13提出的定

28、义存在与文献 11类似的问题 :与目标用户子图中同样数目的相同节点存在边的项节点 (项之间相似度不为 0 则存在边 ),其新颖度相同 .此外 ,该 3 种定义均忽略了前述 Web 社区的特性 .综上所述 ,以上新颖性推荐方法不适用于新颖性 Web 社区推荐 . 2 问题定义 Web 社区中存在用户、社区和社区分类 (taxonomy)3 类对象 ,以及对象之间的 3 类交互关系 .用户通过交互形成的关系网络 ,其邻接矩阵记为 A.用户 -社区 交互由矩阵 R 记录 ,qiR 反映用户 uq在社 区 ci内的活跃程度 .社区之间通过社区分类 (主题 )产生的间接交互 ,由社区分类树 T 记录 .

29、 图 2 为 Web 社区示意图 :交互网络中标出了目标用户 uq的各阶邻域 (定义2);矩阵 R 记录用户 -社区交互 ,用户 -社区边的粗细反映矩阵元素值的大小 ,即用户在社区的活跃程度 ;社区分类树 T 中社区为叶子节点 ,分支节点为社区分类 ,社区之间通过分类节点产生主题上的间接关联 .人工分类广泛存在且呈树状结构19,如 Amazon 为其商品提供的分类(http:/ An illustration of Web community 图 2 Web 社区示意图 Root兴趣 闲聊T1影视 T2八卦c2c3c1八卦来了老友记生活大爆炸1u2u3uqu1c2c3c1T2T社区分类树 T用

30、户交互网络 A 用户 -社区交互矩阵 R社区用户目标用户用户 -社区交互社区 -社区交互用户 -用户交互用户邻域u1uqu2u3 1270 Journal of Software 软件学报 Vol.27, No.5, May 2016 y/ref=sa_menu_top_fullstore);Web 社区提供商对社区的人工分类蕴含社区的主题信息 .本文定义新颖性 Web 社区推荐问题如下 : 定义 1(新颖性 Web 社区推荐 ). 给定用户交互网络、用户 -社区交互矩阵以及社区分类树 ,新颖性 Web 社区推荐旨在向目标用户 uq推荐 k 个社区 ,使得这些社区对 uq新颖的同时保证准确性

31、. 3 NovelRec 方法 本节首先给出 NovelRec 的方法框架 ;然后描述对用户邻域、邻域用户相似度和社区主题距离的建模 ;在离线建模基础上 ,描述该方法的在线推荐部分 ;本节最后分析了 NovelRec 方法的复杂度和用户冷启动问题 . 3.1 方法框架 NovelRec 方法包括离线建模和在线推荐计算两个部分 ,NovelRec 方法框架如图 3 所示 .离线部分从用户交互网络中建模用户邻域 ;结合用户 -社区交互矩阵与社区分类树建模用户主题相似度 ;结合用户邻域和主题相似度建模邻域用户相似度矩阵 ;通过社区分类树建模社区 -社区主题距离 .邻域、邻域用户相似度以及社区 -社区

32、主题距离将用于在线推荐计算 .离线部分将用户之间在邻域和主题上的关联 ,映射到邻域用户相似度矩阵 ,使得单个用户的推荐计算量分别与用户数量、社区数量线性相关 ,从而保证在线方法的低复杂度 (详见第 3.4 节 ). 社区 -社区主题距离矩阵路径计算矩阵运算 &相似性运算邻域用户相似度矩阵主题映射用户 -主题交互矩阵UCT距离计算用户 -候选社区UCT距离矩阵新颖度计算用户 -社区准确度矩阵用户 -社区推荐度矩阵用户候选社区邻域用户 -候选社区参与度邻域交互计算用户 -社区交互矩阵用户网络邻接矩阵社区分类树用户 -社区新颖度矩阵离线建模计算在线推荐计算Fig.3 Framework of Nov

33、elRec 图 3 NovelRec 框架 NovelRec 在线部分首先利用邻域用户相似度和用户 -社区交互矩阵进行邻域交互计算 .邻域交互计算过程中 ,在线推荐算法确定目标用户的候选社区、邻域用户在候选社区中的参与度 ,以及候选社区的推荐准确度 ;同时利用社区 -社区主题距离和用户 -社区交互 ,分别计算目标用户与候选社区在主题和邻域上的距离 ,并将主题和邻域上的较小距离作为两者之间的距离 .在此基础之上 ,在线推荐算法利用该距离与前述参与度计算候选社区的推荐新颖度 ,最终结合准确度和新颖度计算候选社区的推荐度 .表 1 对本文用到的主要符号进行描述 . 余骞 等 :基于用户邻域和主题的新

34、颖性 Web 社区推荐方法 1271 Table 1 Description of main symbols 表 1 主要符号描述 符号 描述 符号 描述 U 用户集合 ,|U|=m R 用户 -主题交互矩阵 C 社区集合 ,|C|=n NShh 阶邻域用户相似度矩阵 A 用户交互网络邻接矩阵 CD 社区 -社区主题距离矩阵 R 用户 -社区交互矩阵 Cq 目标用户 uq的候选社区集合 T 社区分类树 AR 用户 -社区准确度矩阵 ()hqNu用户 uq的 h 阶邻域 NR 用户 -社区新颖度矩阵 Nhh 阶邻域矩阵 UCTR 用户 -社区推荐度矩阵 3.2 离线建模计算 3.2.1 用户邻域

35、建模 本节利用用户交互网络邻接矩阵 A 建模用户邻域 ,直观上与用户存在交互且保持特定距离的其他用户组成该用户的邻域 .Christakis 等人17,18提出如果用户间存在直接或间接的交互 ,其行为和兴趣等会相互影响 .用户邻域反映用户间的交互关系 ,因此本文根据邻域将目标用户有潜在兴趣的社区作为其候选社区 . 邻接矩阵 A 为布尔矩阵 ,如果用户 uq与 ui之间存在交互则 1,qi=A 否则 0.qi=A 用()hA 表示布尔运算下 A的 h 次方 :()1;=AA()1hqi=A 表示交互网络中存在从 uq到 ui长度为 h 的路径 ,()0hqi=A 则表示不存在该路径 . 定义 2

36、(h 阶邻域 ). 用户交互网络中用户 uq的 h 阶邻域定义为用户集合 () 1, ,hhqiqiiNu u u U=N 其中 ,h阶邻域矩阵()11max, 1.,2,3,.,hkhh khhh= =ANAN定义 2 中 Nh为 m 阶方阵 ,m 为用户数量 (见表 1),Nh非零元素记录所有用户的 h 阶邻域用户 ,若 (),hiquNu则 1,hqi=N 否则 , 0.hqi=N 当 h=2,3,hmax时 , 1hqi=N 当且仅当()1hqi=A 同时110hkqik=N :ui属于 uq的 h 阶邻域 ,当且仅当用户交互网络中存在从 uq到 ui长度为 h 的路径 ,同时不存在长

37、度小于 h 的路径 ,即 ui只能属于 uq的某一个特定邻域 .结合图 2,有21(),quNu211;q=N22(),quNu221;q=N33(),quNu331.q=N 如果 (),hiquNu 本 文称 ui为 uq的 h 阶邻域用户 ,例如 u1和 u2均为 uq的 2 阶邻域用户 . 用户邻域由邻接矩阵 A 决定 ,A 的小规模变动不会显著影响 Nh.不妨设邻接矩阵发生小规模变动 :元素qiA由 0 变为 1,即 ui变为 uq的 1 阶邻域用户 ,则仅邻域包含 uq的用户 ux受到影响 :1() (),hhqxi xuNu uNu+ 即如 果 uq为 ux的 h 阶邻域用户 ,则

38、 ui会变为 ux的 h+1 阶邻域用户 .邻域不包含 uq的用户不受影响 .同理 ,新用户邻域如果发生明显变化 ,只会对邻域包含该新用户的其他用户产生影响 . 邻接矩阵 A 的变动在一定时间 (t)内累积 ,会造成 Nh的剧烈变动 .要保证 NovelRec 方法有效 ,需要估算 t内 A 的变化程度 ,从而判断是否需要更新 Nh:例如 ,t 时间内如果 A 的每一行元素均发生变化 ,则需要更新 Nh. 邻接矩阵随时间的变化可根据密度幂律分布 (densification power law)24估算 .根据该分布有 () () ,et nt e(t)为 t时刻图的边数 ,n(t)为节点数

39、,则 t 时刻()log ( ( ).ntet = 用 n(t+t)表示 t+t 时刻的节点数 ,则该时刻边数为().nt t+ 令( )()()(),avgIncdgr n t t n t n t t=+avgIncdgr 为 t+t 时刻节点度数的平均增加值 ,例如 avgIncdgr=1 表明宏观上图中每个节点的度平均加 1、邻接矩阵中 n(t+t)个元素发生变化 .因此通过avgIncdgr 可估算 A 的变化并判断是否需要更新 Nh,且该判断仅需观测节点数量的变化 . 3.2.2 邻域用户主题相似度建模 本节利用社区分类树、用户 -社区交互以及用户邻域 ,建模邻域用户相似度矩阵 ,该

40、矩阵对保证在线推荐计算的低复杂度有重要意义 (见第 3.4 节 );与传统相似度建模相比 ,该建模能够提高相似度的有效性 ,并减少计算 开销 . 1272 Journal of Software 软件学报 Vol.27, No.5, May 2016 数据稀疏问题 ,导致基于共同评分项的传统建模方法13不能准确地反映用户之间的相似度21:实际系统中用户 -推荐项评分矩阵密度 (非零元素所占比例 )通常小于 1%21,如本文所用数据集中用户 -社区交互矩阵 R密度仅为 0.79% ,从而共同评分项所占比重较小 ,会导致大量用户间的相似度无法衡量 .本节利用用户之间以社区分类树为桥梁的主题关联 ,

41、建模用户主题相似度 ,首先定义用户 -主题交互矩阵如下 : 定义 3(用户 -主题交互矩阵 R). 定义用户 -主题交互矩阵 R记录用户与社区分类的交互 ,其矩阵元素 ,ql qi i lcT =RR 其中 ,ciTl表示该社区直属于分类节点 Tl,Tl在社区分类树 T 中处于 h(T)1 层 . 其中 ,h(T)表示分类树的高度 ,不妨约定根节点处于第 1 层 ,叶子节点即社区处于 h(T)层 ,则 h(T)1 层分类节点反映最具体的社区主题 ,如图 2 所示的 T1和 T2.定义 3 将用户与社区的交互 ,映射为用户与主题的交互 . 实际应用中推荐项的数量远大于其分类的数量19,因此相对于

42、传统方法 ,基于 R建模用户主题相似度有两点优势 :(1) 主题相似度的有效性更高 ,因为 R密度大于 R 则 R中的共同评分项多于 R,如本文数据集中 R密度为 8.6% 而 R 密度仅为 0.79% ;(2) 主题相似度计算开销更小 ,因为开销由矩阵列的数量决定 ,如本文数据集中 R列数量为 1 041 而 R仅为 67,则利用 R能够减少约 94% 的计算开销 . 在用户 -主题交互矩阵 R基础上 ,本节建模邻域用户主题相似度如下 : 定义 4(邻域用户主题相似度 ). 用户与其 h 阶邻域用户之间基于社区主题的相似度由矩阵 NSh记录 ,矩阵元 素 (,)hqi q isim =NS

43、R R 表示用户 uq与 ui之间的主题相似度 ,其中 ,max(), 1,2,., ,hiquNuh h=qR 和iR 分别为矩阵R中 uq和 ui对应的行向量 , (,)qisim RR表示两向量间的相似度 . 因为针对有邻域关系的用户进行相似度建模 ,定义 4 能够节省部分计算开销 :传统方法针对全体用户计算相似度 ,需 m(m1)/2 次相似性计算 ,m 为用户数量 ;而邻域用户所需计算次数为所有 Nh的非零元素个数之和 ,本文数据集中 ,当 hmax=3 时邻域用户相似度计算次数减少约 20% .实验部分 (见第 4.1.2 节 )将详细讨论 hmax的取值 . 3.2.3 社区主题

44、距离建模 Web 社区通过社区分类树的分类节点产生主题上的间接关联 ,本节利用该主题关联建模社区之间基于主题的距离 .社区之间的主题距离将用于度量用户与社区之间的距离 ,以及计算社区新颖度 . 任意两个社区通过社区分类树均产生间接关联 .本节基于这种主题关联建模社区之间的主题距离 . 定义 5(社区 -社区主题距离 ). , ,ijcc C若 ,iij jcTc T ci与 cj的主题距离() 1)2,hT lij=CD 即 Ti与 Tj在社 区分类树 T 中的距离 ,Ti与 Tj在 T 的第 l 层拥有共同祖先节点 .矩阵 CD 记录 C 中所有社区间的主题距离 . 定义 5 中 ,iicT

45、 表示 T 中社区 ci直属于分类节点 Ti,h(T)为 T 的高度 .不妨约定 1,0,iiin = CD 则 n 阶 方阵 CD 为对角线元素均为 0 的对称矩阵 ,因此只需建模该矩阵的 “上三角 ”部分 .结合图 2,h(T)=4,社区 c1和 c2 在 T 的第 3 层拥有共同祖先节点 T1,则(4 3 1)1221;= =CD 同理 ,(4 1 1) (4 1 1)13 2324,24. = =CD CD 3.3 在线推荐计算 本节通过邻域交互计算确定目标用户候选社区的推荐准确度 (见第 3.3.1 节 );在邻域交互计算中结合社区 -社区距离矩阵 ,确定候选社区的推荐新颖度 (见第

46、 3.3.2 节 );最终进行新颖性社区推荐 ,同时兼顾准确性 (见第3.3.3 节 ). 3.3.1 社区准确度计算 本节通过邻域交互计算 ,即邻域用户相似度矩阵与用户 -社区交互矩阵的乘法 ,确定目标用户的候选社区 ,并计算候选社区的准确度 . 本节依据 Fowler 和 Singla 等人17,18提出的用户行为理论确定候选社区 :目标用户会对与其有直接或间接交互的用户所加入的社区感兴趣 ,因此 NovelRec 通过邻域交互计算将邻域用户加入 ,且目标用户未加入的社区作为其候选社区 .用户候选社区的定义如下 : 定义 6(用户候选社区 ). 目标用户 uq的候选社区集合 1 , 0 0

47、 0,q i ki qk qiCc km= =hRNS R其中 , 1, ,|,qk mm U= ciC,h=1,2,hmax. 余骞 等 :基于用户邻域和主题的新颖性 Web 社区推荐方法 1273 定义 6 中 0kiR 表示用户 uk已加入社区 ci(存在交互 ); 0qkhNS 表示 uk是 uq的直接或间接交互用户 (邻域用户 ),且两用户的主题相似度不为 0; 0qi=R 表示 uq未加入社区 ci.定义 6 表明 ,确定候选社区同时考虑邻域关 系和主题关联 .假设 uq的全体邻域用户中仅 uk加入 ci,但 uk与 uq无主题关联 (两者相似度为 0),则 ci不会成为 uq的候选社区 ,因为 ci与 uq无主题关联其准确性无法保证 ,根据本文问题定义 ci不应被推荐 . 邻域交互计算通过 1 次矩阵乘法 ,hNS R 可确定由 h 阶邻域决定的用户候选社区 ,命题如下 : 命题 1. 1,1,qm in 如果 0,qi=R 则 ()0 .qi i qcChNS R 证明:11,1,() ,mqi qk kikqm in=