一种融合用户偏好和信任-不信任关系的社会化推荐方法

虞胜杰，熊丽荣，王玲燕

(浙江工业大学 计算机科学与技术学院,杭州 310023)

1 引 言

个性化推荐是解决社会化网络中信息爆炸问题的一种有效手段.传统的基于协同过滤的推荐算法通过对用户上下文信息的学习和分析来预测用户的偏好和需求，但存在数据稀疏性问题[1,2]而影响推荐质量.

为了解决这个问题，一些模型[3-5]结合辅助数据如社交关系来挖掘数据中的隐含信息.相关研究发现[6,7]，在社交网络中，用户的决策通常受到好友的影响，并且用户更倾向于由信任用户产生的推荐.许多工作基于用户与信任用户偏好相似的假设展开：Deng等人[3]将信任关系作为筛选近邻的指标；Yang[4]等人提出一种基于用户信任度和社会相似度的协同过滤算法；Zhu[5]等人考虑用户交互、信任传递以及社区划分等方面对用户信任度的影响，提高了推荐准确度.因此，将信任信息结合到推荐算法中可以有效解决数据稀疏问题.

此外，在线网络的用户也可能建立不信任关系.比如Epinions允许用户根据评论的质量评估其他用户，并与他们形成信任或不信任关系；社交网络上的用户可以对不信任的用户拉黑、屏蔽.但是，很少有工作将不信任纳入到推荐当中：Victor等人[8]证明在基于内存的推荐系统中结合不信任信息是有益的；Forsati等人[9]首次不信任信息结合到基于矩阵分解的模型，并结合用户偏好进行推荐.以上研究表明，不信任信息可以在社会化推荐中发挥重要作用.

目前大部分基于信任的推荐算法通常利用信任网络中的直接信任来提升推荐准确率，而未考虑到直接信任关系也是稀疏的，并且也没有引入不信任信息.本文提出的信任模型TDtrust根据信任产生的多方面性，从全局以及局部两个刻面分析信任网络中用户间的信任关系，增加信任数据的密度，有效缓解数据稀疏问题.同时，利用不信任信息对信任网络进行调节，帮助过滤信任传播中“错误的推论”[8,10].最后将该信任模型结合联合概率矩阵分解[11]方法(UPMF)设计出本文的推荐算法TDRec.该算法结合社交网络用户的评分以及信任两部分数据进行评分预测.本文在Epinions数据集上的实验证明本文提出的算法相比于同类信任增强的矩阵分解算法推荐效果更优.

本文主要有以下两个贡献：

1)本文提出结合了信任和不信任信息的信任计算模型TDtrust.信任方面综合考虑评分相似性、节点中心性等潜在因素，并基于信任传播机制，增加信任数据的密度；利用不信任信息对信任网络进行调节，提高信任数据的可靠性.

2)依据社会平衡理论，提出不信任权重计算方法，帮助过滤信任传播中错误的推论.

本文第2章阐述融合信任、不信任信息的社会化推荐相关工作.第3章给出符号定义.第4章阐述本文提出的融合用户偏好和信任-不信任关系的信任模型，并给出基于联合概率矩阵分解的推荐算法和推荐框架.第5章给出实验结果与分析.第6章总结全文并探讨未来的研究方向.

2 相关工作

随着信息技术的发展，社会化网络中信息过载问题日益严重，个性化推荐是解决该问题的一种有效方法.传统的基于协同过滤的推荐算法主要利用用户偏好信息，但备受数据稀疏问题的影响.为了提高推荐准确率，同时增强推荐结果的可信度，越来越多的研究人员[12-17]将信任信息引入推荐算法当中.

