基于增强二部图网络结构的推荐算法①

张岐山,文 闯

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

引言

人工智能时代背景下产生了许多信息过载[1]问题,协同过滤算法是当今电子商务以及各种个性化推荐中应用最广泛的推荐技术,协同过滤算法存在冷启动问题,同时算法存在需要获取大量用户历史数据,存在稀疏性等问题.为解决以上问题,国内外许多专家学者提出并完善了基于信任的推荐系统[2],

Guo[3]根据信任的来源将信任分为显性信任(Explicit Trust 和隐性信任(Implicit Trust),显性信任是指用户网络之中主体之间的直接交互,主动表达的信任关系,隐性信任是指根据用户网络中主体之间的直接交互关系挖掘出信任关系,根据用户的某些行为(如评分)来推测用户之间的信任关系,显性信任具有很强可靠性和准确性,而隐性信任更好的区分信任度,能显著提高覆盖率,缓解冷启动问题.Massa 等人[4,5]提出一种使用显示信任的推荐系统,用信任权重代替传统推荐系统的相似度进行推荐,相比传统算法,提高了精度,增加了覆盖范围,可预测的评分总数,同时也能规避恶意用户虚假评分降低推荐质量的隐患.Jamali[6]也考虑了信任问题,采取随机游走的方法利用显性信息,在用户网络中随机选取信任邻居,把用户看成网络中的节点,连接的边即为信任关系,其强度代表了两个用户间信任度.文献[7]引入了全局变量,融合用户间局部信任度和全局信任度,从海量用户历史数据中,挖掘出用户潜在的信任关系,缓解了数据的稀疏性问题,提高了推荐的准确性.Ray 等[8]设定了相似性阈值,提出了当用户间相似度低于设定阈值则舍去,重构信任网络之后再预测评分,此法提高了算法精确度,但是牺牲了数据的覆盖率,也无从缓解冷启动问题.Moradi 等[9]提出了RTCE 模型,该模型首先基于显性信任机制为目标项目进行打分,同时设定信任阈值,对于评分可靠性低于阈值的用户,通过综合考虑积极因子,消极因子重构信任度.文献[10]创建了用户间信任繁殖算法以此拓宽信任网络,通过信任繁殖得到了更多有效邻居用户,提高了算法的覆盖率,缓解了推荐算法中的数据稀疏性和冷启动问题.Zhou 等[11]利用动力学传播原理构建用户-项目二部图网络结构,用户将自己的资源均衡分配给关注的项目,从而计算用户与用户的资源相关信任值,该算法提高了推荐预测精度,减少了算法的复杂度.

针对推荐算法的相关问题,本文在已有的研究成果上聚焦于用户显性信任关系以及通过设定阈值衍生繁殖隐性信任关系,充分考虑了信任关系的主观性,非对称性,传播性,弱传递性,以及适应性,同时融合用户偏好,依据评分相似性选择目标用户的最优近邻集合,从而进行预测.本文的主要创新点主要体现在以下方面：

1)在基于加权用户项目二部图[12]的信任繁殖[13]模型过程中加入对直接信任的阈值筛选控制,降低了推荐系统的噪声,同时构建用户信任与用户偏好关系融合的强化模型,具有一定现实合理性,最后设计与不融合用户偏好的算法模型进行自身对比,对比结果证明了融合用户偏好信任的优越性.

2)计算得到的信任度最后融合实验下表现更加优异的基于MSD 和Jaccard 相似性的JMSD 相似系数[14],在Movielens 数据集和Last.FM 数据集下的实验表明与基准算法相比较,本文提出基于二部图的增强繁殖信任推荐算法模型以下简称BTUCF 算法模型,缓解了了推荐算法的数据稀疏性和冷启动问题,提高了算法结果召回率,降低了算法的平均绝对误差.

下一节本文对传统协同过滤以及传统加权二部图推荐算法性能特点及局限性进行分析,第二节对本文提出增强的自适应繁殖信任模型进行描述,第三节讨论分析了本文得到实验模型结果.

1 相关工作

1.1 传统协同过滤

基于用户的协同过滤算法基础流程如下：

