融合信任和基于概率矩阵分解的推荐算法

田保军 杨浒昀 房建东

摘 要：針对推荐精度不准确、数据稀疏、恶意推荐的问题，提出融合信任基于概率矩阵分解（PMF）的新推荐模型。首先，通过建立基于信任的协同过滤模型（CFMTS）将改进的信任机制融入到协同过滤推荐算法中。信任值通过全局信任及局部信任计算获得，其中局部信任利用了信任传播机制计算用户的直接信任值和间接信任值得到，全局信任采用信任有向图的方式计算得到。然后，将信任值与评分相似度融合以解决数据稀疏、恶意推荐的问题。同时，将CFMTS融入到PMF模型中以建立新的推荐模型——融合信任基于概率矩阵分解模型（MPMFFT），通过梯度下降算法对用户特征向量和项目特征向量进行计算以产生预测评分值，进一步提高推荐系统的精准度。通过实验将提出的MPMFFT与经典的PMF、社交信息的矩阵分解（SocialMF）、社交信息的推荐（SoRec）、加权社交信息的推荐（RSTE）等模型进行了结果的对比和分析，在公开的真实数据集Epinions上MPMFFT的平均绝对误差（MAE）和均方根误差（RMSE）比最优的RSTE模型分别降低2.9%和1.5%，同时在公开的真实数据集Ciao上MPMFFT的MAE和RMSE比最优的SocialMF模型分别降低1.1%和1.8%，结果证实了模型能在一定程度上解决数据稀疏、恶意推荐问题，有效提高推荐质量。

关键词： 推荐系统;信任关系;概率矩阵分解;特征向量

中图分类号：TP183

文献标志码：A

Abstract：  For the problems of low recommendation accuracy， data sparsity and malicious recommendation， a new recommendation model based on Probability Matrix Factorization （PMF） and fusing trust was proposed. Firstly， by establishing a Collaborative Filtering Model based on Trust Similarity （CFMTS）， the improved trust mechanism was integrated into the collaborative filtering recommendation algorithm. The trust value was obtained through global trust and local trust calculation. The local trust was obtained by calculating the direct trust value and the indirect trust value of the user by the trust propagation mechanism， the global trust was calculated by the trust directed graph. Then， the trust value was combined with the score similarity to solve the problems of data sparsity and malicious recommendation. At the same time， CFMTS was integrated into the PMF model to establish a new recommendation model — Model based on Probability Matrix Factorization and Fusing Trust （MPMFFT）.

The user feature vectors and the project feature vectors were calculated by the gradient descent algorithm to generate the predicted scores， further improving the accuracy of the recommender system. Through experiments， the proposed MPMFFT was compared with the classical models such as PMF， Social Matrix Factorization （SocialMF）， Social Recommendation （SoRec） and Recommendations with Social Trust Ensemble （RSTE）. The proposed model has the Mean Absolute Error （MAE） and Root Mean Squared Error （RMSE） decreased by 2.9% and 1.5% respectively compared with the optimal model RSTE on the open real dataset Epinions， and has the MAE and RMSE decreased by 1.1% and 1.8% respectively compared with the optimal SocialMF model on open real dataset Ciao， verifying that the proposed model is significantly improved on the above indicators. The results confirme that the propose model can resolve the problem of data sparseness and malicious recommendation to some extent， and effectively improved the recommendation quality.

Key words：  recommender system; trust relationship; Probability Matrix Factorization （PMF）; feature vector

0 引言

随着云计算、物联网和移动社交网络等的快速发展，信息量迅速增长，中国互联网络信息中心（China Internet Network Information Center， CNNIC）在2018年7月发布信息，在《第43次中国互联网络发展状况统计报告》中统计的情况：截止到2018年12月，国家现有的网民的规模大约为8.29亿人，比上一年增加了约5653万网民，和2017年末相比较网民数量增加了7.3%，互联网基本的普及率达到了59.6%[1]。大家在分享和利用这些数据的同时，由于海量数据的出现，用户从互联网上获取有价值的信息越来越困难，无法将有用的信息转为自己的需求，使得用户对信息的利用率逐渐下降，出现了 “信息超载”（Information Overload）现象[2]。

