结合用户行为信息和信任传递的推荐算法

张邦佐，王佳同，孙 玮，乔书玉，冯国忠，孙小新

(东北师范大学信息科学与技术学院，吉林 长春 130117)

结合用户行为信息和信任传递的推荐算法

张邦佐，王佳同，孙 玮，乔书玉，冯国忠，孙小新

(东北师范大学信息科学与技术学院，吉林 长春 130117)

通过用户行为信息并结合信任传递推断用户隐式信任关系，提出了基于矩阵分解的PTtrustSVD算法，并在Filmtrust数据集上进行了实验.结果表明，加入隐式信任关系优于仅使用显式信任关系的推荐方法，证明了隐式信任关系对于改进推荐系统性能的有效性.

推荐系统；隐式信任；信任传递

0 引言

20世纪90年代中期，为了有效地解决大数据时代所面临的信息过载问题，推荐系统[1]便应运而生.推荐系统使用的主流方法是协同过滤技术，它分为基于记忆和基于模型的协同过滤：基于记忆的方法是假设用户过去的历史可以很好地代表用户的兴趣[2]；而基于模型的方法却是假定推荐来自某一模型，通过数据训练来确定.这些方法不考虑用户之间可能存在的社交关系，但在现实世界中用户可以从朋友处得到更好的建议.随着社交网络的出现，信任关系作为现实世界人际关系在社交网络中的反映，表达了用户对其他用户观点的认可程度，同时也成为优化推荐结果的有力工具[3].研究显示，相比于有共同爱好的陌生人的在线推荐，目标用户更倾向于选择他们信任的朋友的推荐[2].信任关系在大多数的社交网络中可以直接通过好友关注等方式获得，这些信任关系称为显式信任.在大部分社交网站中，用户对的数量远远大于显式信任的数量，因此显式信任是十分稀疏的.但是在一些电子商务网站上，信任关系并没有明显的体现，往往需要通过相似的用户行为来推测，比如用户评分相同或评论内容相近，即隐式信任关系.

目前，基于用户社交信任关系的推荐方法是推荐系统中的研究热点，2015年G.Guo等[4]提出了一种基于用户信任和评分项目的矩阵分解技术，在SVD++算法[5]基础上，扩展了隐式信任关系，将显式和隐式信任关系加入到推荐方法中.对于兴趣推荐来说，信任关系比朋友关系更有价值[6].为了更好地发现隐式信任关系，人们将心理学中的两个著名理论结构平衡理论和社会地位理论[7-9]推广到社交网络中.结构平衡理论基于“朋友的朋友是朋友”、“敌人的敌人是朋友”等原则.在社会地位理论中，正向边(x，y)意味着x有比y更高的地位，反向边(x，y)意味着x比y的地位更低.结构平衡理论和社会地位理论可以有效地指导我们利用用户行为在社交网络中推断用户之间的关系，同时社会地位理论表明社会地位是具有传递性.

基于心理学的结构平衡理论和社会地位理论，本文将信任传递性加入到隐式信任关系推断中，同时将显式信任关系与隐式信任关系相结合，进一步扩展隐式信任关系，大大增加了信任关系的数量，从而缓解了信任关系稀疏的问题.

1 结合用户行为信息和信任传递的推荐算法PTtrustSVD

1.1 信任的定义

在社交网络中，信任一般是指在用户交互过程中，一个人对另一个人的信念和预期.在推荐系统中主要关注2个用户对于相同物品的喜好程度.在Filmtrust数据集中，用户之间会根据相似的电影喜好来添加信任的用户.G.Guo等[10]总结了信任关系具有不对称性、传递性、动态性、上下文依赖性等性质.

1.2 信任的测量

在大多数情况下，用户在网络上参与一些评论、评分等用户行为的时候，基本上都会有一个共同的背景.比如Filmtrust注册的用户会给出他们相应的电影评分，这些电影就是一个共同的大背景，只是每个人喜好不同、评分不同，自然会影响着互相之间的信任.M.Papagelis等[11]提出了利用皮尔森相关系数来衡量2个用户之间信任程度，从而表明2个用户之间的兴趣相似程度，计算公式为

(1)

(2)

其中n是2个用户之间共同的评分个数.我们设定一个相似度阈值θ，超过阈值的可以作为信任关系，计算公式为

(3)

其中tu，v是用户u与用户v的隐式信任关系.只有能够达到阈值的值才能够判定为信任关系，计算公式为

