基于增强相似度和隐含信任的推荐算法①

郑 鹏, 王应明

(福州大学 经济与管理学院,福州 350108)

引言

互联网的高速发展以及电子商务的迅速崛起,有力地促进了推荐系统的研究发展. 其中,协同过滤(Collaborative Filtering,CF)推荐算法是推荐系统中应用最广泛、最成功的推荐技术之一[1]. 虽然协同过滤推荐算法取得了一些成果,但是它同时也存在数据稀疏性、冷启动和扩展性等一系列问题[2].

现实生活中,人们更愿意相信好友推荐的物品,因此推荐系统如果结合用户的信任关系信息,则能够进一步提高推荐精度. 随着在线社会网络的普及,利用社会网络中用户之间的信任关系来缓解传统协同推荐存在问题的信任感知推荐系统(TARS)成为推荐领域新的研究热点[3-5]. Massa等[6]提出使用信任度取代相似度的TARS系统,根据信任网络传播来估计一个信任度的权值,该方法增加了覆盖范围(可预测的评分总数),并未降低精确度(预测误差),但需要用户的显式信任声明. Yuan等[7]根据隐含信任网络的小世界特性,提出一种基于用户相似度的隐含信任感知推荐系统(ITARS),该方法虽然不需要用户提前对自己在整个信任网络中的信任关系做出声明,但是该方法需要根据用户之间的相似度构建隐含的信任网络,并估算信任网络的平均路径长度. 郭艳红等[8]提出以用户的评价个数和为他人提供推荐的次数为要素的可计算的信任模型推荐算法. 该算法改变传统推荐过程中,用户之间的相似度唯一决定预测结果的现状,提高了推荐的精度,但该算法无法对没有邻居的用户做出推荐. 杜永萍等[9]在传统基于用户的协同过滤推荐算法的基础上,引入信任关系计算,设计并构建一个集用户声望信任和用户局部信任的混和信任网络,实现了对协同过滤推荐算法稀疏性问题的优化,但该方法未考虑用户的全局信任值. 张俊等[10]提出一种融合用户兴趣相似性和评分相似性的协同过滤推荐算法,该算法引入兴趣度进行相似度计算,并通过引入专家信任度的概念对用户未评分项目进行评分预测填充,但该算法需要进行恶意用户检测,算法复杂度较大. 杨秀梅等[11]提出融合用户信任模型的协同过滤推荐算法,该算法考虑用户评分相似性和用户之间信任关系对推荐结果的影响,利用层次分析法实现用户信任模型的构建. 但该算法在计算用户信任度过程中引入信息过少,导致用户信任模型过于简单. 陈婷等[12]提出一种可信推荐模型(Trust-PMF),该算法首先结合全局信任和局部信任,利用信任的传播性质对信任关系进行建模. 然后,设置推荐权重,综合考虑相似度和信任度来构建用户间的偏好关系,筛选出邻居. 最后,将基于记忆的协同过滤思想和社交网络的信任关系融入概率矩阵分解模型,但该算法同样需要用户提供信任声明. 王瑞琴等[13]提出一种基于多元社交信任的协同过滤推荐算法,该算法借鉴社会心理学中的信任产生原理,提出基于多个信任要素的信任度计算方法,基于用户间的综合信任度选取可信邻居,完成对目标用户的个性化推荐,但该算法的时间复杂度较高. 针对上述问题,本文提出一种基于增强相似度和隐含信任的协同过滤算法(ETCF),在考虑用户兴趣度的同时,不需要用户提供显式声明,该算法不仅提高了推荐准确度和覆盖率,而且弥补了传统算法的不足,有效缓解了数据稀疏性问题.

1 基于增强相似度和隐含信任的协同过滤推荐算法

协同过滤算法的关键在于用户之间的相似度测量,但是由于数据稀疏性问题的存在,使得传统的相似度测量方法都存在着缺陷. 本文的基本思路是将传统的相似度度量方法和信任结合,采用增强的用户相似度和隐含信任来计算用户之间的相似度.

1.1 增强的用户相似度

计算用户相似度的方法有很多,比较传统的方法有皮尔逊相关(PCC)、受约束的皮尔逊相关(CPC)、均方偏差(MSD)和Jaccard相似度. 本文使用均方偏差和Jaccard相似度进行用户相似度的度量.

