结合二部图投影与排序的协同过滤

小型微型计算机系统

JournalofChineseComputerSystems

2010年5月第5期Vol131No.52010

结合二部图投影与排序的协同过滤

刘　淇,陈恩红

(中国科学技术大学计算机科学与技术学院,安徽合肥230027)E2mail:cheneh@

摘　要:协同过滤是推荐系统中应用最为广泛的方法.提出一类基于二部图一维投影与排序相结合的协同过滤算法,文中采用结构相似进行二部图投影并利用随机游走对节点排序.该方法不仅可以防止冷启动,具有较高准确度,且可扩展性良好.另外,该算法可以避免低覆盖率造成的推荐不准确.算法可以有两类不同的实现,分别是基于项协同过滤的项排序算法和基于用户协同过滤的用户排序算法,在标准数据集MovieLens上的测试表明了算法的有效性.关键词:协同过滤;二部图投影;结构相似;排序;随机游走中图分类号:TP311　　　　　文献标识码:A　　　　　　文章编号:100021220(2010)0520835205

CollaborativeFilteringThroughCombiningBipartiteGraphProjectionanding

LIUQi,CHENEn2hong

(SchoolofComputerScienceandTechnologyUniversityofScienceandofChina,,)

Abstract:CollaborativeFilteringisthemostwidelyusedapproachinsproposesanovelcollaborativefilteringapproachthroughcombiningbipartitegraphproachbipartitegraphisprojectedbasedon

structuralsimilarityandrandomwalkisusedtothe.mnotonlydealwith"coldstartproblem"togethighprecisionbutalsohavegoodscalability.ourmtherankbasedonthesimilaritybetweenalluser2itempairs,thusmakingitavoidsrate.Thealgorithmistestedinboththeitem2collaborative2baseditemrankingwayandthe2baseduserrankingway.TheexperimentalresultsobtainedonabenchmarkdatasetMovielensclearlyshowroposedapproach.

Keywords:filtering;bipartitegraphprojection;structuralsimilarity;ranking;randomwalk

1　引　言

推荐系统根据用户与系统的交互历史以及用户的个人信息等构建用户的兴趣模型,去预测用户可能感兴趣的产品或项.推荐系统大致可以分为三类[1]:基于协同过滤的方法

(collaborativefiltering)[2,4],基于内容的方法(content2basedfiltering)

[5,8]

和将二者结合的混合推荐算法(hybridrecom2

.其中,基于协同过滤(CF)的方法在保持较好

mendation)

[6,7]

推荐效果的同时,其实现和维护代价都比较低,因而得到了最广泛的应用.

例如,MovieLens系统[3,9]利用CF做电影推荐,Amazon.

com

[2]

利用CF推荐书籍,CD等产品,还有为用户推荐新闻

和电影的GroupLens[4]等等.协同过滤又可以分为基于用户的协同过滤和基于项的协同过滤,前者认为给定用户会喜欢那些与他们有相似喜好的用户所喜爱的项,而后者则认为给定的项会被那些喜欢与它们相似的项的用户所喜欢[2,4].

推荐的准确性是推荐系统是否有效的一个重要评判标准,然而在实际应用中还要综合考虑算法的时空复杂性,随着项和用户数目的增加导致算法实现的可扩展性等等问题.例如,因为实际系统中的用户数往往比项数有更高的数量级,所

以基于用户的协同过滤算法会面临扩展瓶颈.而在一个项数目更高的系统中,如果使用基于项的协同过滤算法也会面临同样的问题.更多的情况下,同一个系统中项的数目与用户数目是时高时低的,这就需要一种可以随时应变的协同过滤算法,当项数目过高时就采用基于用户的协同过滤,而当用户数目过高时就采用基于项的协同过滤.

