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

小型微型计算机系统

JournalofChineseComputerSystems

2010年5月第5期Vol131No.52010

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

刘　淇,陈恩红

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

摘　要:协同过滤是推荐系统中应用最为广泛的方法.提出一类基于二部图一维投影与排序相结合的协同过滤算法,文中采用结构相似进行二部图投影并利用随机游走对节点排序.该方法不仅可以防止冷启动,具有较高准确度,且可扩展性良好.另外,该算法可以避免低覆盖率造成的推荐不准确.算法可以有两类不同的实现,分别是基于项协同过滤的项排序算法和基于用户协同过滤的用户排序算法,在标准数据集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的部分有很强的依赖,即使节点是紧密相连的时候也是一样,所以经常会造成计算得到的相似度与实际相似度有较大偏差.[22]利用每次游走有限步作为抵消该依赖的一种方法.另一种抵消方法是,让从节点i到节点j的游走周期性"重启动",即每一步以一定的概率c返回i重新走步,这样几乎不会走到图中偏远的部分.随机重启也是进行网页排序的PageRank算法[14]的基本思想.[18]用带重启动的随机游走(RWR,randomwalkwithrestart)来发现已知多媒体对象中各个媒体属性间的关联,而[21]则用RWR来发现情感与音乐属性的关联从而进行音乐推荐.类似地,

[17]也将PageRank算法的思想用到推荐系统中.

会造成原二部图信息的损失,因此如何计算σ(i,j)使其能最好地揭示出节点i,j在原二部图中的相似情况不仅是投影过程中的关键也是对节点正确排序的重要保证.本文选择利用结构相似的计算方法来求解σ以及CC.实验中选择下面四种结构相似计算方法:

σunnorm(i,j)=|Γi∩Γj|(1)　　　

Γ||Γ∩

σjaccard(i,j)=(2)　　　

Γj||Γi∪Γj||Γi∩

σcosine(i,j)=(3)　　　

ΓΓ|i|3|j|

Γ||Γ∩

σmin(i,j)=(4)　　　

min(|Γi|,|Γj|)

其中,Γi为投影前节点i的邻居节点集合.σ(i,j)可以分别由公式(1)(2)(3)(4)得到.图1(b),1(c)就是二部图1(a)根据公式(1)得到的两个投影.

这里的每个投影图就是项或者用户组成的关联图.相应地,可以得到关联图对应的矩阵CC,其中当i≠j时,CCi,j=σ

(i,j),且CCi,i=0.为了与RWR相结合,再对CC以列为单位

进行归一化得到随机矩阵C,C可以视为关联图的关联矩阵,

Ci,j表示节点i对于节点j的关联系数,即对节点j而言节点i

实际应用中,推荐算法不仅要求较高的预测准确度,还要具备良好的扩展性,但是目前的推荐算法都有其不足之处.例如,基于聚类的方法往往不能有效地覆盖所有的项或者用户,而基于图的方法虽然可以为所有的用户2项对产生相似排序,但往往消耗大量的空间资源,可扩展性较差,而且其推荐准确度也有待提高

[15,19]

的重要程度.这样,关联图中所有节点对间的关联程度都可以用C中相应的元素表示.可以看到CC是一个对称矩阵,而C则不再具有这个性质.

例如,图1(b)对应的用户关联矩阵C就可以表示为:

0.0.

CU=

0.0.0.

0125375250125125

0.20000.2000.2000.2000.200

0.2730.09100.2730.1820.182

0.2220.1110.33300.1110.222

0.0.0.0.16716733316700.167

0.0.0.0.0.0

.

基于上述分析,本文提出了基于二部图投影和对投影后得到的关联图中节点进行排序的BGPR推荐算法.下面,通过基于结构相似进行二部图投影和RWR进行节点排序的一个

5期　　　　　　　3.2　排序算法

刘　淇等:结合二部图投影与排序的协同过滤　　837

332028,0.331414,0.001391,0.001755),与前边的结果相符,

BGPR算法的目标是通过排序的方式估计用户与项之间此时可以发现I5最有可能被推荐给U6.

输入:表示用户与项之间关系的二部图G,待推荐对象Oq,参数c输出:对Oq的推荐序列

