结合时间权重与信任关系的协同范文

《计算机应用研究杂志》2015年第五期

1本文算法

1.1问题建模社会化标注和社会化网络服务（SNS，如Facebook,Twitter等）体现了Web2.0的分享特点，这种开放、共享的模式为个性化搜索和推荐提供了一个高效的获取用户模型的原始数据来源。本文主要利用社会化标注和社会化网络服务中的好友信息来进行个性化的推荐，所以，我们首先对这两大类数据源进行形式化的描述。对于m个用户的集合可以表示为U={u1,u2,…,um}，n个资源的集合可表示为R={r1,r2,…,rn}、p个标签的集合可表示为S={s1,s2,…,sp}。图1给出了当前已达成共识的对于社会化标注的数据模型。由于用户在不同时间对资源的标注，体现出了用户兴趣的变化。因此，考虑到时间维度，则社会化标注的数据模型可形式化为F=(U,S,R,T).定义在F上的关系F{u,r,s:uU,rR,sS,tT}为标注关系集合，表示用户u在t时刻使用标签s标注资源r。对于好友信息，则可形式化描述为G=(U,U).定义在G上的关系{,:,}1212GuuuUuU为好友关系集合，表示用户u1和u2是好友关系。由于用户关注好友的时间的先后并不体现用户对于好友的关注程度。所以，在此，我们不对用户关注好友的时间信息进行建模。利用这些数据源，我们通过一系列的挖掘算法，可得出用户的兴趣相似度和用户的熟悉相似度，并利用这两个相似度综合为用户产生推荐。其中，两个相似度都可形式化描述为关系图G(V,E)，其中V为用户节点构成的集合，即V=U；E为用户关系构成的边集合。

1.2基于时间权重的用户兴趣相似度由于用户对资源的偏好可以通过标签刻画，那么用户ui对资源rj的偏好可以通过用户ui对标注在资源rj上的标签集T(ui,rj)的偏好表示。基于此，本节首先构建用户对资源的偏好矩阵，然后在此基础上计算基于时间权重的用户相似度。

1.2.1用户对资源的兴趣剖面一般来说，一个标签被某一用户标注的次数越多，越能说明该标签对于该用户的重要程度越高。因此定义用户ui对标签tk的偏好如下。

1.2.2基于时间权重的用户兴趣相似度计算传统的协同过滤推荐算法忽略了时间对用户兴趣变化的影响，从而在一定程度上影响预测的准确性。本节利用2.2节得到的用户-资源矩阵，综合考虑从用户标注资源的时间方面计算用户之间的相似度。其基本思想是，用户对最近标注的资源应该有较大的兴趣权重，而对过去标注的应该有较小的时间权重。因此，定义用户ui对用户uj的相似度为：

1.3基于信任关系的用户熟悉相似度在2.1节构建用户信任关系图后，我们首先定义一级好友与二级好友：定义1.(一级好友)用户信任关系网络中直接相连的两个用户互称为一级好友。定义2.(二级好友)用户信任关系网络中拥有共同的一级好友的用户互称为二级好友。那么用户ui与一级好友uj的熟悉相似度定义为两个用户之间边的权重，即：如图2所有为用户信任关系网络的一个子图，可以看出用户A的一级好友为{B,D,E,F,G},二级好友为{C,H,I}。此外，由于用户A的二级好友C同时与用户A的一级好友B和D连接，因此用户A与用户C的熟悉相似度时需进行两次计算，首先通过用户B计算的得到的用户A与用户C的相似度为simtrust(A,C)=0.65×0.35=0.2275，而通过用户D计算得到的用户A与C的相似度为simtrust(A,C)=0.6×0.8=0.48，取二者较大值作为用户A与用户C的相似度，即simtrust(A,C)=0.48。

1.4加权的用户相似度在得到用户基于时间权重的兴趣相似度和基于信任关系的熟悉相似度后，我们通过设定权重α对两种相似度进行线性组合，得到最终的用户相似度公式。

1.5产生推荐在为目标用户进行预测时，我们仍然考虑时间信息对预测值的影响，因为一般来说，用户现在的行为应该和用户最近的行为关系更大。

2实验和分析