PtrustSet={(u，v)|tu，v≥θ；u，v∈U}.

(4)

公式(4)能够通过用户的评分行为清楚地找到用户之间隐式的信任关系.

1.3 信任传递

信任传递是建立在结构平衡理论和社会地位理论之上的，它反映的是信任主体根据一些相关联的实体或信息对信任客体进行的间接推断，这些推断往往不能直观判断，而是需要信任主体对其他信任客体产生的信任关系互相关联得到，这种认知的过程称为信任传递.

从社会学和心理学角度的社会地位理论来看，用户u和w的地位关系可以通过第三方共同关系v来建立.例如，在u，v关系中，u地位低于v；在v对w关系中，v地位低于w；通过判断得到u相对于w有一个较低的地位.从而可以将社会地位理论拓展到信任传递中来[13]，即如果u信任v，v信任w，那么可以推测u对w也具有信任关系，表示为：

(5)

这样就得到了一个新的隐式信任数据集，即

TtrustSet={(u，C)|u→B，B→C⟹u→C；u，B，C∈U}.

(6)

根据六度分隔理论[14]，在同一个社交网络中，任意2个用户想要找到对方，只需要有限次的关系传播.当然如果2个距离较远的用户要产生联系，传播距离就会较长，相应的影响也就会越低，本文只考虑一跳传播.

1.4 trustSVD

(7)

但是针对用户的评分，每个人衡量事物的标准不一样，有的人只要觉得一般喜欢，可能就会给出高分，而有的人比较苛刻很少给出高分.那么基于这种情况，在SVD方法的基础上，SVD++加入了基准偏移量bui和用户评分隐式反馈信息yi，计算公式为

(8)

其中:Iu是用户u评分过的项目集；buj由评分偏差μ、用户u与其他用户之间的评分平均值偏差bu以及项目j和其他项目的评分平均值偏差bi共同组成，即buj=μ+bu+bj；yi提供了用户隐式反馈信息，是用户爱好的额外指示.

G.Guo等[4]在SVD++的基础上加入了显式信任信息，提出了trustSVD，通过利用用户之间的信任影响，来探索更加精确的预测评分，其评分模型计算公式为

(9)

其中Tu为用户之间的信任集合.

1.5 PTtrustSVD

通过用户行为信息和信任传递得出的隐式信任关系公式(见(4)和(5))，结合trustSVD算法得出的新算法，这里称作PTtrustSVD，评分预测函数为

(10)

本文基于Guo G.等[4]的trustSVD算法较活跃、频繁的用户或较流行的物品实施相对小的惩罚，对于冷启动的用户或物品实施比较大的惩罚，最终求解的损失函数为

(11)

其中exT是显式信任相关变量，imT是隐式信任相关变量，最后通过梯度下降法对损失函数进行求解.

2 结果与讨论

2.1 数据集

Filmtrust是一个对电影进行评分和评论的社交网站.为了保护用户的隐私，每个用户都进行了数字编号，包括了1 508名用户对2 071部电影进行的35 497个评分.评分范围为0～4分，递增步长为0.5.同时还包括609个用户提供的1 853条信任关系，信任关系数据十分稀疏.

2.2 评估标准

(12)

(13)

2.3 结果对比分析

图1 2种方法的MAE和RMSE结果对比

从图1可以看出，当θ在0.45时，只加入了用户行为相似度的PtrustSVD的MAE可以达到0.587，RMSE达到0.786.而同时融合了信任传递的PTtrustSVD的MAE可以达到0.582，RMSE可以达到0.780.可见本文方法是非常高效的.

表1是本文方法和G.Guo等[4]的trustSVD方法的对比结果.从表1中可见，深度挖掘出的隐式信任关系可以有效缓解数据稀疏性问题，从而得到了更好的推荐效果.

由于数据稀疏，在对信任关系进行分解时，大量的空白值需要填补，因而本文方法具有更大的意义.相比于文献[12]提出的方法，本文方法更加有效.θ的取值能够决定挖掘信任关系的数量，由图1可见，无论是PtrustSVD还是PTtrustSVD算法，θ为0.45时效果最好，当θ值再继续减小时，效果反而不好，出现了过拟合现象.以上实验说明深度挖掘隐式信息不仅能缓解数据稀疏问题，而且有助于矩阵分解算法实现更好地推荐效果.

表1 PtrustSVD、PTtrustSVD与trustSVD性能对比

3 结束语

