基于用户多维度信任的冷启动推荐模型

何 利，胡 飘

(重庆邮电大学 计算机科学与技术学院， 重庆 400065)

0 引 言

大数据时代带来的信息过载问题日渐突出，使得人们从海量信息中找到对自己有效的信息变得愈发困难。推荐算法(recommendation algorithm,RA)是有效解决信息过载问题的重要方式，而且与人们的日常生活息息相关。推荐算法是指应用知识发现技术产生个性化推荐，从而帮助用户在大量的文章、产品、电影、音乐、网页等中筛选出有用的信息[1-2]。

协同过滤(collaborative filtering ,CF)[3]是推荐算法中整体性能最佳的技术之一，与传统推荐算法相比，其使用用户的历史交互信息得出用户的兴趣偏好信息，从而为用户给出推荐，可以避免由于不完全或不精确特征抽取而产生的不准确推荐[4]。当用户评分信息较少时，传统协同过滤却面临推荐服务质量低的问题，即用户冷启动(cold start)、数据稀疏(data sparsity)问题[5]。

围绕用户冷启动问题，近年来引入用户的辅助信息来缓解冷启动问题的方法得到了诸多学者的广泛研究。这些辅助信息包括统计信息[6]、会员信息和社交信任[7-8]等。其中，由于社交信任信息比会员信息和统计信息等更加可靠和明确，所以，引入信任信息已然成为目前解决用户冷启动问题的有效手段之一。该类方法在一定程度上缓解了传统推荐系统中的数据稀疏和用户冷启动等问题，提高了推荐算法的准确性；但现有的基于信任的推荐技术多数仅简单使用用户的二值信任来寻找可信好友，未考虑用户间信任传递问题以及用户间隐含的信任信息，使得用户间信任估计精度低，导致对冷启动用户的推荐质量不高。

1 相关工作

目前，引入信任关系是解决协同过滤中用户冷启动问题的有效手段，并且已经取得部分成果：在采用聚类分析和概率矩阵分解方法来利用引入的信任信息方面，Moradi等[9]将用户评分相似作为用户间的信任值，并结合用户的社交拓扑图对用户进行K-Means聚类分析。而Ullah等[10]和Guo等[11]采用社区检测聚类算法，通过用户兴趣对用户信任进行加权，使多个初始簇中拥有较高用户兴趣和信任相似的用户分配到同一社区聚类中。Guo等[12]提出一种结合信任的多视图聚类的方法，从评分和信任这2个关系视图对用户进行K-Mediods交叉聚类来扩大冷启动用户的邻居集，从而在一定程度上缓解了用户数据稀疏的问题。该类方法并未考虑信任传递的方向性对用户信任的影响以及忽视了用户在社交关系中存在的信任信息、用户对间接用户信任强度的差异。

潘一腾等[13]和Zhang等[14]通过贝叶斯概率矩阵分解(Bayes probabilistic matrix factorization,BPMF)社交信任矩阵，并利用梯度下降法得到信任关系隐含相似度，放大用户间信任程度细微的差异，从而选出更加可信的邻居好友。Li等[15]则采用矩阵奇异值分解(singular value decomposition,SVD)和信任传播相结合的方法来最大化地挖掘评分信息和信任信息中的潜在有效信息，提高冷用户的推荐质量。为了解决传统矩阵分解无法建立潜在因素与项目显示属性间的关联关系，Zhao等[16]提出一种混合矩阵分解(hybrid matrix factorization,HMF)方法，通过结合隐式和显示属性并利用显示属性间的关联关系对因素矩阵进行约束，缓解矩阵分解中的过拟合问题。但由于矩阵分解采用的是数据降维处理，当矩阵数据甚少时，矩阵分解难以得到更加准确的隐含信任关系甚至会使仅有的有效信息丢失。