为了让用户更准确获取到所需要的信息，推荐系统应运而生，推荐系统主要对用户的历史行为进行分析，从而获取到用户的偏好，然后为用户进行推荐，推荐的内容是个性化的。通过这样的方法，提供给用户的信息既有用又高效。

目前，推荐方法大致有三种：基于内容的方法[3-4]、基于协同过滤的方法[5-8]和混合推荐方法[9-11]。本文对这三种方法的特点进行了对比，见表1所示。

方法分类基本要点优缺点基于内容的推荐基于内容推荐的核心是，得到推荐者的兴趣偏好，按照推荐内容与之相匹配的程度来推荐优点：较成熟的技术，没有冷启动问题;缺点：推荐结果会受目标用户特征提取能力限制基于协同过滤的推荐基于协同过滤算法的核心是，通过用户行为以及偏好，找到用户邻居，结合邻居对项目的评分，较高的来进行推荐优点：算法稳定，对新来源的信息能较好的推荐;缺点：普遍存在数据稀疏、可扩展问题混合推荐混合推荐方法的核心是，独立计算两类推荐算法结果进行混合。选择不同的混合方式对其结果混合，如将预测分数线性混合，或者设立评价标准，对推荐结果进行比较取较高优点：可以较好地对结合算法的缺陷补全，推荐结果较优;缺点：由于结合多个算法，计算难度上升虽然推荐系统能够缓解大数据下的“信息超载”问题，但是正面临着一些严峻的挑战：第一，稀疏性问题。如何有效解决数据稀疏性问题，是协同过滤算法面临的最主要问题。协同过滤方法仅依赖于评分数据，预测相似性或训练模型，而评分数据集的极度稀疏性使得推荐结果的质量很差。第二，恶意推荐问题。传统推荐算法主要是依据评分数据来计算用户间相似度，这种有效相似度的前提是评分数据是真实的、可靠的。但在实际应用场景中，这种前提往往很难得到保证。例如：在电子商务平台，一些商家会通过各种手段给他的竞争对手肆意地进行差评，或通过其他方式（使用优惠政策）让用户对其产品或服务予以好评，如果将这些不可靠的数据直接用来给目标用户预测评分，将导致推荐系统的推荐质量严重下降。第三，推荐精度低问题。

基于概率矩阵分解（Probability Matrix Factorization， PMF）的隐因子模型（Latent Factor Model， LFM）因具有可扩展性好及灵活性高等诸多特点是目前推荐系统的主流模型，得到了广泛的应用，它可以无缝地将用户、项目等特征融入到模型中，使得该模型得到较好的推荐预测准确性。

1 融合信任和基于概率矩阵分解的推荐算法

1.1 信任基本模型

在用户项目评分矩阵较为稀疏的情况下，结合社交网络的推荐算法比传统的推荐算法具有更多的优点，可以提高推荐的质量。

Massa等[12]使用来自流行的互联网网站Epionios数据集的数据，采用了信任网络的传播特性，推断其他用户的额外权重，利用信任关系解决数据稀疏性、冷启动和安全性。Golbeck等[13]提出了一种在使用信任网络中的连续值计算这些信任关系的算法TidalTtrust，先计算用户的直接信任度，通过原用户与目标用户之间的最短路径，采用宽度优先搜索的方式结合评分权值，计算出他们之间综合的信任度。