Jamali和Ester提出的TrustWalker算法[12]通过在信任网络中随机游走选择相似物品的评分从而避免在信任网络中游走太深，而在相同游走深度下TrustWalker又能够在信任网络更大范围内来查找相似物品的评分，提高了推荐的准确性和覆盖率.但Jamali等人只在二值信任网络中游走，每个信任用户被选择的概率是相同的，缺乏区分性.Wang[13]等人结合用户偏好和信任相似度，加权得到用户间的信任度量. Davoudi等人[14]构建的信任模型同时考虑了用户相似性、节点中心性和社会关系.潘等人[15]在SocialMF的基础上，提出基于信任关系隐含相似度的推荐算法.杜等人[16]研究信任用户间接影响用户偏好和直接影响用户评分两种不同机制，提出基于用户间信任关系融合建模的概率矩阵分解模型TPMF.王等人[17]提出的TM-PMF挖掘了用户评分过程中潜在的信任关系，增加了信任数据密度.但是，上述研究都忽略了用户社交关系中的不信任信息.

最近，一些研究工作[8-10,18-20]尝试将不信任关系纳入到推荐过程.Victor等人[8]探究了不信任信息在推荐过程中可能的角色：不信任作为扭转信任权重偏差的指标，不信任作为过滤器，不信任作为信任网的调试器.并通过实验说明不应该在推荐过程中使用不信任来扭转信任权重偏差，使用不信任作为信任网的过滤器或调试器是可以探索的方向.Rafailidis等人[18]最早将信任和不信任关系引入Top-N推荐任务中，设计了学习排名模型LTRW，提出一种加权策略来衡量用户的朋友或敌人对物品选择的影响.Lee等人[19]利用信任和不信任信息选择最近邻居，并采用混合推荐方法进行推荐.Ma等人[20]从信任的个人、人际关系和非个人方面获得一系列相关特征，通过这些特征训练逻辑回归模型，预测用户信任和不信任值，并应用到信任感知推荐算法中.实验结果表明，同时利用信任和不信任信息能有效提高推荐准确度.

相比于基于内存的协同过滤，基于模型的协同过滤方法在数据稀疏的情况下推荐效果更优，且具有良好的可扩展性.其中UPMF可以结合多种上下文信息(评分、信任、地点等)，实现更优的推荐效果.Ma等人[11]提出了一种基于概率矩阵分解的因子分析方法SoRec，联合用户信任数据和评分记录进行推荐.Davoudi[21]提出了一种结合相似度以及节点重要性的信任计算模型，同时采用联合概率矩阵分解来进行推荐.文中的信任模型主要分为两部分：相似信任、节点中心性.其中相似信任采用向量相似度(VSS)计算，节点中心性则是参考用户在社交网络中的入度值，两者结合作为用户的信任值.但Ma和Davoudi等人只利用用户间直接信任信息，没有进一步挖掘潜在的间接信任关系.Wang[22]提出的TUPMFRec虽然从多方面刻画了信任关系，并结合UPMF进行推荐，但未利用社交关系中的不信任信息.

与上述工作相比，本文提出的信任模型综合考虑信任网络中用户间直接信任值、用户数量以及用户间的相似度，并结合信任的传播，增加信任数据的密度，有效缓解信任数据稀疏问题.同时利用不信任信息对信任网络进行调节，提高信任数据的可靠性.在此基础上，融合联合概率矩阵分解方法提高推荐的精度.

3 符号定义

定义用户集合UM={u1,u2,…,un}，n为用户的数量，定义项目集合VM={v1,v2,…,vm}，m为项目的数量.在评分矩阵R=[rij]n×m中，rij表示用户i对项目j的评分，其中i=1…n，j=1…m.在矩阵分解方法中，评分矩阵R通过R=UTV得到，信任矩阵S通过S=UTT得到.考虑到用户间信任和不信任关系，我们定义有向权重图G(ν,ε)来表示用户的社交关系网络,其中ν表示用户节点，ε表示连接用户节点的边，其中“+”表示信任关系，“-”表示不信任关系.

表1给出文中相关的符号定义.

4 推荐算法TDRec

4.1 信任模型TDtrust

在社交网络中，用户间存在着信任和不信任关系.现有文献[3-5，11-17，22]提出的信任模型在评估用户间关系时，存在以下问题：

1)大多数文献[3-5，11]计算全局信任均只考虑全局网络中所有用户对目标用户的信任评价值，过于片面.

2)计算局部信任选择路径时,大多选取最短路径[4,5]，往往忽略了对评分预测有参考价值的用户反馈.

3)缺乏对不信任信息的有效应用方法.