1.根据公式(1)(2)(3)或(4)得到G的一维投影图对应的关联图,若

Oq∈U,则投影得到关于项的关联图,若Oq∈I,则投影得到关于用户

的关系.BGPR用向量表示查询节点,向量中的每一维都代表关联图中的一个节点,其值则表示相应节点与该查询节点的亲和度.BGPR采用带重启动的随机游走(RWR)来预测一个节点(或向量)Y对查询节点(或向量)X的重要性或关联程度.考虑从节点向量X开始的随机游走,每走一步保证两件事情:首先,如果一个节点Z与节点P联系紧密,而X又是与P相关联的,则通过P,X与Z也会建立一定的联系.其次,由于X是通过间接的方式与Z建立联系的,所以相比较P与Z,X与P,X与Z的联系强度会有一定的"衰减

".

的关联图

2.令关联图对应的矩阵CC对角线的元素为0,再以列为单位将其归

一化,得到关联矩阵C

3.由(5)得到向量V′Oq,并对其归一化得到向量VOq4.t=0,初始化SOq=VOq

5.while(SOq不收敛‖t<MAX-LOOP)6.{

7.　SOq=(1-c)3C3SOq+c3VOq8.　t++9.}

10.SOq11.若q(j)Vqj)0,SOq(j)对应的项(用户)推

图1　用户与项组成的二部图(a),以及

它在用户维与项维的两个投影(b)(c)

Fig.1　Abipartitegraphaboutusersanditems(a),with

