文 凯，朱传亮

(1.重庆邮电大学 通信新技术应用研究中心，重庆 400065； 2.重庆信科设计有限公司，重庆 401121)

0 引言

推荐算法主要是帮助用户从大量的商品中筛选出自己感兴趣的商品，目前广泛使用的推荐方法是协同过滤方法，该方法基于相似用户有相似偏好来为用户作出推荐[1]。然而在真实世界中，由于用户偏好数据的稀疏性，导致协同过滤方法的推荐准确率不太高，并且对新用户的推荐也无从下手。随着社交网络的发展，用户间的交互越来越多，其中信任网络成为了一个重要的研究方面，为了解决数据稀疏带来的问题，许多学者提出了基于用户间信任的推荐算法[2-3]，这种结合信任的推荐算法主要考虑的是用户更喜欢他们的朋友所推荐的商品。同样地，在真实的社交网络中，显示的信任数据也是十分稀疏的，需要对隐式关系进行挖掘。另外，在一些社交网络中，用户间不仅可以建立信任关系，还可以建立不信任关系，例如在Epinions网站中，允许用户根据其他用户的评论对其进行信任或不信任的评价，因此用户间的不信任关系也是一个最近值得研究的方面。

本文针对信任关系稀疏的问题并且考虑到了用户间的不信任关系，提出了一种结合社交网络和用户间兴趣相关性的矩阵分解正则化推荐模型，该方法不仅扩展了信任关系，并且将不信任关系也融合到推荐系统中，在正则化过程中还考虑到了用户间的兴趣因素，本文的工作主要包括以下几个方面：

1)针对含有不信任关系的社交网络，提出一种修正的结合全局和局部信任的信任评估方法，扩展了用户间稀疏的信任矩阵，并构建了用户间的不信任矩阵。

2)构建用户间的兴趣相关性，对已有的社会正则化约束的矩阵分解方法进行了修正，加入信任和不信任关系矩阵以及用户间的兴趣相关性。

3)在Epinions数据集上的实验证明了本文提出的方法在用户-评分数据和信任关系数据都稀疏的情况下，相比其他类似的算法在推荐精度上有所提高。

1 相关工作

社交网络环境下基于信任的推荐方法有很多的研究成果，Ma等[4]提出了一种SoRec方法将用户间的信任关系和用户对物品的评分信息融入概率矩阵分解；Wang等[5]提出一种基于矩阵因子的分解方法，将用户间的相似关系作为信任关系的补充，综合考虑了信任关系、项目间的相似关系来作为预测评分的权重；Yang等[6]提出了一种TrustMF算法，该算法结合矩阵分解框架，将评分矩阵和社交关系矩阵同时融合进矩阵分解中，反映了信任用户间的关系对矩阵分解的评分预测的影响；Lai等[7]在基于信任的推荐系统上提出了一种混合的个人信任模型，并且考虑到具有相似偏好的用户通常来自于同一组，用户的偏好可能受组成员的影响，将个人信任和组信任混合，提高推荐的性能。以上提出的方法仅仅考虑了用户间的信任关系而忽略了不信任关系。

最近几年，也有一些学者尝试将用户间的不信任关系融入推荐系统中，印桂生等[8]提出一种结合受限信任关系的概率矩阵分解方法，利用用户间的不信任关系对信任关系进行修正，然后联合用户的信任关系和评分信息进行联合概率矩阵分解；Forsati等[9]提出一种PushTrust方法，该方法能够同时利用信任、不信任和中立关系，并且对社交网络的规模有着线性的依赖关系，将基于排序的社会正则化思想融入到矩阵分解算法中；李慧等[10]通过计算信任网络中节点的声望值与偏见值来发现信任网络中的不可信节点,并通过对其评分权重进行弱化来减轻其对信任网络产生的负面影响。Jang等[11]充分考虑显式信任关系和显示不信任关系，利用传播特性扩展了用户间的信任和不信任关系。

以上提出的方法虽然都利用了不信任关系，但大都只是利用不信任关系对信任进行修正，这样没有充分地利用不信任关系，因此本文将信任和不信任关系分开考虑，利用网络的拓扑特性在信任网络子图和不信任网络子图中进行随机游走得到用户的全局影响力，结合局部信任度得到修正的用户信任度矩阵，同时本文还定义了用户间的不信任度，提出了一种定义用户间的兴趣相关性的方法，然后将这些同时作为正则化项对用户-商品的矩阵分解进行约束。

2 融合社交网络和兴趣的正则化推荐算法

2.1 问题描述

表1 符号表

2.2 用户信任关系矩阵的获取