在信任传播寻找用户的邻居好友方面，Massa等[17]提出的moletrust模型利用信任传播理论评估信任的手段，提高了引入信任网络进行推荐的准确性和覆盖率。Guo等[18]提出一种“融合”[14]方法，将评分信息和社交信任值有效整合，并在信任传播中运用六度空间理论有效缩小了信任传播的路径长度，提高信任传播的传播效率。Ma等[19]和Lee等[20]考虑到不可信任传播的存在，通过在传统社会化推荐算法[13]中加入不可信任关系矩阵，并基于奇异值分解的聚类算法来处理信任和不信任关系矩阵，以使冷用户更容易发现信任社区[10]。但不可信任信息较二值信任信息更难获取，并且信任与不可信任关系存在着重叠的可能性，这也会使部分用户的信任估计被放大导致相似计算准确度较低。Kalaï等[21]和Liu等[22]则基于专家协商机制，通过设置某个信任阈值，检测不同层次好友中的最值得信赖的好友或专家的信任级别，并使用好友或专家的历史信息为用户提供服务推荐。该方法在一定程度上可以减少冷用户匹配好友群或专家群的时间，但也可能使用户的直接信任好友被忽视，用户间的信任估计较片面。

上述研究并没有考虑到用户信任关系的复杂性以及信任信息的丢失问题，尤其是没有从多方面考虑影响用户信任的因素而仅从单一维度衡量用户信任，导致用户间信任计算精度低的问题。

针对冷用户信任度计算问题[23]，本文通过深入分析用户在社交网络中的信任机制[24-25]，用户信任关系必须含有直接信任关系和间接信任关系，并且用户信任受所处社交网络中的局部和全局因素的影响。本文从多角度考虑影响用户信任的隐含因素，提出一种多维度信任度量模型，得到用户综合信任，将用户综合信任按照一定的权重与用户评分相似进行有效融合得到基于用户多维度信任的冷启动推荐算法(user multidimensional trust-based cold-start recommendation algorithm,UMTCRA)，通过提高用户综合相似精度来提高对冷启动用户推荐的质量。

2 多维度信任度量模型

用户间信任度量的准确度会影响基于信任的协同过滤算法对冷启动用户的推荐质量。信任度量越准确，协同过滤算法对冷启动用户的个性化服务质量就越高；否则就难以保证对冷启动用户的高质量推荐。本文提出的多维度信任度量模型中，用户信任包括间接信任和直接信任，并且从信任传递的方向性和用户的全局声望2个维度量化分析其对用户信任的影响。由此，本文得到用户的局部可被信任概率和全局可被信任概率；并分别使用局部可被信任概率和全局可被信任概率对直接信任和间接信任进行线性加权处理，得到用户的综合信任度。

用户间的信任度指一个用户对另一个用户的信任程度，同时信任度分为直接信任度和间接信任度。图1表示目标用户U1所处社交网络中用户间的信任关系，其中，节点U1-U2代表用户，图1中的有向边表示用户间存在着直接信任关系，且箭头所指的用户为该信任关系中受托人(Trustee[7])，与箭头尾部连接的用户为该信任关系中的信托人(Truster[7])。

图1 用户间的信任关系Fig.1 Trust relationship among users

2.1 直接信任度

直接信任度Dt(u,v)表示存在着直接信任关系的用户u和用户v之间的信任度。如图1中用户U1和用户U2间的信任度即为直接信任度。在本文中，直接信任值由用户的社交信任数据转换得到，构成用户间的有向邻接矩阵UU。表1表示由图1中的用户信任关系转换得到的用户间的有向邻接矩阵。在表1中，数值0或1表示用户间是否存在着直接信任关系，如用户U1与用户U2存在直接信任关系，故Dt(U1,U2)=1；用户U1与用户U4不存在直接信任关系，故Dt(U1,U4)=0。其中，用户是相信自己本身，故对角线值应该为1。

表1 有向邻接矩阵

2.2 局部可被信任概率

信任度量局部可被信任概率l(u,v)表示当用户u和用户v间存在直接信任关系时，用户v被用户u直接信任的概率，即用户u直接信任用户v的概率。Jaccard相似系数可计算存在直接联系的用户间的局部可被信任概率，但未考虑用户间信任的非对称性。因此，本文的局部可被信任概率由两直接联系用户的共同直接好友数占信托人好友总数的比例得到。为避免两直接联系的用户间的局部可被信任概率为零导致用户间信任值可能为零的问题，本文假设用户本身也是自己的一个好友；故本文的局部可被信任概率被定义为

