融合信任关系的物质扩散与热传导混合推荐算法

李普聪，王 顺，钟元生，孔伟晶

(江西财经大学 软件与物联网工程学院，南昌 330013)

1 引 言

数据稀疏和冷启动问题是目前大多数个性化推荐算法都会面临的困扰[1].通常推荐系统根据用户过往的偏好信息进行个性化推荐，当新用户加入系统时，常常由于没有可作为依据的历史信息，无法为其提供有效的个性化推荐服务.部分应用通过用户偏好设置过程中所选的标签来获取用户的兴趣偏好，但该方法仍无法保证推荐信息的质量.为了提高推荐服务的质量，解决新用户个性化推荐的冷启动问题，众多学者提出了多种较为有效的方法，如基于用户上下文信息的推荐算法[2]以及基于信任关系的推荐算法.其中，基于用户上下文信息的推荐算法，如文献[3]提出的具有边界值的朴素贝叶斯算法，在推荐的准确率和回召率方面都有不错的表现；文献[4]提出了一种用于事件推荐的语义增强和上下文感知混合协作过滤方法，实验证明了该算法优于同等方案；文献[5]利用循环神经网络处理用户上下文信息，通过与其它经典的特征收集方法比较，验证了循环神经网络对于提高推荐算法效率的有效性；文献[6]提出了一种基于用户上下文信息和动态预测的协同过滤算法，实验证明该算法能够缓解评分数据稀疏性对协同过滤推荐算法的影响.在基于信任关系的推荐算法研究方面，文献[7]基于可信图方法，将可信朋友的影响力和公众影响力加入到信任关系网络，从而提高推荐算法准确性；文献[8]将信任机制引入社交网络，使用关联规则挖掘来捕获网络中用户的当前阅读趋势，提出了一种图书推荐系统；文献[9]基于用户间的信任关系和相似性，将用户社区结构融入到“用户-项目”联合社区的矩阵分解模型，提出了一种结合用户社区和评分联合社区的推荐模型，实验证明该模型能有效提升推荐的准确性和精度.

目前大多数推荐算法都无法在保证推荐精度的同时保证推荐的多样性[10]，难以满足用户对高质量信息过滤的要求.近年来，基于复杂网络的推荐算法[11]越来越受到重视，与传统推荐算法相比，基于二部图网络结构的资源扩散推荐算法在精确性、多样性、适应性和扩展性等方面都表现出较好的性能.受基于网络的动态资源分配推荐算法的启发，Zhou等人发现个性化推荐过程与二部图投影问题存在相似之处，通过把推荐过程转化为双向含权网络投影过程，提出了一种基于物质扩散的推荐算法[12]；此后他们又融合物质扩散和热传导思想，修正原有推荐算法，实验证明新方法可同时兼顾推荐的准确性和多样性，并增强了算法对不同场景的适应能力[13].文献[14]提出了一种基于热双向传递的推荐算法，该算法对推荐的精确度、新颖性和多样性都有所提升，在发掘长尾商品和解决冷启动问题方面也有不错的效果.文献[15]将基于共同邻居相似性的二部网络投影方法集成到Infomap中，利用随机游动算法得到一个加权的单模网络，提升了推荐算法的准确率.文献[16]提出了一个改进的基于物质扩散和热传导的混合推荐算法，此算法在融合两种传统算法优点的基础上增加了一个调节参数来抑制系统对热门物品的过度推荐，实验表明该混合算法相比传统算法在准确率和多样性上都有提升.

在基于扩散过程的推荐算法这方面，大部分学者对 “用户-物品”二部图网络中资源分配方法关注较多，较少融合用户的社交网络信息.即使在研究中融入了社交网络，大多也是采用平均分配原则进行资源的分配.因此，在基于扩散过程的推荐算法研究中，如何充分利用历史信息确定用户之间的信任度，并根据权重来进行资源分配，成为一个重要的研究方向.为改进现有推荐算法的不足之处，本文将用户上下文信息与信任关系同基于扩散过程的推荐算法相融合，提出一种融合信任关系的热传导和物质扩散混合推荐算法.

2 基于双层网络的资源扩散推荐算法

