信任传递的矩阵分解推荐算法

杨　强，杨　有，余　平

(重庆师范大学计算机与信息科学学院， 重庆　401331)



信任传递的矩阵分解推荐算法

杨强，杨有，余平

(重庆师范大学计算机与信息科学学院， 重庆401331)

[摘要]针对协同过滤推荐系统中数据稀疏性导致推荐准确性低下问题，提出信任传递的矩阵分解推荐算法.该算法利用用户社交网络的直接信任关系，基于信任传递思想，预测用户在社交网络中的间接信任关系，以解决社交网络信任关系的稀疏性问题.该算法使用填充后的社交网络信任数据，预测填充用户评分数据，以解决用户评分数据的稀疏性问题；将处理后的用户评分数据在基于正则化迭代最小二乘方法推荐系统中进行应用，取得良好效果.实验结果表明：使用Epinions数据集，相比传统的矩阵分解算法，该算法的平均绝对误差下降了10.77﹪.

[关键词]推荐系统; 信任传递; 矩阵分解

推荐系统是一个非常有用的工具，它不仅能够帮助用户找到自己可能感兴趣的信息[1]，还能让信息展现在需要它的用户面前.在电子商务领域，推荐系统被广泛使用.例如，国外的Amazon和Last.fm[2]. 然而，推荐系统仍然存在许多问题，如数据稀疏性和冷启动.针对数据稀疏性问题，很多研究人员对此进行了深入的探讨[3-9].但是，以上研究都只使用了用户评分数据，仅仅使用用户评分数据的推荐系统不能提供现实的输出[10].

推荐系统中使用用户的社交网络关系，不仅可以提高推荐系统的准确性[11-13]，缓解数据稀疏性问题，而且还可以一定程度上解决冷启动问题.

在上述基于社交网络的推荐系统中，虽然都可以达到不错的推荐准确性，但他们没有考虑用户之间的信任传递.在用户的信任数据中也存在数据稀疏性问题，如果仅凭用户的少量直接信任关系进行预测评分，容易导致推荐的准确性不高.

针对用户评分数据和社交网络信任数据稀疏性问题，提出基于信任传递的矩阵分解推荐算法(Matrix Factorization Recommender Algorithm Using Trust Propagation，TPMF).实验表明，TPMF算法比传统的矩阵分解算法和文献[14]的推荐算法具有更好的预测效果.

1问题定义

在推荐系统中，我们有用户集合U={u1,u2,…,unu}和项目集合I={i1,i2,…,inm}.R={ri,j}nu×nm表示用户评分矩阵，每个元素ri,j表示用户i对电影j的评分，评分值为整数1到5，评分越高代表用户越喜欢.评分为1表示不喜欢，评分5表示非常喜欢.nu表示用户数量，nm表示电影数量.T= {ti,j}nu×nu表示用户信任矩阵，每个元素ti,j表示用户i对用户j的信任度.信任度为0到1之间的数.数值越大，信任程度越高.

推荐系统的任务是：给出一个用户u∈U和项目i∈I，在用户评分矩阵中，ru,i是未知的.然后使用R和T来预测用户u对项目i的评分.

在用户评分矩阵R中，每个用户和项目都有一个特征矩阵，用户对项目的评分就是用户和项目的特征矩阵的内积.令U=[ui]表示用户特征矩阵.其中，ui∈Rnf,i=1,…,nu，表示矩阵U的第i列.令M=[mj]表示项目特征矩阵.其中，mj∈Rnf,j=1,…,nm，表示矩阵M的第j列.nf表示特征空间的维度.ui和mj的计算如(1)式和(2)式[7].

(1)

(2)

2信任传递的矩阵分解推荐算法

传统的矩阵分解算法只使用了用户的评分数据，没有考虑社交网络的社会性因素，可能会导致推荐系统的推荐精度偏低.本文算法结合了社交网络数据，利用信任传递思想.

2.1　社交网络信任矩阵

信任是一种主观概率，即对于一个给定的活动，一个用户依赖于另一个用户执行的概率.本文采用的社交网络数据是用户之间的信任关系.用户之间的信任关系形成一个信任矩阵T={ti,j}nu×nu.

其中，dout(i)表示用户i的信任出度.每个元素ti,j表示用户i对用户j的信任度，大小由用户i的信任出度决定.信任度为0到1之间的数，数值越大，信任程度越高.E为用户之间的信任度集合.通常情况下，信任矩阵是非对称的.