均方偏差(MSD)的公式如下：

JMSD相比传统的皮尔逊相关系数(PCC)、余弦相似(Cosine)、调整的余弦相似度(Adjusted Cosine)具有明显的优势,但是还是存在着一个问题,那就是没有考虑用户的评分偏好. 假如现在有三个用户,他们对四项物品的评分值分别为U1(4,3,3,4),U2(2,1,-,-),U3(4,2,-,-),这时候使用JSMD计算出的相似度,用户U1和U3的相似度小于U2和U3的相似度,这显然不符合实际情况,主要的原因就是没有考虑用户的评分偏好问题. 有的用户喜欢打高分,有的用户喜欢打低分. 考虑到这个问题,本文引入了一种偏好相似度,其公式为：

基于以上的情况,本文提出一种新的基于用户的相似性度量方法,公式如下：

1.2 隐含信任

在实际的数据集中两个用户之间可能不存在共同评分的项目,这种情况下使用传统的相似性度量方法显然不可行,本文引入信任机制来解决用户之间没有共同评分项的问题.

1.2.1 信任机制

信任在人们的日常生活中占据着举足轻重的地位,但它是一个相对模糊的概念,涉及到的方面很多,以至于至今都未能给出一个令人信服的定义. 虽然信任的定义难以确定,但目前信任有一些公认的特性,包括主观性、不对称性、传递性、动态性等,这些属性彼此之间是相互关联的,所以它们之间出现交叉或冲突等情况是正常现象

下文将给出本文对信任的定义.

定义1. 信任是指接受推荐者对提供推荐者特定行为的主观可能性预测,它是一种单向、相对、局限在一定范围内的主观反映.

定义2. 直接信任是指两个用户根据曾经直接交往的经验建立的信任关系.

定义3. 间接信任是指两个用户通过第三方的推荐建立的信任关系.

定义4. 信任度是根据用户所处的情境以及信任的属性,量化用户间信任程度后的信任值.

1.2.2 用户之间的直接信任

直接信任度来源于两个用户曾经交互的经验积累,本文的直接信任度通过活动用户相似度来度量,例如,如果用户a和用户b的相似度比较大,那么我们可以认为二者属于同一类,是可以相互信任的. 对用户的信任推导,我们使用JMSD,也就是说用户之间的直接信任度：

从中可以很容易的看出如果两个用户之间的共同评分项非空,二者之间的直接信任度非零,否则二者之间的信任度为零. 在现实生活中,人们之间的信任程度受到交互经验的影响,推荐系统中用户间的信任度也会随着项目交互结果的变化而逐渐变化. 本文根据用户评分的均值将用户评分分成两类,即积极评分和消极评分. 如果评分值不小于用户的评分均值就被认为是积极评分,相反则被认为是消极评分. 当用户u和v对项目i的评分同为消极评分或积极评分时,交互是成功的,反之是失败的：

公式中1表示交互成功,0表示交互失败. 交互成功和失败分别用sus和fal表示若交互成功则sus+1,否则fal+1. 结合了用户交互经验的直接信任度计算公式如下：

1.2.3 间接信任的计算

在社会信任网络中,当2个用户之间没有直接的信任关系时,就需要通过信任传播从信任网络中推断出用户之间的间接信任关系. 例如,假定用户a信任用户b,并且用户b信任用户c,通过使用信任传播矩阵,可以推导出用户a在某种程度上信任用户c,在中间用户多于一个的情况下,就需要使用信任聚合方法来合并不同的信任. 一般的信任聚合方法有： 最大值、最小值、均值. 其中加权平均聚合方法相比其他方法被认为具有更好的性能[15],加权平均聚合的基本思想是确保距离源用户比较近的信任路径上的信任值获得比较大的权值. 对任意的用户u,v,w,间接信任计算公式如下：

综合公式(8)和公式(9),可以得到两个用户之间的信任值,该信任值是通过评分矩阵计算得出来的,不同于TARS中用户的显式声明,被称为隐含信任. 表示为,公式如下：

1.2.4 选择邻居

对于邻居的选择过程,根据上一步计算得到的用户相似度和间接信任度,采用Top-N方法选择活动用户最信任或者与用户相似的前N个邻居.

1.2.5 计算加权评分

