Web 社区作为社交网络的重要组成部分正持续高速增长(http://www.nielsen.com/us/en/insights/reports/ 2011/social-media-report-q3.html).为解决海量Web社区带来的信息过载问题,社区推荐通过信息过滤帮助用户选择有价值的社区加入.已有大多数推荐方法属于准确性推荐^{[1, 2, 3, 4, 5, 6]},该类方法旨在提高推荐准确度,认为推荐结果与用户历史偏好越接近,准确度越高、推荐效果越好.然而单纯追求高准确度会降低推荐系统质量^[7].在社区推荐场景下,准确性方法存在以下两个方面的问题:(1) 用户可能对准确性推荐结果不满:准确性方法旨在推荐与用户历史偏好接近的社区,同时倾向于推荐大众流行的社区^[8],则用户可能因为已知被推荐的社区而产生不满.(2) 社区提供商可能对准确性推荐结果不满:准确性推荐对大众流行社区的倾向,会产生“穷者越穷富者越富”的马太效应,使得小众不流行的社区很难被推荐,而占大多数的小众社区(帕累托法则,即80/20法则)却有能力吸引大量用户加入^[9],则社区提供商可能因为小众社区很难进入推荐列表而不满.鉴于准确性推荐方法存在的问题,新颖性推荐方法逐渐得到关注^{[8, 10, 11, 12, 13, 14, 15]}.新颖性社区是指用户有潜在兴趣但不知道的社区^[16].图1通过从豆瓣社区(http://www.douban.com/group/)中抽取的实例,比较了准确性与新颖性社区推荐.

图1(Fig.1)

图1 准确性 vs. 新颖性社区推荐示例 Fig.1 Illustration: Accurate vs. novel community recommendation

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

近年来提出的新颖性推荐方法^{[8, 10, 11, 12, 13, 14, 15]}利用用户与推荐项的交互,即用户-项评分矩阵进行新颖性推荐.然而已有新颖性方法不适用于Web社区推荐,原因如下:(1) 已有新颖性方法不能将用户交互网络用于推荐社区,而存在交互关系的用户其行为会相互影响^{[17, 18]};如图1中u₂和u₃加入c₃会对u_q选择社区产生影响.(2) 已有新颖性方法不能利用用户、社区通过社区主题产生的关联,而这些关联会影响用户对社区的选择^[19];如图1和图2(见第2节)所示,u_q通过c₂以及社区主题(分类)与c₁和c₃产生间接关联,该关联会影响u_q对c₁和c₃的选择.(3) 已有方法缺少合理的新颖度定义,从而无法客观衡量项的新颖度(详见第1.2节).

在真实社会网络中,存在邻域关系(即1跳或多跳的社会关系)的用户,其行为会相互影响;而且Web社区之间存在主题上的关联.因此,为了进行高质量的新颖性社区推荐,本文提出基于用户邻域和主题的新颖性推荐方法NovelRec.该方法从用户交互网络中建模用户邻域;利用社区分类和用户-社区交互建模用户之间、用户与社区之间的主题关联.NovelRec将邻域用户(与目标用户有邻域关系)加入的社区,作为目标用户的候选社区;通过衡量目标用户与候选社区的距离,计算候选社区的新颖度;根据目标用户与其邻域用户的主题关联,计算候选社区的准确度.在此基础上,该方法最终进行新颖性社区推荐,同时兼顾推荐结果的准确性.本文主要贡献如下:

· 提出新颖性社区推荐方法NovelRec,通过多阶邻域交互计算,确定目标用户对候选社区的潜在兴趣,并使候选社区尽可能地远离目标用户,从而提高推荐的新颖性;同时利用邻域用户的行为及其与目标用户在主题上的关联,兼顾推荐的准确性.

· 提出一种用户社区距离度量方式,在该距离基础上定义并计算社区的新颖度;该距离考虑用户与社区间的邻域关系和主题关联,能够客观地衡量社区对用户的新颖程度.

· 提出将用户之间在邻域和主题上的关联,离线建模到邻域用户相似度矩阵,旨在减少在线推荐的计算量,并保证在线计算的低复杂度.

· 豆瓣社区数据上的实验结果表明,NovelRec在新颖性度量标准、包括覆盖率和流行度上均优于已有方法;验证了高质量新颖性推荐需要考虑“三度影响理论”;表明NovelRec能够保证推荐结果的准确性.

大部分已有推荐方法为准确性推荐,而单纯追求推荐准确度会降低推荐系统质量^[7],近年来国内外研究者开始关注新颖性推荐,因此本节从准确性推荐和新颖性推荐两个方面阐述相关工作.

准确性推荐方法旨在提高推荐准确度,认为推荐结果与用户历史偏好越接近,准确度越高、推荐效果越好.已有大多数推荐方法属于准确性推荐,其中最具代表性的是协同过滤CF(collaborative filtering).协同过滤一般分为基于记忆(memory-based)^{[1, 2, 3]}和基于模型(model-based)^[4]两种^[20].基于记忆协同过滤分为3类:(1) 基于推荐项的协同过滤(item-based CF)向目标用户推荐与其历史偏好相似的项(item)^[1];(2) 基于用户的协同过滤(user-b ased CF)向目标用户推荐其相似用户选择的项^[2];(3) 混合型CF结合以上两类CF思想,向目标用户推荐其相似用户选择的,同时与其历史偏好相似的项^[3].基于记忆协同过滤的关键是利用用户-项评分矩阵计算用户相似度或项相似度.基于模型的CF在模型计算过程中融入CF思想,如文献^[4]利用LDA模型从用户-社区评分矩阵中计算出用户与社区基于潜在主题的关联,并向目标 用户推荐关联度高的社区;此外,该方法从用户-社区评分矩阵中挖掘出社区间关联规则,将与目标用户已评分的社区存在关联的其他社区,根据置信度推荐给目标用户;该方法验证了LDA相对于关联规则挖掘能够达到更好的推荐准确性.

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

McNee等人^[7]指出,高准确度的推荐结果可能对用户没有用处.推荐结果准确度越高,反映其与目标用户的历史偏好越接近;推荐结果中远离其历史偏好,即对目标用户“新颖”的项,会降低推荐的准确度,但新颖的项可能对用户更有用.Herlocker等人^[16]也提出了新颖性推荐的概念和一些度量标准.准确性推荐方法的目标,即单纯提高推荐准确度可能存在不足,因此近年来国内外研究者开始关注新颖性推荐.

新颖性推荐的概念由Herlocker等人^[16]首次提出:向目标用户推荐其有潜在兴趣但不知道的项.相对于准确性推荐,新颖性推荐能够更好地拓展用户兴趣,并使得相对小众不流行却能创造巨大价值的项更多地被推荐.近几年国内外研究者提出了一些新颖性推荐方法.Oh等人^[8]提出将用户-项评分矩阵中用户的评分模式建模为PPT(personal popularity tendency),同时为项建立相应的被评分模式;该方法设计了一个PPT匹配算法,项的被评分模式与目标用户的PPT差别越大,则该项的新颖度越高.Onuma等人^[10]将用户-项评分矩阵建模为二分图,用户和项为节点,评分关联为边;该方法利用随机游走方法计算出所有节点之间的关联度,基于该关联度定义项节点的“TANGENT”值,该值越高则项的新颖度越高.Nakatsuji等人^[11]结合用户-项评分矩阵和项的分类信息,将项所属分类与用户已评分的分类之间的距离,定义为该项对目标用户的新颖度;该方法根据项的新颖度排序生成推荐列表.文献^{[14, 15]}利用项的流行度衡量其新颖度:一个项越流行,用户知道该项的可能性越大,该项的新颖度越低.文献^[12]在用户-项评分矩阵中引入评分时间,将较早评分某项的用户视为革新者(innovator),尚未评分该项的用户为其潜在跟随者(follower),认为革新者评分的项对跟随者有高新颖度;该方法视目标用户为跟随者,计算其他用户为其革新者的概率,并根据该概率值将革新者评分的项推荐给目标用户.Zhang等人^[13]构建以项为节点、项相似度为边的图,则用户已评分的项对应该图的子图;该方法将特定项节点加入目标用户的子图,计算该项的聚集因子,该因子值越大,则该项对目标用户的新颖度越高.文献^{[12, 13]}所提出的“惊喜性”推荐方法没有体现“用户反馈”,而“推荐惊喜度=新颖度+用户反馈”^[7],因此仍被归类为新颖性推荐方法.

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

Web社区中存在用户、社区和社区分类(taxonomy)3类对象,以及对象之间的3类交互关系.用户通过交互形成的关系网络,其邻接矩阵记为A.用户-社区交互由矩阵R记录,R^qi反映用户u_q在社区c_i内的活跃程度.社区之间通过社区分类(主题)产生的间接交互,由社区分类树T记录.

图2为Web社区示意图:交互网络中标出了目标用户u_q的各阶邻域(定义2);矩阵R记录用户-社区交互,用户-社区边的粗细反映矩阵元素值的大小,即用户在社区的活跃程度;社区分类树T中社区为叶子节点,分支节点为社区分类,社区之间通过分类节点产生主题上的间接关联.人工分类广泛存在且呈树状结构^[19],如Amazon为其商品提供的分类(http://www.amazon.com/gp/site-directory/ref=sa_menu_top_fullstore);Web社区提供商对社区的人工分类蕴含社区的主题信息.本文定义新颖性Web社区推荐问题如下:

图2(Fig.2)

图2 Web 社区示意图 Fig.2 An illustration of Web community

定义1(新颖性Web社区推荐). 给定用户交互网络、用户-社区交互矩阵以及社区分类树,新颖性Web社区推荐旨在向目标用户u_q推荐k个社区,使得这些社区对u_q新颖的同时保证准确性.

本节首先给出NovelRec的方法框架;然后描述对用户邻域、邻域用户相似度和社区主题距离的建模;在离线建模基础上,描述该方法的在线推荐部分;本节最后分析了NovelRec方法的复杂度和用户冷启动问题.

NovelRec方法包括离线建模和在线推荐计算两个部分,NovelRec方法框架如图3所示.离线部分从用户交互网络中建模用户邻域;结合用户-社区交互矩阵与社区分类树建模用户主题相似度;结合用户邻域和主题相似度建模邻域用户相似度矩阵;通过社区分类树建模社区-社区主题距离.邻域、邻域用户相似度以及社区-社区主题距离将用于在线推荐计算.离线部分将用户之间在邻域和主题上的关联,映射到邻域用户相似度矩阵,使得单个用户的推荐计算量分别与用户数量、社区数量线性相关,从而保证在线方法的低复杂度(详见第3.4节).

图3(Fig.3)

图3 NovelRec框架 Fig.3 Framework of NovelRec

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

表1(Table 1)

表1 主要符号描述Table 1 Description of main symbols 符号 描述 符号 描述 U 用户集合,|U|=m R' 用户-主题交互矩阵 C 社区集合,|C|=n NSh h阶邻域用户相似度矩阵 A 用户交互网络邻接矩阵 CD 社区-社区主题距离矩阵 R 用户-社区交互矩阵 Cq 目标用户uq的候选社区集合 T 社区分类树 AR 用户-社区准确度矩阵 Nh(uq) 用户uq的h阶邻域 NR 用户-社区新颖度矩阵 Nh h阶邻域矩阵 UCTR 用户-社区推荐度矩阵

表1 主要符号描述 Table 1 Description of main symbols

本节利用用户交互网络邻接矩阵A建模用户邻域,直观上与用户存在交互且保持特定距离的其他用户组成该用户的邻域.Christakis等人^{[17, 18]}提出如果用户间存在直接或间接的交互,其行为和兴趣等会相互影响.用户邻域反映用户间的交互关系,因此本文根据邻域将目标用户有潜在兴趣的社区作为其候选社区.

邻接矩阵A为布尔矩阵,如果用户u_q与u_i之间存在交互则${A_{qi}} = 1,$否则${A_{qi}} = 0.$用${A^{\left( h \right)}}$表示布尔运算下A的h次方:${A^{\left( 1 \right)}} = A;{A^{\left( h \right)}}_{qi} = 1$表示交互网络中存在从u_q到u_i长度为h的路径,${A^{\left( h \right)}}_{qi} = 0$则表示不存在该路径.

定义2(h阶邻域). 用户交互网络中用户u_q的h阶邻域定义为用户集合${N^h} = \left\{ \begin{gathered} A,\;\;\;\;{\text{ }}h = 1 \hfill \\ {A^{\left( h \right)}} \wedge \neg \mathop \vee \limits_{^{k = 1}}^{_{h - 1}} {N^k},\;\;h = 2,3,...,{h_{\max }} \hfill \\ \end{gathered} \right..$

定义2中N^h为m阶方阵,m为用户数量(见表1),N^h非零元素记录所有用户的h阶邻域用户,若${u_i} \in {N^h}({u_q}),$则${N^h}_{qi} = 1,$否则,${N^h}_{qi} = 0.$当h=2,3,…,h_max时,${N^h}_{qi} = 1$当且仅当${A^{\left( h \right)}}_{qi} = 1$同时$\mathop \vee \limits_{k = 1}^{h - 1} {N^k}_{qi} = 0$:u_i属于u_q的h阶邻域,当且仅当用户交互网络中存在从u_q到u_i长度为h的路径,同时不存在长度小于h的路径,即u_i只能属于u_q 的某一个特定邻域.结合图2,有${u_1} \in {N^2}({u_q}),$ ${N^2}_{q1} = 1;$ ${u_2} \in {N^2}({u_q}),$ ${N^2}_{q2} = 1;$ ${u_3} \in {N^3}({u_q}),$ ${N^3}_{q3} = 1.$如果${u_i} \in {N^h}({u_q}),$本文称u_i为u_q的h阶邻域用户,例如u₁和u₂均为u_q的2阶邻域用户.

用户邻域由邻接矩阵A决定,A的小规模变动不会显著影响N^h.不妨设邻接矩阵发生小规模变动:元素${A_{qi}}$由0变为1,即u_i变为u_q的1阶邻域用户,则仅邻域包含u_q的用户u_x受到影响:${u_q} \in {N^h}({u_x}) \to {u_i} \in {N^{h + 1}}({u_x}),$即如果u_q为u_x的h阶邻域用户,则u_i会变为u_x的h+1阶邻域用户.邻域不包含u_q的用户不受影响.同理,新用户邻域如果发生明显变化,只会对邻域包含该新用户的其他用户产生影响.

邻接矩阵A的变动在一定时间(Δt)内累积,会造成N^h的剧烈变动.要保证NovelRec方法有效,需要估算Δt内A的变化程度,从而判断是否需要更新N^h:例如,Δt时间内如果A的每一行元素均发生变化,则需要更新N^h.邻接矩阵随时间的变化可根据密度幂律分布(densification power law)^[24]估算.根据该分布有$e(t) \propto n{(t)^a}$为t时刻图的边数,n(t)为节点数,则t时刻$\alpha = {\log _{n(t)}}(e(t)).$用n(t+Δt)表示t+Δt时刻的节点数,则该时刻边数为$n{(t + \Delta t)^\alpha }.$令$\Delta avgIncdgr={\left( n{{(t+\Delta t)}^{\alpha }}-n{{(t)}^{\alpha }} \right)}/{n(t+\Delta t)}\;,$ΔavgIncdgr为t+Δt时刻节点度数的平均增加值,例如ΔavgIncdgr=1表明宏观上图中每个节点的度平均加1、邻接矩阵中n(t+Δt)个元素发生变化.因此通过ΔavgIncdgr可估算A的变化并判断是否需要更新N^h,且该判断仅需观测节点数量的变化.

本节利用社区分类树、用户-社区交互以及用户邻域,建模邻域用户相似度矩阵,该矩阵对保证在线推荐计算的低复杂度有重要意义(见第3.4节);与传统相似度建模相比,该建模能够提高相似度的有效性,并减少计算开销.

数据稀疏问题,导致基于共同评分项的传统建模方法^{[1, 2, 3]}不能准确地反映用户之间的相似度^[21]:实际系统中用户-推荐项评分矩阵密度(非零元素所占比例)通常小于$1\% $^[21],如本文所用数据集中用户-社区交互矩阵R密度仅为$0.79\% $,从而共同评分项所占比重较小,会导致大量用户间的相似度无法衡量.本节利用用户之间以社区分类树为桥梁的主题关联,建模用户主题相似度,首先定义用户-主题交互矩阵如下:

定义3(用户-主题交互矩阵R´). 定义用户-主题交互矩阵R´记录用户与社区分类的交互,其矩阵元素${R'_{ql}} = \sum {{R_{qi}}} ,{c_i} \in {T_l},$其中,c_i∈T_l表示该社区直属于分类节点T_l,T_l在社区分类树T中处于h(T)-1层.

其中,h(T)表示分类树的高度,不妨约定根节点处于第1层,叶子节点即社区处于h(T)层,则h(T)-1层分类节点反映最具体的社区主题,如图2所示的T₁和T₂.定义3将用户与社区的交互 ,映射为用户与主题的交互.

实际应用中推荐项的数量远大于其分类的数量^[19],因此相对于传统方法,基于R´建模用户主题相似度有两点优势:(1) 主题相似度的有效性更高,因为R´密度大于R则R´中的共同评分项多于R,如本文数据集中R´密度为$8.6\% $而R密度仅为$0.79\% $;(2) 主题相似度计算开销更小,因为开销由矩阵列的数量决定,如本文数据集中R列数量为1 041而R´仅为67,则利用R´能够减少约$94\% $的计算开销.

在用户-主题交互矩阵R´基础上,本节建模邻域用户主题相似度如下:

定义4 (邻域用户主题相似度). 用户与其h阶邻域用户之间基于社区主题的相似度由矩阵NS^h记录,矩阵元素$N{S^h}_{qi} = sim({R'_q},{R'_i})$表示用户u_q与u_i之间的主题相似度,其中,${u_i} \in {N^h}({u_q}),h = 1,2,...,{h_{\max }}$, ${R'_q}$和${R'_i}$分别为矩阵R´中u_q和u_i对应的行向量,$sim({{R'}_q},{{R'}_i})$表示两向量间的相似度.

因为针对有邻域关系的用户进行相似度建模,定义4能够节省部分计算开销:传统方法针对全体用户计算相似度,需m(m-1)/2次相似性计算,m为用户数量;而邻域用户所需计算次数为所有N^h的非零元素个数之和,本文数据集中,当h_max=3时邻域用户相似度计算次数减少约$20\% $.实验部分(见第4.1.2节)将详细讨论h_max的取值.

Web社区通过社区分类树的分类节点产生主题上的间接关联,本节利用该主题关联建模社区之间基于主题的距离.社区之间的主题距离将用于度量用户与社区之间的距离,以及计算社区新颖度.

任意两个社区通过社区分类树均产生间接关联.本节基于这种主题关联建模社区之间的主题距离.

定义5(社区-社区主题距离). $\forall {c_i},{c_j} \in C,$若${c_i} \in {T_i},{c_j} \in {T_j},$c_i与c_j的主题距离$C{D_{ij}} = {2^{(h(T) - l - 1)}},$即T_i与T_j在社区分类树T中的距离,T_i与T_j在T的第l层拥有共同祖先节点.矩阵CD记录C中所有社区间的主题距离.

定义5中,${c_i} \in {T_i}$表示T中社区c_i直属于分类节点T_i,h(T)为T的高度.不妨约定$\forall 1 \leqslant i \leqslant n,C{D_{ii}} = 0,$则n阶方阵CD为对角线元素均为0的对称矩阵,因此只需建模该矩阵的“上三角”部分.结合图2,h(T)=4,社区c₁和c₂在T的第3层拥有共同祖先节点T₁,则$C{D_{12}} = {2^{(4 - 3 - 1)}} = 1;$同理,$C{D_{13}} = {2^{(4 - 1 - 1)}} = 4,C{D_{23}} = {2^{(4 - 1 - 1)}} = 4.$

本节通过邻域交互计算确定目标用户候选社区的推荐准确度(见第3.3.1节);在邻域交互计算中结合社区-社区距离矩阵,确定候选社区的推荐新颖度(见第3.3.2节);最终进行新颖性社区推荐,同时兼顾准确性(见第3.3.3节).

本节通过邻域交互计算,即邻域用户相似度矩阵与用户-社区交互矩阵的乘法,确定目标用户的候选社区,并计算候选社区的准确度.

本节依据Fowler和Singla等人^{[17, 18]}提出的用户行为理论确定候选社区:目标用户会对与其有直接或间接交互的用户所加入的社区感兴趣,因此NovelRec通过邻域交互计算将邻域用户加入,且目标用户未加入的社区作为其候选社区.用户候选社区的定义如下:

定义6(用户候选社区). 目标用户u_q的候选社区集合${C_q} = \{ {c_i}\left| {\exists 1 \leqslant k \leqslant m,{R_{ki}} \ne 0 \wedge N{S^h}_{qk} \ne 0 \wedge {R_{qi}} = 0} \right.\} ,$其中,$1 \leqslant q,k \leqslant m,m = |U|,$c_i∈C,h=1,2,…,h_max.

定义6中${R_{ki}} \ne 0$表示用户u_k已加入社区c_i(存在交互);$N{S^h}_{qk} \ne 0$表示u_k是u_q的直接或间接交互用户(邻域用户),且两用户的主题相似度不为0;${R_{qi}} = 0$表示u_q未加入社区c_i.定义6表明,确定候选社区同时考虑邻域关系和主题关联.假设u_q的全体邻域用户中仅u_k加入c_i,但u_k与u_q无主题关联(两者相似度为0),则c_i不会成为u_q的候选社区,因为c_i与u_q无主题关联其准确性无法保证,根据本文问题定义c_i不应被推荐.

邻域交互计算通过1次矩阵乘法$N{S^h} \cdot R,$可确定由h阶邻域决定的用户候选社区,命题如下:

命题 1. $\forall 1 \leqslant q \leqslant m,1 \leqslant i \leqslant n,$如果${R_{qi}} = 0,$则${(N{S^h} \cdot R)_{qi}} \ne 0 \to {c_i} \in {C_q}.$

证明:$\forall 1 \leqslant q \leqslant m,1 \leqslant i \leqslant n,{(N{S^h} \cdot R)_{qi}} = \sum\nolimits_{k = 1}^m {N{S^h}_{qk}{R_{ki}}} ,$ ${(N{S^h} \cdot R)_{qi}} \ne 0 \to \exists 1 \leqslant k \leqslant m,N{S^h}_{qk} \ne 0 \wedge {R_{ki}} \ne 0.$给定${R_{qi}} = 0,$则${(N{S^h} \cdot R)_{qi}} \ne 0 \to \exists 1 \leqslant k \leqslant m,{R_{ki}} \ne 0 \wedge N{S^h}_{qk} \ne 0 \wedge {R_{qi}} = 0,$有${(N{S^h} \cdot R)_{qi}} \ne 0 \to {c_i} \in {C_q}.$ □

在确定用户候选社区后,利用协同过滤^[2]以及社会化推荐^[21]思想进行准确度计算:u_q的邻域用户与其相似度越大,且邻域用户在候选社区c_i中越活跃,则c_i对u_q的准确度越高.同时考虑到u_q对c_i的兴趣来源于其邻域用户的影响,而影响力会随着h(距离)的增加而降低^[17].综合以上因素,定义用户-社区准确度如下:

定义7(用户-社区准确度). 定义候选社区c_i对目标用户u_q的准确度$A{{R}_{qi}}=\sum\nolimits_{h=1}^{{{h}_{\max }}}{\sum\nolimits_{{{u}_{k}}\in {{N}^{h}}({{u}_{q}})}{{N{{S}^{h}}_{qk}{{R}_{ki}}}/{{{2}^{(h-1)}}}\;}},$用户-社区准确度矩阵$AR=\sum\nolimits_{h=1}^{{{h}_{\max }}}{{N{{S}^{h}}\cdot R}/{{{2}^{(h-1)}}}\;},\forall 1\le q\le m,1\le i\le n,{{R}_{qi}}\ne 0\to A{{R}_{qi}}=0.$

定义7中$A{R_{qi}}$的公式反映前述协同过滤思想:邻域用户u_k与u_q相似度即$NS_{qk}^h$越大、u_k在候选社区c_i中越活跃即${R_{ki}}$越大,则候选社区准确度$A{R_{qi}}$越大;$\sum\nolimits_{h = 1}^{{h_{\max }}} $表示考虑u_q的1-h_max阶邻域,不同阶邻域用户行为对准确度的影响随衰减因子${1}/{{{2}^{\left( h-1 \right)}}}\;$^[17]变化.用户-社区准确度矩阵AR为mxn矩阵,由邻域交互计算$N{S^h} \cdot R$得到;对AR的约束$\forall 1 \leqslant q \leqslant m,1 \leqslant i \leqslant n,{R_{qi}} \ne 0 \to A{R_{qi}} = 0,$旨在满足命题1的条件${R_{qi}} = 0,$从而保证AR中所有非零元素均为候选社区对用户的推荐准确度,换言之,用户与其已加入社区对应的矩阵元素值必为0.定义7对$A{R_{qj}}$的定义与矩阵AR定义保持一致:根据AR定义,$A{{R}_{qi}}=\sum\nolimits_{h=1}^{{{h}_{\max }}}{{\sum\nolimits_{{k}'=1}^{m}{N{{S}^{h}}_{q{k}'}{{R}_{{k}'i}}}}/{{{2}^{(h-1)}}}\;},$而$N{S^h}_{qk'} = 1 \to {u_{k'}} \in {N^h}({u_q}),$则$\sum\nolimits_{k' = 1}^m {N{S^h}_{qk'}{R_{k'i}}} = \sum\nolimits_{{u_k} \in {N^h}({u_q})} {N{S^h}_{qk}{R_{ki}}} ,$即$A{{R}_{qi}}=\sum\nolimits_{h=1}^{{{h}_{\max }}}{\sum\nolimits_{{{u}_{k}}\in {{N}^{h}}({{u}_{q}})}{{N{{S}^{h}}_{qk}{{R}_{ki}}}/{{{2}^{(h-1)}}.}\;}}$

用户-社区准确度计算过程详见第3.3.3节中算法2.

本节计算候选社区对目标用户的推荐新颖度:根据用户与社区之间在邻域和主题上的关联,提出一种用户社区距离度量方式;在该距离基础上计算候选社区对目标用户的新颖度.

新颖性社区指用户有潜在兴趣但不知道的社区^[16].目标用户对邻域交互计算所确定的候选社区(见定义6)有潜在兴趣,因此新颖度计算从以下3个方面衡量目标用户不知道候选社区的可能性:(1) 目标用户与候选社区的距离;(2) 邻域用户在候选社区中的参与度;(3) 候选社区的流行度.新颖度计算假设候选社区与目标用户距离越远、加入社区的邻域用户数量越少(参与度低)、社区越不流行,目标用户不知道候选社区的可能性越大,候选社区对目标用户的新颖度就越高.

不妨假设图2中c₃为u_q的候选社区,u_q既能通过已加入的社区c₂经社区分类节点到达c₃,也可以通过其邻域用户u₂和u₃到达c₃.依托社区分类树,u_q与c₃存在主题距离;基于用户邻域,u_q与c₃存在邻域距离.

定义8(用户-社区主题距离). 用户u_q与其候选社区c_i的主题距离$T{D_{qi}}$,定义为社区c_i与u_q已加入社区的最小主题距离,$T{D_{qi}} = \min \{ C{D_{ik}}\left| {\forall 1 \leqslant k \leqslant n,{R_{qk}} \ne 0} \right.\} .$

社区-社区主题距离矩阵CD(见第3.2.3节)记录C中所有社区之间的主题距离.如图2所示,u_q加入社区c₂,则u_q与社区c₁的主题距离$T{D_{q1}} = C{D_{12}} = 1,$u_q与c₃的主题距离$T{D_{q3}} = C{D_{32}} = 4.$

定义9(用户-社区邻域距离). 用户u_q与其候选社区c_i的邻域距离$N{D_{qi}}$,定义为u_q所有加入社区c_i的邻域用户与u_q的最短距离,$N{D_{qi}} = \min \{ h\left| {{u_k} \in {N^h}({u_q}) \wedge {R_{ki}} \ne 0,h = 1,2,...,{h_{\max }}} \right.\} .$

其中,${R_{ki}} \ne 0$表示u_k与社区c_i存在交互.以图2为例,u_q加入c₁的邻域用户为u₁且${u_1} \in {N^2}({u_q}),$则$N{D_{q1}} = 2;$u_q加入c₃的邻域用户为u₂和u₃且${u_2} \in {N^2}({u_q}),{u_3} \in {N^3}({u_q}),$则$N{D_{q3}} = \min \{ 2,3\} = 2.$

目标用户与其候选社区通过社区分类树和用户邻域分别可达,即同时存在主题距离与邻域距离,结合社区主题与用户邻域定义用户-社区UCT(user-community-taxonomy)距离如下:

定义10(用户-社区UCT距离). 用户u_q与其候选社区c_i的UCT距离${D_{qi}},$定义为两者主题距离与邻域距离的最小值,${D_{qi}} = \min \{ T{D_{qi}},N{D_{qi}}\} ,$矩阵D记录U中所有用户与其候选社区的UCT距离.

仍以图2为例,对c₁而言,如果仅考虑邻域关系该社区与u_q距离为2,而c₁与u_q的主题距离为1,则${D_{q1}} = \min \{ T{D_{q1}},N{D_{q1}}\} = 1.$对c₃而言,该社区与u_q主题距离为 4,而邻域距离为2,则${D_{q3}} = \min \{ T{D_{q3}},N{D_{q3}}\} = 2.$

给定通过h阶邻域交互计算确定社区c_j为用户u_i的候选社区,算法1计算两者之间的UCT距离,该算法将被第3.3.3节的算法2调用.算法1第1步如果${D_{ij}} = 0,$说明D_ij尚未计算,因为任意用户与社区的UCT距离不小于1,而0为D在算法2中的初始值;第2步~第4步根据定义10计算D_ij.第1步如果${D_{ij}} \ne 0,$说明该值在h´(h´<h)阶邻域已经计算,且${D_{ij}} = \min \{ T{D_{ij}},h'\} ,$因为h´<h,所以无需再次计算D_ij,跳过第2步~第4步,保留已经计算的D_ij值.

算法 1. 用户-社区UCT距离算法UCTDistance(u_i,c_j,h).

输入: 社区c_j为用户u_i的候选矩阵,邻域的阶h.

输出: 用户u_i与社区c_j的UCT距离D_ij.

1. if ${D_{ij}} = 0$

2. for k where ${R_{ik}} \ne 0$

3. $T{D_{ij}} = \min \{ C{D_{jk}}\} $

4. ${D_{ij}} = \min \{ T{D_{ij}},h\} $

UCT距离综合考虑用户与社区之间在邻域和主题上的关联,能够客观地反映目标用户与候选社区之间的距离.衡量候选社区新颖度的另外两个方面是社区流行度,以及邻域用户在候选社区中的参与度.社区流行度由社区成员数决定.邻域用户在目标用户候选社区中的参与度由矩阵NH记录,$N{H_{qi}}$表示加入社区c_i的u_q的邻域用户数量,即$N{H_{qi}} = |Se{t_{qi}}|,$而$Se{t_{qi}} = \{ {u_k}\left| {N{S^h}_{qk} \ne 0 \wedge {R_{ki}} \ne 0,h = 1,2,...,{h_{\max }}} \right.\} ,$ $Se{t_{qi}}$为加入c_i(${R_{ki}} \ne 0$)且属于u_q邻域的用户集合,$Se{t_{qi}}$中的用户同时需要保证与u_q存在主题关联$(N{S^h}_{qk} \ne 0).$

约定参与度矩阵NH归一化后的矩阵表示为$\overline {NH} $,即$\forall 1\le q\le m,1\le i\le n,{{\overline{NH}}_{qi}}={N{{H}_{qi}}}/{\sum\nolimits_{k\in \left[ 1,n \right]}{N{{H}_{qk}}}}\;;$同理,UCT距离矩阵D经过行归一化后的矩阵为$\overline{D},{{\overline{D}}_{qi}}={{{D}_{qi}}}/{\sum\nolimits_{k\in \left[ 1,n \right]}{{{D}_{qk}}}}\;;$约定|c_i|表示该社区成员数,对|c_i|归一化得到$\overline{|{{c}_{i}}|}={{{c}_{i}}}/{\sum\nolimits_{k\in \left[ 1,n \right]}{{{c}_{k}}}}\;.$在前述问题基础上,本节定义用户-社区新颖度如下:

定义11(用户-社区新颖度). 定义候选社区c_i对目标用户u_q的新颖度$N{{R}_{qi}}=-{{\log }_{2}}\left( {{\overline{NH}}_{qi}}\cdot {\overline{|{{c}_{i}}|}}/{{{\overline{D}}_{qi}}}\; \right),$用户-社区新颖度矩阵NR记录U中所有用户与其候选社区之间的推荐新颖度.

因为$N{H_{qi}},$|c_i|和${D_{qi}}$的取值范围不同,所以对其进行不改变值分布的归一化处理.新颖度公式使用熵的自信息形式(-log₂X),旨在体现对新颖度的假设:候选社区与目标用户距离越远(即${\overline D _{qi}}$越大)、加入社区的邻域用户数量越少(即${\overline {NH} _{qi}}$越小)、社区越不流行(即$\overline {|{c_i}|} $越小),目标用户不知道候选社区的可能性越大,社区新颖度就越高.

在邻域交互计算(矩阵乘法$N{S^h} \cdot R$)过程中,增加1次加法运算即可得到邻域用户-候选社区参与度;用户-社区UCT距离由算法1得到;社区流行度为已知信息.用户-社区新颖度的计算过程见第3.3.3节算法2.

本节计算候选社区对目标用户的推荐度,该值融合准确度和新颖度,使得候选社区对目标用户新颖的同时保证准确性.候选社区的推荐度UCTR定义如下:

定义12(用户-社区推荐度UCTR). 定义候选社区c_i对目标用户u_q的推荐度$UCT{{R}_{qi}}={{{\overline{NR}}_{qi}}}/{{{\overline{AR}}_{qi}}}\;,$其中,${{\overline{AR}}_{qi}}={A{{R}_{qi}}}/{\sum\nolimits_{k\in \left[ 1,n \right]}{A{{R}_{qk}}}}\;,$ ${{\overline{NR}}_{qi}}={N{{R}_{qi}}}/{\sum\nolimits_{k\in \left[ 1,n \right]}{N{{R}_{qk}}}}\;,$矩阵UCTR记录所有用户与其候选社区之间的推荐度.

根据社区推荐度定义,如果c_i新颖度较高则UCTR值较高,准确度较高则UCTR值较低.该定义使用除法融合准确度和新颖度;此外,准确度和新颖度均经过归一化处理,以保证计算在相同数值范围内进行.

NovelRec在线推荐计算的核心是邻域交互计算$N{S^h} \cdot R,$候选社区的确定,候选社区的准确度、新颖度以及推荐度计算都基于该稀疏矩阵乘法.下面给出NovelRec在线推荐计算算法.该算法分两部分:(1) 第1步~第 8 步为邻域交互计算$N{S^h} \cdot R,$即在各阶邻域进行1次矩阵乘法;(2) 第9步~第12步根据邻域交互计算的结果,计算候选社区的新颖度和推荐度.

算法第1步表示对用户交互网络中1~h_max阶邻域进行邻域交互计算;算法第3步~第6步为稀疏矩阵乘法运算.

第3步按行扫描矩阵$N{S^h};$第4步定位$N{S^h}$第i行中非零元素的列号k;第5步将列号k作为矩阵R的行号并寻找R第k行中非零元素;第6步为矩阵乘法结果计算.算法第5步的判断条件${R_{ij}} = 0$使得$N{S^h} \cdot R$可确定用户的候选社区(命题1),并且使得当前用户已加入社区对应的矩阵AR元素值必为0(定义7);第6步累加各阶邻域的${N{{S}^{h}}(i,k)\cdot R(k,j)}/{{{2}^{(h-1)}}}\;$得到AR_ij.算法第7步~第8步仍在稀疏矩阵乘法过程中.第7步计算u_i的h阶邻域用户在候选社区c_j中的参与度.第8步通过最多|R_i|次比较运算得到两者之间的UCT距离(详见第3.4节复杂度分析).第9步~第12步基于邻域交互计算的结果,计算候选社区的新颖度和推荐度.算法第9步按行扫描矩阵NH和D;第10步定位NH和D的第i行中的非零元素,如果$N{H_{ik}} \ne 0,$则c_k为候选社区;第11步计算社区新颖度,其中包括归一化运算;第12步计算社区的推荐度.

算法 2. NovelRec在线推荐算法.

输入: 邻域用户相似度矩阵$N{S^h},$用户社区交互矩阵R.

输出: 用户-社区推荐度矩阵UCTR.

1. for h=1 to h_max

2. 矩阵AR,NR,NH,D所有元素初始化为0

3. for i=1 to m do

4. for k where ${R_{kj}} \ne 0 \wedge {R_{ij}} = 0$

5. for j where ${R_{kj}} \ne 0 \wedge {R_{ij}} = 0$

6. $AR(i,j)=AR(i,j)+{N{{S}^{h}}(i,k)\cdot R(k,j)}/{{{2}^{(h-1)}}}\;$

7. $NH(i,j) = NH(i,j) + 1$

8. UCTDistance (u_i,c_j,h)

9. for i=1 to m

10. for k where $N{H_{ik}} \ne 0$

11. $N{{R}_{ik}}=-{{\log }_{2}}({{{\overline{NH}}_{ik}}\cdot \overline{|{{c}_{k}}|}}/{{{\overline{D}}_{ik}}}\;)$

12. $UCT{{R}_{ik}}={{{\overline{NR}}_{ik}}}/{{{\overline{AR}}_{ik}}}\;$

研究表明,实际系统中用户和推荐项的数据密度一般小于1%^[21];本文数据集中NS¹密度为0.013%,NS²密度为0.6%,NS³为9%,R为0.79%.算法2将NS^h和R处理为稀疏矩阵,使用稀疏矩阵乘法技术SpGEMM^{[25, 26]}计算$N{S^h} \cdot R,$并采用行压缩技术CRS进行矩阵存储.

NovelRec离线部分的用户邻域建模使用稀疏矩阵乘法技术SpGEMM处理邻接矩阵A(本文数据集中A的密度0.013%);${A^{(h)}}$的计算决定邻域建模的时间复杂度为$O(flops + nnz(A) + m)$^[25],其中,flops指矩阵运算中非零算术运算次数,nnz(A)为矩阵A非零元素数量,m为A的列数量.邻域用户相似度矩阵NS^h建模的时间复杂度为$O(\max \{ \max \{ nnz({N^h})\} ,nnz(R)\} ),$其中,$nnz({N^h})$和$nnz(R)$表示N^h和R的非零元素数量;该部分复杂度由N^h和R的矩阵遍历决定.社区-社区主题距离矩阵CD建模的时间复杂度为O(n²),n为社区数量.

在线用户-社区UCT距离计算(算法1)最多需要进行|R_i|次比较运算,R_i表示用户-社区交互矩阵R的行向量,|R_i|表示用户u_i已加入社区的数量;用户交互社区的数量为常量,因此该算法时间复杂度为O(1).算法1不需要存储中间运算结果,空间复杂度为O(1).在线推荐计算(算法2)的时间复杂度为$O(flops2 + \max \{ nnz(N{S^h})\} + n)$^[25],其中,flops 2指算法2中非零算术运算次数,包括该算法第6步~第8步中的基本算术运算,nnz(NS^h)为h阶邻域相似度矩阵非零元素数量,n为社区数量.算法2需要存储的中间计算结果包括矩阵AR,NH,NR和D.其中,AR,NH和NR密度相同,非零元素位置严格对应,用nnz(AR)表示AR的非零元素数量;矩阵D的非零元素数量为(1+n)n/2,n为社区数量.则算法2的空间复杂度为$O(nnz(AR) + {n^2}).$

算法2中任意两个用户的在线推荐计算过程相互独立:根据该算法,用户u_i候选社区的确定,及其准确度、新颖度以及推荐度在$N{S^h}_i \cdot R$基础上得到,$NS_i^h$表示NS^h中u_i对应的行向量;换言之,$\forall 1 \leqslant i,j \leqslant m,$u_i和u_j的推荐计算过程相互独立.该独立性质由矩阵乘法性质决定,也因为邻域用户主题相似度矩阵NS^h建模了用户之间在邻域、社区以及社区主题上的关联.在线推荐计算的用户间独立性,使得单个用户的推荐计算量与用户数量线性相关.如果实际应用中只需对部分用户(比如k个用户)进行计算,则在线部分只需要全局计算量的k/m.此外,根据矩阵乘法性质,单个用户的推荐计算量与社区数量也线性相关.上述线性相关性质,表明对邻域用户相似度的离线建模能够保证在线推荐计算的低复杂度.

推荐系统向新增加用户推荐社区时会遇到冷启动问题:由于新用户缺乏数据,对其进行推荐难以达到较好的效果.冷启动用户可大致分为两类:第1类为无数据的冷启动用户,即新用户与社区和其他用户均无交互;第2类为数据稀疏的冷启动用户,该类新用户与社区和其他用户的交互数据少.针对第1类无数据用户,根据社区流行度(加入社区的成员数量)向其推荐热门社区,因为新用户更有可能对热门流行社区感兴趣.针对第2类冷启动用户,如果NovelRec推荐给该类用户的社区不足k个(k为推荐列表长度,见定义1),提出如下策略补足推荐列表:不妨设u_q为第2类用户,且由于缺乏数据NovelRec仅向其推荐了k´(k´<k)个社区.该策略定位u_q已加入社区所属的社区分类集合{T₁,T₂,…,T_a},将属于该分类集合的社区按流行度排序,取出前(k-k´)个社区补充到u_q的推荐列表.第4.4节将分析冷启动用户的推荐效果.

本节由实验数据分析、推荐准确度分析和推荐新颖度分析这3部分组成.第4.1节对本文使用的豆瓣社区数据进行了展示和分析,包括用户交互网络、用户-社区交互矩阵以及社区成员数等;同时确定用户邻域阶数的上界h_max(见定义2).第4.2节和第4.3节根据相应度量标准,比较了NovelRec与3种其他推荐方法^{[4, 13, 15]}在推荐准确性和推荐新颖性上的表现.本文实验环境如下:Intel(R) Core(TM) i5-2320 3.00GHz处理器,4GB内存,Windows 7旗舰版64位操作系统,使用Java 1.6语言编写程序,数据库为Mysql 5.0.

豆瓣社区是典型的社会网络应用,目前拥有超过70 000 000用户和320 000社区.本文数据集包括:115 962个用户,1 041个社区,949 226条用户-社区交互记录,1 841 964条用户-用户交互记录(实验部分使用的用户交互关系为“关注”关系),包含根节点在内共76个分类节点,社区分类树T中处于h(T)-1层(见定义3),即第3层的分类节点数为67.用户-社区交互记录形式为(Uid,Cid,Rating),Uid和Cid分别为匿名化后用户和社区的标识符,Rating为用户与社区交互的频度.用户-用户交互记录的形式为(Uid,Uid),即连接用户节点的边.社区记录的形式为(Cid,Pop,Tid),其中,Pop为社区流行度,Tid为该社区直属的分类节点.社区分类记录的形式为(Tid,P_Tid),其中,Tid,P_Tid分别为该分类节点及其父亲分类节点的标识符.

实验部分沿用表1中的符号描述.用户交互网络的节点数为115 962,边数为1 841 964,其中用户最多关注870个用户,最少关注1个用户.本节对用户关注的分布进行了统计分析,如图4(a)所示,横轴为用户关注人数,纵轴为拥有相应关注人数的用户数量;在log-log标度下其符合幂律(power law)分布,表明用户交互网络具有典型的社会网络特征.图4(b)为用户-社区交互分布,横轴所示的用户加入社区数量即用户交互的社区数量,纵轴为加入相应数量社区的用户数量,用户-社区交互矩阵$R$的密度为0.79%,其中有24 746个用户仅与1个社区交互,而单个用户最多与87个社区交互;在log-log标度下,用户与社区的交互也符合幂律(power law)分布.图4(c)为社区流行度分布,坐标轴为线性标度,横坐标为社区成员数即社区流行度,纵轴为累积分布;社区成员数最大为 349 700,最小为6.如图所示,$80\% $的社区其成员数不超过50 000;而成员数超过100 000的社区仅占全体社区的7%,可见本数据集中的社区流行度分布符合帕累托法则,即80/20法则.

图4(Fig.4)

图4 豆瓣社区数据集分析 Fig.4 Analysis of the Douban community dataset

用户邻域阶数上界h_max(见定义2)的选择对NovelRec方法有重要意义:h_max影响用户候选社区集合的大小和在线推荐算法(见算法2)的计算量,也对候选社区推荐度计算结果产生影响.本节根据实验分析选择h_max=3,同时验证了进行高质量新颖性社区推荐需要考虑“三度影响理论”^[17].

定义6依据社会网络用户行为理论^{[17, 18]},将目标用户u_q的h阶邻域用户加入且u_q其未加入的社区c_i作为其候选社区,即c_i成为候选社区由于u_q受其邻域用户的影响.本节通过随机抽样和全局统计,分析用户的候选社区集合随邻域阶数上界h_max的变化,见表2.表中第1列对用户真实ID做了匿名处理;第2列~第5列分别为不同h_max取值下用户候选社区集合C_q的大小.

表2中前3行为3个随机抽取用户的候选社区数量与h_max的对应关系,表中数据说明1跳~3跳关系 (h_max=3)对用户的候选社区影响明显,同时影响程度随跳数增加而减小.为不失一般性,表2的第4行显示了不同h_max下矩阵AR密度的变化;AR的密度变化能够反映用户候选社区的变化,因为AR非零元素即为用户与其候选社区的准确度(见定义7).数据反映AR的密度受1跳~3跳关系影响较大,而4跳关系的影响很小;也反映抽样数据(表2前3行)与统计数据基本保持一致.以上分析表明新颖性社区推荐需要考虑“三度影响理论”^[17]:3跳以内的邻域关系(h_max=3)对推荐影响明显;邻域关系的影响随跳数增加而减小.

表2(Table 2)

表2 |Cq| vs. hmaxTable 2 |Cq| vs. hmax 目标用户 |Cq|(hmax=1) |Cq|(hmax=2) |Cq|(hmax=3) |Cq|(hmax=4) u1 210 747 1 003 1 019 u2 340 885 992 1 000 u3 196 788 988 1 008 全体用户 9.3% 48.2% 83.5% 84.9%

表2 |Cq| vs. hmax Table 2 |Cq| vs. hmax

本节比较了NovelRec与3种对比方法^{[4, 13, 15]}在推荐准确性上的表现.为便于叙述,实验部分将文献^[4]所提方法称为Orkut,文献^[13]称为Auralist,文献^[15]称为TRelation(total relation).Orkut为准确性Web社区推荐方法,利用LDA模型从矩阵R中计算出用户与社区基于潜在主题的关联,并向目标用户推荐关联度高的社区.Auralist为新颖性推荐方法,构建以项为节点、项相似度为边的图,则用户已评分的项对应该图的子图.该方法将特定项节点加入目标用户的子图,并以该项的聚集因子作为项对目标用户的新颖度.TRelation为新颖性推荐方法,通过挖掘用户网络中存在的潜在社团,确定用户的候选新颖性社区,并根据潜在社团中用户的行为计算社区的新颖度.以上3种对比方法没有充分利用用户与社区的交互、用户交互网络和社区主题进行推荐.实验结果表明,NovelRec方法能够保证推荐的准确性.

本节选择通用的“leave-one-out”^[16]方法衡量推荐的准确性.对用户-社区交互矩阵R中的每个用户,随机从其加入的社区中抽出1个(leave one out)作为测试集,${R_{leave}}$为训练集,${R_{leave}}$表示矩阵R被抽掉115 962(R中的用户数)个元素后的矩阵.${R_{leave}}$的推荐结果中,被抽出的测试社区在对应用户的推荐列表中的排名越高,说明推荐方法越准确.

因为R中有24 746个用户仅交互1个社区(见第4.1.1节),所以${R_{leave}}$中用户数降为91 216,社区数降为1 034,则91 216个用户的推荐列表中最多出现1 034个不同的独立社区.Orkut和Auralist均用到LDA模型,为其统一设置LDA参数如下:迭代次数为1 000;主题数67,与豆瓣数据集保持一致;a=2,b=0.5.推荐准确性对比结果如图5和图6所示.

图5(Fig.5)

图5 推荐准确性的宏观视图 Fig.5 Macro view of recommendation accuracy

图6(Fig.6)

图6 推荐准确性的微观视图 Fig.6 Micro view of recommendation accuracy

图5为测试社区排名累积分布的宏观视图,其中,AR为第3.3.1节计算的推荐准确度,横坐标0.1代表测试社区在对应用户的推荐列表中排名前10%;100%表示该社区在列表中排名最后.AR的准确性远高于对比方法,其40%的测试社区排名比例在前10%,而NovelRec(即UCTR)有1.6%的测试社区排名比例在前10%,Auralist有6.7%的测试社区排名比例在前10%,Orkut为0.46%,TRelation为0.42%.宏观视图下排名比例在前40%时,NovelRec在准确性上优于Orkut和TRelation,但稍逊于Auralist;而当排名比例超过40%时,NovelRec在准确性上优于所有对比方法.图5中代表5种方法的曲线汇聚在点(100%,100%),因为测试社区在所有用户的推荐列表中的排名一定在前100% (最差情况下排名最后).图6为测试社区排名累积分布的微观视图,显示测试社区排名比例在前1%~10%的累积分布,其结果与图5所展示的结果保持一致:排名比例在前1%~10%时,NovelRec在准确性上优于Orkut和TRelation,但稍逊于Auralist,AR的准确性远高于所有对比方法.

图5和图6的结果表明,虽然NovelRec在推荐准确性上部分情况(测试社区排名比例在前40%)下稍逊于Auralist,但其他情况下均优于Auralist;且NovelRec全局优于Orkut和TRelation.这说明NovelRec能够保证推荐的准确性.同时观察到AR在准确性上优势明显,说明第3.3.1节由邻域交互计算确定的社区准确度效果良好.NovelRec的准确性在部分情况下的劣势,由用户推荐度UCTR的计算公式(见定义12)造成,即社区的准确性排名被其新颖性排名拉低.虽然NovelRec牺牲了一定的推荐准确性,但极大地提高了推荐新颖性(详见第 4.3节).

本节比较了上述方法在推荐新颖性上的表现,使用的度量标准为流行度和覆盖率^[16].流行度标准指用户推荐列表中的前k个社区的流行度分布,该分布与社区流行度分布(如图4(c)所示)和k的取值有关;社区流行度由其成员数衡量.在流行度标准下,高流行度的社区被推荐得越多,推荐方法的新颖性就越低.覆盖率是指进行top-k推荐时,用户被推荐的所有社区中独立社区的数量与独立社区总数的比值,该比值越大说明被推荐的独立社区越多.在覆盖率标准下,该比值越大,则推荐方法越新颖.实验结果表明,在新颖性度量标准,包括覆盖率和流行度上,NovelRec均明显优于已有方法.

在“leave-one-out”比较方法下,推荐用户数为91 216,社区总数为1 034;社区流行度分布如图4(c)所示,80%的社区其成员数不超过50 000;而成员数超过100 000的社区仅占全体社区的7%.图7~图9显示了在top-1、top-5和top-10推荐下,各种方法的推荐结果在社区流行度上的分布,其中,NR表示第3.3.2节所计算的社区新 颖度.

图7显示,在top-1推荐情景下,NovelRec,TRelation和NR在流行度上的表现接近:这3种方法推荐的 91 216 (被推荐用户数)个社区中97.7%的流行度不超过25 000;而全体社区中有66.6%其流行度不超过25 000.相比之下,Auralist所推荐社区中仅5%其流行度在25 000以下;Orkut相应比例为0.超过80%的社区其流行度不超过50 000,NR推荐的社区中有99.4%其流行度在50 000以下,NovelRec有98.8%在50 000以下,TRelation相应比例为99.3%;相比之下,Auralist为21.3%,而Orkut仍为0.可见,在top-1推荐情景下,NovelRec,TRelation和NR在流行度上的表现基本接近,且远远好于其他对比方法;Auralist在流行度上优于Orkut.图7同时显示,在进行top-1推荐时,Orkut推荐的社区中有约15%的社区,其流行度超过300 000,而这样的社区在全体社区中所占比例小于0.5%.

图7(Fig.7)

图7 Top-1推荐的流行度分布 Fig.7 Popularity distribution of top-1 recommendation

图8(Fig.8)

图8 Top-5推荐的流行度分布 Fig.8 Popularity distribution of top-5 recommendation

图8显示在top-5推荐下,各方法在流行度上的表现,此时方法推荐的社区数为91216x5=456080.图8与图7显示的情况大体一致,但在top-5推荐下,NovelRec在流行度上稍好于NR,与TRelation接近.NovelRec推荐的社区中有97%其流行度在25 000以下,NR为93.7%;NovelRec推荐的社区中有99.2%其流行度在50 000以下,NR为96.3%.NovelRec,TRelation和NR在流行度上明显优于其他对比方法,Auralist优于Orkut.图9为top-10推荐下各方法在流行度上的比较,此时推荐的社区数为912 160.图9显示的情况与图8基本一致,进一步验证了NovelRec和NR在流行度上优于Orkut和Auralist.

图10显示各方法在覆盖率上的对比结果,横轴的K为推荐列表的长度,纵轴为覆盖率的值.NovelRec在覆盖率上略优于NR,这两种方法在覆盖率上明显优于其他对比方法;Auralist优于Orkut和TRelation.

图9(Fig.9)

图9 Top-10 推荐的流行度分布 Fig.9 Popularity distribution of top-10 recommendation

图10(Fig.10)

图10 Top-K 推荐的覆盖率分布 Fig.10 Coverage distribution of top-K recommendation

当进行top-1推荐时,91 216个社区被推荐,NovelRec推荐了972个独立社区,覆盖率为0.936;NR推荐独立社区952个,覆盖率为0.921;Auralist覆盖率为0.656;TRelation为0.069 3;Orkut推荐独立社区18个,覆盖率0.017 4.进行top-3推荐时,91216x3=273648个社区被推荐,NovelRec推荐的独立社区数为1 034,即覆盖率达到100%;NR推荐独立社区1 031个,覆盖率为0.997;Auralist覆盖率0.81,而Orkut覆盖率仍仅为0.027,推荐独立社区28个.进行top-4推荐时,364 864个社区被推荐,NoverRec覆盖率维持在100%;NR的覆盖率达到100%; Auralist覆盖率为0.849.进行top-10推荐时,912 160个社区被推荐,Auralist覆盖率为0.95,仍只推荐到982个独立社区;而Orkut推荐的独立社区仅为52个.TRelation方法虽然有良好的流行度分布,但覆盖率低.

基于以上流行度和覆盖率的对比分析,NovelRec方法在推荐新颖性上明显优于其他对比方法.根据第3.3.2节的新颖度定义,该方法推荐在邻域和主题上距离目标用户较远的社区,从而能够推荐更多在邻域和主题上较为分散的社区,并得到较高的覆盖率;该方法推荐邻域用户较少参与同时成员数较少的社区,从而能够推荐更多相对小众、流行度低的社区.NovelRec相对于3种对比方法,能够更充分地利用Web社区特性,从而达到更优的新颖性.

在以上对比分析中,部分情况下,NovelRec在新颖性上甚至优于NR,如进行top-5推荐时,NovelRec在流行度上稍好于NR:NovelRec推荐的社区中有97%其成员数在25 000以下,NR只有93.7%的推荐社区其成员数小于25 000.该情况侧面反映了定义12会拉低社区的准确度并提高了其新颖度,部分解释了NovelRec的准确性在部分情况下差于Auralist的现象,.

本节分析了NovelRec方法性能随数据量大小以及数据维度的变化.首先分析了NovelRec性能随用户数量的变化,如图11所示,横轴为用户数量;左纵轴表示NovelRec为相应数量用户进行推荐的运行时间,单位为ms;右纵轴为相应的社区推荐数量.该部分实验随机取样了12组用户,统计了不同用户数量下,NovelRec的运行时间和推荐社区数量的变化;其中用户数量从108逐渐增加到30 464,对应构成曲线的12个数据点.比较两条曲线的变化趋势,社区推荐数量的增幅超过运行时间,说明NovelRec可扩展性强,该可扩展性由方法性质决定,即第3.4节所述,单个用户的推荐计算量与用户数量和社区数量均线性相关.

本节接下来分析NovelRec方法性能随不同数据维度的变化.如前文所述,NovelRec方法利用了3个维度的数据,分别为用户-社区交互、用户-用户交互和社区-社区交互维度.应对不同的维度组合,基于NovelRec有4个基准方法,见表3. NovelRec-CC方法仅考虑社区-社区交互维度,该方法的推荐度计算公式去除了与用户相关的维度数据.NovelRec-UC仅考虑用户-社区交互维度,其推荐度计算公式去除了用户-用户交互维度的数据.NovelRec-UUC不考虑社区-社区交互维度,则计算$A{R_{qi}}$时去除了用户相似度,计算$N{R_{qi}}$时去除了主题距离和社区流行度.NovelRec-UCC不考虑用户-用户交互维度,其推荐度计算公式中去除了邻域和邻域距离.

图11(Fig.11)

图11 NovelRec 效率 vs. 用户数量 Fig.11 NovelRec efficiency vs. number of users

表3(Table 3)

表3 基于NovelRec 的基准方法Table 3 Baseline methods based on NovelRec 方法名称 用户-社区交互 用户-用户交互 社区-社区交互 方法描述 推荐度计算公式 NovelRec-CC - - √ 仅考虑社区-社区交互维度 $UCT{R_{qi}} = \overline {\left| {{c_i}} \right|} $ NovelRec-UC √ - - 仅考虑用户-社区交互维度 $UCT{R_{qi}} = A{R_{qi}} = \sum {{S_{qk}}{R_{ki}}} $ NovelRec-UUC √ √ - 考虑两种维度的组合 $$A{{R}_{qi}}=\sum\nolimits_{h=1}^{{{h}_{\max }}}{\sum\nolimits_{{{u}_{k}}\in {{N}^{h}}({{u}_{q}})}{{{{N}^{h}}_{qk}{{R}_{ki}}}/{{{2}^{(h-1)}}}\;}},$$ $N{{R}_{qi}}=-{{\log }_{2}}\left( {{{\overline{NH}}_{qi}}}/{{{\overline{ND}}_{qi}}}\; \right),$ $UCT{{R}_{qi}}={{{\overline{NR}}_{qi}}}/{{{\overline{AR}}_{qi}}}\;$ NovelRec-UCC √ - √ 考虑两种维度的组合 $$A{{R}_{qi}}=\sum{{{S}_{qk}}{{R}_{ki}}},N{{R}_{qi}}=\sum{-{{\log }_{2}}\left( {\overline{|{{c}_{i}}|}}/{{{\overline{TD}}_{qi}}}\; \right)},$$ $UCT{{R}_{qi}}={{{\overline{NR}}_{qi}}}/{{{\overline{AR}}_{qi}}}\;$

表3 基于NovelRec 的基准方法 Table 3 Baseline methods based on NovelRec

图12(Fig.12)

图12 推荐准确性宏观视图:NovelRec vs. 基准方法 Fig.12 Macro view of recommendation accuracy: NovelRec vs. baselines

根据第4.2节和第4.3节所述度量标准,图12~图14比较了NovelRec及其基准方法的推荐准确性和新颖性.图12为推荐准确性的宏观视图.因为NovelRec-UC退化为准确性推荐方法,所以其准确性最高;NovelRec- UCC和NovelRec-UUC的准确性接近;前述3种基准方法在准确性上略优于 NovelRec.NovelRec-CC 缺少用户信息,不能构建测试集和训练集,无法衡量其准确性,因此没有出现在图12中.第4.2节已分析NovelRec准确性稍差的原因:社区的准确性排名被其新颖性排名拉低.在流行度和覆盖率标准下,NovelRec均明显优于其基准方法.NovelRec能够达到更优的推荐新颖性,因其考虑了社区推荐场景下更丰富维度的数据,充分利用了Web社区特性.NovelRec-CC在图13、图14中对应与横轴“平行”的线条,因为该方法对所有用户均推荐流行度最高的k个社区.流行度top-10社区的成员数量均超过300 000,因此图13中NovelRec-CC对应线条的纵坐标均为0;图14中当K=1时其纵坐标为1/1034,当K=10时其纵坐标为10/1034=0.97%.

图13(Fig.13)

图13 Top-10 推荐的流行度分布: NovelRec vs. 基准方法 Fig.13 Popularity distribution of top-10 recommendation: NovelRec vs. baselines

图14(Fig.14)

图14 Top-K 推荐的覆盖率分布: NovelRec vs. 基准方法 Fig.14 Coverage distribution of top-K recommendation: NovelRec vs. baselines

本节同时对冷启动用户的推荐效果进行了实验,构建了由100个(实验数据集中用户数量的0.1%)冷启动用户组成的集合:其中,10个用户为第3.5节所述第1类无数据的冷启动用户;剩余90个为第2类数据稀疏用户.为保证数据稀疏,从本文数据集中随机挑选90个用户:保证这些用户仅与1个用户存在交互,同时,其中10个用户仅加入2个社区,另外80个仅加入1个社区.利用第3.5节所述策略对该用户集合进行推荐.

图12~图14统计了冷启动用户的推荐结果(对应ColdStart曲线).第4.2节所述“leave-one-out”方法需要构建测试社区集合,因此准确性衡量只对加入2个社区的10个用户有效.图12表明,冷启动用户的准确度结果比NovelRec及其基准方法要差,因为该10个用户的数据过于稀疏,导致测试社区的排名很低.图13表明,冷启动用户的推荐社区大多是流行度高的社区,该结果由第3.5节所述推荐策略造成.因为大多数推荐结果集中在流行度高的社区,所以图14显示新用户推荐结果的覆盖率较低.

社区推荐场景下从数据性质的角度,有以下几种特殊用户:(1) 冷启动用户;(2) 仅与社区交互的用户,该类用户仅产生与社区交互的数据,不与其他用户交互;(3) 仅与其他用户交互的用户,该类用户与其他用户进行互动,但不加入社区.针对冷启动用户的推荐策略第3.5节已述;基准方法NovelRec-UC仅考虑用户-社区交互维度,NovelRec-UCC仅考虑用户-社区以及社区-社区交互维度,因此该两种方法可针对上述第2种用户进行推荐,用户-用户交互维度数据对该两种方法没有影响;同理NovelRec-UUC仅考虑用户-社区以及用户-用户维度数据,可针对上述第3种用户进行推荐,该方法不受社区-社区交互维度数据影响.NovelRec方法集中了上述基准方法的优点,可针对不同的特殊用户进行推荐.同时NovelRec方法针对用户数量的变化可扩展性强,如图11所示.因此,NovelRec方法拥有良好的鲁棒性.

NovelRec的社区新颖度计算充分考虑了用户之间的邻域关系、用户与社区之间基于邻域和主题的关联,以及社区自身特性,以提高推荐新颖性;社区准确度计算根据协同过滤和社会化推荐思想,结合邻域用户相似度与邻域用户行为,以保证推荐准确性.NovelRec通过将用户之间的邻域关系和主题关联,离线建模到邻域用户相似度矩阵中,使得单个用户的推荐计算量分别与用户数量、社区数量线性相关,从而保证方法的低复杂度.实验结果表明,NovelRec方法在推荐新颖性上优于已有方法:针对不同的推荐列表长度,该方法能够提升5.1%~29%的覆盖率;针对不同的流行度,该方法能够提升1.6%~90%.实验结果同时表明,该方法能够保证推荐结果的准 确性.