(1)

(1)式中：Fu表示用户u的直接信任好友；Fv表示用户v的直接信任好友；Fu∩Fv表示用户u和用户v的共同直接信任好友。

2.3 间接信任度

间接信任度IDt(u,v)表示若用户u和用户v间存在着可达路径，如path=(u,m1,m2,…,mn,v),其中，m1,m2,…,mn表示该可达路径的中间用户，且可达路径的长度d至少为2时，则称用户u和用户v间存在的间接信任关系，用户u和用户v间的信任度为用户的间接信任度。依据社交网络中的信任传播与信任机制的相关研究可知，用户间的信任强度会随着传播路径的增长而衰减，即用户间的间接信任与可达路径的长度成反比关系。本文利用如下公式计算用户间的间接信任度

(2)

当用户与邻居用户存在着多条可达路径时，用户间的间接信任度为

(3)

(3)式中：N表示用户u与用户v的可达路径的总数目。

2.4 全局可被信任概率

全局可被信任概率g(u,v)表示用户v在目标用户u所处的信任关系图中可被其他用户信任的概率。依据社会学中有关声望机制的研究可知，在某个社会群体中，若一个人被信任的次数越多，其被其他人信任的概率越大；那么在某信任关系图中，一个用户的信任入度(信任该用户的用户数目)越大，则其可被信任的概率也就越大。因此，用户v全局可被信任概率为

(4)

2.5 用户综合信任度

如上所述，本文将用户信任分为直接信任和间接信任，并针对用户在直接信任关系和间接信任关系中处于信任关系图中的局部与全局位置，提出用户在信任关系图局部与全局可被信任的概率。故利用局部可被信任概率和全局可被信任概率分别对直接信任与间接信任加权融合，用户u对用户v的综合信任度为

T(u,v)=l(u,v)·Dt(u,v)+g(u,v)·IDt(u,v)

(5)

3 UMTCRA

3.1 用户评分相似度计算

由于冷启动用户评分的项目数甚少，直接使用用户的评分数据来计算用户评分相似准确度低。故本文从计数、占比、均值、加权等角度分析用户-项目矩阵UI中的评分数据，提取出每个用户的行为特征。据此得到每个用户的特征向量，如F1=(f11，f12，…,f1n)表示用户1的n维特征向量(其中，f11等表示前面提取出的行为特征值)，最终获取到m个用户的特征向量集合F={F1,F2,…,Fm}。据此，用户u与用户v的评分相似度为

(6)

(6)式中，(fu1，fu2，…,fun)和(fv1，fv2，…,fvn)分别表示用户u与用户v的n维特征向量。

3.2 评分信息与信任信息的融合

由于用户评分相似与社交信任都能在一定程度上反映出用户间的行为偏好相似，所以，本文将得到的综合信任度和用户评分相似进行线性加权融合，得到用户间的综合相似度为

CS(u,v)=α·T(u,v)+β·S(u,v)

(7)

(7)式中：CS(u,v)为用户间的综合相似度；α，β分别表示T(u,v)和S(u,v)的权重系数，且满足α+β=1。

3.3 评分预测

(8)

(8)式中，r(v,i)表示用户v对项目i的真实评分。

3.4 算法描述

UMTCRA算法主要针对冷启动用户做出个性化推荐，该算法的实现过程主要分为5个步骤：①用户综合相似计算；②用户评分相似计算；③用户综合相似计算;④最近可信邻居选择;⑤评分预测。以下为该算法的具体实施步骤。

输入：目标用户u,其他用户v，有向邻接矩阵UU，用户-项目矩阵UI，用户特征向量集合F，最近可信邻居集合TNu，可信邻居好友的个数k；

步骤1依据有向邻接矩阵UU，采用公式(5)计算用户u与v的综合信任度T(u,v)；

步骤2依据用户-项目矩阵UI提取得到的用户特征向量集合F，采用公式(6)计算用户u与v的评分相似S(u,v)；

步骤3对步骤1和2得到的T(u,v)和S(u,v)，采用公式(7)得到用户u与v的综合相似度CS(u,v)；