表1 符号说明Table 1 Explanation of symbols

本文综合考虑信任网络中所有用户对目标用户的信任评价值、用户数量以及用户间的相似度，全面考虑影响全局信任的潜在因素；在计算局部信任选择路径时，注重对评分预测最有参考价值的用户反馈，选取最有效路径[23]进行间接信任值计算.同时，利用不信任信息对信任网络进行调节，选择符合社会平衡理论的稳定的路径，利用Jaccard系数的变体计算用户间的不信任权重，对于不信任权重大于设定阈值的用户，否定其局部信任度量的结果.

4.1.1 全局信任

关于全局信任计算，本文主要考虑以下3点，大多数文献[3-5，11]都只考虑了第1点：

1)用户的全局信任跟全局网络中所有用户对该用户的信任评价值有关；

2)有关研究[24]表明，社交网络中的“大V”更能影响其他用户的选择，而这些个人影响力大的用户通常有较多的关注者.即，用户的全局信任跟全局网络中对该用户有信任评价的用户数有关.

3)基于协同过滤的推荐算法往往认为兴趣爱好一致的用户相似度较高.即，用户的全局信任与用户间相似度有关.

用户全局信任值计算公式[25]如式(1)所示:

(1)

其中|F+(uj)|表示信任网络中信任用户uj的用户数量，dtkj表示用户uk与用户uj间的直接信任度，Simik表示用户ui与uk之间的相似度.

4.1.2 局部信任

1)直接信任

若用户间存在直接信任，则用直接信任评价值dtij进行度量.

2)间接信任

若用户间不存在直接信任评价值，则利用信任传递性度量用户间间接信任评价值idtij.

本文根据“六度空间”理论，在计算间接信任时设置最大路径长度Max_Hop<=6，依据路径长度L设计衰减度函数，如公式(2)所示:

(2)

信任传播会产生多条路径，本文选择最有效路径[19]进行间接信任值计算.用户间间接信任值计算[25]如公式(3)所示:

(3)

其中Ui、Uj分别表示源、目标用户节点，Uk表示某条路径Pathi中第k个用户节点，TUk-1→Uk表示用户节点Uk-1对用户节点Uk的信任值.

最终间接信任值计算[25]如公式(4)所示:

(4)

综上所述，用户间最终信任值计算公式[25]如式(5)所示:

sij=αgtij+(1-α)ltij

(5)

其中ltij表示局部信任值，若存在直接信任，ltij=dtij，否则ltij=idtij.参数α用于控制衡量全局与局部信任所占的比重.

4.1.3 不信任的调节

在信任网络中，如果用户A完全信任用户B，B完全信任C，由信任传播可以推出用户A信任用户C；但是此信任网络中，如果用户A与C之间存在直接不信任关系，那么我们就需要否定前面信任传播的结果.

本文利用不信任信息对信任网络进行调节，帮助过滤类似上述的“错误的推论”[8,10]，提高信任数据的可靠性.

如图1所示的信任网络中,“+”表示信任，“-”表示不信任，用户节点A和C之间存在间接信任和间接不信任关系，其中B、D、E是不同传播路径的中间用户节点.我们的目标是衡量两个节点间的不信任权重.

图1 信任-不信任传播Fig.1 Trust-distrust propagation

关于A、B、C之间的链路关系我们可以根据社会平衡理论[26,27]确定.社会平衡的基本原则[28]是：“我的朋友的朋友是我的朋友，我的敌人的朋友是我的敌人，我的敌人的敌人是我的朋友”.在社交网络中，3个相互连接的节点有4种可能的情况，如图2所示.根据社会平衡理论中三角形的平衡，(1)、(2)在结构上是稳定的，(3)、(4)在结构上是不稳定的.如果所有3个节点组成的三角形在结构上都是稳定的，则由3个以上节点组成的网络在结构上是平衡的[29].本文选择符合社会平衡理论的稳定路径，即A信任B并且B信任C、A不信任B并且B信任C的情况，利用Jaccard系数的变体[19]计算用户间的不信任权重.

图2 社交网络中的4个基本的无向三元组[29]Fig.2 Four basic undirected triples in social network