2.2　更新社交网络矩阵

信任传递的思想类似于相似性传播.相似性传播的思想是：用户在找到自己相似的用户之后，认为相似用户的相似用户也是自己相似的用户.文献[15]认为：用户A信任用户B，用户B信任用户C，一定程度上可以推出，用户A信任用户C.由于社交网络信任矩阵存在数据稀疏性问题，如果仅仅使用直接的信任关系容易导致推荐系统的准确性不高.为了缓解社交网络信任矩阵的稀疏性问题，更好地使用用户的信任数据，利用信任传递的思想，获取更多间接的信任邻居很有必要.

在本文中，我们认为ti,j的大小等于用户i对用户j的直接信任程度与用户i对用户j的间接信任程度之和:

其中，N为社交网络中用户的总数量.

采用信任传递思想更新信任矩阵T后，矩阵T的稀疏度与更新前的稀疏度对比如表1所示.其中，稀疏度为矩阵中未知元素的个数与所有元素个数的比值.

表1　矩阵T和矩阵R在更新前与更新后的稀疏度对比

2.3　使用信任度初步预测用户评分

在用户评分矩阵R中，由于已知的用户评分很少，所以R是一个非常稀疏的矩阵.如果对一个非常稀疏的矩阵进行分解，再用分解得到的用户特征矩阵和项目特征矩阵来计算预测评分，容易导致推荐精度不高.

为了缓解评分矩阵的稀疏性，提高推荐的准确性，我们借助于社交网络信任矩阵对用户评分矩阵R中的缺失值进行初步预测，把用户之间的信任度作为权值，然后用信任的用户对项目的评分来预测用户对此项目的评分，从而一定程度上缓解数据的稀疏性，如表1所示.预测评分公式[16]如下：

其中，tu,v>threshold.threshold是信任度阈值，表示大于此阈值的信任用户才用来预测评分，小于或等于此阈值的信任度可忽略不计.tu,v表示用户u对用户v的信任度.rv,i表示用户v对项目i的实际评分.Pu,i表示用户u对项目i的预测评分，V为用户u的信任集合.

2.4　TPMF算法

TPMF算法的思想是，首先将社交网络数据转换成信任矩阵T，采用信任传递思想更新信任矩阵T.再根据信任矩阵T对用户评分矩阵R中的缺失值进行预测，使得用户评分矩阵R的稀疏性得到一定程度的缓解.然后再对矩阵R进行潜在因子分解，从而根据公式(1)和公式(2)计算出用户特征矩阵U和项目特征矩阵M.最后，根据矩阵U和矩阵M计算预测评分.算法步骤如下：

Step1 读取用户评分训练数据和社交网络信任数据，得到用户评分矩阵R和信任矩阵T.

Step2 使用信任传播原理，对信任矩阵T进行预测填充.

Step3 使用填充后的信任矩阵对用户评分矩阵进行预测填充.

Step4 使用ALS-WR方法进行迭代计算用户特征矩阵U和项目特征矩阵M[7].

Step5 读取测试数据集，根据用户特征矩阵U和项目特征矩阵M来预测试数据集中用户对电影的评分，计算MAE.

算法的工作流程示意图如图1.图1中粗斜体部分为本文主要工作.

图1　TPMF的工作流程示意图

3实验

实验中包含了本文算法与传统的矩阵分解算法(MatrixFactorization，MF)和社会矩阵分解算法[14](SocialMatrixFactorization，SMF)的实验结果对比分析.同时，因为本文算法涉及多个参数，所以实验中还包含各个参数在不同取值下的实验结果对比分析.

3.1　评价标准

平均绝对误差(MeanAbsoluteError，MAE)是一种常用的统计精度测试方法.计算用户实际评分和预测评分之间的MAE测量方式被广泛运用[17].ri表示实际评分.pi表示预测评分.假设测试数据集中有N个用户的评分，我们首先计算测试集中每个评分与预测评分的差值，再对这些差值的绝对值求和，最后求得平均绝对误差：

3.2　数据集