1)基于用户的协同过滤算法,输入数据集为用户-项目的评分矩阵,记为Rum,用户u对项目m的评分记为rum,未评分项目即rum=0,用户-项目评分矩阵共有m行n列,每一行都分别代表用户u依次对各项目的评分,每一列都分别代表某个项目受到各用户的评分数据,形式如下：

协同过滤算法主要通过构建相似度矩阵来预测目标用户对该项目的喜好程度,相似度计算方法是协同过滤算法推荐的关键因素,相似度的度量方法主要分为四种：修正的Pearson 相关系数,均方偏差(MSD),Jaccard 相似度和斯皮尔曼等级相关(Spearman’s rank correlation).

显式用户评分矩阵非常稀疏,相比其它相似度量本文采用的Jaccard 相似度能一定程度的从全局角度利用用户间的交互关系,但是缺少了用户与用户之间的直接信任交互与间接信任用户间的交互信息,只考虑传统协同过滤缺少了对这些必要信息的有效补充.

1.2 传统加权二部图推荐算法

二部图中定义用户集合U={u1,u2,u3,···,ui} 定义项目集合为O={m1,m2,m3,···,mj}将i个用户节点和j个项目的关系转化为一种选择关系,当用户Ui评价过项目mj就连接此用户与项目,对每一条用户与项目的连接线都赋予权重Wi,特别的当用户对项目的评分大于等于3 时Wi=1；当用户对项目的评分小于3 时Wi=β通过实验证明当β=0.5 时推荐结果最优[13],本文中亦使用该最优值.

1)用户-项目关系图构造如图1所示.

图中用户对项目的关注度如式(4)所示：

其中,Aij为项目mj受到用户Ui关注项目总数,len(ui)为用户ui评价过的项目权重总和,eij为用户ui是否对项目mj有评价的布尔类型,有即为1 没有即取0.

2)项目-用户有向图类似于用户-项目有向网络图构建,将项目得到的用户关注度重新反馈给用户如图2所示.

图1 用户—项目模型

图2 用户—项目模型

图中项目对用户的反馈表达式如式(3)所示：

其中,f(ui)为项目反馈给用户ui的关注度,len(mji)为用户ui评价过项目mj的项目权重总和,eji为项目mj是否对用户ui有评价的布尔类型,有即为1 没有即取0,Aij为项目mj受到用户ui关注项目总数.

最后结合用户-项目,项目-用户的有向网络图,从而可以得到用户-用户的有向网络图,结合式(4)和(5)推导出用户与用户之间的推导信任,推导信任取值范围为0 与1 之间.0 表示无评价历史,无信任交互,信任值越大信任程度越高,如式(7)所示：

Guo[3]阐述的衡量主体与主体之间的信任关系5 个重要特性：主观性：不同的主体有不同的兴趣偏好,判断标准,所以主体对于其他主体可能会有不同的信任值；非对称性：主体对主体的信任都是单方面的,一般是不对称的,在实际中A 对B 的信任度一般不等于B 对A 的信任值；弱传递性：信任是具有传递性的,在A 信任B,B 信任C 的前提下,trustAB和trustBC足够大时,A 对C 的信任值是有显著意义的；传播性：主体之间的直接信任关系以及其变化会影响其他主体之间的信任关系,特别是当一个主体的兴趣或者发生不诚信行为时,与其有信任关系的其余主体评估水平就会发生变化,这样通过该主体获得推荐的信任关系也会发生相应变化；适应性：主体之间的信任关系会随着时间函数的变化,上下文环境的变化而变化,由于信任的动态性,推荐系统中的信任建立之后,要根据系统内各种要素的变化不断调整调和参数.对比五种特性,传统加权二部图法在主观性上一分为二的权重考虑没有充分考虑用户偏好,没有在用户之间建立不对称的可适应性传递信任,没有充分挖掘非直接交互的用户间的潜在信任信息,同时没有设定阈值的广泛信任关系加入了不存在的信任关系,降低了系统的抵抗恶意攻击能力,增加了系统噪声.

2 一种增强的自适应繁殖信任模型

2.1 增强的二部图网络信任机制