步骤4对步骤3得到的CS(u,v)进行从高到低排序，选择相似性最大的前k个用户作为目标用户u最近可信邻居好友TNu；

4 实验

4.1 实验数据

实验使用Epinions(http://www.epinions.com)真实数据集对本文提出的方法进行验证。epinions是一个大众消费点评网站，用户可以在该网站上通过评分表达自己对物品的喜好程度，也可以将其他人添加到自己的信任列表中作为好友。Epinions数据集包含用户对项目的评分信息和用户信任列表中的信任关系信息，其中，用户评分是从1到5的整数评分，信任值是0或1(1表示信任，0表示不信任)。关于该数据集的具体信息如表2所示。

表2 Epinions数据集信息

从Epinions数据集的统计信息中可以看出，该数据集数据量大且非常稀疏。如图2，图3所示，在该数据集中，冷启动用户[17]有16 910个，占整个用户数的34.3%。其中，大部分冷启动用户的直接信任好友数和评论过物品数非常少，冷启动用户集的数据极其稀疏。综上所述，该数据集完全符合本实验对冷启动用户推荐效果验证的要求。

本文采用评估预测中广泛使用的留一法对数据集进行划分并预测评分，即保留冷用户的一条评分信息，用其余的所有信息预测该评分。故测试集为所有保留一条评分信息的冷用户，训练集为非冷启动用户以及剔除一条保留的评分信息后的冷用户。

图2 拥有不同直接好友数的冷用户的数目Fig.2 Number of cold users with different direct friends

图3 不同已评项目数的冷用户的数目Fig.3 Number of cold users with different rated items

4.2 评估指标

1)实验采用平均绝对误差(mean absolute error,MAE)作为评估预测评分与真实评分接近程度的重要指标，该指标在大多数研究中被采用。

(9)

2)评分覆盖率(rating coverage, RC)可以评估预测出的评分数占测试集评分数的比例为

(10)

(10)式中，M和N分别表示预测出评分的项目数与测试集中已评分的项目数。

3)鲁棒性(F-measure,F1)通过综合考虑评分准确度和评分覆盖率来评估推荐方法的整体性能平衡性和稳定性。评分准确度iMAE和F1分别为

(11)

(12)

4.3 实验结果对比分析

为评估本文UMTCRA算法对冷启动用户的推荐效果，将Epinions中的所有冷启动用户作为实验的测试数据集。在通过信任传播寻找冷启动用户的可信好友时，为了避免无意义的搜索和减少计算开销，将可达路径d的最大值严格设置为3。同时，在选取冷启动用户的最近可信邻居用户时，为了便于对参数α的调节和由于d的严格控制导致评分预测时有效可信邻居用户的数目较少，因此，实验不对k进行设置，直接使用所有相似用户作为目标用户最近可信邻居用户。

实验1(α的选择)。因为α+β=1，所以仅需通过调节α或β的值来验证UMTCRA算法的性能。由于本文通过融合用户的评分信息和信任关系信息来缓解冷启动用户的数据稀疏问题，单独使用评分信息或信任关系信息对冷启动用户进行推荐很明显会使冷启动用户再次面临原有的数据稀疏问题。因此，实验将α的初始值设置为0.1，最高取值为0.9，且α以0.1为增量逐级递增；α的值越大表明基于用户信任预测的评分值的占比越大。

通过实验得到α分别对UMTCRA算法的评估指标MAE，RC，F1的影响，如图4—图6所示。其中，图4显示随着α的增长，MAE整体呈现先增大后减小，并且当α取值为[0.1,0.4]时，MAE值的上下波动较为明显，尤其，α取值为0.2时，该算法的平均绝对误差最小；而当α取值为[0.4,0.9]时，MAE值波动较为平稳。图5显示RC随着α的增长整体呈现先增大后减小，在α取值为[0.2,0.7]时，RC值较为平稳，其中，当α在[0.2,0.5]时，该算法有最好的覆盖率；图6显示，F1随着α的增长整体呈现先增大后减小，当α取值为[0.1,0.3]时，F1值上下波动较为明显，α在[0.3,0.7]时,F1值波动较为平稳，且在[0.4,0.55]时有最好的稳定性。综上所述，当α取值为0.5时，该算法表现出最佳的推荐效果。除此之外，实验结果表明，当用户综合相似度中的权重分配过于偏向综合信任和评分相似时，算法推荐性能不稳定，所以在对冷启动用户预测评分时需要平衡俩者之间的权重，也说明人们与其信任的好友和评分相似的邻居之间的偏好相似程度相当。