实验采用的是Epinions数据集(http://www.trustlet.org/wiki/Downloaded_Epinions_dataset).数据集包含社交网络数据和用户评分数据.社交网络数据包含487 183条记录，每条记录包括source_user_id、target_user_id和trust_statement_value、trust_statement_value.值全部为1，表示ID为source_user_id的用户对ID为target_user_id的用户存在信任关系.用户评分数据包含664 824条记录，每条记录包括user_id、item_id和rating_value.表示ID为user_id的用户对ID为item_id的电影评分值为rating_value.rating_value值的范围是1~5.

由于数据量比较大，本实验采用的数据是用户ID在2 000以内(包括2 000)并且项目ID在4 000以内(包括4 000)的社交网络数据和评分数据.其中，用户评分数据的80﹪作为训练数据，20﹪作为测试数据.社交网络数据的100﹪作为训练数据.

3.3　实验结果与分析

本实验采用联想笔记本，在Matlab7.11.0平台下运行.由于只有TPMF算法才用到参数threshold,经过多次实验，当nf=2和λ=0.05时可以取得较好的效果.所以，在第一组实验中假设nf=2和λ=0.05，然后考察不同的threshold取值对实验的影响情况.实验结果如图2所示.实验结果表明，随着threshold值的增大，MAE逐渐增大，直到接近平稳.这表明随着阈值的增大，只有信任度大于阈值的才加入预测.也就是说，当阈值增大时，可用的信任度变少，从而导致能够进行初步预测的评分变少，不能够很好缓解评分矩阵稀疏问题.这使得推荐准确性逐渐变低直至平稳，最后接近于没有对用户评分矩阵预测的情况.

图2　threshold取值不同对TPMF算法MAE的影响

由于threshold决定了此信任度是否要加入计算，当threshold值较小时引入此信任度反而会增大预测结果的误差.所以，当threshold比较小时对其忽略不计.多次实验表明，当threshold>0.1时可以使推荐算法取得最佳预测效果.因此在第二组实验中，本文考察了当threshold>0.1、nf=2时，MF、SMF和TPMF 3种算法在不同λ取值下MAE的变化情况.实验结果如图3.实验结果表明，当λ取值较小时，相比MF和SMF算法，TPMF算法的MAE明显更小.也就是说，当λ取值较小时，TPMF算法有更高的推荐准确度.

图3　MF、SMF与TPMF在不同λ取值下的MAE对比

在第3组实验中，本文考察了threshold>0.1、λ=0.05时，MF、SMF和TPMF3种算法在不同nf取值下MAE的变化情况.实验结果如图4.实验结果表明，MF和SMF算法的MAE随着参数nf的增加先增大，然后接近平稳.也就是随着特征数的增加，推荐的准确性呈下降趋势，直至接近平稳.相比MF和SMF算法，TPMF的MAE比较稳定，而且明显比MF的MAE小.这表明TPMF比MF具有更好的预测效果.

图4　MF、SMF与TPMF在不同nf取值下的MAE对比

参数λ和nf的不同取值影响着MF、SMF和TPMF算法的MAE.在第2组实验中，实验取了9个不同的参数λ来测试对MAE的影响.在第3组实验中，实验取5个不同的参数nf.通过这两组实验，实验中共包含两种算法MF和TPMF的14个MAE.MF算法的这14个MAE总和为13.983 6，平均值为0.998 8.SMF算法的这14个MAE总和为15.016 1，平均值为1.072 6.TPMF算法的这14个MAE总和为12.476 7，平均值为0.891 2.相比MF算法，TPMF算法的MAE降低了10.77﹪，如表2所示.

表2　MF、SMF与TPMF算法的MAE综合比较

4结语

本文提出信任传递的矩阵分解推荐算法，采用信任传递思想，预测填充社交信任关系矩阵，利用信任关系数据预测填充用户评分，缓解了信任关系数据和用户评分数据的稀疏性，并将处理后的数据用于ALS-WR推荐系统中，预测的平均绝对误差下降了10.77﹪，明显提高了推荐系统的准确性.

[参考文献]

[1]MoghaddamMG,ElahianA.Anoveltemporaltrust-basedrecommendersystem[C]. 2014 22ndIranianConferenceonElectricalEngineering(ICEE).IEEE, 2014: 1142-1146.

[2]ShambourQ,LuJ.AneffectiverecommendersystembyunifyinguseranditemtrustinformationforB2Bapplications[J].JournalofComputerandSystemSciences,2015.

[3]ChujaiP,SuksawatchonU,RasmequanS,etal.Imputingmissingvaluesincollaborativefilteringusingpatternfrequentitemsets[C].ElectricalEngineeringCongress(iEECON)2014InternationalIEEE,2014:1-4.

[4]赵琴琴,鲁凯,王斌.SPCF:一种基于内存的传播式协同过滤推荐算法[J]. 计算机学报,2013(3):671-676.

[5]LopesARS,PrudencioRBC,BezerraBLD.Acolla-borativefilteringframeworkbasedonlocalandglobalsimilaritieswithsimilaritytie-breakingcriteria[C].2014InternationalJointConferenceonNeuralNetworks(IJCNN).IEEE, 2014: 2887-2893.

[6]JiH,ChenX,HeM,etal.Improvedrecommendationsystemviapropagatedneighborhoodsbasedcollaborativefiltering[C].ServiceOperationsandLogistics,andInformatics(SOLI), 2014IEEEInternationalConferenceonIEEE, 2014: 119-122.

[7]ZhouY,WilkinsonD,SchreiberR,etal.Large-scaleparallelcollaborativefilteringforthenetflixprize[M].AlgorithmicAspectsinInformationandManagement.SpringerBerlinHeidelberg, 2008: 337-348.

[8]SharifiZ,RezghiM,NasiriM.Anewalgorithmforsolvingdatasparsityproblembased-onnonnegativematrixfactorizationinrecommendersystems[C]. 2014 4thInternationaleConferenceonComputerandKnowledgeEngineering(ICCKE).IEEE, 2014: 56-61.

[9]CaiY,LeungH,LiQ,etal.Typicality-basedcollaborativefilteringrecommendation[J].IEEETransactiononKnowledgeandDataEngineering, 2014, 26(3): 766-779.

[10]ChenC,ZengJ,ZhengX,etal.Recommendersystembasedonsocialtrustrelationships[C].2013IEEE10thInternationalConferenceone-BusinessEngineering(ICEBE).IEEE, 2013: 32-37.

[11]OechsleinO,FleischmannM,HessT.AnapplicationofUTAUT2onsocialrecommendersystems:incorporatingsocialinformationforperformanceexpectancy[C].2014 47thHawaiiInternationalConferenceonSystemSciences(HICSS).IEEE,2014:3297-3306.

[12]QianX,FengH,ZhaoG.Personalizedrecommendationcombininguserinterestandsocialcircle[J].IEEETransactionsonKnowledgeandDataEngineering, 2013(26): 1763-1777.

[13]JiangM,CuiP,WangF,etal.Scalablerecommendationwithsocialcontextualinformation[J].IEEETransactionsonKnowledgeandDataEngineering, 2014, 11(26): 2789-2802.

[14]李卫平, 杨杰. 基于随机梯度矩阵分解的社会网络推荐算法[J]. 计算机应用研究, 2014, 31(6): 1654-1656.

[15]GuoG,ZhangJ,ThalmannD.Mergingtrustincollaborativefilteringtoalleviatedatasparsityandcoldstart[J].Knowledge-BasedSystems,2014,57:57-68.

[16]FaridaniV,JahanMV,JalaliM.Combiningtrustincollaborativefilteringtomitigatedatasparsityandcold-startproblems[C].ComputerandKnowledgeEngineering(ICCKE), 2014 4thInternationaleConferenceonIEEE,2014:233-238.

[17]YangX,GuoY,LiuY,etal.Asurveyofcollaborativefilteringbasedsocialrecommendersystems[J].ComputerCommunications, 2014, 41: 1-10.

(责任编辑穆刚)

Matrix factorization recommender algorithm using trust propagation

YANG Qiang, YANG You, YU Ping

(School of Computer and Information Science, Chongqing Normal University, Chongqing 401331, China)

Abstract：Due to the data sparsity problems which lead to inaccuracy of recommendation in collaborative filtering recommender systems, a matrix factorization algorithm was proposed, which uses the trust propagation. The proposed method used the direct trust relationship between users of social networks, based on the idea of trust propagation, predicted indirect trust relationship in social networks to solve the problem of sparse trust relations; the algorithm used social network trust data after filling for predicting and filling the user rating data to solve the problem of the sparsity of user rating data; It achieved good results in the recommender system based on the alternating-least-squares with weighted-λ-regularization method using user rating data that predicted and filled. The experimental results show that: the average absolute error of this algorithm decreases 10.77﹪ on the Epinions data sets, compared with the traditional algorithms.

Key words：recommender systems; trust propagation; matrix factorization

[中图分类号]TP391.3

[文献标志码]A

[文章编号]1673-8004(2015)05-0125-05

[作者简介]杨强(1988—)，男，江西抚州人，硕士研究生，主要从事推荐系统方面的研究.

[基金项目]重庆市教委科技项目(KJ130646).

[收稿日期]2015-04-01