itstwoprojectionsonusers(b)(c荐给Oq,Oq图2　推荐算法BGPR流程

Fig.2　FlowchartofBGPRalgorithm

或者说,X游走到PPP

有联系的节点.,X重新走步,[2state概率SX(Y)表示从节点XY的概率.那么SX(Y)就表示了Y相对于X的亲密程度.

定义Oq为查询对象,它可以是一个用户或一个项,如果Oq是一个用户,BGPR算法要得到与它关系最紧密的项,而如果Oq是项,BGPR算法得到与它关系最紧密的用户.这里若关联图或关联矩阵C由k个节点组成,则Oq对应的stead2y2state概率向量Sq=(Sq(1),…,Sq(k))即为所求.定义归一化向量VOq是根据Oq在训练集中的记录而建立的节点向量,在归一化VOq之前向量V′oq第j维的元素对应于:

1　ifOqisuserandOqratedIj,or

V′Oqj

4　实　验

MovieLens

[3,9]

是一个进行电影推荐的网站,GroupLens

小组从中整理出了适用于各种推荐场景的一个标准数据集.

在本文使用的数据集中,对用户进行了处理,只考虑那些对超过20部电影打分的用户,总共包含943个用户(m=943)对

1,682部电影(n=1,682)的评分,共约100,000个评分.

实验中使用数据集的方法与[15,17,19]中类似:对于参数训练部分(主要是对参数c的测试),将整个数据集分成训练集与测试集两部分,而测试部分则使用五对数据集进行52交叉测试,每次用80%的评分数据做训练集20%的评分数据作为测试集.

4.1　评价标准

　　　ifOqisitemandUjratedOq

0　otherwise

本文采用DOA(degreeofagreement)[20]为标准对实验结

(5)

果进行评价.根据使用对象的不同将其扩展为用户的DOA

(U-DOA)和项的DOA(I-DOA),其思想是:

由3.1和3.2本文设计的推荐算法BGPR如图2所示.

在推荐算法BGPR中,可调参数c为随机游走重启动的概率,(12c)为衰减因子,用来衡量信息的衰减程度.实际应用中,平均情况下,t=20时,SOq即可收敛[17].

考虑一个简单的例子,如果根据结构相似公式(1)进行二部图投影然后对图1(a)中的用户U6做推荐预测.U6的节点向量Vu6=(0,0,0.5,0.5,0),运行BGPR算法,得到一个关于项的steady2state概率向量SU6=(0.002357,0.001176,0.496886,0.496674,0.002903).此时I5最有可能推荐给U6.作为验证,再对I5做用户推荐预测,则其节点向量VI5=(0.333,0,0.333,0.333,0,0),再次运行BGPR算法,得到一个关于用户的steady2state概率向量SI5=(0.331319,0.001089,0.

对于U-DOA,先定义NWui=n/(Lui∪Tui),其中n为所有项的个数,Lui为用户Ui在训练集中评价过的项集合,Tui为

Ui在测试集中评价的项集合.

check-orderUi(Ij,Ik)=

1,　if(predict-rankIj≥predict-rankIk)0,　otherwise

从而对于用户Ui,其DOA得分定义如下:

DOAUi=

(j∈TU,k∈NWU)

∑

check-order(Ij,Ik)

(6)

|TUi|3|NWUi|

I-DOA的定义与U-DOA类似,这里不再赘述.通过定

义可以看出,随机预测的DOA值大约为50%,而理想情况下

838　　　　　　小　型　微　型　计　算　机　系　统　　　　　　2010年

的DOA值为100%.并且,实验中以所有用户(项)的DOA取平均作为总体的效果评价.

∑DOAUi∑DOAIiUiIi

U-DOA或I-DOA=

|U||I|

4.2　

参数选择及实验结果

在PageRank算法中重启动概率c经

常取为0.15,而在实验中,通过各个方法对c在(0,1)之间变化时的表现情况可以发现,c越接近于1,BGPR算法的推荐效果越好.其实这一方面与所用的关联图的

图3　随着c的变化各个方法的表现[18]

半径有关,一方面

Fig.3　BGPRperformance

与数据的性质有关,

underdifferentc

首先,由表1、2可以发现在同一个数据集中,将二部图投影得到电影之间的关联图然后对电影排序(Movie-Rank)的推荐效果明显优于建立用户之间的关联图然后对用户排序(User-Rank)的结果,其实这与MovieLens数据集的性质有关.MovieLens数据集对用户进行了处理只保留了至少评价了20部电影的用户,以保证每个用户的兴趣都可以得到确切的反映,而数据集中的电影却没有经过相似处理.对用户的处理可以让一般的推荐算法防止"冷启动"问题但是BGPR算法采用了RWR做为距离评判标准,可以有效地防止"冷启动"问题.而且对用户的预处理使得BGPR构造的用户关联图过于稠密(数据显示用户关联图对应的用户关联矩阵中非零元素的比例在[0.922,0.934]区间,而此比例在项关联图中仅为[0.625,0.642]),从而降低了用户与用户间的区分度,造成了对用户排序(User-Rank).图4显示了电影度数的幂律分布情况,=0.8的幂律分布

λ

(p(k)～k2),M,即Movie.总之,R"冷启动"问题,而且根据实际RWR紧密融合,使得BGPR算法有巨大的实用价值.

表3　不同算法效果比较

AlgorithmMAXFCTPCACTOne2wayReturnL+

ItemRankKatz

()

DOA(%)

Differencewith()

在当前的MovieLens数据集中,项(用户)的相似度绝大部分比例依赖于项(用户)间的直接路径数.图3显示了随着c的变化,几种二部图投影方法对应的BGPR算法的表现.的实验中若无特殊说明,选择c=0.99.

表1　Movie-Table1　M-52crossvalidation

METHODIT2IT3SPLIT4SPLIT5MEANMovieUnnorm

-RankJaccardDOACosine(%)89.

90.90.57.90.90.12376889.90.91.29640289.90.90.09386788.90.90.88175389.90.90.093769Movie-Rank

表1、表2显示了不同的结构相似对应的Movie-Rank和User-Rank方法在进行52交叉测试时的表现.

表3显示了使用MovieLens作为数据集的不同推荐算法的效果比较,这些算法的具体细节和实现可以参见[15,17,19].这里BGPR算法选择基于Movie-Rank的Cosine结构相似(MR-Cosine)为代表与其他算法进行比较,其中的Item

Rank

[17]

84.84.84.84.72.87.87.85.07090408632376830+0.0220.03+0.01211.44+3.16+3.69+1.76与本文基于公式(1)的Movie-Rank实现方法类似.

表2　User-Rank52交叉测试结果

Table2　User-Rankperformanceon52foldcrossvalidation

User-Unnorm75.5281.1580.9979.9476.4078.80RankJaccard74.0680.7581.1180.5676.8678.67DOACosine74.3581.0481.6080.9477.3479.05(%)对于其中的每个算法,给出了其52交叉测试后的平均实验结果,以及与传统的MaxF算法的表现差异比较.MaxF算法简单地将项按被浏览次数进行降序排序,每次都将其没有评价过且排序最靠前的项推荐给给定用户[17].MaxF算法也是比较的基准算法.4.3　讨　论

在计算效率方面,给定关联矩阵C时,BGPR只要经过较

少次数的迭代就可在O(n2)或O(m2)时间里得到一次推荐,

而L+或者CT算法只能一次得到所有推荐,所以只能定时更新推荐而无法做到实时更新推荐.但BGPR算法的一个问题在于,如果关联矩阵C中有一个节点发生了更新,则整个关联矩阵都需要更新,图4　电影度数的幂律分布

这将消耗O(n2)或OFig.4　Power2lawdistribution

(m2)的时间,所以可以ofMovies′degree

选择定时更新关联矩阵

C而实时更新节点向量的方法,以得到更好的推荐效果.

5期　　　　　　　刘　淇等:结合二部图投影与排序的协同过滤　　839

最后是算法的空间复杂度和可扩展性.当基于项过滤对项进行排序时,关联矩阵C的大小与用户数无关,这是一个

很有用的性质.因为一般的应用中,用户数目比项的数目有更高的数量级[17],而且一般用户可能只对少数的一些项感兴趣,可以将用户的兴趣直接用链表的形式表现出来,从而节省巨大的空间资源.如果用ku表示每个用户平均感兴趣的项个数,那么此时算法的空间复杂度为O(n2+m3ku),即使用户数目不断增加,用户对项的兴趣也不断增加,BGPR算法都可以有效地应用.当有新的项时,BGPR和ItemRank只需要O(n)的空间消耗,其L+与CT等则需要O(m+n).而当增加一个新用户时ItemRank和BGPR需要O(ku)的空间,而L+,CT等算法却需要O(m+n)的空间,问题在于在一般的应用中mµnµku.而基于用户过滤的用户排序,虽然空间消耗可能要高于对项排序的方法,但仍然小于L+与CT等方法,这里不再赘述.

5　结　论

本文展示了一种基于二部图投影与排序相结合的协同过滤推荐算法BGPR,它可以预测每个用户可能喜欢的项,也可以将项推荐给那些可能喜欢它的用户.更重要的是B一个协同过滤的框架算法,案可以产生不同的推荐算法.R),"冷启动"问题而.通过在同一个数据集上与其它的一些优秀算法的比较证实了BGPR不仅有更高的推荐准确度,同时保持较低的时空复杂度,较好的可扩展性,而且可以适用于不同情况的针对海量数据的实际推荐应用中.

由结构相似得到的投影图可以用来描述原二部图所隐含的节点间的信息.但是这类相似计算方法是对称性的,认为σ(i,j)等于σ(j,i),即节点i,j视对方是同等重要的.其次,结构相似简单地视节点i,j的所有邻居节点对i,j的相似程度

Γi∩Γj,且ΓsµΓt,则显有相同的影响,然而,假设节点s,t∈

然邻居节点t应当比邻居结点s更能说明节点i,j相似.由于结构相似存在着以上种种缺点和不足,使其不能完全地反映原二部图所隐含的节点间的相似信息.为了更准确地挖掘原二部图的信息,寻找新的二部图投影方案将是未来工作的主要努力方向.

References:

[1]GedimiinasAdomavicus,AlexanderTuzhilin.Towardthenext

generationofrecommendersystems:asurveyofthestate2of2the2artandpossibleextensions[J].IEEETransactionsonKnowledgeandDataEngineering,June2005,17(6):7342749.

[2]LindenG,SmithB,http://recommendations:i2

tem2to2itemcollaborativefiltering[J].IEEEInternetComputing,2003,7(1):76280.

[3]MillerBN,AlbertI,LamSK,etal.MovieLensunplugged:ex2

perienceswithanoccasionallyconnectedrecommendersystem[C].ProceedingofInt′lConf.IntelligentUserInterfaces,Miami,USA:2003,2632266.

[4]ResnickP,IacovouN,SuchakM,etal.Grouplens:anopenar2

chitectureforcollaborativefilteringofnetnews[C].ProceedingoftheCSCWConference,ChapelHill,NC:1994,1752186.[5]KimJW,LeeBH,ShawMJ,etal.Applicationofdecision2tree

inductiontechniquestopersonalizedadvertisementsonInternetstorefronts[J].InternationalJournalofElectronicCommerce,2001,5(3):45262.

[6]BalabanovicM,ShohamY.Fab:content2based,collaborativerec2

ommendation[J].Comm.ACM,1997,40(3):66272.

[7]PazzaniM.Aframeworkforcollaborative,content2based,andde2

mographicfiltering[J].ArtificialIntelligenceRev.,Dec.1999,13:3932408.

[8]SouvikDebnath,NiloyGanguly,PabitraMitra.Featureweighting

incontentbasedrecommendationsystemusingsocialnetworkanal2ysis[C].ProceedingsofWWW,Beijing,China:April,2008,pages104121042.

[9]http://www.movielens.umn.edu.

[10]PavlovD,PennockD.Amaximumentropyapproachtocollabora2

tivefilteringindynamic,sparse,highdomains[C]http://rmationProcessingSystemsIPS′02),,2.

[11]reeseJD,panalysisofpredic2

sfor[C].ProceedingsofthethUinArtificialIntelligence,Madison:,252.[]D2Nowell,JonKleinberg.Thelink2predictionproblem

networks[J].JournaloftheAmericanSocietyforInfor2mationScienceandTechnology,2007,58:101921031.

[13]LeichtEA,PetterHolme,NewmanMEJ.Vertexsimilarityin

networks[J].PhysicalReviewE,2006,73:026120.

[14]BrinS,PageL.Theanatomyofalarge2scalehypertextualWeb

searchengine[J].ComputerNetworksandISDNSystems,1998,30(127):1072117.

[15]FoussF,PirotteA,SarensM.Random2walkcomputationofsimi2

laritiesbetweennodesofagraph,withapplicationtocollaborativerecommendation[J].IEEETransactionsonKnowledgeandDataEngineering,2007,19(3):3552369.

[16]LuhYen,MarcoSaerens,AminMantrach,etal.afamilyofdis2

similaritymeasuresbetweennodesgeneralizingbothshortest2pathandthecommute2timedistances[C].ProceedingsoftheACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining(KDD),LasVegas,USA:2008,7852793.[17]MarcoGori,AugustoPucol.Arandom2walkbasedscoringalgo2

rithmwithapplicationtorecommendersystemsforlarge2scalee2commerce[C].ProceedingsofWEBKDD′06,Philadelphia,USA:2006,1272146.

[18]PanJY,YangHJ,FaloutsosC,etal.Automaticmultimedia

cross2modalcorrelationdiscovery[C].ProceedingsofACMIntl.

(ConferenceonKnowledgeDiscoveryandDataMiningKDD′

04),SeattleUSA:2004,6532658.[19]FoussF,PirotteA,RendersJM,etal.Anovelwayofcomputing

dissimilaritiesbetweennodesofagraph,withapplicationtocollab2orativefiltering[C].ProceedingsofIEEE/WIC/ACMInterna2tionalJointConferenceonWebIntelligence,Compiegne,France:2005,5502556.

[20]SiegelS,CastellanJ.Nonparametricstatisticsforthebehavioral

sciences[M].NewYork,USA:McGraw2HillCollege,1988.[21]KuoFF,ChiangMF,ShanMK,etal.Emotion2basedmusic

recommendationbyassociationdiscoveryfromfilmmusic[C].Proceedingsofthe13thAnnualACMInternationalConferenceonMultimedia.Singapore:2005,5072510.

[22]SarkarP,MooreA.Atractableapproachtofindingclosesttrun2

cated2commute2timeneighborsinlargegraphs[C].ProceedingsofUAI.Vancouver,BC,Canada:2007.