基于万有引力的个性化推荐算法

工程科学学报，第37卷，第2期：255-259,2015年2月 Chinese Journal of Engineering,Vol.37,No.2:255-259,February 2015 DOI:10.13374/j.issn2095-9389.2015.02.019:http://journals.ustb.edu.cn 基于万有引力的个性化推荐算法 王国霞四，刘贺平，李擎 北京科技大学自动化学院，北京100083 ☒通信作者，E-mail:kdmycevin@sohu.com 摘要本文把物理学中的万有引力定律引入推荐系统，提出一种个性化推荐算法，即基于万有引力的个性化推荐算法.算 法把用户使用的标签看作用户喜欢物体的组成颗粒，标注项目的标签被看作项目物体的组成颗粒，社会标签的类型就是颗粒 的类型，由此构建了用户喜好物体模型和项目物体模型.喜好物体和项目物体间存在着万有引力，并且引力大小遵循万有引 力定律.计算喜好物体和项目物体间的万有引力，并把该引力大小作为二者的相似度度量，引力越大，二者的相似度就越高， 对应的项目物体就越有可能被用户喜欢.实验结果证明本文提出的算法可以获得好的推荐性能· 关键词推荐算法：个性化：万有引力：社会标签 分类号TP391 Gravitation-based personalized recommendation algorithm WANG Guo-ia,LIU He-ping,LI Qing School of Automation and Electrical Engineering,University of Science and Technology Beijing,Beijing 100083,China Corresponding author,E-mail:kdmycevin@sohu.com ABSTRACT A recommendation algorithm is proposed by introducing the universal law of gravitation into a recommendation system. This new algorithm is named as the gravitation-based personalized recommendation (GBPR)algorithm.In the algorithm,social tags used by users are regarded as particles that made up of their preference objects,social tags marking on items are considered as parti- cles that made up of item objects,and the user preference objects and item objects are taken as a user preference object model and an item object model,respectively.Gravitation exists between the user preference objects and item objects,and its strength obeys the universal law of gravitation.The strength of gravitation between the user preference objects and the item objects is computed,and it is regarded as their similarity.The bigger the strength is,the more similar they are,and the corresponding item objects are more proba- ble to be liked by users.Experimental results show that the proposed algorithm can get good performance. KEY WORDS recommendation algorithms;personalization:gravitation:social tags 个性化推荐技术因其在解决信息超载和资源迷向是一个数值网，分值的高低仅能反映用户对某项目的 问题上的优越性，使得它在学术界的研究和商业的应 好恶，而用户真正喜欢的项目类型及项目自身特征等 用等方面都取得了良好的发展和应用，作为其核 信息无法从中获得，所以依据评分信息获得的推荐有 心的推荐算法更是学术界的研究热点，日前大量具有 失偏颇.另外，推荐系统存在于被基本物理定律控制 良好推荐性能的推荐算法被提出来. 的物理世界中，但现有的推荐算法缺乏物理学方面的 现有的推荐算法能取得好的推荐性能，但因算法 深层理解和解释，这不失为一种严重的遗憾。 固有特点而存在一些无法克服的缺点.例如大多算法 Web2.0技术的发展使得社会标签(lag)越来越为 的推荐依据主要是用户的评分，而用户的评分仅仅就 用户所熟知.用户在发布或浏览网上资源时，自由选 收稿日期：2013-12-23 基金项目：国家软科学研究计划资助项目(2013GXS5B178)

工程科学学报，第 37 卷，第 2 期: 255--259，2015 年 2 月 Chinese Journal of Engineering，Vol． 37，No． 2: 255--259，February 2015 DOI: 10． 13374 /j． issn2095--9389． 2015． 02． 019; http: / /journals． ustb． edu． cn 基于万有引力的个性化推荐算法 王国霞，刘贺平，李 擎 北京科技大学自动化学院，北京 100083  通信作者，E-mail: kdmycevin@ sohu． com 摘 要 本文把物理学中的万有引力定律引入推荐系统，提出一种个性化推荐算法，即基于万有引力的个性化推荐算法． 算 法把用户使用的标签看作用户喜欢物体的组成颗粒，标注项目的标签被看作项目物体的组成颗粒，社会标签的类型就是颗粒 的类型，由此构建了用户喜好物体模型和项目物体模型． 喜好物体和项目物体间存在着万有引力，并且引力大小遵循万有引 力定律． 计算喜好物体和项目物体间的万有引力，并把该引力大小作为二者的相似度度量，引力越大，二者的相似度就越高， 对应的项目物体就越有可能被用户喜欢． 实验结果证明本文提出的算法可以获得好的推荐性能． 关键词 推荐算法; 个性化; 万有引力; 社会标签 分类号 TP391 Gravitation-based personalized recommendation algorithm WANG Guo-xia ，LIU He-ping，LI Qing School of Automation and Electrical Engineering，University of Science and Technology Beijing，Beijing 100083，China  Corresponding author，E-mail: kdmycevin@ sohu． com ABSTＲACT A recommendation algorithm is proposed by introducing the universal law of gravitation into a recommendation system． This new algorithm is named as the gravitation-based personalized recommendation ( GBPＲ) algorithm． In the algorithm，social tags used by users are regarded as particles that made up of their preference objects，social tags marking on items are considered as parti￾cles that made up of item objects，and the user preference objects and item objects are taken as a user preference object model and an item object model，respectively． Gravitation exists between the user preference objects and item objects，and its strength obeys the universal law of gravitation． The strength of gravitation between the user preference objects and the item objects is computed，and it is regarded as their similarity． The bigger the strength is，the more similar they are，and the corresponding item objects are more proba￾ble to be liked by users． Experimental results show that the proposed algorithm can get good performance． KEY WOＲDS recommendation algorithms; personalization; gravitation; social tags 收稿日期: 2013--12--23 基金项目: 国家软科学研究计划资助项目( 2013GXS5B178) 个性化推荐技术因其在解决信息超载和资源迷向 问题上的优越性，使得它在学术界的研究和商业的应 用等方面都取得了良好的发展和应用［1--2］，作为其核 心的推荐算法更是学术界的研究热点，目前大量具有 良好推荐性能的推荐算法被提出来． 现有的推荐算法能取得好的推荐性能，但因算法 固有特点而存在一些无法克服的缺点． 例如大多算法 的推荐依据主要是用户的评分，而用户的评分仅仅就 是一个数值［3］，分值的高低仅能反映用户对某项目的 好恶，而用户真正喜欢的项目类型及项目自身特征等 信息无法从中获得，所以依据评分信息获得的推荐有 失偏颇． 另外，推荐系统存在于被基本物理定律控制 的物理世界中，但现有的推荐算法缺乏物理学方面的 深层理解和解释，这不失为一种严重的遗憾． Web2. 0 技术的发展使得社会标签( tag) 越来越为 用户所熟知． 用户在发布或浏览网上资源时，自由选