(1)传统加权二部图基础上的信任繁殖.利用传统加权二部图得到直接信任,但是直接信任只反映了有相互交互的用户之间的关注度程度,实际数据中许多用户之间并没有直接互动,根据信任的可传递性与传播性,用户A 信任B,用户B 信任用户C,则存在用户A 信任用户C,挖掘潜在的间接信任可以拓宽信任关系,信任繁殖可以极大的提高算法的覆盖率与算法精度.根据文献[13]创建的信任进行了拓展,同时设定阈值d,本文只对直接信任大于0.01 才计算ITrust间接信任计算公式如下：

(2)综合信任度.结合用户间直接信任DTrust与间接信任ITrust,可计算用户间综合信任度,计算公式如下：

自适应性因子∂ 表达式如下：

(3)结合用户偏好的信任增强机制.增强的信任加权的二部图在用户-项目关系连接线上考虑了权重Wi当评分大于3 时Wi=1,当评分小于3 时Wi=0.5,加入权重后的二部图模型具有较为明显的优势,但仍存在一个问题,加入权重的推荐系统降低了系统抵抗恶意攻击的能力,没有考虑用户的评分偏好问题,乐观用户偏向于打高分,消极用户偏向于打低分,传统加权二部图中假设三个用户对四个项目的评分值分别为(1,1,1,1),(2,2,2,2)和(1,2,2,3),计算得到的信任关系u1与u2,u3与u4是相同的,这显然不符合不符合实际情况,根据信任特性u1与u2用户的信任度应该大于u1与u3,用户针对此问题,本文提出了一种偏好的调整信任度,其公式为：

基于以上,本文在第一种模型上提出一种新的偏好调整用户信任度度量方法构建第二种模型,增强信任公式表现如下：

2.2 结合JMSD 相关系数推荐

本文采用的是实验下性能更加优异的基于MSD和JMSD相似性的JMSD系数,基于用户共同评分项的个数来度量的JMSD系数中作为一种补充的全局信任信息结合二部图网络信任机制全面的挖掘了用户之间信任关系.均方偏差MSD公式为：

MSD无法处理用户共同评分项过少这个问题,而Jaccard相似度是基于用户共同评分项的个数来度量,其公式如下：

JMSDuv其公式如下：

基于相似度与偏好调整信任度的研究,对于目标用户ui的未知评分预测,给出综合相似系数Sim如公式：

(12)根据计算的相似系数Sim,对于用户未进行评分的项目,可采用如下预测公式预测：

3 实验结果和分析

3.1 实验数据集

为检验算法的合理性,本文使用Grouplens 提供组供的Movielens 数据集和在线音乐系统Last.FM 提供的Last.FM 数据集对算法模型进行验证,Movielens 由美国Minnesota 大学计算机科学与工程学院的Grouplens项目组创办,本文选择其中的Ml100k 数据集,数据集包括了943 个用户的100 000 条评价数据,评分范围1-5,每个用户至少对20 部电影项目作出评价,分值越大喜好越大；Last.FM 数据集包含了1892 个用户对17 632 张音乐专辑的收听信息,实验中与基准对比算法一致将收听数量转化成收听评分用于对比.两个数据集均按照4：1 划分训练集和测试集,Movielens 数据集和Last.FM 数据集根据数据稀疏性定义计算分别为：

3.2 度量标准

本文采用推荐系统的度量标准是广泛应用于评价协同过滤推荐算法的平均绝对误差(MAE),以及召回率(Recall)定义如下：

1)平均绝对误差和均方根误差通过训练集计算用户的预测评分和测试集的实际真实评分之间的偏差来度量算法的推荐准确性,所以MAE和RMSE越小,推荐的结果越准确.

2)召回率(Recall)又叫查全率,主要指通过算法可以预测出来的评分数与所有待测分数之间的比值.其中m表示通过算法模型得到的测试集预测评分数,n表示测试集中待测评分数.

3.3 算法推荐性能比较