信任网络是一种复杂的网络关系，具有差异性、传递性、非对称性等特点，信任的分类不同，其度量的方法也有所不同，包括集中与分布式、成对与成组式、全局与局部式，其中的全局和局部式是当前较流行的度量方法，因此本文采用一种基于改进的PageRank算法[12]的全局计算方法和基于多路径传播的局部信任计算方法。

2.2.1 PageRank全局信任度计算

全局信任指的是每个用户在整个信任网络中的地位和水平，代表了网络中其他节点对其的综合评价[13]，是从全局的角度出发的。PageRank算法最初应用于计算网页的重要性，因为该算法考虑到了网络的全局拓扑特性，所以本文采用此算法来计算用户的全局信任度。之前利用PageRank算法计算信任度时往往只考虑到了用户间的信任关系，然而用户之间也可能存在不信任关系，在网络图中一个用户被越多人信任，其影响力越大；相反，一个用户越不被人信任，其影响力越小，因此其全局信任度应该是要综合考虑这两个因素的，本文将在网络子图G+中和G-中分别运行PageRank算法，利用不信任网络子图上游走的结果来修正用户的全局影响力，得到最终的用户影响力，即用户的全局信任度。

根据文献[14]中的描述，将计算网页重要度的算法映射到两个网络子图G+和G-中，将节点映射为网络中的用户，将边映射为用户间有信任关系或不信任关系的边，在整个网络中，一个用户的全局信任度取决于所有信任他的用户以及不信任他的用户，其公式如下：

(1)

(2)

然而式(1)和式(2)中描述的PageRank算法在游走过程中游走到下一个相邻节点时的概率是一样的，未考虑到相邻用户之间的相似性，一个节点到下一个节点的概率必然是有所差别的，本文考虑到在游走过程中，从一个节点跳转到下一个相邻节点时的概率应该是与相似性成正比的，在信任网络中，由于彼此信任，则相似度越大的用户之间转移的概率就大；同样地，在不信任网络中，两者之间相似度越小就越可能转移到此不信任节点，因此，本文考虑拟将用户间的相似性比值作为下次跳转概率的权重，因此改进的计算公式分别如下：

(3)

(4)

式(3)、(4)中相似度的计算本文采用Person相似度，计算公式如下：

(5)

2.2.2 局部信任度计算

由于在最原始的信任度矩阵中，用户之间的信任关系都是二进制的，因此本文首先使用用户之间的相似度来作为两个用户之间的直接相似度，计算如式(4)，根据Golbeck[15]提出的用户之间的共同信任邻居越多，两者之间的信任度越大，因此两个非相邻用户之间的信任度计算公式如下：

(6)

2.2.3 综合全局和局部信任度

通过对信任网络的扩展，将用户信任度矩阵变得稠密，然而，用户的个人影响力也是在某种程度上也可以反映出用户的信任度，因此本文考虑将用户的全局信任度和局部信任度结合起来考虑用户之间的信任度，公式如下：

(7)

其中：β的取值范围是[0,1],该值表示局部信任度所占的比重,β的值越大,说明在整个网络中，用户之间的局部信任成为主要的因素，用户有很强的主观意识，而被信任人的个人影响力因素减弱，β最终的取值可以通过实验数据观察得出，将最后得到的信任度存入矩阵T中。

2.3 不信任关系矩阵的获取

对于不信任矩阵的获取问题，由于不信任关系与信任关系不同，其不具有很强的可传递性，不信任关系的扩展问题一直是一个难点，目前无法合理地计算其不信任度，根据文献[16]中提出的敌人的敌人是朋友的可能性往往较大，并且这种思想传递的路径长度也十分有限，因此为了简化本文的计算，本文只考虑到敌人的敌人是朋友这样一种情况，并且传递路径长度只计算2步，因此提出根据不信任用户之间的共同不信任邻居数来定义两个用户之间的不信任值，对网络子图G-中的两个用户u和v，如果两个用户之间的共同不信任邻居数越多，则他们之间的共同偏好可能相似，即他们之间的不信任度就会比较小，定义不信任度矩阵为D，则两个用户之间的不信任度计算公式如下：

(8)

其中：O(u)表示用户u的不信任邻居数，O(u)∩O(v)表示两个用户之间的共同不信任邻居数，经过对不信任度的计算，得到两个用户之间的不信任度，将其存入不信任度矩阵D中。一个简单的不信任网络子图如图1所示。

图1 不信任网络子图