评分预测是推荐系统中最重要的步骤,本文的评分预测采取融合信任度与相似度的方式进行加权,计算公式如公式(11)：

2 算法流程

将上述所建立的用户增强相似度以及用户隐含信任度相结合,形成了本文新的协同过滤算法. 算法的具体步骤如下文.式(1)(2)(3)计算用户的相似度JMSD,建立用户相似度矩阵,根据公式(4)计算用户的偏好相似度,最后根据公式(5)计算用户的增强相似度

步骤2. 根据公式(7)计算用户的交互成功和失败项目集合,并根据公式(8)建立用户的直接信任矩阵

步骤3. 根据用户直接信任矩阵,利用公式(9)计算用户的传播信任,并根据公式(10)计算用户的隐含信任,建立隐含信任矩阵.

步骤4. 确定用户的邻居数目N,根据公式(11)计算用户的预测评分值进行降序排列,将前N个项目推荐给用户.

3 实验与分析

3.1 实验数据集

本实验基于目前推荐系统研究中经常使用的由美国Minnesota大学的GroupLens研究小组提供的MovieLens100 k(943个用户、1682部电影、100 000条评分)和Epinions(49 290个用户、139 738个项目、664 824条评分)数据集作为测试数据集. 两个数据集的数据稀疏性(未评分过的项目数占整个数据集的比例)分别为93.7%和99.9%. 两个数据集评分范围为1-5. 实验中将数据集按照1：4的比例划分成两个部分：前者作为测试集合,测试模型的性能,后者作为训练集.

3.2.1 平均绝对误差

本实验采用当前被广泛使用的平均绝对误差(Mean Absolute Error,MAE)度量推荐算法的性能,它属于统计精度方法. 它的原理是通过对比用户对项目预测评分与用户对项目实际评分的偏差,进行算法预测准确性的度量. 公式如下：

其中Pi为用户对目标的预测评分,Ri为实际评分,n代表预测评分的次数. 从公式(12)可以看出,MAE值越小,算法预测的精确性越高.

3.2.2 覆盖率

覆盖率(Coverage)用来衡量一个算法能够预测的项目占所有项目的百分比,在推荐系统中Coverage衡量的是推荐系统为用户推荐的项目集对用户兴趣的覆盖范围,Coverage值越大,算法的全面性越好,Coverage的公式如下：

其中P(u)代表推荐系统为用户u推荐的项目集合,R(u)代表用户u在测试集上的评分集合.

3.3 实验结果分析

3.3.1 参数 λ对MAE的影响

图1 不同的λ值下算法的精确度变化 (MovieLens100k)

3.3.2 近邻数对算法精确度影响

为了进一步验证所提出的ETCF算法的有效性,2种传统的算法和两种改进的传统算法被选作比较对象： 基于PCC的协同过滤算法,基于Cosine的协同过滤算法,基于SPCC的协同过滤算法以及基于JMSD的协同过滤算法,近邻数K的取值为10-90. 从图3可以看出,在MovieLens100k数据集下,随着邻居数K的增加,五种算法的精确度都逐渐提高,之后稍有下降,但是从整体上看本文提出的ETCF算法的精确度一直优于其他4种算法. 从图4可以看出在Epinions数据集下随着K增加,JMSD、Cosine、PCC三种算法的精确度都逐渐降低,接着逐渐升高,最后趋于稳定. SPCC的精确度随着K的增加先下降然后逐渐上升. 本文所提出的ETCF算法随着K的增加逐渐降低,随后逐渐升高. 但从整体上看,本文提出的ETCF算法的精确度一直优于其他4种算法.

图2 不同的λ值下算法的精确度变化 (Epinions)

图3 近邻数对算法精确度的影响 (MovieLens100k)

3.3.2 近邻数对算法覆盖率的影响

图5和图6分别为MovieLens100k和Epinions数据集下算法的覆盖率随邻居数k的变化情况,随着邻居数K的增加,在两个数据集下算法的覆盖率都逐渐提升,但本文的ETCF算法覆盖率一直优与其他4种算法.

图4 近邻数对算法精确度的影响 (Epinions)

图5 近邻数对算法覆盖率的影响 (MovieLens100k)

图6 近邻数对算法覆盖率的影响 (Epinions)