本文提出一类基于二部图投影和排序的协同过滤算法框架(BipartiteGraphProjectionandRanking,BGPR)并提出基于此框架的一个具体实现.在BGPR中,首先用二部图表示用户对项的喜好关系,二部图的两类顶点分别表示用户和项,通过对二部图进行一维投影就可以将其转化成一个表示用户间或项之间相似关系的图.再根据特定的排序算法对投影图中的节点进行排序.不用预测用户对项的可能打分,就可以产生推荐序列.而且,BGPR算法既可以实现基于项的协同过滤又可以实现基于用户的协同过滤,即分别将项作为投影图中的节点为给定用户对所有项进行排序的方法和将用户作为投影图中节点为给定项进行用户排序的方法.本文主要贡献在于:

提出基于BGPR的协同过滤算法框架,因为可以采用不同的二部图投影方案和对节点的排序方法,所以基于此框架有可以有许多不同的协同过滤算法实现.

　　收稿日期:2009202218　基金项目:国家自然科学基金项目(60775037)资助;国家“八六三”高技术研究发展计划项目(2009AA01Z132)资助.　作者简介:刘　淇,男,1986年生,硕士研究生,研究方向为数据挖掘、推荐系统、社会网络;陈恩红,男,1968年生,博士,教授,博士生导师,研究方向为语义Web、机器学习与数据挖掘、网络信息处理、约束满足问题.

836　　　　　　小　型　微　型　计　算　机　系　统

具体实现,详细介绍BGPR算法框架.

　　　　　　2010年

　　提出一个具体的BGPR算法实现,其中利用结构相似作为二部图投影时的连边权重学习方法,然后将待推荐对象在

投影图上进行带重启动的随机游走(RWR,random2walkwith

restart),根据待推荐对象停留在每个节点的概率对图中的节

3　BGPR算法描述

协同过滤是为给定用户推荐其可能感兴趣的项,但也可以将给定的项推荐给可能对其感兴趣的用户.对于前者,BG2

PR将投影得到由项组成的关联图,然后用给定用户的用户向

点进行排序.

通过在一个推荐系统的通用数据集MovieLens[9](由Minnesota大学的GroupLens研究小组提供)上的实验结果验证了BGPR算法比其它优秀算法有更高的推荐准确度.

量在相应的项关联矩阵上进行RWR,从而得到所有项的排序,排名靠前即得分较高的项将被推荐给用户(Item-Rank,因为实验中使用的item为电影,所以又称Movie-Rank).而对于后者,BGPR将投影得到用户组成的关联图,然后用给定项的项向量在相应的用户关联矩阵上进行RWR,得到所有用户的排序,该项将被推荐给得分较高的用户(User-Rank).本文,I表示项的集合,U表示用户的集合;n,m分别表示项和用户的个数.3.1　二部图投影

G=〈X,E〉,X=U∪I,pIq,则为

Up与.,).投影后节点iσ(i,j)表示节点i与j的相似度.用矩阵,CCi,j=σ(i,j).投影的过程

2　相关工作

近十年来,已经有大量基于协同过滤的推荐系统出现在

科研或实际应用中.一部分学者提出了一种启发式的、根据用户以往的所有评价去推荐的Memory2based方法.这种方法的一般思路是先为每个用户寻找相似的用户,再根据相似用户对给定项的打分和用户相似度进行项的排序

[1]

,然而,Memo2

ry2based方法不能很好地应对数据稀疏的情况而且其可扩展

性往往比较差.而另有一部分学者研究了利用已有的用户评价数据建立一个模型,然后根据此模型进行评价预测的Mod2el2based方法,例如到目前为止已经有人提出了基于贝叶斯网络的方法[11],基于最大熵的方法[10]等等,但是Model常不能像Memory2based.近来,行协同推荐[15,17,12]总结和比较了大量.[13]也提出.

在图结构中,经常用随机游走(Randomwalk)对节点间的相似度进行衡量[15,16,19],该方法以两个节点间的平均首达时间(ACT,averagecommutetime)为标准.但ACT的问题在于它对图中远离节点i,j的部分有很强的依赖,即使节点是紧密相连的时候也是一样,所以经常会造成计算得到的相似度与实 …… 此处隐藏：3658字，全部文档内容请下载后查看。喜欢就下载吧 ……