由式(7)的计算可以知道，用户u和用户v之间的不信任度为1-2/3=1/3，根据敌人的敌人是朋友这样一个理论，用户u和v之间共同敌人越多，则其是朋友的可能性越大，即两者间的不信任度越小。

2.4 用户间兴趣相关性度量

用户对某个项目的评分在某种程度上代表了用户的兴趣，但仅仅依靠项目评分来并不能准确定义用户的兴趣。可以这样假设如果两个项目之间的关联度高，那么同时对这两个项目进行评分的用户之间的兴趣相似性就大，因此本文提出一种结合项目间的关联度来量化用户间兴趣相关性的方法，根据文献[17]的描述可以知道在数据挖掘中的项目的支持度(Support)和置信度(Confidence)都可以在某种程度上反映出两个项目之间的相关性，支持度和置信度的计算公式分别如下：

Support(a,b)=(C(a)∩C(b))/|U|

(9)

Confidence(a,b)=(C(a)∩C(b))/C(a)

(10)

式(9)、(10)中：C(a)表示对物品i评分过的用户数,|U|表示评价过商品的用户总数，可以看出支持度是从全局的角度出发来评估项目之间的关联性，而置信度是从局部的角度来评估的，因此，与计算信任度的方法类似，本文考虑将这两者结合起来，定义一个阈值ω，来均衡两者的比例，具体的计算公式如下：

(11)

其中阈值ω的表示项目支持度占的比重。若ω=0则表示物品间的置信度就是两个物品间的关联度，随着ω的增加置信度占的地位越来越大。其中ω的取值根据文献[18]可以知道当ω取100时得到的效果是最好的，本算法得到了两个项目之间的关联相似性之后，根据如果两个用户对两个相似物品有相似的评分，则表示这两个用户之间的兴趣相似性大，因此定义两个用户之间的兴趣相似性公式如下：

(12)

2.5 正则化推荐模型

(13)

同样地，在不信任网络中，两个不信任用户之间的隐特征向量之间的距离应尽可能地大，将用户之间的不信任矩阵和兴趣不相似度(1-In(i,k))同时作为权重，其公式如下：

(14)

本文结合式(12)和式(13)构造关于隐特征向量Ui的正则项，表达式如下：

(15)

矩阵分解过程中的主要目的就是求出特征矩阵U和V，通过将上一步构造的正则项融入矩阵分解的过程中，得到矩阵分解的损失函数如下所示：

(16)

其中:第二项和第三项是正则化项，防止矩阵分解过拟合问题，参数λ和α是控制正则化项影响的参数。

为了最小化式(15)的函数，本文采用基于梯度下降的优化方法，由于式(14)得到的值可能是非正的，导致目标损失函数的非凸性，因此本文定义了一个辅助的矩阵H∈Rm×k，在目标函数迭代优化的过程中，令迭代次数为n，如果Ψ(Ui)>0，令Hi=1；否则，令Hi=0，因此加入辅助矩阵之后的目标损失函数如下所示：

(17)

添加了辅助矩阵H之后，函数变成凸函数，因此可以使用梯度下降法来求解，矩阵U和矩阵V的迭代求解过程如下所示：

(18)

(19)

(20)

(21)

3 实验及评估

3.1 实验数据和评价标准

本次实验采用学术界普遍使用的Epinions数据集，该数据集中含有信任和不信任关系数据，本文对数据集进行了一次划分，选取了其中对商品评价个数大于10并且至少有一个信任关系的用户，经过筛选之后的Epinions数据集的统计情况如表2所示。

表2 Epinions数据集统计

可以看出评分数和社交关系的稀疏度都是非常高的，为了评估本文提出的方法的有效性，从数据集中随机选取80%的评分数据作为训练集，剩下的20%作为测试集，本文采用五折交叉验证的方法，取5次实验结果的平均值作为本实验的结果。由于本文提出的正则化推荐模型是为了提高推荐的准确度，因此采用平均绝对误差(Mean Absolute Error, MAE)和均方根误差(Root Mean Square Error, RMSE)来作为实验的评估方法：

(22)

(23)

式(22)、(23)中‖K‖表示测试集中用户-商品的评分数量，RMSE和MAE的值越小表示推荐的效果越好。

3.2 超参数对实验的影响

在本文提出的方法中，求解用户的全局信任度时，一般取d为0.85，ω取100；参数β表示局部信任所占的比重，表示在计算用户的全局信任和局部信任的重要性；参数α表示信任和不信任关系的正则项，表示用户的社交关系在推荐中的地位；参数λ表示用户-商品矩阵的正则项系数；参数η表示梯度下降求解过程中的学习速率。在验证参数某个参数对实验的影响时固定其他参数，下面经过实验得出最优的α、β、λ和η的值,各个参数的实验结果如图2所示,下面依次对各参数的实验结果作进一步的分析。