·256· 工程科学学报，第37卷，第2期 择词汇对其进行标注，以方便对网络资源进行分类、共 引力的主要区别是，这一引力仅仅是一种数量上的度 享、浏览等.标签作为一种新的网络数据，一方面来 量，而没有方向.同时还有同类型的项目颗粒间存在 源于用户对资源的理解和概括，具有一定的个性化特 引力，不同类型的项目颗粒间则不存在引力. 征：同时标签又可以对资源进行描述和分类，相比较用 定义5（项目物体引力(gravitation between item 户评分，标签携带了更多的信息量.日前，学术界 object))项目物体间因其组成颗粒间的引力而存在 的很多研究开始利用社会标签进行个性化推荐、 着类万有引力的引力，并且该引力遵循万有引力定律. 信息检索等，都取得了良好的效果. 同样的，该引力仅仅是数量上的度量而没有方向. 本文在充分考虑社会标签信息的基础上，试图在 引理1（叠加原理(superposition principle)两项 物理学的框架下给出一种新的个性化推荐算法.该算 目物体间的引力大小由项目物体的项目颗粒间的引力 法把目标用户喜欢项目特征视为物体颗粒，从而虚拟 叠加形成的.若项目物体i包含项目颗粒有(a,la, 出目标用户喜欢的物体模型，根据项目特征构建项目 …,ln),项目物体j包含的项目颗粒有(h2…,l), 物体模型.然后考察用户喜好物体和项目物体间的万 其中表示项目物体i中的第g个项目颗粒，'表示项 有引力的大小，并把它看作是二者相似性的度量，引力 目物体j中的第g个项目颗粒，同类项目颗粒间的引 越大，二者就越相似，也就是用户喜欢该项目物体的可 力分别为(，，…，∫)，项目物体i和j间的引力为： 能性就越大，依此目标用户就可获得推荐. (2) 1相关定义 g点6 式中∫为两项目物体中的第g个项目颗粒之间的 1.1万有引力定律 引力 万有引力作为自然界四种基本作用力之一，存在 定义6（引力场(gravitation field)推荐系统中 于宇宙中任何两个物体之间.牛顿发现了这一引力并 的项目物体因引力，形成了一个充满整个数据空间的 在1687年《自然哲学原理》上发表文章，提出了万有 场，这个场叫做引力场. 引力定律.万有引力定律说明万有引力的大小和两物 定义7（引力子场(gravitation subfield))存在于 体质量的乘积成正比，与两物体间的距离的平方成 整个数据空间的引力场是由若干个引力子场组成.每 反比： 个项目物体因与其他物体间的引力而在其周围形成了 F=Gm 一个小的引力场，该小场叫做引力子场 2 (1) 对于每个引力子场，GBPR算法重点考察其三个 式中：m1和m2分别为物体1和物体2的质量，r为两 因素，分别是中心点、作用点和引力强度 物体间的距离，G为万有引力常量，F为万有引力 定义8（引力子场中心点(centre of gravitation 1.2相关定义 subfield))形成引力子场的点即为中心点，所以每个 基于万有引力的个性化推荐(gravitation-based 项目物体即为每个引力子场的中心点. personalized recommendation,GBPR)算法把物理学中 定义9（引力作用点(action point of gravitation)) 的万有引力定律引入了推荐系统中，就需要把推荐系 引力场∫会对场中项目物体j施加引力作用，则项目 统中的概念映射到物理学的框架中来 物体j为引力子场的其中一个作用点. 定义1（项目物体(item object))推荐系统中的 定义I0(引力强度(gravitation strength))引力强 项目因其实际存在而被认为是物体，并被命名为项目 度等于引力子场中心点和引力作用点对应的项目物体 物体.项目物体与物理学中的物体一样，具有自身特 间的万有引力大小. 有的属性以及质量. 在GBPR算法中，引力强度考察的都是针对某个 定义2（项目颗粒(item particle)项目颗粒是项 引力子场的某一作用点上的引力强度. 目物体的组成成分.项目颗粒有两个重要的要素，分 2GBPR算法 别是质量和类型. 定义3（项目物体的质量）项目物体的质量由 2.1问题描述 组成它的项目颗粒的质量形成的，令9表示项目物体 当用户选择社会标签对项目进行标注后，形成了 i中第g个项目颗粒的质量，并且9≥0，则项目物体i 如图1所示“用户-项目-标签”网络，假设系统用户 的质量可用一个质量向量表示，q:=(qa92,,9g). 集合为U=(u1,山2，…，“n),n为用户总数，项目集合为 定义4（项目颗粒引力(gravitation between item I=(i1,i2,…,i),m为项目总数，标签集合为T=(1, particle))项目颗粒间存在类万有引力的引力，并且 2,…,l),g为标签种类数，推荐算法就是利用三者之 其大小遵循万有引力定律.这里的引力和物理学上的 间的关系数据，计算目标用户对未选择项目的喜好程