图4 权重系数α对MAE的影响Fig.4 Influence of weight coefficient α on MAE

图5 权重系数α对RC的影响Fig.5 Influence of weight coefficient α on RC

图6 权重系数α对F1的影响Fig.6 Influence of weight coefficient α on F1

实验2(不同算法推荐效果对比)。为了验证本文提出的UMTCRA算法对冷启动用户的推荐效果，在所有冷启动用户作为测试数据集下，与以下3种方法进行比较分析：UBCF(user-based collaborative filter)，Mole(moletrust)和Merger3[18]。其中，UBCF为使用Pearson系数计算用户相似的传统协同过滤算法，相似度阈值设置为0；Mole为MoleTrust信任增强模型的实现算法，在信任网络中信任传播的长度设置为3，仅将被信任的邻居用于项目的评分预测；Merger3为Guo等[18]提出的针对用户冷启动推荐的方法，信任传播的长度设置为3。最后，UMTCRA算法中的α为0.5。

通过实验得到UMTCRA与其他3种方法对冷启动用户推荐的对比结果，如图7所示。在这4种方法中，除UBCF仅使用评分信息寻找最近邻给用户做出推荐外，其他3种方法均引入了用户的信任关系信息。由于引入了用户间的信任关系，除UBCF外的3种方法均可以在一定程度上缓解冷启动用户的数据稀疏问题，并且在冷启动用户集中相比UBCF有着明显的提高。从实验结果中可以观察到UMTCRA在MAE方面，MAE值越低表明算法预测出的评分与真实评分的误差越小，算法评分预测越精确。图7中， UBCF算法的MAE值最低，后3种算法的MAE明显降低；其中，本文的UMTCRA的评分误差最低，相较于Merge3的评分绝对误差减少了6.29%，表明本文算法提高了对冷用户进行评分预测的准确度；在RC方面，RC越高表明预测出的评分数占测试集评分数的比例。如图7所示，4种算法的评分覆盖率依次升高，UBCF评分覆盖率最低，本文算法的评分覆盖率最高，且为87.05%，相较于Merge3的52.66%显著提高了34.39%，表明本算法在对冷用户的推荐面更广；在F1方面，F1越高表明算法的稳定性越好，能越好地对冷用户进行个性化推荐。如图7所示，4种算法的F1逐渐提高，其中，UBCF的推荐性能最低，后3种算法较UNCF有了明显提高，并且本文算法相对于Merge3算法在F1上提高了32.12%，表明本文算法在对冷用户推荐上的稳定性更好。因此，本文提出的UMTCRA在冷启动用户集下的推荐效果优于其他对比算法。

图7 不同推荐算法的实验结果对比Fig.7 Comparison of experimental results of different recommendation algorithms

5 结 论

引入信任关系是目前解决传统协同过滤算法中用户冷启动问题行之有效的方法，而仅使用二值信任或仅从单一方面估计用户信任大大降低了信任估计的准确度，导致对冷启动用户的推荐效果不佳。鉴于此，本文提出多维度信任度量模型用于量化用户信任，该模型以用户的直接信任和间接信任为信任估计的基础，考虑用户在信任关系图局部非对称信任和全局声望对用户信任的影响，得到用户的综合信任度；并将其与传统协同过滤中的用户评分相似线性融合。试图通过提高用户信任估计的准确度来提高算法对冷启动用户的推荐质量。实验表明，该算法提高了对冷启动用户的推荐精度和覆盖率，整体性能表现稳定，明显改善了对冷启动用户个性化推荐的质量。本文在计算用户信任时，未考虑到时间因素对用户间信任关系的影响，用户间的信任值会随着时间发生波动。因此，引入时间函数到信任度量中提高用户间信任估计的准确度将是我们未来的工作。