Massa等[14]提出的MoleTrust模型的整體思路与TidalTrust模型相似，它们都是用宽度优先搜索来迭代计算用户间的信任度，只是MoleTrust模型在计算用户对目标用户信任时，搜索目标用户之间的路径设置不同，参照了目标用户的最路径长度。Jamali等[15]结合了信任网络与协同过滤的随机游走模型TrustWaller，为了避免随机游走的深度增加，距离目标用户越来越远，影响推荐精准度，该随机游走模型的深度，尽量选择距离用户较近的邻居，且考虑目标信任用户对项目的评分，以及这些项目的相似项目的评分。Guo等[16]提出了三个因子相似性模型，其中基于隐式用户反馈结合了项目推荐的社会信任信息。该模型引入矩阵分解技术，根据用户用户和项目项目的相似性，计算用户项目评分和未评分项目之间的用户偏好，通过三个真实数据集的实验结果表明，该模型可以获得优于其他同行的排名表现。Zhang等[17]提出一种基于社交网络中随机梯度矩阵分解的社会推荐模型，以提高预测精度。将社会网络作为辅助信息，根据基于社会推荐模型的矩阵分解，系统地说明了如何利用社会正规化设计矩阵分解目标函数。它将社交网络矩阵与用户评分矩阵结合，并提出了一种用于矩阵分解的随机梯度下降算法，对两个大型数据集的实证分析表明，其模型具有较低的预测误差，并且明显优于其他最先进的模型。Nazemian等[18]利用社交网络中的信任信息和用户个人数据来提供个性化推荐，提出了一个提高信任感知推荐系统精准度的模型。在Extended Epinions数据集上进行评估模型，这种模型可以显著提高推荐系统的精准度，同时不会降低推荐系统的覆盖范围。

本文将信任关系引入到推荐系统当中，综合考虑了全局和局部信任，通过信任的传播建立了新的信任模型，充分挖掘用户之间的信任关系，设置推荐权重，结合信任度和评分相似度来度量用户之间的相似度，以提高推荐的可信度和准确度，解决只依靠评分进行推荐的局限性。

概率矩阵分解模型是目前推荐系统的研究热点之一，本文将社交信任关系、评分信息融入到概率矩阵分解模型中，使用自适应权重，动态调整各部分的影响因子，形成高效统一的模型，进一步提高了推荐系统的质量。

1.2 改进信任值的度量

通常，采用信任网络有向图的方式计算信任值。

其中用户的局部信任网络如图1所示。

1.2.1 全局信任值全局信任值是整个信任网络中的声望或地位，也就是每个用户在处于当前的信任网络中只拥有一个全局信任值。全局信任值的计算如式（1）所示：

其中：td（u）代表了信任网络中用户u的入度，其值代表了信任用户u的用户数量，该数量直接体现了用户u的全局信任度;min（td （w））代表了信任网络图中，所有用户节点中最小的入度，可以理解为信任关系图中信任关系最少的用户;max（td （w））代表了信任网络中，所有用户节点中最大的入度，可以理解为信任关系图中最受用户信赖的目标用户，全局信任度Gu的值是在[0，1]内。

1.2.2 局部信任值

对于局部信任值，采用信任传播的计算方法。MoleTrust是一种经典的信任传递模型，该模型计算用户u和用户v间的信任值，如式（2）所示：

其中：Tuk表示用户u对用户k的信任度;Tkv表示用户k对用户v的信任度;N（u）是用户u的邻居集;tuv是通过信任传递计算得到的用户u与用户v的间接信任值。

MoleTrust模型虽然考虑了信任传播特性，但忽略了信任值与信任传播路径的关系。因此本文在其基础上进行了改进，得到改进后的局部信任的计算方法，如式（3）所示：

其中：d代表了在信任网络中用户u与用户v连接最短路径的长度，也就是通过信任传播到达用户v的最短距离。本文采用深度优先算法搜索进行计算，为了避免路径过长，数据冗余和失真等“垃圾”数据的产生，根据的“六度区隔”理论[19]，对d的范围限定在区间[0，6]。

在计算全局信任值与局部信任值之后，采用加权求和的方法得到用户u与用户v的最终信任值，如式（4）所示：

其中：Gu表示通过式（3）得到的用户u与用户v的局部信任值;Luv表示通过式（1）得到的用户u的全局信任值。

1.3 建立融合信任度与评分相似度的协同过滤模型

本文采取融合评分相似度和信任值的方法，建立了基于信任相似度的协同过滤模型（Collaborative Filtering Model based on Trust Similarity， CFMTS）。

利用皮尔逊相关系数公式计算用户间的评分相似性，公式如下：

其中：rui表示用户u对项目i的评分值;rvi表示用户v对项目i的评分值项目i的评分值;Iuv表示用户u与用户v的共同评分项目集;Iu表示用户u的评分项目集，Iv表示用户v的评分项目集;ru表示用户u所有评分项目的平均值;rv表示用户v所有评分项目的平均值。