图2 不同参数值对推荐准确度的影响

1)确定局部信任所占的比重β。

局部信任所占的比重β表示了在信任矩阵度量时全局信任和局部信任各自的重要性，在实验中本文将参数β的取值设置在0.1～0.9，以0.1为步长，记录推荐结果的RMSE值随β取值不同的变化情况。结果如图2(a)所示。

从图2(a)中可以看出，当β取0.3时得到的结果最好，说明在计算用户信任度的时候，用户的全局信任占主导地位，分析其原因就是用户之间的信任关系数据稀疏，用户只能更多地依靠其自身影响力来决定用户的信任度，因此全局信任度占的比重较大。

2)确定正则项系数α。

社交关系正则化项系数α表示信任和不信任关系对矩阵分解的影响程度，当α=0时相当于基本的矩阵分解模型，本文设定α的取值范围为0.1～0.9进行实验。

从图2(b)中可以看出，当α取值较小时，推荐的误差较大，随着α取值的增加，推荐误差逐渐减小，当α=0.5时到达一个最小误差值，再次增加α的值，误差再次增加，分析其原因就是α取值过小说明社交关系的在推荐中的作用小，则由于评分数据稀疏性，则误差大，α取值过大说明用户的社交关系所占的比重超过了用户的偏好所占的比重，则用户偏好数据没有被合理地利用，也会导致误差过大。

3)确定参数λ。

参数λ的作用是防止模型的过拟合，在实验中λ的取值分别为0.000 01，0.000 1，0.001，0.01，0.1，记录推荐结果的RMSE随λ取值的变化情况，如图2(c)所示。从图2(c)中可以看出，当λ取0.001时误差最小，分析其原因就是当λ取值过小时，整个模型是欠拟合的，取值过大时，导致了整个模型的过拟合。

4)确定步长η。

步长η表示在梯度下降过程中的学习速率，η的值过大或过小都会导致最后求得的结果的不准确，在实验中同样取η的值为0.000 01，0.000 1，0.001，0.01，0.1，结果如图2(d)所示。从图2(d)中可以看出当η取值为0.000 1时效果最好，可以明显看出当步长取值过大时，误差较明显，因为此时结果可能无法收敛到一个稳定值，因此在求解过程中应当选择合适的步长。

3.3 对比实验

为了更好地验证本文提出的算法的有效性，本文选取了以下四种对比算法：SocialMF[19]、SoRec[4]、TrustMF[6]、CTRPMF[8]、RecSSN[20]，通过之前的实验分析可知当正则化系数λ=0.001，步长η=0.000 1，社交网络正则项系数α=0.5，全局信任的比例β=0.3时，算法有最好的推荐效果，因此本文的参数依此取值，用户及项目的特征向量的维度均取10，算法的对比实验结果如表3所示。

表3 不同算法MAE和RMSE对比

从表3可以看出，本文提出的融合信任和不信任网络正则化推荐模型相比其他算法在推荐准确度上有所提高，分析其原因如下：SocialMF、SoRec算法和TrustMF算法仅仅考虑了用户间的信任关系，而忽略了用户间的不信任关系；CTRPMF算法只是简单地利用不信任关系对信任关系进行修正，对信任关系进行了简单的扩展，并未考虑全局和局部因素，而且也未对不信任关系作出评估；RecSSN算法没有考虑用户间兴趣相关性的影响。本文提出的算法在扩展用户间的信任关系时同时考虑到了用户间的信任和不信任关系，缓解了社交关系稀疏的问题，另一方面利用信任和不信任关系为用户-物品的隐特征矩阵提供了更多的约束条件，同时还考虑到了用户间的兴趣相关性作为约束，因此本文提出的算法有更好的推荐精度，其中RMSE值降低了1.1%～9.5%，MAE值降低了2%～10.1%。

4 结语

传统的基于社交关系的推荐系统面临着社交关系数据稀疏的问题，同时没有考虑到用户间的不信任关系对推荐结果的影响，因此本文提出一种在矩阵分解模型中融入用户间的信任和不信任关系的正则化推荐模型，通过不信任关系度量信任值改善了社交关系稀疏的问题，然后结合矩阵分解技术改善了用户评分数据稀疏的问题；但是随着数据量的增加，推荐需要的开销大、计算时间长，推荐的可扩展性成为了一个亟待解决的问题，因此本文下一步考虑如何利用信任和不信任关系进行更合理的聚类，减小计算开销。