传统的基于物质扩散的推荐算法(Probabilistic-spreading Recommendation Algorithm，简称ProbS算法)、基于热传导的推荐算法(Heat-spreading Recommendation Algorithm，简称HeatS算法)以及ProbS与HeatS混合推荐算法(PHS算法)是目前研究较多的基于“用户-物品”二部网络的推荐算法.部分研究者尝试在基于扩散过程的推荐算法中引入社交网络算法表示用户之间的关系，但大部分未考虑用户之间信任关系的强弱，也大多没有针对新用户冷启动问题提出切实有效的解决方法.因此，本文基于传统的ProbS和HeatS的混合推荐算法，通过结合用户行为、用户上下文和用户兴趣偏好等3类信息，将用户信任关系网络与“用户-物品”二部图相结合，形成二层网络，使资源扩散过程在“用户-用户-物品”双层网络中进行，提出一种融合信任关系网络的物质扩散和热传导混合推荐算法(Fusion Trust Relationship Network Heat-Probabilistic-Spreading-Based Hybrid Recommendation Algorithm，简称THP算法).

2.1 融合用户上下文信息的信任网络构建方法

本文主要依赖用户行为、用户上下文以及用户兴趣偏好等3类信息来构建一种信任关系网络.

假设有一无向含权信任关系网络G，网络中的节点代表用户，结点个数n表示网络中的用户数，用户之间的信任关系用结点之间的连线表示，则可用邻接矩阵Ttru=[txy]n×n表示信任关系网络.其中，txy指用户x与用户y之间的信任强度.用户之间的信任度可利用相似性计算方式求解，则Ttru计算公式可表示为：

Ttru=Tbeh+Tcon+Tint

(1)

其中，Tbeh、Tcon、Tint分别为基于用户行为、用户上下文信息和用户兴趣偏好生成的信任关系矩阵.通过归一化处理用户邻接矩阵Ttru，得到用户之间的信任关系矩阵TUU.

2.1.1 基于用户行为产生的信任关系

假设存在一个如图1(a)所示“用户-物品”二部图G(U，I，E)，U为用户集合，I为物品集合，E为用户与物品之间的连线，代表U中用户和I中物品之间的选择关系.

图1 二部图及用户相似行为投影图

当要向用户x推荐物品时，首先分析x的过往行为记录，在系统中查找与其行为具有最大相似度的用户y，比较用户x与用户y的历史选择记录，将用户y历史选择清单中未被选择的物品推荐给x.通常“用户-物品”二部图只保存了用户选择物品的记录，无法直观地反映出不同用户之间行为的相似关系，通过二部图投影可生成反映用户行为相似关系的无向含权图.具体方法是：判断两个用户是否选择了相同的物品，如果选择了相同物品，则用一条无向边连接两个用户结点，并用所选相同物品的件数作为连边的权值.例如，在图1中，用户u1选购了i1、i3和i43件物品，用户u2选购了i1、i2、i3和i44件物品，则用户u1和用户u2选购了3件相同的物品i1、i3和i4，因此在u1与u2之间建立连边，并把边的权值赋为3.采用同样方法处理其它所有结点，从而得到如图1(b)所示的用户之间的相似行为投影图.

Jaccard相似系数可用于计算集合之间的相似度，为求解基于用户行为产生的信任度，本文引入Jaccard相似系数，计算公式如公式(2)所示：

(2)

如图2(a)所示，Inter(x，y)为x和y两个用户所选物品的交集，Union(x，y)为x与y两个用户所选物品的并集.tbeh(x，y)为信任关系矩阵Tbeh中的元素，取值范围为[0，1]，tbeh(x，y)值越大，说明x与y的相似度越高.

图2 基于用户行为生成的信任关系网络过程

构建基于用户行为的信任关系网络的算法描述如下：

输入：用户购物信息列表

输出：基于用户行为的信任关系矩阵Tbeh

1.基于用户购物信息列表，构建“用户-物品”二部图模型；

2.基于“用户-物品”二部图，求解所有用户的行为向量，若用户选择了某物品，将对应列的元素赋值为1，否则，赋值为0；

3.计算每两个用户所选物品的总数和所选同一物品的数目；

4.基于二部图投影策略，利用3中用户的物品选择信息，构建用户行为矩阵；

5.根据Jaccard相似系数公式，计算所有连边结点的权值；

6.综合5的计算结果构建用户信任关系矩阵Tbeh.