本文提出JMSDuv相关系数与增强信任繁殖模型构建BTUCF 算法模型,在Python3.6 环境下,为了评价推荐算法的精度,对提出的模型算法进行试验验证,在相同的实验环境下,对不同数据集首先对算法模型进行敏感性分析,然后与三种基准算法进行实验对比和分析,参照的基准算法包括了主流的基于用户的协同过滤推荐TraCF 算法[15],基于信任模型的协同过滤推荐Tru_1CF 算法[16]以及一种改进的基于信任的改进算法Tru_2CF[17].第一种基准对比算法是基于用户推荐的经典推荐算法,第二种基准对比算法是经典的采用构建信任网络上的局部和全局信任构建信任矩阵引入信任模块和相似度模块不同权重推荐算法,第三种基准改进算法设置了通信信任,相似信任,和传递信任三个信任度构建信任矩阵.最后为了证实本文引入用户偏好的合理性,设置了JMSDuv相关系数与信任繁殖模型构建算法模型,即没有融合用户偏好的算法模型(以下简称BTCF 算法模型)作为另外一组对比算法进行自身对照.

3.3.1 敏感性分析

敏感性实验主要分析在Movielens 数据集和Last.FM 数据集下参数λ对本文提出的BTCF 和BYUCF 推荐精度MAE的影响,实验结果分别如图3和图4.

图3 Movielens 数据集下MAE 分析

图4 Last.FM 数据集下MAE 分析

从图3图4中中我们可以看到JMSD系数和融合用户偏好的信任在推荐结果中的影响力是不一样的,Movielens 数据集下λ=0.8 时取得了最好的结果.Last.FM 数据集下中λ=0.8 时取得最优结果.

基于二部图的自适应性繁殖信任推荐算法其评分预测结果主要来源于两个部分：评分相似系数和偏好信任系数,当λ=0.0 时表示在算法模型中融合用户偏好的信任对最后的推荐结果起唯一作用,当λ=1.0 时表示在算法模型中JMSD系数对最后的推荐结果起唯一作用,相比于传统信任算法推荐,比较从λ=0.0 和λ=1.0的变化,采用用户之间的评分数据其推荐质量高于采用用户之间的融合用户偏好的信任,这表明在推荐模型中,信任必须来源于用户的评分,这符合信任的定义和特点,同时也表明了本文基于融合用户偏好的信任挖掘了用户之间的潜在信任联系,提高了推荐质量.

3.3.2 性能对比分析

不同数据及下本文提出的BTUCF 算法模型与基于用户的协同过滤推荐TraCF 模型,基于信任模型的协同过滤推荐Tru_1CF 算法,一种改进的基于信任的改进算法Tru_2CF 以及本文提出的没有融合用户偏好BTCF 算法对比如下：

表1 Movielens 数据集最佳点推荐精度比较

表1可知Movielens 数据集下BTUCF 算法模型有较大改进,对比试验结果,在参数K=7,λ=7 时(算法最佳点)具有更低的MAE值和更高的召回率.

表2 Last.FM 数据集最佳点推荐精度比较

由表2可知Last.FM 数据集下BTUCF 算法模型在MAE指标表现上优于传统协同过滤算法和经典信任算法,但是与对比算法一种改进的基于信任的改进算法处于相同水平,召回率表现还是更加优异,MAE在Movielens 数据下系统更加优秀是因为推荐系统采用的是在较小邻居域表现更好的JMSD相似系数,Last.FM 数据集相比Movielens 数据集更加稀疏推荐系统的优势被相对稀释,进一步说明了本模型对数据稀疏性的反应程度.

图5、图6给出了五种算法在不同数据集和不同邻居数量下的MAE和Recall值,我们可以直观的发现,结合JMSD系数的推荐模型算法与结合皮尔逊以及改进的皮尔逊算法模型有较大差异,在K 较小的区间内结合JMSD系数的推荐模型算法具有更好的表现.这也验证了文献[17]的结论和本文引入JMSD系数的合理性,在算法结果对比下本文提出的BTUCF 算法模型在召回率的变现上更好,同时具由较低的平均绝对误差.

图5 Movielens 数据集下的MAE 对比图

图6 Movielens 数据集下的Recall 对比图

同时对比BTCF 算法模型和TUCF 算法模型,前者因为算法模型引入了繁殖信任融合JMSD系数,改进算法的同时也增加了数据噪声对推荐系统的影响,引入用户偏好的BTUCF 算法模型可以缓解噪声数据的影响,使得系统在K较小值范围能更取得更低的MAE,但是作为引入用户偏好的模型也降低了系统的召回率.