融合信任传播和混合相似性度量的推荐算法

杨 磊，刘美枝

(山西大同大学物理与电子科学学院，山西大同 037009）

协同过滤(Collaborative Filtering,CF)是最成熟、应用最广泛的推荐算法之一，它可以分为基于模型的方法和基于内存的方法。但是协同过滤算法的信息源仅仅来自用户评分矩阵，而用户评分的项目数量比较少，甚至用户从未对任何一个项目进行过评分，会导致稀疏性和冷启动问题。近年来，为了解决稀疏性和冷启动问题，学者们致力于挖掘额外信息建立训练模型，比如将社交网络信息融入推荐模型，尤其是信任关系。

1 相关工作

经典的信任模型有TidalTrust 模型[1]和Mole-Trust 模型[2]，此外，Ma H 等提出一种基于矩阵分解的协同推荐算法RSTE，将用户信任关系融合到概率矩阵分解模型中，充分利用用户之间的信任值来训练用户特征向量[3]；Jamali 等在基于项目的协同过滤算法基础上融合信任关系，提出随机游走(Trust Walker)推荐策略，随后又在矩阵分解的社交推荐模型的基础上，引入了信任传播，提出了SocialMF 模型，可以有效缓解冷启动问题[4]；Ma H 等同样基于概率矩阵分解，结合用户社交与用户评分信息，提出SoRec 模型[5]；Yao 等结合显性和隐性交互信息，提出RoRec 模型[6]；Qian 等提出一种结合用户兴趣和社交圈的个性化推荐算法，将个人兴趣、人际兴趣相似性、人际交互三个社会因素融合起来，用于解决冷启动和数据稀疏问题[7-8]；Qu 等将知识图谱和图神经网络引入到社交网络中，提出KNI模型[9]；Wang 等提出一种用于个性化推荐的深度联合神经网络，用以解决隐性反馈的推荐问题[10]；Guo等将显性信任和隐性信任融合到SVD++中，提出TrustSVD 模型[11]；鲜征征等在TrustSVD 的基础上引入差分隐私保护技术，提出DPTrustSVD 算法[12]；Wang 等从社会学角度出发，研究信任关系的发展规律，提出SocialTrust 模型[13]；Zheng 等在推荐系统中引入超图拓扑结构，提出HMF 模型[14]；陈玲姣等将用户信任关系引入到基于扩散的推荐算法中，提出一种基于信任关系的资源分配算法[15]。上述推荐算法中，有利用局部、全局相似度提高推荐性能的，也有利用信任传播挖掘用户隐性信任关系的，但是没有将信任传播和混合相似度同时融合到算法中。

在社交网络推荐算法的基础上，提出一种融合信任传播和混合相似性度量的推荐算法(Recommendation Algorithms for Fusion Trust Propagation and Hybrid Similarity Measurement,TPHS)，利用信任传播机制，预测缺失信任值，完善用户之间的信任网络，进而克服信任矩阵的稀疏性和冷启动问题；利用混合相似性度量，更好地描述用户之间的相似性；综合考虑用户之间的信任关系和相似性关系，进行预测评分，得出推荐列表。

2 算法描述

2.1 社交网络

在推荐系统中引入社交网络和信任关系能够有效缓解稀疏性和冷启动问题，如图1(a)所示社交网络，每个节点代表一个用户，每条有向边代表信任关系。在信任矩阵中T=[Tu,v]N*N，Tu,v代表用户u对用户v的信任值为value，其中value∈[0,1]。需要注意的是，信任关系是单向的，即信任矩阵是非对称的，如图1(b)所示。

图1 社交网络

推荐系统中的信任关系包括显性信任和隐式信任，通常将数据集中明确表明某用户对其他用户的信任值称为显性信任，如Epinions 数据集，用户u将对其他用户的信任值添加到自己的信任列表中，但是对于没有信任关系的数据集，如Movielens 数据集，可以通过评分矩阵计算其信任关系，将直接通过评分矩阵计算的信任值称为显性隐式信任；而隐性信任是在指在数据集中没有明确表明或者通过计算显性隐式信任依然缺失的信任关系，但可以通过信任传播推导出来，以弥补信任关系无法获取或稀疏的问题。

对于没有信任关系的数据集，计算显性隐式信任值是基于一个假想：用户u和用户v共同评价过的项目越多，且对于同一项目i，用户u对其评分rui与用户v对其评分rvi的差值越小，表示用户u与用户v具有越高的兴趣相似度，用户u和用户v之间的信任关系越强[16]。利用用户评分矩阵，可以计算用户之间的显性隐式信任值Tu,v，其计算公式如下：

其中，Iuv表示被用户u用户v共同评分过的项目集，L 代表评分矩阵中评分最大值与最小值的差值，比如Movielens 数据集中最高评分为5，最低评分为0，那么L=5。

但是Tu,v没有考虑用户的活跃度以及共同评分项目的数量，用户活跃度是指用户评分过的项目数量，比如，用户u是一位批发商，其活跃度很高，而用户是一位普通用户v，活跃度较低，用户u、用户v与用户w共同评分过的项目都为1，且评分差值相同，那么按公式(1)计算信任关系时，Tu,w和Tv,w的值相同，但这显然是不合常理的，在此引入基于用户的Jaccard加权相似性度量，将公式(1)改进为：

其中，Iu和Iv分别表示被用户u和用户v评价过的项目集。

评分矩阵本身具有稀疏性，当用户之间不存在共同评价过的项目时，就无法计算用户之间的显性隐式信任值，则社交网络中信任关系也存在着稀疏性问题，为了能够进一步挖掘用户之间的信任关系，基于信任关系具有传递性的特性，在此引入信任传播机制。

2.2 信任传播机制

信任传播理论是基于一种假想：假如用户a（源用户）信任用户b（中间用户），用户b信任用户c（目标用户），那么用户a在某个程度上信任用户c，即信任可以传播[16]。如果源用户到目标用户之间存在多个中间用户，即存在多跳路径，在此，先定义一下信任传播跳数。

定义1 信任传播跳数k。在社交网络中，任选两个用户作为源用户和目标用户，从源用户传播信任到目标用户所经过的跳数，记为k。

在图1所示社交网络中，从用户u1到用户u3需要两跳，而从用户u1 到用户u5 需要三跳。对于信任多跳传播，需要一种聚合方法来计算源用户对目标用户的信任值，常用的信任路径聚合方法有：最大值，最小值和平均值。考虑到不同信任传播跳数对信任传播的贡献不同，所以采用加权平均聚合的方法，对于任意用户a,b,c∈U，用户a对用户c的隐式信任值为：

其中，Na表示用户a到用户c的中间用户的集合，且∈[λ,1]，表示用户a对用户b的显性隐式信任值，参数λ∈(0,1]是可调信任阈值；一般认为近距离信任传播比起远距离传播应该分配更高的信任分值，在此引入路径权值，αk表示传播路径的权值，其中，kMAX表示信任传播的最大跳数。例如，如果kMAX设置为3，则信任关系最远传递距离为3跳，那么，如果源用户到目标用户的路径为两跳，则α2=(3-2+1)/3=0.667，如果源用户到目标用户的路径为三跳，则α3=(3-3+1)/3=0.334。

2.3 混合相似度

推荐算法一般根据用户的历史评分数据计算用户相似度，找到与目标用户相似度较高的邻居用户并产生预测值。在计算用户相似度时，综合考虑以下三个方面：①用户对同一项目的评分时间间隔，引入时间衰减函数f(t)；②项目的活跃度。一般认为，活跃项目对相似度的贡献应该小于不活跃的项目，引入活跃度衰减因子，对活跃项目进行惩罚；③用户对共同评分项目的评分差值。一般认为，两用户共同评分的项目越多，且对同一项目评分差值越小，用户之间的相似度越高，皮尔逊相似度可以较好的反映用户评分差值对相似度的影响，所以采用皮尔逊相似度。综合考虑上述三个方面，用户u和用户v的混合相似度为：

其中，α∈[0,1]，是一个权重因子，λ是一个时间衰减调节因子，用于调节衰减速度，t表示用户u和用户v对同一项目评分的时间间隔，Iuv表示被用户u和用户v共同评价过的项目集，Iu和Iv分别表示被用户u和v评价过的项目集，rui和rvi分别表示用户u和用户v对项目i 的评分，分别表示用户u和用户v对所有评价过项目的评分均值，是基于时间衰减和活跃项目惩罚的相似度，是基于共同评分项目的评分差值的相似度。

2.4 加权评分预测与推荐

依据信任传播机制（即公式3），可以获取目标用户u与其他用户的隐式信任值，采用Top-n方法，选取隐式信任值最高的n 个用户作为最信任邻居集合NTrust。同样，依据混合相似性度量（即公式5），可以获取目标用户u与其他用户的混合相似性。由于计算混合相似性时，存在用户冷启动问题，所以采用相似性阈值法，即选取与目标用户的混合相似性超过一定阈值的用户作为最相似邻居集合NSim。然后利用下述公式进行评分预测。

3 实验结果与分析

3.1 数据集

实验采用的数据集是Epinions(来源于Epinions.com)和Movielens，评分数据均采用5 分制评分，数据描述如表1。

表1 数据集描述

3.2 评价指标

使用平均绝对误差(MAE)和均方根误差(RMSE)来计算评分预测准确性，并引入影响指标(Influence) 来优化参数设置，其值越小，表示推荐效果越好，计算方法如下式：

在衡量方案性能时，还需要用到召回率、准确率，其中召回率和准确率的值越大，说明推荐的效果越好。

3.3 结果分析

为了评价算法的性能，将提出的算法与以下几种推荐算法进行对比：

(1) RSTE：基于矩阵分解的协同推荐算法，在算法中融入了用户之间的显性信任关系，但是不考虑信任传播。

(2) SoRec：基于概率矩阵分解，结合用户社交关系与评分信息。

(3) SocialMF:基于矩阵分解的社交推荐模型，引入信息传播机制。

(4) TPHS：融合信任传播和混合相似性度量的推荐算法，即本算法。

3.3.1 TPHS 算法中参数调优

在计算用户混合相似度时，引入时间衰减调节因子λ和权重因子α，因此，需要调优λ和α。首先在Epinions 数据集中，设置λ=0.2，使α在0.0 到1.0 范围内以0.1为步长调优，实验结果如图2。从公式可5可知，当α=0 时，则用户相似度只考虑用户对共同评分项目的评分差值，此时的相似度为皮尔逊相似度；当α=1 时，则用户相似度只考虑用户对同一项目的评分时间间隔、项目的活跃度以及用户共同评分项目的数量。由图可知，当α=0.6时，影响取得最小值。其次，设置α=0.6，使λ在0.0 到1.0 范围内以0.1 为步长调优,实验结果如图3。从公式8 可知，当λ=0 时，f(t)=1，表示不考虑用户对同一项目的评分时间间隔因素，由图可知，当λ=0.3 时，影响取得最小值。

图2 参数α对TPHS算法的影响

图3 参数λ对TPHS算法的影响

根据实验结果，可以得出对比单一相似性度量，引入混合相似度和时间衰减因子对推荐效果有积极影响，因此，在下文所述实验中将α设置为0.6，λ设置为0.3。

3.3.2 推荐性能分析

实验1 推荐精度对比。为了评价评分预测的准确性，使用平均绝对误差(MAE)和均方根误差(RMSE)指标。实验中随机选取数据集中50%的数据当做训练集，其余50%当做测试集，然后进行不同算法的实验，实验结果为5 次实验的平均值，具体情况如表2。由表可知，本算法在推荐精度方面相较其他算法效果更好。

表2 不同算法的MAE和RMSE比较

实验2 算法对稀疏性的影响。为了评价推荐算法改善数据稀疏性能力，查看算法性能对训练数据的依赖程度，引入比例因子β，β是训练集占数据集的比例，如β=0.1，表示在数据集随机选取10% 的数据作为训练集，其余90% 的数据作为测试集，实验中，使β以0.1 为步长从0.1增长到0.9。图4 和图5 分别表示各种算法在不同比例因子下的召回率和准确率，横轴表示训练集占数据集的比例，纵轴分别为召回率和准确率。当β值越小，即训练集中的数据越少，评分网络和信任网络越稀疏，越符合冷启动的条件，从图中可知，提出算法TPHS 在β值较小时，召回率和准确率明显高于其他三种算法，比如在β=0.2 时，在Epinions 数据库中，召回率相较SocialMF、SoRec 和RSTE 算法分别提高了2.5%、4.1% 和4.7%，在Movielens 数据库中，召回率相较SocialMF、SoRec 和RSTE 算法分别提高了0.27%、1.28% 和2.44%；在Epinions 数据库中，准确率相较SocialMF、SoRec 和RSTE 算法分别提高了3.4%、6.7% 和6.9%，在Movielens 数据库中，准确率相较SocialMF、SoRec 和RSTE 算法分别提高了1.8%、3.1%、3.9%。而且随着β值，曲线的上升速率也略高于其他算法。也就是说在数据稀疏的情况下，提出算法TPHS 融合了信任传播和混合相似性度量，可以有效克服数据稀疏给推荐结果带来的负面影响，进而有更好的推荐性能。

图4 不同算法的召回率

图5 不同算法的准确率

4 结论

充分利用用户评分信息和社交信任关系，提出一种融合信任传播和混合相似性度量的推荐算法。主要思路为：首先，在社交信任网络的基础上，融入一种信任传播机制，有效解决社交信任网络稀疏性的问题；其次，在计算用户间的相似性时，采用混合相似性度量，综合衡量用户之间的相似性；最后在进行评分预测时，综合考虑用户之间的信任关系和相似性关系，进而给出推荐结果。实验结果表明，本算法在召回率和准确率性能方面明显优于其他算法，尤其是当训练集数据较少时，能够有效缓减稀疏性和冷启动问题。下一步工作将考虑信任传播的时间成本问题以及不同传播跳数对推荐性能的影响。