2.1.2 基于上下文信息产生的信任关系

已有研究表明，不同性别、年龄、职业的人，他们的生活需求通常存在较大的差异，而年龄接近、职业类似的人在较多生活需求方面存在较高的相似度.因此我们选择性别、年龄以及职业类别3类用户信息构建用户属性上下文信息，并对它们分类处理：

·性别(2类)：男(F)、女(M)；

·年龄(7类)：1-18、19-24、25-34、35-44、45-49、50-55、56以上；

·职业(8类)：党政事业单位人员，专业技术人员、农林水利生产人员、商业服务业人员、设备操作人员、办事人员、军人、其他从业人员(分类源自《中华人民共和国职业分类大典》).

表1 用户属性上下文信息表

表2 用户u1与u2观影记录

为评估用户基于上下文信息产生的信任度，本文采用余弦相似度计算公式(如公式(3)所示)，计算两个用户时间上下文属性向量的夹角余弦值，来评估两者之间的相似度.由于本文讨论的用户上下文向量中各元素不可能为负数，因此余弦相似度的取值范围为[0，1].

(3)

综上所述，构建基于用户上下文信息的信任关系网络的算法可描述为：

输入：用户上下文信息列表

输出：基于用户上下文的信任关系矩阵Tcon

3.采用余弦相似度公式进行计算，生成用户属性上下文相似度矩阵Satt和用户时间上下文相似度矩阵Stime；

4.依据步骤3的计算结果，计算Satt和Stime的和；

5.生成信任关系矩阵Tcon

2.1.3 基于兴趣偏好产生的信任关系

通常如果两个用户的偏好相似，则两个用户可能存在相同的兴趣点，从而可以为他们推荐类似的商品.另一方面，如果两个用户兴趣偏好相似，他们对所购商品的评价也可能类似，因而可以通过分析两个用户对相同物品评分信息的相似度来评判两个用户的兴趣偏好相似度.目前电商平台一般都会保存用户信息、商品信息以及用户的交易评价信息等数据，基于这些数据，利用相似度计算公式，就可求解用户两两之间的偏好相似度.假设U={u1，u2，u3，…，ua…，un}(n为用户总数)为用户集合，I={i1，i2，i3，…，ib，…，im}(m为物品总数)为物品集合，则利用用户交易评价信息中给出的评分数据，就能构建一个n×m的交易评分矩阵R=[rab]n×m，如表3所示.

表3 “用户-物品”评分矩阵

(4)

·0.8-1.0 极强相关

·0.6-0.8 强相关

·0.4-0.6 中等程度相关

·0.2-0.4 弱相关

·0.0-0.2 极弱相关或无相关

综上所述，基于用户兴趣偏好生成信任关系网络的构建过程如图3所示，算法描述如下：

图3 基于用户兴趣偏好生成的信任关系网络过程

输入：用户信息列表、用户订单商品列表、商品评分列表

输出：基于用户兴趣偏好的信任关系矩阵Tint

1.利用用户订单记录中的商品信息及相应的交易评分数据，构建“用户-物品”评分矩阵R=[rab]m×n，其中，评分的取值范围为1-5的整数，未选购商品的评分记为0；

表4 “用户-物品”评分表

tint(u1，u2)=

(5)

2.2 THP算法提出

传统的基于扩散过程的推荐算法性能受限于数据的稀疏性问题，并且无法处理新用户冷启动问题，在一定程度上并不能满足用户需求.为了进一步提升推荐算法的性能，本文提出了融合信任关系的物质扩散和热传导混合推荐算法(THP算法).该算法将融合用户上下文信息的信任关系网络与传统的“用户-物品”二部图相结合，利用物理学和社会心理学的思想，通过资源的扩散方式预测用户感兴趣的物品.

2.2.1 二部图

二部图是隶属于图论的一种特殊模型，主要通过分析拓扑结构特征来寻找节点间的联系.假设存在一个无向图G(X，Y，E)，其中X、Y分别表示分属不同类型的节点集合，且均不为空集，其中，同类节点之间不存在直接的交集关系.E(x，y)为不同结点集中节点x和y的连边集合，其中x∈X，y∈Y，连边关系通常用“0-1”模型进行表示，根据是否存在连边设定相应的值，满足以上条件，这里我们就可以说G是一个二部图.现实生活的许多场景都可以构建二部图模型，比如购物、旅游等.由于二部图的结构特性与推荐系统中常用的“用户-物品”关系结构较为相似，近年来被引入到推荐算法研究中.