工程科学学报，第 37 卷，第 2 期 择词汇对其进行标注，以方便对网络资源进行分类、共 享、浏览等［4］． 标签作为一种新的网络数据，一方面来 源于用户对资源的理解和概括，具有一定的个性化特 征; 同时标签又可以对资源进行描述和分类，相比较用 户评分，标签携带了更多的信息量［4--6］． 目前，学术界 的很多研究开始利用社会标签进行个性化推荐［7--9］、 信息检索等，都取得了良好的效果． 本文在充分考虑社会标签信息的基础上，试图在 物理学的框架下给出一种新的个性化推荐算法． 该算 法把目标用户喜欢项目特征视为物体颗粒，从而虚拟 出目标用户喜欢的物体模型，根据项目特征构建项目 物体模型． 然后考察用户喜好物体和项目物体间的万 有引力的大小，并把它看作是二者相似性的度量，引力 越大，二者就越相似，也就是用户喜欢该项目物体的可 能性就越大，依此目标用户就可获得推荐． 1 相关定义 1. 1 万有引力定律 万有引力作为自然界四种基本作用力之一，存在 于宇宙中任何两个物体之间． 牛顿发现了这一引力并 在 1687 年《自然哲学原理》上发表文章，提出了万有 引力定律． 万有引力定律说明万有引力的大小和两物 体质量的乘积成正比，与两物体间的距离的平方成 反比: F = G m1m2 r 2 ． ( 1) 式中: m1 和 m2 分别为物体 1 和物体 2 的质量，r 为两 物体间的距离，G 为万有引力常量，F 为万有引力． 1. 2 相关定义 基于万有引力的个性化推荐 ( gravitation-based personalized recommendation，GBPＲ) 算法把物理学中 的万有引力定律引入了推荐系统中，就需要把推荐系 统中的概念映射到物理学的框架中来． 定义 1( 项目物体( item object) ) 推荐系统中的 项目因其实际存在而被认为是物体，并被命名为项目 物体． 项目物体与物理学中的物体一样，具有自身特 有的属性以及质量． 定义 2( 项目颗粒( item particle) ) 项目颗粒是项 目物体的组成成分． 项目颗粒有两个重要的要素，分 别是质量和类型． 定义 3 ( 项目物体的质量) 项目物体的质量由 组成它的项目颗粒的质量形成的，令 qig表示项目物体 i 中第 g 个项目颗粒的质量，并且 qig≥0，则项目物体 i 的质量可用一个质量向量表示，qi = ( qi1，qi2，…，qig ) ． 定义 4 ( 项目 颗 粒 引 力( gravitation between item particle) ) 项目颗粒间存在类万有引力的引力，并且 其大小遵循万有引力定律． 这里的引力和物理学上的 引力的主要区别是，这一引力仅仅是一种数量上的度 量，而没有方向． 同时还有同类型的项目颗粒间存在 引力，不同类型的项目颗粒间则不存在引力． 定义 5 ( 项 目 物 体 引 力( gravitation between item object) ) 项目物体间因其组成颗粒间的引力而存在 着类万有引力的引力，并且该引力遵循万有引力定律． 同样的，该引力仅仅是数量上的度量而没有方向． 引理 1( 叠加原理( superposition principle) ) 两项 目物体间的引力大小由项目物体的项目颗粒间的引力 叠加形成的． 若项目物体 i 包含项目颗粒有 ( ti1，ti2， …，tig ) ，项目物体 j 包含的项目颗粒有( tj1，tj2，…，tjg ) ， 其中 tig表示项目物体 i 中的第 g 个项目颗粒，tjg表示项 目物体 j 中的第 g 个项目颗粒，同类项目颗粒间的引 力分别为( f1，f2，…，fg ) ，项目物体 i 和 j 间的引力为: Fij = ∑ g x = 1 fx ． ( 2) 式中 fg 为两项目物体中的 第 g 个 项 目 颗 粒 之 间 的 引力． 定义 6( 引力场( gravitation field) ) 推荐系统中 的项目物体因引力，形成了一个充满整个数据空间的 场，这个场叫做引力场． 定义 7( 引力子场( gravitation subfield) ) 存在于 整个数据空间的引力场是由若干个引力子场组成． 每 个项目物体因与其他物体间的引力而在其周围形成了 一个小的引力场，该小场叫做引力子场． 对于每个引力子场，GBPＲ 算法重点考察其三个 因素，分别是中心点、作用点和引力强度． 定义 8 ( 引 力 子 场 中 心 点 ( centre of gravitation subfield) ) 形成引力子场的点即为中心点，所以每个 项目物体即为每个引力子场的中心点． 定义 9( 引力作用点( action point of gravitation) ) 引力场 fi 会对场中项目物体 j 施加引力作用，则项目 物体 j 为引力子场 fi 的其中一个作用点． 定义 10( 引力强度( gravitation strength) ) 引力强 度等于引力子场中心点和引力作用点对应的项目物体 间的万有引力大小． 在 GBPＲ 算法中，引力强度考察的都是针对某个 引力子场的某一作用点上的引力强度． 2 GBPＲ 算法 2. 1 问题描述 当用户选择社会标签对项目进行标注后，形成了 如图 1 所示“用户–项目–标签”网络，假设系统用户 集合为 U = ( u1，u2，…，un ) ，n 为用户总数，项目集合为 I = ( i1，i2，…，im ) ，m 为项目总数，标签集合为 T = ( t1， t2，…，tg ) ，g 为标签种类数，推荐算法就是利用三者之 间的关系数据，计算目标用户对未选择项目的喜好程 · 652 ·