权衡信任度和评分相似性度对推荐结果的影响。得到用户u和用户v的新的相似度ωuv，可以通过式（6）计算得到：

考虑到信任值的传递会随路径的增长而减小，因此，在式（6）中的引入影响因子a，其计算方法如式（7）所示：

其中：tuvr′表示第r条路径上用户u与用户v的信任值;road（u，v）表示信任网络中，用户u连接到用户v所有路径的集合;road（u，v）表示用户u到用户v之间最短路径长度。

影响因子b的计算如式（8）所示：

1，其他（8）

其中：n为用户u与用户v共同打分项目的数量;n1是系统中对项目的最少打分数量;n2是系统中对项目的最多打分数量。当用户u和用户v的共同打分数量n接近n2时，

说明两个用户的偏好程度较高。

1.4 建立基于PMF的推荐模型

基于PMF的推薦模型，由于其推荐精度高而成为学术界最流行的推荐方法之一，主要思想是通过矩阵分解技术将用户项目映射到一个低维公共的隐特征空间，将用户对某一个项目的评分，对应到它们的隐向量的内积。

本文将CFMTS融入到PMF模型中，建立了新的融合信任基于概率矩阵分解模型（Model based on Probability Matrix Factorization and Fusing Trust， MPMFFT），进一步提高了推荐系统的精准度。

将PMF模型分解后得到的用户i与项目j的隐因子向量分别为U和V，

利用式（9）得到用户i对项目j的评分：

其中： Ni表示用户i的最近邻居集。

那么，新推荐模型MPMFFT，用户i对项目j的评分Rij 关于特征向量U、V 的条件概率分布为：

其中：U∈Rd×M和V∈Rd×N是用户与项目的特征矩阵，都满足均值为0、方差为σ2U、σ2V的高斯先验分布;

N（xμ，σ2R）是均值为μ、方差为σ2R的高斯分布;

IRij为指示函数，如已为用户u对项目i进行了评分则为1，否则为0;g（x）=1/（1+exp（-x））是逻辑回归函数，限定用户对项目的评分值，从而使得评分值转换为[0，1]内。

对式（10）取对数后得到式（11）：

其中：C是常量，不依赖于任何参数;D是对应的潜在特征矩阵的维数。最大化式（11）的后验概率，等同于最小化式（12）的目标函数：

本文的实验设λU=λV，以降低算法的复杂度。

利用梯度下降方法对式（12）求得极小值，得到了用户的特征向量U和项目的特征向量V。

其中：Ut+1i和Vt+1j表示迭代后的计算结果，Uti和Vtj为迭代之前的数值，τ为迭代步长。从而计算出用户i对项目j的预测评分R^ij。

1.5 算法流程

MPMFFT的具体流程如下：

输入 对信任的矩阵Z初始化，用户项目评分矩阵R初始化（其中：用户的數量为N，项目数量为M）。

输出 对评分矩阵的预测评分R′。

1）遍历信任整个网络，根据式（1）计算每个用户全局信任度Gu;

2）遍历信任整个网络，根据式（3）计算每个用户的局部信任度Luv;

3）根据式（4）计算综合信任度Tuv;

4）遍历用户集中（包含N个用户）任意两个用户u与v，根据式（5）计算用户间的相似度sim[u][v];

5）权衡信任关系和评分相似性关系对推荐结果的影响，遍历用户集中任意两个用户i与k，根据式（6）计算推荐权重ωik;

6）计算p（U，VR，σ2R，σ2U，σ2V）;

7）计算ln p（U，VR，σ2R，σ2U，σ2V）;

8）计算L（U，V，R，T′）;

9）利用梯度下降法，根据式（13）和（14）分别计算Ui和Vj;

10）根据式（15）计算R^ij。

2 实验分析

2.1 实验环境

采用CPU 3.5 GHz Intel Core i7，1TB硬盘、内存8GB、千兆交换机;操作系统为Windows 7（64位）;编程环境使用Anaconda 3，开发语言为Python 3.7。

2.2 实验评价标准