2.1数据集及预处理我们的实验数据为Last.fm上的数据集。在初始实验数据中，共计2690个用户、4460个艺术家、8482个标签，其中每个用户至少对20个艺术家进行了标注，每个艺术家至少被20个用户标注。在实验中，艺术家被当做资源建模。由于数据集中用户使用标签标注艺术家都有时间戳标识，因此我们将数据集中每个用户的记录按时间由高到低排序，取前20%的记录作为测试数据，后80%的记录作为训练数据。本文实验的对比算法有：(1)传统的基于用户的协同过滤推荐算法(rCF)；(2)基于标签的协同过滤推荐算法(Tag-basedCF)，该算法与本文算法的唯一不同之处在于不考虑用户的信任关系，即在计算用户相似度时，α=1的情况;(3)文献[18]基于信任网络的推荐算法ITRAS。试验度量方法本文使用平均绝对误差MAE作为评判度量，用来评估推荐算法预测的资源评分与用户实际对资源的评分的偏差程度。其计算公式如下：Rec(u,i)为推荐系统为用户u预测的资源i的偏好值。ru,i为用户u对资源i的实际偏好值，这里我们将ru,i取为1。testsetu为测试集中为用户u预测的资源数。MAE越低，表示推荐系统的预测精度越高。覆盖率(Coverage)可以描述一个推荐系统对物品长尾的发掘能力。本文使用指标基尼系数(GiniIndex)统计资源在推荐列表中出现次数的分布来描述推荐算法挖掘长尾的能力。如果这个分布比较平，那么说明推荐系统的覆盖率较高，而如果这个分布较陡峭，说明推荐系统的覆盖率较低。公式如下。由于用户的兴趣是广泛的，推荐列表需要能够覆盖用户不同的兴趣领域，因此我们使用多样性指标(Diversity)描述推荐列表中资源的多样性。其中，s(i,j)表示资源i与资源j的相似度，R(u)为用户u的推荐列表，Diversity的值越高，说明推荐的资源具有更高的多样性。

2.2实验结果和分析

2.2.1时间衰减因子λ对MAE的影响λ作为时间衰减因子在公式(5)中起着非常重要的地位，如果λ取值不当，会造成时间权重ftime出现过大或者过小的值，影响推荐的精度。如图3所示为不同取值的λ计算得到的MAE值，可以看出，λ在取值较小时，MAE下降速度很快，但当λ取值较大后，MAE呈现缓慢增长的趋势，因此λ取较小值可以使推荐精度更高，在本文中λ=0.3时MAE取到最优值。

2.2.2α对MAE的影响由公式(9)可知，α=1为只结合时间得到的用户相似度；而α=0为只结合社交信任关系得到的用户相似度，而0,1则综合考虑了结合时间和信任关系信息加权得到的用户相似度，以α为变量，计算出相应的MAE值，实验结果如图4所示。从图中可以看出，当α=0.6时，推荐效果最佳，MAE值最小，也说明综合时间权重与信任关系的推荐效果比只考虑时间权重和信任关系的推荐效果都要好。

2.2.3β对MAE的影响图5显示的是在为目标用户进行预测时，时间衰减因子β对MAE的影响，可以看出，β=0时为不考虑时间对预测结果的影响的情况，此时MAE取值较大；β=0.2时，MAE达到最小。

2.2.4几种算法的推荐效果本文以邻居个数为变量，几种算法的推荐效果如图6所示，图6(a)为四种推荐算法的MAE值对比，可以看出，在邻居取值较小时，ITRAS算法具有最好的推荐效果，其MAE值为0.652；但随着邻居个数的增加，ITRAS算法的推荐效果越来越差，而其它三种推荐算法的MAE值均呈现先下降后上升的趋势，其中本文算法TTCF在邻居个数大于30后与其它算法相比，推荐效果一直处于较高的优势，且在邻居个数为60时MAE值达到最优，为0.635。图6(b)所示为四种推荐算法在覆盖率指标上的对比，而覆盖率反应的是推荐算法挖掘长尾的能力。可以看出，几种推荐算法随着邻居个数的增加，其覆盖率都呈现上升的趋势，其中传统协同过滤推荐算法CF的覆盖率变化较大，而其它三种推荐算法变化较均匀，本文算法TTCF一直处于较高的覆盖率，也说明本文算法具有较强的挖掘长尾的能力。图6(c)所示为四种推荐算法在多样性指标上的对比，可以看出，随着邻居个数增加，传统协同过滤推荐算法CF变化较为明显，成逐渐上升的趋势，而其它三种推荐算法基本趋于稳定状态，只在很小的范围内变化，且可以看出，本文推荐算法具有较高的多样性。

3结束语

时间作为一种动态信息，可以体现用户的兴趣变化；而社交行为可以反映用户之间的信任和兴趣信息，本文将二者结合起来，并融入到基于标签的推荐算法中，提出一种结合时间和信任关系的协同过滤推荐算法。考虑利用标签的流行度刻画用户对资源的偏好，在计算用户相似度时，同时考虑用户行为的时间因素与好友信任关系信息，且在信任关系中，同时考虑一级好友与二级好友，最后结合用户相似度与时间衰减项实现推荐，并通过实验验证了本文算法的有效性，可以较好的提高推荐精度。

作者：赵海燕 侯景德 陈庆奎 单位：上海理工大学 光电信息与计算机工程学院 上海现代光学系统重点实验室