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

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.0 …… 此处隐藏：3669字，全部文档内容请下载后查看。喜欢就下载吧 ……