考虑到随着传播路径的增加，计算复杂程度剧增，因此本文选择计算信任和不信任传播的最大路径长度为2[30，31].用户ui和用户uj间的不信任权重Wij的计算如公式(6)所示:

(6)

若Wij大于设定阈值η，则本文认为用户ui与用户uj是不信任的，关于用户ui和用户uj的局部信任度量是错误的推论，应当给予否定，此时sij=αgtij.

4.2 结合UPMF的推荐算法

相比于传统的协同过滤算法，矩阵分解算法从技术上降低数据稀疏性带来的影响.结合上述提出的信任模型TDtrust，本文提出基于UPMF的社会化推荐算法TDRec.

TDRec模型假设:

(7)

(8)

(9)

其中I表示单位矩阵，N(x|μ,σ2)表示均值为μ，方差为σ2的概率密度函数.

评分矩阵R的条件概率分布如公式(10)所示:

(10)

同理，信任矩阵S的条件概率分布如公式(11)所示:

(11)

根据贝叶斯规则推导出后验分布函数:

(12)

最大化上述对数后验概率等价于最小化公式(13)：

(13)

(14)

(15)

(16)

4.3 完整推荐框架

本文完整推荐框架如图3所示.

图3 推荐框架Fig.3 Recommendation framework

1)从数据库中得到评分、信任和不信任信息；

2)利用信任数据计算用户间综合信任值，利用不信任信息得到不信任权重Wij，若Wij大于设定阈值，调节其信任值sij=αgtij；

3)联合评分矩阵和信任矩阵分解得到用户潜在特征向量和项目潜在特征向量，根据R=UTV得到预测评分值.

5 实验与结果分析

5.1 实验数据

本文采用Epinions数据集.评分数据包括用户ID、项目ID和评分值，信任数据包括用户ID、信任用户ID和信任值(默认为1)，不信任数据包括用户ID、不信任用户ID和不信任值(默认为-1).Epinions公开的数据集中包含132000个用户，841372条用户关系(包括717667条信任关系、123705条不信任关系)和13668320条评分数据).为了降低模型TDtrust的训练时间，我们需要对数据集进行处理.从原始数据集中随机选取数据并不能构成关系网络，不能很好地验证信任和不信任关系对推荐准确度的影响.本文对信任用户进行游走，得到信任网络，选取对应用户的评分数据和不信任数据进行实验.处理后的数据集包含23107个用户和111778条用户关系(包括67118条信任关系、44660条不信任关系和3703078条评分数据).

5.2 评价指标

本文采用平均绝对误差(Mean Absolute Error,MAE)和均方根误差(Root Mean Square error,RMSE)作为实验评估标准.MAE和RMSE表示预测值和真实值的差距，MAE和RMSE值越小推荐效果越好.MAE、RMSE计算公式如公式(17)、公式(18)所示:

(17)

(18)

其中n为测试集大小，p为预测评分，q为真实评分.

5.3 对比算法

为了证明TDRec算法的有效性，本文选取了以下对比算法进行实验：

PMF[32]：基于概率模型的矩阵分解方法，只利用了评分信息.

User-Based[33]：传统的基于用户相似度的协同过滤方法.

Item-Based[33]：传统的基于项目相似度的协同过滤方法.

SoRec[11]：同时利用评分信息和社交关系信息进行矩阵分解的方法.

VSS[21]：提出了结合相似度以及节点重要性的信任计算模型，结合UPMF方法进行推荐.

TUPMFRec[22]：提出的信任模型多方面考虑信任关系，但是没有利用不信任信息，结合UPMF方法进行推荐.

5.4 实验分析

5.4.1 参数α的评估

当用户间存在直接信任度时，为了得到更准确的全局信任值所占比重，实验1对此时的权重参数α取不同值进行实验.实验中α取值为0.1，0.3，0.5，0.7，0.9，本文在不同比例训练集中进行实验，实验结果如图4所示.

由图4可知，随着α的逐渐增大，MAE和RMSE呈增大趋势，故在本实验中α取值为0.1时效果最好.这也符合我们的认知，当用户ui对uj存在直接信任时，计算ui对uj的信任评价值以ui对uj的直接信任为主，与uj在整个社会化网络中的全局信任度关系不大.