王国霞等：基于万有引力的个性化推荐算法 257 度，从而把目标用户可能喜欢的项目推荐给他 用点的引力强度 (4)相似度衡量.根据定义4和引理1可知，对 用户1 动作中国导演A 各作用点的引力强度越大，山，的喜好物体与项目物体 爱情主演X动作导演A 的相似度越高，所以引力强度可被视为一种相似度的 爱情美国主演入 伦理导演B中国主演1 电影2 度量 用户2 (5)获得推荐.对引力子场∫的各作用点的引力 强度倒序排列，引力强度大的前N个作用点对应的项 电影3 爱情美国主演Y动作导演A 目物体可能是目标用户山比较喜欢的物体项目，把它 们推荐给目标用户： 用户3 电影4 2.3用户喜好物体和项目物体模型 美国主演X导演B 用户在对项目进行浏览和使用时，依据个人对项 伦理主演X导演B 目的理解，选择简单的词语对自己喜欢的项目进行标 用户4 主演以 电能5 注，这些词语就是社会标签(social tag).BGPR算法主 要依据社会标签信息构建用户喜好物体和项目物体 图1社会标签系统示例 模型. Fig.1 Example of the social tag system 对目标用户而言，他们使用社会标签对自己喜欢 为方便算法以后的计算，根据“用户一项目一标签” 的项目进行分类和描述，以方便对项目的浏览、组织和 之间的关系图，给出几个矩阵的定义如下： 分享，所以标签可以在一定程度上反映用户的喜好 定义11（用户-项目矩阵R(user-item matrix)) 比如用户Jack在对电影标注时经常使用“喜剧”、“爱 如果有n个用户U=（u,山2，…，u.)和m个项目I= 情”、“战争”等标签，Jak可能喜欢这类电影.如果 (i,i2,…,i),它们之间因选择关系形成一个n×m的 Jack使用的标签中“战争”类标签使用的次数很多， 那么他会更喜欢战争类的电影.也就是说用户使用的 矩阵，矩阵的行为用户，列为项目，当用户u:选择了项 标签类别和频率可以反映用户的喜好特征 目j并且评分为x时，矩阵中的rg=x,否则rg=0. 对目标用户4：，用户使用的标签类别可以反映用 定义12（用户-标签频率矩阵A(user-tags frequency 户喜欢项目类别，所以该用户使用过的标签被视为组 matric))如果有n个用户U=(u,u2,…,un)和g个 成u:喜好物体的项目颗粒.若推荐系统中有g类标 标签T=(41,l2,…,l),它们形成一个n×g的矩阵，矩 签，则用户“：的喜好物体模型可用一个向量表示： 阵的行为用户，列为标签，当用户4：使用了z个标签 0.=(pP2,P）. (3) lg,则a4=2,否则a=0 式中p,为用户u,使用的第g类标签的频率. 定义l3(标签-项目频率矩阵B(tags-item frequen- 对项目而言，社会标签是它们的分类信息，即标签 cy matric))如果有g个标签T=(1,l2,,t)和m 可以反映出项目的部分属性.比如“张艺谋”、“爱情” 个项目1=(i,i2,…,),它们形成一个g×m的矩阵， 标签标注到“红高粱”这部电影上时，可以知道“红高 行为标签，列为项目，当有y个标签1。标注了项目i 粱”这部电影为张艺谋执导的爱情类电影.如果某一 时，ba=y,否则ba=0. 部电影有很多用户使用了“爱情”这一标签，那么该电 2.2BGPR算法框架 影是爱情类电影的可能性就会更高。总的说来，对项 基于项目间引力的考虑，BGPR算法的框架如下. 目标注的标签类别和频率可以从很大程度上反映项目 (1)构建目标用户的兴趣偏好模型.对目标用户 的属性信息 4:,根据其使用的标签信息获取其兴趣偏好，从而构建 鉴于上述分析，GBPR算法选择对项目标注的标 目标用户山：的兴趣偏好模型.该模型也是虚拟的项目 签为项目物体的项目颗粒，若推荐系统中有g类标签， 物体，因为它反映了用户的喜好，所以又被叫做喜好 则项目物体的模型可用一个向量表示： 物体. 0=(s52,5g） (4) (2)构建项目物体模型.根据对项目物体标注的 式中s。为项目物体i接收到的第g类标签的频率. 标签信息，构建出能反映项目自身属性特征的模型，该 2.4引力强度的计算 模型叫做项目物体模型. 以用户u,的喜好物体O.为中心点的引力场为例 (3)计算引力强度.在推荐系统中，以目标用户 来说明引力强度的计算.喜好物体0.对作用点j(即 u的喜好物体为中心点，以：没有选择的项目物体为 项目物体)引力强度等于两物体之间的万有引力 作用点，建立山：喜好物体的引力子场∫，计算对各作 强度

王国霞等: 基于万有引力的个性化推荐算法 度，从而把目标用户可能喜欢的项目推荐给他． 图 1 社会标签系统示例 Fig． 1 Example of the social tag system 为方便算法以后的计算，根据“用户--项目--标签” 之间的关系图，给出几个矩阵的定义如下: 定义 11( 用户--项目矩阵 Ｒ( user--item matrix) ) 如果有 n 个用户 U = ( u1，u2，…，un ) 和 m 个项目 I = ( i1，i2，…，im ) ，它们之间因选择关系形成一个 n × m 的 矩阵，矩阵的行为用户，列为项目，当用户 ui 选择了项 目 j 并且评分为 x 时，矩阵中的 rij = x，否则 rij = 0． 定义12( 用户--标签频率矩阵 A( user--tags frequency matric) ) 如果有 n 个用户 U = ( u1，u2，…，un ) 和 g 个 标签 T = ( t1，t2，…，tg ) ，它们形成一个 n × g 的矩阵，矩 阵的行为用户，列为标签，当用户 ui 使用了 z 个标签 tg，则 aig = z，否则 aig = 0． 定义 13( 标签--项目频率矩阵 B( tags--item frequen￾cy matric) ) 如果有 g 个标签 T = ( t1，t2，…，tg ) 和 m 个项目 I = ( i1，i2，…，im ) ，它们形成一个 g × m 的矩阵， 行为标签，列为项目，当有 y 个标签 tg 标注了项目 i 时，bgi = y，否则 bgi = 0． 2. 2 BGPＲ 算法框架 基于项目间引力的考虑，BGPＲ 算法的框架如下． ( 1) 构建目标用户的兴趣偏好模型． 对目标用户 ui，根据其使用的标签信息获取其兴趣偏好，从而构建 目标用户 ui 的兴趣偏好模型． 该模型也是虚拟的项目 物体，因为它反映了用户的喜好，所以又被叫做喜好 物体． ( 2) 构建项目物体模型． 根据对项目物体标注的 标签信息，构建出能反映项目自身属性特征的模型，该 模型叫做项目物体模型． ( 3) 计算引力强度． 在推荐系统中，以目标用户 ui 的喜好物体为中心点，以 ui 没有选择的项目物体为 作用点，建立 ui 喜好物体的引力子场 fi，计算 fi 对各作 用点的引力强度． ( 4) 相似度衡量． 根据定义 4 和引理 1 可知，fi 对 各作用点的引力强度越大，ui 的喜好物体与项目物体 的相似度越高，所以引力强度可被视为一种相似度的 度量． ( 5) 获得推荐． 对引力子场 fi 的各作用点的引力 强度倒序排列，引力强度大的前 N 个作用点对应的项 目物体可能是目标用户 ui 比较喜欢的物体项目，把它 们推荐给目标用户 ui ． 2. 3 用户喜好物体和项目物体模型 用户在对项目进行浏览和使用时，依据个人对项 目的理解，选择简单的词语对自己喜欢的项目进行标 注，这些词语就是社会标签( social tag) ． BGPＲ 算法主 要依据社会标签信息构建用户喜好物体和项目物体 模型． 对目标用户而言，他们使用社会标签对自己喜欢 的项目进行分类和描述，以方便对项目的浏览、组织和 分享，所以标签可以在一定程度上反映用户的喜好． 比如用户 Jack 在对电影标注时经常使用“喜剧”、“爱 情”、“战争”等标签，Jack 可能喜欢这类电影． 如果 Jack 使用的标签中，“战争”类标签使用的次数很多， 那么他会更喜欢战争类的电影． 也就是说用户使用的 标签类别和频率可以反映用户的喜好特征． 对目标用户 ui，用户使用的标签类别可以反映用 户喜欢项目类别，所以该用户使用过的标签被视为组 成 ui 喜好物体的项目颗粒． 若推荐系统中有 g 类标 签，则用户 ui 的喜好物体模型可用一个向量表示: Oui = ( p1，p2，…，pg ) ． ( 3) 式中 pg 为用户 ui 使用的第 g 类标签的频率． 对项目而言，社会标签是它们的分类信息，即标签 可以反映出项目的部分属性． 比如“张艺谋”、“爱情” 标签标注到“红高粱”这部电影上时，可以知道“红高 粱”这部电影为张艺谋执导的爱情类电影． 如果某一 部电影有很多用户使用了“爱情”这一标签，那么该电 影是爱情类电影的可能性就会更高． 总的说来，对项 目标注的标签类别和频率可以从很大程度上反映项目 的属性信息． 鉴于上述分析，GBPＲ 算法选择对项目标注的标 签为项目物体的项目颗粒，若推荐系统中有 g 类标签， 则项目物体 i 的模型可用一个向量表示: Oi = ( s1，s2，…，sg ) ． ( 4) 式中 sg 为项目物体 i 接收到的第 g 类标签的频率． 2. 4 引力强度的计算 以用户 ui 的喜好物体 Oui 为中心点的引力场为例 来说明引力强度的计算． 喜好物体 Oui 对作用点 j ( 即 项目物体 j) 引力强度等于两物体之间的万有引力 强度． · 752 ·

·258· 工程科学学报，第37卷，第2期 根据万有引力的计算方法，如式(1)所示，首先要 计算两物体的质量.项目物体和喜好物体都是由项目 d= (bi-a)2 (9) 颗粒组成，它们的质量由组成它的项目颗粒的质量决 式中，b5为矩阵B第j行的转置，a,为矩阵A中用户 定的.GBPR算法把社会标签视为项目颗粒，项目颗粒 山，对应的第j行，d为喜好物体和项目物体j间的 的质量等同于社会标签对其标注的项目物体的重要程 距离 度：同理，喜好物体包含的项目颗粒等同于用户使用的 那么，项目物体j和用户“：的喜好物体间的引力 标签对自己的重要程度 强度的计算如式如下： 由于很多项目颗粒可能存在于不同的项目物体 99 中，它们在不同的项目物体中时，其重要性可能是不相 F=(d) (10) 同的，有必要定义它们独立于具体项目物体的质量，即 其中F.为项目物体j和用户4：喜好物体间的引力 平均质量.GBPR算法中，项目逆频率被定义为颗粒的 强度 平均质量，即 2.5获得推荐 p=in(m.) (5) 依据定义4和引理1，项目物体j和目标用户4：喜 好物体间的引力强度可以被认为是二者的相似度，它们 式中：q(p,)是第g个项目颗粒的平均质量；m推荐系 之间的引力强度越大，目标用户的喜好物体中包含的项 统中的项目总数：n。是项目颗粒g的总数，即社会标 目颗粒和相应项目物体中相同类型的项目颗粒含量相 签的总数 同的就越多，那么该项目物体就越有可能被用户喜欢. 项目物体j中的第g个项目颗粒的质量，即第g 对目标用户“：，倒序排列其引力子场中各作用点 个项目颗粒对项目物体的重要程度，计算方法如下： 的引力强度，前N个作用点对应的项目物体被认为是 9a=n(pg)×g(p). (6) 用户可能喜欢的，从而把它们推荐给目标用户· 其中9是项目物体j中的第g个项目颗粒的质量， w(p,i)是颗粒g对项目物体j的重要性参数，q(p) 3 实验结果 是第g个项目颗粒的平均质量. 3.1数据集和评价矩阵 式(6)中的重要性参数采用(TF×DF(tem 本文采用的数据集为MovieLens.该数据集为 frequency-inverse document frequency)方法来计 GroupLens小组整理所得，从网站www.grouplens.org 算0.该方法通常用来评价一字词对一个文件集中 下载.由于该数据集被大多数推荐系统测试使用，所 某分文件的重要程度，其中TF(term frequency).,即词 以用它来测试的算法性能比较具有说服力.当然，本 频，在本文中用来表示项目颗粒的在某项目物体中出 文采用MovieLens数据集中带有tag的数据集.该数据 现频率，如果n,是项目物体j中项目颗粒g的数目， 集中用户数为2113，电影数为10197，标签数为13222 ,是项目物体j中所有项目颗粒的总数，那么TF的计 随即选择数据集中的20%作为测试集，80%作为训练 算式为 集来进行测试. tn TF=- (7) 由于该算法预测结果的依据是用户的喜好物体和 tn 项目物体间的引力强度，也即推荐结果没有项目的评 DF(inverse document frequency),即逆向文件频 分，故测试的性能选择为准确率(Precision)和排名准 率，在本文用来表示项目颗粒的类别区分能力.如果 确率(Hit rank). m是项目物体总数，in,是包含第g个项目颗粒的项目 准确度为用户喜欢的项目被预测正确的比例，计 物体总数，则DF的计算式为 算方法如下a.2: IDF log in m (8) Hits Precision (11) N 根据定义3可得项目物体j的质量向量9，同理可 式中，Hts为预测的命中个数，N为推荐个数 得用户山：喜好物体的质量向量q。· 排名准确率为推荐正确的项目在推荐列表中排名 然后要计算用户喜好物体和项目物体之间的距 情况的度量，排名越靠前说明推荐效果越好，计算方法 离.欧几里得距离又叫欧式距离，通常用来计算两向 如下： 量之间的距离，也可以认为是二者之间的差距.GBPR (12) 算法计算用户山：使用的标签频率向量和标注项目j的 标签频率向量间的欧式距离，并把该距离作为用户“： 式中，n为用户数，h推荐列表中命中的个数，c为排名 的喜好物体和项目物体j之间差距： 位置

工程科学学报，第 37 卷，第 2 期 根据万有引力的计算方法，如式( 1) 所示，首先要 计算两物体的质量． 项目物体和喜好物体都是由项目 颗粒组成，它们的质量由组成它的项目颗粒的质量决 定的． GBPＲ 算法把社会标签视为项目颗粒，项目颗粒 的质量等同于社会标签对其标注的项目物体的重要程 度; 同理，喜好物体包含的项目颗粒等同于用户使用的 标签对自己的重要程度． 由于很多项目颗粒可能存在于不同的项目物体 中，它们在不同的项目物体中时，其重要性可能是不相 同的，有必要定义它们独立于具体项目物体的质量，即 平均质量． GBPＲ 算法中，项目逆频率被定义为颗粒的 平均质量，即 q( pg ) ( = ln m tn ) g ． ( 5) 式中: q( pg ) 是第 g 个项目颗粒的平均质量; m 推荐系 统中的项目总数; tng 是项目颗粒 g 的总数，即社会标 签的总数． 项目物体 j 中的第 g 个项目颗粒的质量，即第 g 个项目颗粒对项目物体 j 的重要程度，计算方法如下: qjg = w( pg，ij ) × q( pg ) ． ( 6) 其中 qjg 是项目物体 j 中的第 g 个项目颗粒的质量， w( pg，ij ) 是颗粒 g 对项目物体 j 的重要性参数，q( pg ) 是第 g 个项目颗粒的平均质量． 式( 6 ) 中 的 重 要 性 参 数 采 用 ( TF × IDF ( term frequency--inverse document frequency ) ) 方 法 来 计 算［10--11］． 该方法通常用来评价一字词对一个文件集中 某分文件的重要程度，其中 TF ( term frequency) ，即词 频，在本文中用来表示项目颗粒的在某项目物体中出 现频率，如果 tnj t g 是项目物体 j 中项目颗粒 g 的数目， tnj T是项目物体 j 中所有项目颗粒的总数，那么 TF 的计 算式为 TF = tnj t g tnj T ． ( 7) IDF ( inverse document frequency) ，即逆向文件频 率，在本文用来表示项目颗粒的类别区分能力． 如果 m 是项目物体总数，int g 是包含第 g 个项目颗粒的项目 物体总数，则 IDF 的计算式为 ( IDF = log m int ) g ． ( 8) 根据定义3 可得项目物体 j 的质量向量 qj ，同理可 得用户 ui 喜好物体的质量向量 qui ． 然后要计算用户喜好物体和项目物体之间的距 离． 欧几里得距离又叫欧式距离，通常用来计算两向 量之间的距离，也可以认为是二者之间的差距． GBPＲ 算法计算用户 ui 使用的标签频率向量和标注项目 j 的 标签频率向量间的欧式距离，并把该距离作为用户 ui 的喜好物体和项目物体 j 之间差距: dju = ∑ g t = 1 ( b'jg － ajg ) 槡 2 ． ( 9) 式中，b' j* 为矩阵 B 第 j 行的转置，aj* 为矩阵 A 中用户 ui 对应的 第 j 行，dju 为 喜好物体和项目物体 j 间 的 距离． 那么，项目物体 j 和用户 ui 的喜好物体间的引力 强度的计算如式如下: Fji = q·j qui ( diu ) 2 ． ( 10) 其中 Fji 为项目物体 j 和用户 ui 喜好物体间的 引 力 强度． 2. 5 获得推荐 依据定义 4 和引理 1，项目物体 j 和目标用户 ui 喜 好物体间的引力强度可以被认为是二者的相似度，它们 之间的引力强度越大，目标用户的喜好物体中包含的项 目颗粒和相应项目物体中相同类型的项目颗粒含量相 同的就越多，那么该项目物体就越有可能被用户喜欢． 对目标用户 ui，倒序排列其引力子场中各作用点 的引力强度，前 N 个作用点对应的项目物体被认为是 用户可能喜欢的，从而把它们推荐给目标用户 ui ． 3 实验结果 3. 1 数据集和评价矩阵 本文采用的数据集为 MovieLens． 该 数 据 集 为 GroupLens 小组整理所得，从网 站 www． grouplens． org 下载． 由于该数据集被大多数推荐系统测试使用，所 以用它来测试的算法性能比较具有说服力． 当然，本 文采用 MovieLens 数据集中带有 tag 的数据集． 该数据 集中用户数为 2113，电影数为 10197，标签数为13222． 随即选择数据集中的 20% 作为测试集，80% 作为训练 集来进行测试． 由于该算法预测结果的依据是用户的喜好物体和 项目物体间的引力强度，也即推荐结果没有项目的评 分，故测试的性能选择为准确率( Precision) 和排名准 确率( Hit_rank) ． 准确度为用户喜欢的项目被预测正确的比例，计 算方法如下［4，12--13］: Precision = Hits N ． ( 11) 式中，Hits 为预测的命中个数，N 为推荐个数． 排名准确率为推荐正确的项目在推荐列表中排名 情况的度量，排名越靠前说明推荐效果越好，计算方法 如下［4］: Hit_rank = 1 n ∑ h i = 1 1 ci ． ( 12) 式中，n 为用户数，h 推荐列表中命中的个数，ci 为排名 位置． · 852 ·

王国霞等：基于万有引力的个性化推荐算法 ·259* 3.2实验结果和结论 分元素为0，所以其计算的时间复杂度和标签数量的 协同过滤推荐是推荐算法中最获得认可的算法之 平方成正比.在对目标用户推荐时，所需就是用户的 一，所以本文把BGRP算法和协同过滤推荐中的基于 喜好向量，并且该向量的元素大多数为0，所以推荐时 用户的推荐和基于项目的推荐性能进行对比.同时， 所需的计算复杂度和其他的算法比也较低 最近提出了很多基于标签的协同过滤推荐，从中选择 参考文献 一个较好算法的性能也拿来做性能的对比.在实验 [Xu H L,Wu X,Li X D,et al.Comparison study of internet rec- 时，随即抽取10个目标用户，Top-V中N取30个，在 ommendation system.J Softuare,2009,20(2):350 不同的运算规模下计算其推荐性能，最后取每一运算 (许海玲，吴潇，李晓东，等.互联网推荐系统比较研究.软 规模下的平均值来获得最后结果.图2是精确度的对 件学报，2009,20(2)：350) 比，图3是排名准确度的对比 2] Wang GX,Liu H P.Survey of personalized recommendation sys- tem.Comput Eng Appl,2012,48(7)66 ■基于用户的协同过滤 (王国霞，刘贺平.个性化推荐系统综述.计算机工程与应 ■基于项目的协州同过滤 用，2012,48(7)：66) 05 ■基于标签的协州同过滤 B3]Jin Y A.Research on Technologies and Methods of Social Tag Rec- ■GBPR算法 ommendation [Dissertation].Wuhan:Huazhong University of Science and Technology,2011 (新延安.社会标签推荐技术与方法研究[学位论文].武汉： 华中科技大学，2011) 4 Zheng N,Li Q D.A recommender system based on tag and time information for social tagging systems.Expert Syst Appl,2011, 38:4575 20) 300 400 500 600 [5]Kim H N,Ji A T.Ha I,et al.Collaborative filtering based on 电影数 collaborative tagging for enhancing the quality of recommendation. 图2准确度对比 Electron Commer Res Appl,2010,9(1):73 Fig.2 Comparison of precision 6]Durao F.Dolog P.A personalized tag-based recommendation in social web systems Workshop on Adaptation and Personalication 0.050 ·基于用户的协厨过 for Web 2.0,UMAP09.Trento,2009:22 0.048 。一基于项目的协同过洁 一一基于标签的协同过滤 7] Wang W P,Zhang L J.Collaborative filtering based on similarity 0.046 ◆一GBPR算法 fusion of tag and rating under the background of SNS.Comput Syst 0.044 4ppl,2011,20(10):78 0.042 (王卫平，张丽君.SNS背景下基于Tag和Rating相似度融合 0040 的协同过滤.计算机系统应用，2011,20(10)：78) 0.038 8] Feng W,Wang J Y.Incorporating heterogeneous information for 0.036 personalized tag recommendation in social tagging systems//Pro- 0.034 ceedings of the 18th ACM SIGKDD International Conference on 0.032 100 200 300400500600 Knowledge Discovery and Data Mining.Beijing,2012:12 [9] 电影数 Adomavicius G,Sankaranarayanan R,Sen S,et al.Incorporating contextual information in recommender systems using a multidi- 图3排名准确度对比 mensional approach.ACM Trans Inf Syst,2005,23 (1):103 Fig.3 Comparison of hit_rank 1o] Yan X L,Liu Y Q,Ma S P,et al.Study on website keyword ex- GBPR算法与其他的推荐算法相比复杂性也降低 traction for browsing recommendation.CAAl Trans Intell Syst, 了很多，无论是时间复杂度还是空间复杂度都比较低 2013,7(5):398 一旦确定目标用户，需要存储一个长度为【（社会标签 (闫兴龙，刘亦群，马少平，等.面向浏览推荐的网页关键词 个数)的一维向量，存储空间较其他算法大大减少.并 提取.智能系统学报，2013,7(5)：398) 01] Song Y,Liu Z L,Li L J.Research on social tag recommendation 且需要的存储空间仅仅随着社会标签个数的增加而增 techniques based on content.I Harbin Inst Technol New Ser, 加，与系统中用户个数和项目个数无关.这一点对算 2013,20(2):74 法复杂度的影响很关键，因为在推荐系统实际应用时， 02] David M,Pennock E H,Lee C.Social choice theory and recom- 用户的数量以及用户感兴趣的项目数量都会迅速增 mender systems:analysis of the axiomatic foundations of collabo- 长，其增长速度会远远超过其他各项的增长速度 rative filtering /Proceedings of the Seventeenth National Confer- ence on Artificial Intelligence.Austin,2000 在进行推荐计算的过程中，喜好物体和项目物体 [13]Kristina Lerman.Social networks and social information filtering 间万有引力计算也仅仅与标签数量相关，所得的项目 on digg Proceedings of the Int1 Conference on Weblogs and So- 间质量和引力矩阵在实际应用中为稀疏性矩阵，大部 cial Media.Washington D.C.,2006