2.2.2 双层网络模型构建

过去以单一二部图为基础构建的基于扩散过程的推荐算法往往难以满足不同应用场景对推荐算法性能的要求.本文结合多维用户信息构建基于“用户-用户-物品”的二层网络模型.为更好地阐述THP算法的原理，我们假设有一双层网络G(U，I，EUI，EUU)，其中U={u1，u2，…，un}为由n个用户构成的用户集合，I={i1，i2，…，im}为由m个物品构成的物品集合，EUI(aui|aui=0或aui=1，0

2.2.3 算法描述

传统的基于扩散过程的推荐算法的局限性在于只考虑了资源在用户和物品之间的扩散方式，利用额外的附属标签信息提升推荐性能，未处理新用户到来时的冷启动问题.而THP推荐算法将资源扩散过程从物品与用户之间引入到任意两个用户之间，基于用户行为、用户上下文以及用户兴趣偏好3个维度的相似度求解用户之间的信任关系强度，将融合多维用户信息的信任关系网络有效融入到改进的基于扩散过程的推荐算法中.具体来说，THP算法的推荐过程可描述为以下3个步骤：

(6)

式(6)引入调节因子λ，使资源在λ的调节下在双层网络上扩散.其中，当λ为1时，

(7)

则THP算法转变为融合信任关系网络的物质扩散推荐算法.

而当λ=0时，

(8)

则THP算法转变为融合信任关系网络的热传导推荐算法.

基于上述分析，可将THP推荐算法的推荐过程(含相关公式的推导过程)分解为以下5个步骤：

步骤4.基于用户信任关系矩阵，在信任关系网络中进行资源扩散，求解目标用户的资源向量：

THP算法推荐过程可直观表示为图4所示过程.

图4 融合信任关系网络的物质扩散和热传导混合推荐过程

THP推荐算法可形式化描述如下：

算法：THP推荐算法

输入：用户物品选择关系矩阵AUI，用户信任关系矩阵TUU，目标用户x调节因子λ；

输出：推荐给目标用户x的商品列表Rx.

1.求解AUI的转置矩阵BIU；

2.求解用户活跃度对角矩阵ΛU、物品流行度对角矩阵ΛI；

8.对推荐集合L中的元素降序排列，生成推荐给用户x的物品列表Rx，最终向用户推荐排名靠前的d个物品.

3 实验及分析

为检验THP算法的有效性，对测试数据进行预处理和特征分析，采用TopN推荐方式生成运算结果，然后从两个维度来比较THP算法与相关算法的推荐性能差异：1)相同推荐列表长度不同调节因子的推荐性能对比；2)相同调节因子不同推荐列表长度的推荐性能对比.

3.1 实验数据

本实验所用的测试数据为MovieLens提供的MovieLens-100K数据集.该数据集包含了1682部电影的相关评分数据，由943位用户提供，共100000条评分记录.

3.2 评价指标

借鉴推荐算法评价的传统作法，本文通过查准率(Precision)、查全率(Recall Ratio)、排序分(Ranking Score)、多样性(Diversity)、新颖性(Novelty)以及覆盖率(Coverage)等6个指标来检验THP算法的质量.

3.2.1 查准率指标

基于传统的TopN推荐方式，假设目标用户为x，推荐列表的长度为l，查准率Prex(l)计算公式为：

(9)

其中，Rx(l)为存在于目标用户x的预测物品集又同时存在于测试集的物品数目.若U(x1，x2，…，xn)为用户集合，则可用式(10)计算推荐算法的平均查准率Pre.

(10)

3.2.2 查全率指标

假设推荐列表长度为l，则可用式(11)计算目标用户x的查全率Recx.

(11)

其中，Rx(l)为存在于目标用户x的预测物品集，同时也存在于测试集的物品数目，Qx为被目标用户最终选择了的测试集中物品的数目.

3.2.3 排序分指标

假设U(x1，x2，…，xn)为用户集合，Tx为推荐给目标用户x的物品集合，txα为Tx中物品α在推荐列表中的排名，Sx为测试集中目标用户所选物品集合，则可用式(12)计算目标用户x推荐排序分RSx.