图4 参数α的影响(MAE和RMSE)Fig.4 Impact of parameter α(MAE and RMSE)

5.4.2 信任模型有效性

为了验证本文提出的信任模型的有效性，实验2将TDtrust模型分别应用于两种结合信任的基于用户的协同过滤算法[33,34]以及两种基于TrustWalker思想的算法TrustWalker[12]、RelevantTrustWalker[35].将未利用不信任调节的算法分别为命名为[33]*、[34]*、TW*、 RTW*，将利用不信任调节的算法命名为[33]*D、[34]*D、TW*D、RTW*D.本文分别在不同大小训练集中进行实验，图5展示的是训练集大小为70%时信任模型结合算法效果比较.同时再将结合信任模型的联合概率矩阵分解算法TDRec与另外3种矩阵分解算法PMF、SoRec、TUPMFRec进行分析比较，实验结果如表2、表3所示.

图5 信任模型结合算法效果比较(MAE和RMSE)Fig.5 Comparison of trust model effectiveness with algorithms(MAE and RMSE)

由图5可以看出，结合了本文信任模型的协同过滤算法相较于原始的算法，推荐准确率明显提高；并且结合了本文信任模型的两种TrusterWalker算法相比于原始的算法，推荐准确度有一定提升.因此，本文提出的信任模型可以有效推进协同过滤等推荐算法，提高评分预测准确度.

表2 4种矩阵分解算法效果比较(MAE)Table 2 Comparison of four matrix decomposition algorithms(MAE)

表3 4种矩阵分解算法效果比较(RMSE)Table 3 Comparison of four matrix decomposition algorithms(RMSE)

根据表2、表3可得，随着训练集的增大，4种算法的MAE和RMSE都逐渐减少.同时结合本文信任模型的联合概率矩阵分解算法TDRec在不同训练集大小下的MAE和RMSE都要小于其余3种算法，特别是在数据稀疏的情形下，TDRec算法推荐效果也相对较好.从而验证了本文的信任模型可以有效的应用于矩阵分解类算法当中，提高其算法的评分预测准确度.

5.4.3 算法对比

实验3选取传统协同过滤算法User-Based、Item-Based和4个联合信任的矩阵分解算法PMF、SoRec、VSS、TUPMFRec与本文提出的TDRec进行分析比较.

图6 TDRec与其他算法比较(MAE和RMSE)Fig.6 Comparison between TDRec and other algorithms (MAE and RMSE)

根据图6可以看出结合本文提出的信任模型的联合概率矩阵分解算法TDRec推荐效果优于传统的协同过滤算法和同类信任增强的矩阵分解算法.并且在不同稀疏程度的数据集下，TDRec均能得到较好的推荐效果.

综合上述实验，根据实验2可知，本文提出的信任模型在传统协同过滤、TrustWalker、矩阵分解3类算法中均得到了较好的推荐效果，从而证明了该模型的有效性.同时根据实验3，我们可以很明显的看出，结合本文提出的信任模型的联合概率矩阵分解算法TDRec，其推荐效果要优于User-Based、Item-Based 、PMF、SoRec、VSS、TUPMFRec，说明本文的信任模型在结合UPMF时得到的推荐效果是最佳的.

6 总结与展望

本文综合考虑信任和不信任信息，提出信任计算模型TDtrust.考虑到信任产生的多源性，本文从全局和局部两个刻面挖掘信任网络中用户间的信任关系，同时利用不信任信息对信任网络进行调节，帮助过滤信任传播中“错误的推论”，提高推荐的准确性.最终将通过模型得到的信任数据应用于基于UPMF的社会化推荐算法TDRec，得到较好的评分预测准确度.在Epinions数据集上的实验证明本文提出的算法相比于传统协同过滤推荐算法和同类信任增强的矩阵分解算法推荐效果更优.考虑到用户间会建立和取消信任和不信任关系，在未来的工作中我们会探索适应不断变化的社交关系的信任模型，并应用到社会化推荐算法中去.