为了评价本文提出的推荐模型的质量，采用了经典的平均绝对偏差（Mean Absolute Error， MAE）和均方根误差（Root Mean Squared Error， RMSE）作为评价标准。通过计算预测值和真实值之间的平均绝对偏差来反映预测结果与实际情况的偏差，所计算的MAE与RMSE值越小，则表示模型对应的预测值和真实的评分值之间的误差就越小，代表着推荐结果的精度就越高。

其中：T表示测试集评分记录数;Rij表示用户i对项目j的真实评分;R^ij表示用户i对项目j的预测评分值。

2.3 实验结果分析

Epinions是由Epinios.com网站提供的真实数据集，它是一个对文章的评论网站，该网站成立于1999年，用户可以在文章原有评论的基础上增加自己的评论，并且能够在[1，5]内对项目评分，这些评分信息和评论等行为都会被系统记录，同时在其他顾客来访时产生影响，而且该网站对每个用户都保留了信任列表，这个列表代表着用户与用户之间的行为关系，其信任关系是离散且简单的0、1有向信任关系。

Ciao（ciao.co.uk）数据集通常被用于推荐系统实验，该数据集也包含了用户对电影的评分信息，评分值均在[1，5]内，其信任关系也是0、1的有向信任关系。两个数据集的具体信息见表2所示。

首先，评测式（9）中的参数α对本文中MPMFFT的影响。若α=1，则MPMFFT就变成概率矩阵分解模型PMF，是用户正常喜好推荐;若α=0，则MPMFFT只通过信关系预测用户的喜好;当α∈（0，1）内时，MPMFFT将用户项目评分矩阵R与用户间信任关系融入到概率矩阵分解模型中，预测用户对项目的评分。

1）本文将Epinions数据集进行随机分割，采取5折交叉验证和10折交叉验证，将其 80%和 90%作为训练集来计算MAE的值和RMSE的值。先假定特征矩阵的潜在维度D=20，目标函数的迭代次数τ=40，确定了参数α的值后，再进行实验对特征矩阵维度D的最优取值。

参数α对实验评价标准MAE和RMSE值的影响，实验结果如图2～3所示。

从图2中，可以得出以下结论：在特征矩阵维数D=20，迭代次数τ=40的条件下，不论是将数据集的80%还是 90%作为训练集进行交叉实验，MAE的值将随着α的值的增加而变化，总体上先下降，后上升的趋势，MAE都在α=0.4时取得最小值。

从图3中，可以得出以下结论：在特征矩阵维数D=20，迭代次数τ=40的条件下，不论是将数据集的80%还是 90%作为训练集进行交叉实验，RMSE的值随着α的值得增加而变化，总体上先下降，后上升的趋势，RMSE都在α=0.4时取得最小值。

2）通过上述实验的结果可知，在参数α=0.4的情况下，采取采用5折交叉验证以及采用10折交叉验证，MAE值和RMSE值均为最小值。因此，采用α=0.4，验证参数β对MAE值和RMSE值的影响，如图4～5所示。

从图4～5中能够看出，在Ciao和Epinions数据集上，当β为0.1 和0.3 时，RMSE与MAE的评价指标均达到最小值。

3）特征矩阵维数D对MPMFFT的影响。图6～7为在参数α=0.4， β=0.1及迭代次数τ=40的条件下，特征矩阵维数D对MPMFFT的MAE值和RMSE值的影响。从图6～7可看出：无论使用 80%或 90%的训练数据，MAE值和RMSE值都是随着特征矩阵维数D的增加而减小。还可以从图6～7中进一步观察到，当维度D大于某一阈值80时，MAE和RMSE预测精准度下降趋势变得平坦。根据以上实验的结果，本文采用D=80。

在参数α=0.4， β=0.1，潜在特征矩阵维度D=80及迭代次数τ=40的条件下，将本文所提出的MPMFFT与4种经典模型：PMF模型、加权社交信息的推荐（Recommendations with Social Trust Ensemble， RSTE）模型、社交信息的推荐（Social Recommendation， SoRec）模型和社交信息的矩阵分解（Social Matrix Factorization， SocialMF）模型，分别在Epinions与Ciao两种数据集上进行了RMSE与MAE值的比对，其中，数据集中的80%作为训练集，20%作为测试集进行训练。模型的其他参数设置见表3所示。实验结果如图8～9所示。