实验结果分析： 由于Movielens数据集和Epinions数据集的稀疏性比较高,用户之间的共同评分项较少.Cosine和PCC都是基于用户之间的共同评分项来计算相似系数,所以性能比较差,SPCC和JMSD考虑了用户之间共同评分项较少的问题,公式中引入了用户之间的共同评分作为参考项,因此和传统的算法比性能上有了一定的提升,但是这两种算法同样存在着缺陷,首先没有考虑用户评分的兴趣度问题,其次没有考虑两个用户没有共同评分项的问题. 本文提出的EFCF算法在一定程度上解决了上述问题,因此具有较好的性能.

4 结束语

针对推荐系统中的数据稀疏性问题,本文提出基于增强相似度和隐含信任的协同过滤算法,首先对传统的相似性度量方法进行改进,引入了一种基于用户偏好和JMSD的增强相似度. 其次,考虑到两个用户之间可能没有共同评分项的问题,提出了一种基于隐含信任的信任传播模型,在直接信任的计算过程了融入了用户的交互经验,然后根据直接信任提出了一种间接信任的计算方法. 最后将用户增强相似度和信任度分别进行近邻选择,然后进行融合. 实验表明,本文提出的ETCF算法相比传统算法在推荐精度上和覆盖率上有明显的提升,然而该算法传统相似度和用户信任度融合的比例问题还需要进一步的探讨.

1王立才,孟祥武,张玉洁. 上下文感知推荐系统. 软件学报,2012,23(1)： 1-20.

2黄创光,印鉴,汪静,等. 不确定近邻的协同过滤推荐算法.计算机学报,2010,33(8)： 1369-1377.

3徐守坤,孙德超,李宁,等. 一种结合语义Web和用户信任网络的协同过滤推荐模型. 计算机应用研究,2014,31(6)：1714-1718.

4Eirinaki M,Louta MD,Varlamis I. A trust-aware system for personalized user recommendations in social networks. IEEE Transactions on Systems,Man,and Cybernetics： Systems,2014,44(4)： 409-421. [doi： 10.1109/TSMC.2013.2263128]

5Abbas A,Zhang LM,Khan SU. A survey on context-aware recommender systems based on computational intelligence techniques. Computing,2015,97(7)： 667-690. [doi： 10.1007/s00607-015-0448-7]

6Massa P,Avesani P. Trust-aware recommender systems.Proceedings of the 2007 ACM Conference on Recommender Systems. Minneapolis,MN,USA. 2007. 17-24.

7Yuan W,Shu L,Chao HC,et al. ITARS： Trust-aware recommender system using implicit trust networks. IET Communications,2010,4(14)： 1709-1721. [doi： 10.1049/ietcom.2009.0733]

8郭艳红,邓贵仕,雒春雨. 基于信任因子的协同过滤推荐算法. 计 算 机 工 程,2008,34(20)： 1-3. [doi： 10.3778/j.issn.1002-8331.2008.20.001]

9杜永萍,黄亮,何明. 融合信任计算的协同过滤推荐方法.模式识别与人工智能,2014,27(5)： 417-425.

10张俊,刘满,彭维平,等. 融合兴趣和评分的协同过滤推荐算法. 小型微型计算机系统,2017,38(2)： 357-362.

11杨秀梅,孙咏,王丹妮,等. 融合用户信任模型的协同过滤推荐算法. 计算机系统应用,2016,25(7)： 165-170. [doi：10.15888/ j.cnki.csa.005229]

12陈婷,朱青,周梦溪,等. 社交网络环境下基于信任的推荐算法. 软件学报,2017,28(3)： 721-731. [doi： 10.13328/j.cnki.jos.005159]

13王瑞琴,蒋云良,李一啸,等. 一种基于多元社交信任的协同过滤推荐算法. 计算机研究与发展,2016,53(6)：1389-1399. [doi： 10.7544/issn1000-1239.2016.20150307]

14Bobadilla J,Serradilla F,Bernal J. A new collaborative filtering metric that improves the behavior of recommender systems. Knowledge-Based Systems,2010,23(6)： 520-528.[doi： 10.1016/j.knosys.2010.03.009]

15Loll F,Pinkwart N. Using collaborative filtering algorithms as elearning tools. Proceedings of 42nd Hawaii International Conference on System Sciences. Big Island,HI,USA. 2009.1-10.