王国霞等: 基于万有引力的个性化推荐算法 3. 2 实验结果和结论 协同过滤推荐是推荐算法中最获得认可的算法之 一，所以本文把 BGＲP 算法和协同过滤推荐中的基于 用户的推荐和基于项目的推荐性能进行对比． 同时， 最近提出了很多基于标签的协同过滤推荐，从中选择 一个较好算法的性能也拿来做性能的对比． 在实验 时，随即抽取 10 个目标用户，Top-N 中 N 取 30 个，在 不同的运算规模下计算其推荐性能，最后取每一运算 规模下的平均值来获得最后结果． 图 2 是精确度的对 比，图 3 是排名准确度的对比． 图 2 准确度对比 Fig． 2 Comparison of precision 图 3 排名准确度对比 Fig． 3 Comparison of hit_rank GBPＲ 算法与其他的推荐算法相比复杂性也降低 了很多，无论是时间复杂度还是空间复杂度都比较低． 一旦确定目标用户，需要存储一个长度为 t ( 社会标签 个数) 的一维向量，存储空间较其他算法大大减少． 并 且需要的存储空间仅仅随着社会标签个数的增加而增 加，与系统中用户个数和项目个数无关． 这一点对算 法复杂度的影响很关键，因为在推荐系统实际应用时， 用户的数量以及用户感兴趣的项目数量都会迅速增 长，其增长速度会远远超过其他各项的增长速度． 在进行推荐计算的过程中，喜好物体和项目物体 间万有引力计算也仅仅与标签数量相关，所得的项目 间质量和引力矩阵在实际应用中为稀疏性矩阵，大部 分元素为 0，所以其计算的时间复杂度和标签数量的 平方成正比． 在对目标用户推荐时，所需就是用户的 喜好向量，并且该向量的元素大多数为 0，所以推荐时 所需的计算复杂度和其他的算法比也较低． 参 考 文 献 ［1］ Xu H L，Wu X，Li X D，et al． Comparison study of internet rec￾ommendation system． J Software，2009，20( 2) : 350 ( 许海玲，吴潇，李晓东，等． 互联网推荐系统比较研究． 软 件学报，2009，20( 2) : 350) ［2］ Wang G X，Liu H P． Survey of personalized recommendation sys￾tem． Comput Eng Appl，2012，48( 7) : 66 ( 王国霞，刘贺平． 个性化推荐系统综述． 计算机工程与应 用，2012，48( 7) : 66) ［3］ Jin Y A． Ｒesearch on Technologies and Methods of Social Tag Ｒec￾ommendation ［Dissertation］． Wuhan: Huazhong University of Science and Technology，2011 ( 靳延安． 社会标签推荐技术与方法研究［学位论文］． 武汉: 华中科技大学，2011) ［4］ Zheng N，Li Q D． A recommender system based on tag and time information for social tagging systems． Expert Syst Appl，2011， 38: 4575 ［5］ Kim H N，Ji A T，Ha I，et al． Collaborative filtering based on collaborative tagging for enhancing the quality of recommendation． Electron Commer Ｒes Appl，2010，9( 1) : 73 ［6］ Durao F，Dolog P． A personalized tag-based recommendation in social web systems / / Workshop on Adaptation and Personalization for Web 2. 0，UMAP'09． Trento，2009: 22 ［7］ Wang W P，Zhang L J． Collaborative filtering based on similarity fusion of tag and rating under the background of SNS． Comput Syst Appl，2011，20( 10) : 78 ( 王卫平，张丽君． SNS 背景下基于 Tag 和 Ｒating 相似度融合 的协同过滤． 计算机系统应用，2011，20( 10) : 78) ［8］ Feng W，Wang J Y． Incorporating heterogeneous information for personalized tag recommendation in social tagging systems / / Pro￾ceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining． Beijing，2012: 12 ［9］ Adomavicius G，Sankaranarayanan Ｒ，Sen S，et al． Incorporating contextual information in recommender systems using a multidi￾mensional approach． ACM Trans Inf Syst，2005，23( 1) : 103 ［10］ Yan X L，Liu Y Q，Ma S P，et al． Study on website keyword ex￾traction for browsing recommendation． CAAI Trans Intell Syst， 2013，7( 5) : 398 ( 闫兴龙，刘亦群，马少平，等． 面向浏览推荐的网页关键词 提取． 智能系统学报，2013，7( 5) : 398) ［11］ Song Y，Liu Z L，Li L J． Ｒesearch on social tag recommendation techniques based on content． J Harbin Inst Technol New Ser， 2013，20( 2) : 74 ［12］ David M，Pennock E H，Lee C． Social choice theory and recom￾mender systems: analysis of the axiomatic foundations of collabo￾rative filtering / / Proceedings of the Seventeenth National Confer￾ence on Artificial Intelligence． Austin，2000 ［13］ Kristina Lerman． Social networks and social information filtering on digg / / Proceedings of the Int'l Conference on Weblogs and So￾cial Media． Washington D． C． ，2006 · 952 ·