基于心理学中结构平衡理论和社会地位理论，通过分析用户之间的行为数据，使用Pearson相关系数挖掘出用户之间的隐式信任关系，结合信任传递机制，从而可以有效地改进基于社交网络的协同过滤推荐效果.

对于信任关系的处理还可以改进，比如衡量信任关系的标准有很多，信任关系也存在负关系等，信任传递时是否还有其他更一般的方法.这些都是我们今后要研究的问题，如果能够更加深入地考虑信任关系，可以进一步提高推荐的效果.

[1] 胡勋， 孟祥武， 张玉洁， 等. 一种融合项目特征和移动用户信任关系的推荐算法[J]. 软件学报， 2014， 25(8)：1817-1830.

[2] JUDITH MASTHOFF. Recommender systems handbook [M]. Boston：Springer， 2010：85-89.

[3] GUADOMAVICIUS， A TUZHILIN. Towards the next generation of recommender systems：a survey of the state-of-the-art and possible extensions [J]. IEEE Transactions on Knowledge and Data Engineering， 2005，17:634-749.

[4] GUO G， ZHANG J， YORKE-SMITH NEIL. TrustSVD：collaborative filtering with both the explicit and implicit influence of user trust and of item ratings[C]//Proceedings of the 29th AAAI Conference on Artificial Intelligence.Palo Alto：AAAI Press，2015:123-129.

[5] KOREN Y. Factorization meets the neighborhood：a multifaceted collaborative filtering model[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). Newyork：ACM， 2008:426-434.

[6] GUO G， ZHANG J， THALMANN D. Merging trust in collaborative filtering to alleviate data sparsity and cold start [J]. Knowledge-Based Systems， 2014， 57 (2)：57-68.

[7] HEIDER F. Attitudes and cognitive organization [J]. Journal of Psychology， 1946， 21(1):107-112.

[8] 程苏琦， 沈华伟， 张国清， 等. 符号网络研究综述[J]. 软件学报， 2014， 25(1)：1-15.

[9] 王英， 王鑫， 左万利. 基于社会学理论的信任关系预测模型[J]. 软件学报， 2014， 25(12)：2893-2904.

[10] GUO G， ZHANG J， THALMANN D， et al. From ratings to trust：an empirical study of implicit trust in recommender systems[C]//ACM Symposium on Applied Computing.Newyork：ACM， 2014:248-253.

[11] PAPAGELIS M， PLEXOUSAKIS D， KUTSURAS T. Alleviating the sparsity problem of collaborative filtering using trust inferences[M]. Berlin：Springer Berlin Heidelberg， 2005：224-239.

[12] WANG JIATONG， FEI ZHENQIAN， QIAO SHUYU， et al. A novel recommendation method based on user’s interest and heterogeneous information[C]//Asia-Pacific Web Conference. Switzerland：Springer International Publishing， 2016:90-101.

[13] BEIGI G， TANG J， WANG S， et al. Exploiting emotional information for trust/distrust prediction[C]//International Conference on Data Mining.Philadelphia：SIAM，2016:81-89.

[14] CALLINGHAM R. Six degrees：the science of a connected age[J]. Times Literary Supplement Tls， 2005， 61(1):93.

Arecommendationalgorithmbasedonuserbehaviorinformationandtrusttransferring

ZHANG Bang-zuo， WANG Jia-tong， SUN Wei， QIAO Shu-yu， FENG Guo-zhong， SUN Xiao-xin

(School of Information Science and Technology， Northeast Normal University， Changchun 130117，China)

Based on the similarity of user behavior information and trust transferring to infer the implicit trust relationship， this paper proposes a novel algorithm that integrated with matrix composition technique， namely， PTtrustSVD. The experimental results show that the purposed method using the implicit trust relation outperforms that only using explicit trust relation in the Filmtrust dataset， and prove that the implicit trust relation is effective for the recommender system.

recommender system； implicit trust； trust transferring

1000-1832(2017)04-0071-05

10.16163/j.cnki.22-1123/n.2017.04.014

2016-10-27

国家自然科学基金资助项目(71473035，11501095)；吉林省科技发展计划项目(20150204040GX，20170520051JH)；吉林省发改委项目(2015Y055)；东北师范大学自然科学基金资助项目(2014015KJ004).

张邦佐(1971—)，男，博士，副教授，主要从事数据库与数据挖掘、推荐系统研究.

TP 391.3学科代码520·2040

A

(责任编辑：石绍庆)