基于项目评分预测的协同过滤推荐算法

Vol.14,No.9©2003JournalofSoftware软件学报1000-9825/2003/14(09)1621基于项目评分预测的协同过滤推荐算法∗邓爱林1,2+,朱扬勇1,施伯乐11(复旦大学计算机与信息技术系,上海200433)2(上海电信技术研究院,上海200122)ACollaborativeFilteringRecommendationAlgorithmBasedonItemRatingPredictionDENGAi-Lin1,2+,ZHUYang-Yong1,SHIBai-Le11(DepartmentofComputerandInformationTechnology,FudanUniversity,Shanghai200433,China)2(ShanghaiTelecomTechnologyResearchInstitute,Shanghai200122,China)+Correspondingauthor:Phn:86-21-58755256,E-mail:[e-mail];[e-mail](9):1621~1628.:RecommendationsystemisoneofthemostimportanttechnologiesinE-commerce.WiththedevelopmentofE-commerce,themagnitudesofusersandcommoditiesgrowrapidly,resultedintheextremesparsityofuserratingdata.Traditionalsimilaritymeasuremethodsworkpoorinthissituation,makethequalityofrecommendationsystemdecreaseddramatically.Toaddressthisissueanovelcollaborativefilteringalgorithmbasedonitemratingpredictionisproposed.Thismethodpredictsitemratingsthatusershavenotratedbythesimilarityofitems,thenusesanewsimilaritymeasuretofindthetargetusers’neighbors.Theexperimentalresultsshowthatthismethodcanefficientlyimprovetheextremesparsityofuserratingdata,andprovidbetterrecommendationresultsthantraditionalcollaborativefilteringalgorithms.Keywords:E-commerce;recommendationsystem;collaborativefiltering;itemsimilarity;recommendationalgorithm;MAE(meanabsoluteerror)摘要:推荐系统是电子商务系统中最重要的技术之一.随着电子商务系统用户数目和商品数目的日益增加,在整个商品空间上用户评分数据极端稀疏,传统的相似性度量方法均存在各自的弊端,导致推荐系统的推荐质量急剧下降.针对用户评分数据极端稀疏情况下传统相似性度量方法的不足,提出了一种基于项目评分预测的协同过滤推荐算法,根据项目之间的相似性初步预测用户对未评分项目的评分,在此基础上,采用一种新颖的相似性度量方法计算目标用户的最近邻居.实验结果表明,该算法可以有效地解决用户评分数据极端稀疏情况下∗SupportedbytheNationalHighTechnologyDevelopment863ProgramofChinaunderGrantNos.863-317-01-04-99,863-306-ZT06-07-02(国家高科技发展计划(863))第一作者简介:邓爱林(1975－),男,湖北黄冈人,博士,工程师,主要研究领域为数据库,知识库.1622JournalofSoftware软件学报2003,14(9)传统相似性度量方法存在的问题,显著地提高推荐系统的推荐质量.关键词:电子商务;推荐系统;协同过滤;项目相似性;推荐算法;平均绝对偏差中图法分类号:TP391文献标识码:A随着互联网的普及和电子商务的发展,推荐系统逐渐成为电子商务IT技术的一个重要研究内容,越来越多地得到研究者的关注.目前,几乎所有大型的电子商务系统,如Amazon,CDNOW,eBay,当当网上书店等,都不同程度地使用了各种形式的推荐系统.最近邻协同过滤推荐是当前最成功的推荐技术[1],其基本思想就是基于评分相似的最近邻居的评分数据向目标用户产生推荐.由于最近邻居对项目(电子商务中的商品、电影、音乐等)的评分与目标用户非常相似,因此目标用户对未评分项目的评分可以通过最近邻居对该项目评分的加权平均值逼近.随着电子商务系统规模的进一步扩大,用户数目和项目数据急剧增加,导致用户评分数据的极端稀疏性[1],在用户评分数据极端稀疏的情况下,传统相似性度量方法均存在各自的弊端,使得计算得到的目标用户的最近邻居不准确,推荐系统的推荐质量急剧下降.针对用户评分数据的极端稀疏性,本文提出了一种基于项目评分预测的最近邻协同过滤推荐算法,通过计算项目之间的相似性,初步预测用户对未评分项目的评分,然后采用一种新颖的相似性度量方法计算用户的最近邻居.实验结果表明,本方法可以有效地解决用户评分数据极端稀疏情况下传统相似性度量方法存在的不足,显著地提高推荐系统的推荐质量.1相关工作为了产生精确的推荐,保证推荐系统的实时性要求,研究者提出了各种不同的推荐算法,如协同过滤推荐系统、基于项目的协同过滤推荐、Bayesian网络技术、聚类技术、关联规则技术以及基于图的Horting图技术等.Typestry[2]是最早提出来的基于协同过滤的推荐系统,目标用户需要明确指出与自己行为比较类似的其他用户.GroupLens[3]是基于用户评分的自动化协同过滤推荐系统,用于推荐电影和新闻.Ringo推荐系统[4]和Video推荐系统[5]通过电子邮件的方式分别推荐音乐和电影.Breese[1]等人对各种协同过滤推荐算法及其改进进行了深入分析.传统的协同过滤推荐通过用户的最近邻居产生最终的推荐,基于项目的协同过滤推荐首先计算项目之间的相关性,然后通过用户对相关项目的评分预测用户对未评分项目的评分[6].Bayesian网络技术利用训练集创建相应的模型[7],模型用决策树表示,节点和边表示用户信息.训练得到的模型非常小,所以对模型的应用非常快.这种方法适合于用户的兴趣爱好变化比较慢的场合.聚类技术将具有相似兴趣爱好的用户分配到相同的簇中[8,9],聚类产生之后,根据簇中其他用户对商品的评价预测目标用户对该商品的评价.由于聚类过程离线进行,所以在线的推荐算法产生推荐的速度比较快.关联规则技术在零售业得到了广泛的应用,关联规则挖掘可以发现不同商品在销售过程中的相关性.基于关联规则的推荐算法根据生成的关联规则模型和用户当前的购买行为向用户产生推荐[10].关联规则模型的生成可以离线进行,因此可以保证有效地推荐系统的实时性要求.Horting图技术是一种基于图的方法[11],节点代表用户,边代表两个用户之间的相似度.在图中搜索近邻节点,然后综合近邻节点的评分形成最后的推荐.Horting图技术可以跳过中间节点寻找最近邻居,考虑了节点之间的传递相似关系.因此,推荐精度优于最近邻协同过滤技术.针对数据的极端稀疏性问题,文献[12]提出通过奇异值分解(SVD)减少项目空间的维数,使得用户在降维后的项目空间上对每一个项目均有评分,实验结果表明,这种方法可以有效地解决同义词(synonymy)问题,显著地提高推荐系统的伸缩能力.但降维会导致信息损失,降维效果与数据集密切相关,在项目空间维数很高的情况下,降维的效果难以保证[13].邓爱林等:基于项目评分预测的协同过滤推荐算法16232传统的相似性度量方法及其分析协同过滤推荐根据其他用户的观点产生对目标用户的推荐列表,它基于这样一个假设[1]:如果用户对一些项目的评分比较相似,则他们对其他项目的评分也比较相似.协同过滤推荐系统使用统计技术搜索目标用户的若干最近邻居,然后根据最近邻居对项目的评分预测目标用户对项目的评分,产生对应的推荐列表.为了找到目标用户的最近邻居,必须度量用户之间的相似性,然后选择相似性最高的若干用户作为目标用户的最近邻居.目标用户的最近邻居查询是否准确,直接关系到整个推荐系统的推荐质量.准确查询目标用户的最近邻居是整个协同过滤推荐成功的关键.用户评分数据可以用一个m×n阶矩阵A(m,n)表示,m行代表m个用户,n列代表n个项目,第i行第j列的元素Ri,j代表用户i对项目j的评分.用户评分数据矩阵如图1所示.度量用户i和用户j之间相似性的方法是,首先得到经用户i和用户j评分的所有项目,然后通过不同的相似性度量方法计算用户i和用户j之间的相似性,记为sim(i,j).Item1…Itemk…ItemnUser1R1,1…R1,k…/………………UserjRj,1…/…Rj,n………………Userm/…Rm,k…Rm,nFig.1Userratingdatamatrix图1用户评分数据矩阵2.1传统的相似性度量方法度量用户间相似性的方法有多种,主要包括如下3种方法[6]:余弦相似性、相关相似性以及修正的余弦相似性.•余弦相似性(cosine):用户评分被看做是n维项目空间上的向量,如果用户对项目没有进行评分,则将用户对该项目的评分设为0,用户间的相似性通过向量间的余弦夹角度量.设用户i和用户j在n维项目空间上的评分分别表示为向量ijrr,,则用户i和用户j之间的相似性sim(i,j)为..),cos(),(jijijijisimrrrrrr==分子为两个用户评分向量的内积,分母为两个用户向量模的乘积.•相关相似性(correlation):设经用户i和用户j共同评分的项目集合用Iij表示,则用户i和用户j之间的相似性sim(i,j)通过Pearson相关系数度量:.)()())((),(2,2,,,∑∑∑∈∈∈−−−−=ijijijIcjcjIciciIcjcjiciRRRRRRRRjisimRi,c表示用户i对项目c的评分,iR和jR分别表示用户i和用户j对项目的平均评分.•修正的余弦相似性(adjustedcosine):在余弦相似性度量方法中没有考虑不同用户的评分尺度问题,修正的余弦相似性度量方法通过减去用户对项目的平均评分来改善上述缺陷,设经用户i和用户j共同评分的项目集合用Iij表示,Ii和Ij分别表示经用户i和用户j评分的项目集合,则用户i和用户j之间的相似性sim(i,j)为.)()())((),(2,2,,,∑∑∑∈∈∈−−−−=jiijIcjcjIciciIcjcjiciRRRRRRRRjisimRi,c表示用户i对项目c的评分,iR和jR分别表示用户i和用户j对项目的平均评分.2.2传统相似性度量方法分析随着电子商务系统规模的扩大,用户数目和项目数目呈指数级增长,用户评分数据极端稀疏.在大型电子商1624JournalofSoftware软件学报2003,14(9)务系