(12)

推荐系统整体排序分RS为所有用户排序分的均值.

(13)

3.2.4 多样性指标

假设U(x1，x2，…，xn)为用户集合，L为推荐列表长度，可用式(14)计算用户x与y的海明距离Hxy：

(14)

其中，Txy表示用户x和y的推荐列表中相同物品的数量.推荐算法的整体推荐多样性Div可用式(15)来计算，即求解所有用户海明距离Hxy的平均值.

(15)

3.2.5 新颖性指标

假设U(x1，x2，…，xn)为用户集合，推荐给目标用户x的物品集为Tx，可用式(16)计算目标用户的推荐新颖性Novx.

(16)

其中kα表示选择了物品α的用户数，即流行度.推荐算法的新颖性值Nov可用式(17)来计算，即求解所有用户推荐列表新颖性值的平均值，取值越小则说明新颖性越高.

(17)

3.2.6 覆盖率指标

假设存在用户集合U和物品集合I，推荐给目标用户x的物品集为Tx，可用式(18)计算推荐算法的覆盖率Cov.

(18)

3.3 实验结果与分析

本次实验主要采用两种方法对THP算法进行分析，验证其推荐效率：1)固定推荐列表长度，以调节因子λ为自变量，分别运行PHS算法和THP算法，观察比较两种算法6项评价指标的变化趋势.2)将调节因子λ固定为某一最佳值，以推荐列表长度为自变量，观察比较PHS算法和THP算法6项评价指标的变化趋势.

3.3.1 不同调节因子的算法比较

THP算法是在PHS算法的基础上进行改进的.因此，为了确定和展现该算法优势，通过设置不同的调节因子λ来分析其对算法推荐性能的影响.通过对MovieLens数据集中调节因子λ的取值进行不同设置，判断取得算法最优性能的λ值.此处我们将推荐列表长度设置为20.THP算法与PHS算法在6类评价指标下的推荐效果对比如图5所示.其中，横坐标为调节因子λ，取值范围设为[0，1]，间隔为0.1.

图5 相同推荐长度下不同调节因子的性能指标对比图

PHS算法是通过引入调节因子λ融合ProbS算法与HeatS算法得到，λ=1时就转化为ProbS算法，λ=0时就转化为HeatS算法.从图5的推荐结果可以发现，ProbS算法获得了较好的查准率但多样性相对较差，相反，HeatS算法获得较好的多样性但查准率相对较差.相比之下，PHS算法在精确性和多样性方面达到了平衡，两方面均有所改进.

在图5的precision部分可以看到，与PHS算法、ProbS算法和HeatS算法相比，THP算法的推荐精准度更好.在λ=0.2时，THP算法获得0.1416的查准率值，较其它3个算法，查准率提升幅度分别达到2.76%、48.73%、1142%.在查全率方面，THP算法的为0.2612，较其它3个算法，查全率提升幅度分别达到2.88%为、57.54%、11.87%.从排序指标方面，本文所使用的THP算法与PHS算法的效果基本一致.结合图5中diversity和novelty性能指标对比，THP算法在推荐多样性和新颖性方面具有较大优势.多样性指标方面：当λ=0.1时，THP算法的值达到0.9253，对比ProbS算法，有60.70%的大幅提升，对比Heat算法和PHS算法，也有9.57%和1.17%的小幅提升.此外，在新颖性方面，相对于其他算法，THP算法也有一定的提升，当λ的值逐渐靠近1，与PHS算法相比THS算法逐渐与其接近，表明新颖性会随着资源趋向于以物质扩散的方式扩散时而不断降低.综上所述，调节因子对THP算法的性能有着较大的影响.所有算法在不同评价指标下的表现详细见表5.

表5 同调节因子λ下各算法的最佳性能比较

从推荐结果分析可得，在λ=0.2时，使用MovieLens数据集，THP算法在各个性能指标上达到最佳，也就是说在整个资源扩散过程中，有20%的资源通过物质扩散的方式进行扩散，其它80%的资源通过热传导的方式进行扩散.因此，当λ=0.2时，THP算法的推荐精确度和多样性可得到有效的提升.

3.3.2 不同推荐长度的算法比较

以Top推荐算法方式辅助用户找到感兴趣的商品，是目前大多数推荐系统向用户推送商品列表的主要手段，比如“天猫”、“亚马逊”等大型的电商平台.THP算法也采用了同样的方式产生推荐列表，通过对目标用户的最终资源向量进行筛选和排序，从而生成推荐列表，然后优先推荐排序靠前的物品.因此，本节主要分析不同的推荐长度对于各个推荐性能指标的影响趋势，更好的对比不同算法直接的推荐性能差异.以20、40、60、80和100的取值方式设定推荐列表的长度来实现相应的实验.从上节可知，PHS算法与THP算法在λ的值为0.2时，各项推荐性能指标都比较好，所以在本节中我们将它们的调节因子均固定为0.2，然后基于推荐算法常用的查准率、查全率、排序分以及多样性4项指标，对几个常见推荐算法进行比较，各算法在不同性能指标下的变化趋势如图6所示.

1)查准率性能比较

从图6中的precision部分可知，推荐列表的长度(简称L)与查全率的比例成反比，随着L的增加各算法的性能都呈下降趋势.其中，传统的HeatS算法因其本身的局限性，在查准率方面明显低于其他算法.反观THP算法，随着L的增加该算法的查准率下降趋势基本与经典的PHS算法相同.同时，在相同L值下，THP算法与其他算法相比都有不同程度的提升，且一直处于较高的位置，可见该算法在推荐查准率方面具有明显的改进.

2)查全率性能比较

如图6中recall部分所示，各个推荐算法的查全率与推荐列表长度L呈正比，即推荐查全率随L的增长而增长.推荐查全率方面，CF算法与ProbS算法较为接近，而相比THP算法与PHS算法，两者依然处于最高位置，且THP算法表现的更加优越一些.综合观察查准率与查全率的变化趋势，可知THP算法与其他算法相比，能够保证不错的推荐精确度.

3)多样性性能比较

图6中diversity部分可见各算法的推荐多样性有较大的差距.随着L的增加各个算法的多样性在逐渐的降低.其中ProbS算法表现最差，主要是因为该算法在保证精确度的同时丢失了推荐多样性.而THP算法和PHS算法对于推荐多样性显著的高于其他算法.可见THP算法在推荐多样性方面也具有不错的表现，向用户提供不同种类的物品的能力均优于其他对比算法.

图6 相同调节因子不同推荐长度的性能指标对比图

4)排序分性能比较

排序分主要用于评价推荐算法挖掘用户潜在兴趣的能力.优秀的推荐算法应该是将用户感兴趣的物品放在排名靠前的位置，而并不是将热门商品放在推荐列表靠前的位置.根据本文设定的排序分指标值的定义，要求排序分越低越好.图6中ranking score部分为各算法的排序分变化趋势图.由图可见，随着L的增长，排序分会逐步上升，基数越大，排序分上升的趋势也会变大.几种算法的排序分明显分化为两组，CF、HeatS以及ProbS算法的排序分比较接近，处于较高位置，而THP和PHS算法的排序分接近，处于较低的位置.与其它算法相比，THP算法排序分最低，而且随着L的增长，THP算法排序分的增长趋势相对平缓，可见其性能更具优势.

综上所述，与传统的推荐算法相比，将信任关系网络与物质扩散算法和热传导的混合推荐算法相融合，对于推荐的各个性能都有一定程度的提升.

4 总 结

针对数据稀疏性和新用户冷启动问题，本文提出了一种融合用户上下文信息与信任关系网络的基于扩散过程的推荐算法.借鉴社会心理学人际信任建立机制，整合用户行为信息、用户上下文信息、用户兴趣偏好信息3个维度的用户相似度，建立用户信任关系，扩展传统的“用户-物品”单层网络为“用户-用户-物品”双层网络，构建用户信任关系网络.不同于传统的基于资源扩散推荐算法中资源平均分配方式，本研究根据用户之间的信任度来确定资源分配比例，让资源按照权重分配进行扩散.研究表明，本文所提出的THP算法相较传统推荐算法在一定程度上提升了推荐的准确度和多样性，有效缓解了数据稀疏性对推荐算法性能的影响，较好地解决了用户冷启动问题，为优化基于扩散过程的推荐算法研究提供了新的方向.