非对称的异质信息网络推荐算法*

赵 传，张凯涵，梁吉业+

1.山西大学 计算机与信息技术学院，太原030006

2.山西大学 计算智能与中文信息处理教育部重点实验室，太原030006

3.山西大学 智能信息处理研究所，太原030006

1 引言

推荐系统是大数据时代解决信息过载问题的重要手段之一[1]。在众多关于推荐系统的研究工作中，异质信息网络作为一种有效的信息建模方法[2]，逐渐受到人们的关注。异质信息网络可以通过构建多种类型的实体以及实体之间的联系[3]表示各种数据信息，将多种不同的数据信息利用到推荐任务中可以带来更好的推荐效果[4-5]，因此有越来越多的推荐工作利用异质信息网络解决[6-7]。基于元路径进行相似性度量是最重要和基础的一个方向。目前基于元路径已经开展了大量的研究工作。例如，Sun 等人[8]通过抽取两个用户之间对称的元路径度量用户之间的相似性，提出PathSim 算法；Shi 等人[9]提出基于元路径的双向随机游走算法HeteSim 度量网络中任意节点之间的相关性；Lao 等人[10]利用在元路径上的随机游走度量网络里任意实体之间的相似性。

上述基于元路径计算用户相似度的算法均假设用户之间的相似度满足对称性，而在实际中利用对称性相似度计算方法有时会导致用户相似度存在误差，比如当用户u与用户v对物品的评分向量分别为(2,5,4,5,4,1)和(2,-,-,-,-,1)时（“-”表示用户未对物品进行评分），传统的对称性相似度计算方法根据共同评分项会得出用户u与用户v具有高相似度的结果，但用户v对于其他未评分物品的兴趣程度不一定会与用户u相同。因此，在这种情况下，用户间的相似度是非对称的[11]。另外，基于元路径度量用户相似度时，多条不同的元路径会得到不同的相似度[12]，元路径从不同的角度反映了用户之间的联系，因此为了统一用户之间的相似程度，有必要对不同的元路径赋予不同的权重，通过权重融合不同元路径的相似度结果，能够更加准确地体现用户之间的关系。

为此，本文在计算用户间相似度时，一方面考虑用户间相似度的非对称性；另一方面考虑用户间不同元路径的权重，以准确度量用户间的相似度。首先利用用户的评分信息和物品的属性信息构建异质信息网络，通过考虑用户之间共同评分项在已评分项中占的比例，即非对称系数，计算用户间的非对称相似度；然后根据元路径的特征计算不同元路径的权重，权重用于融合不同元路径的相似度结果，得到用户总的相似度矩阵；最后利用矩阵分解模型将评分矩阵和相似度矩阵进行联合分解，计算用户和物品的潜在特征向量，预测未知评分。在数据集MovieLens 的三个不同规模的数据集上进行实验比较，结果显示本文所提算法在评价指标均方根误差和平均绝对误差上优于已有算法。

2 相关概念2.1 加权异质信息网络

给定一个有向图G=(V,E,W)。G里每一个对象v∈V是一个特殊的对象类型φ(v)∈A，A 是对象类型的集合；每一个连边e∈E是一个特殊的链接类型ψ(e)∈R，R 是链接类型的集合；每一个属性值w∈W是一个特殊的属性值集合θ(w)∈W 。如果对象类型数量A＞1 或者关系类型数量R＞1，该网络叫作异质信息网络[13]，如果权重数量W＞1，该网络叫作加权异质信息网络[14]。图1 为一个包含用户、电影、电影类型、导演的加权异质信息网络。

网络模式是异质信息网络的模板[15]。用δ=(A,R)来表示网络模式。图2 为图1 的网络模式图。

Fig.1 Diagram of weighted heterogeneous information network图1 加权异质信息网络图

Fig.2 Network schema图2 网络模式图

元路径是异质信息网络最重要的概念，它定义在网络模式上，用来描述异质信息网络中任意两节点间的不同路径类型[16]。它可以表示为P=A1→A2→…→Al→Al+1，A1,A2,…,Al+1表示节点类型。P-1=Al+1→Al→…→A2→A1代表相反的元路径。在两条元路径P1=A1→A2→…→Al→Al+1和P2=A′1→A′2→…→A′l→A′l+1中，如果Al+1=A′1，则两条元路径可以合并为一条元路径，表示为P=P1P2，比如元路径User→Movie和元路径Movie→User连接成元路径User→Movie→User。用户之间可以通过不同的元路径连接，不同的元路径包含不同的语义[17-18]。在图1 的加权异质信息网络中，元路径User→Movie→User和 元 路 径User→Movie→Type→Movie→User所 连接的用户之间具有不同的语义关系，前者将看过相同电影的用户连接起来，后者将看过相同电影类型的用户连接起来。

2.2 矩阵分解模型

在推荐系统里，矩阵分解模型的基本思想是将用户-物品的评分矩阵R分解成两个低维潜在特征矩阵U和V，通过U和V的点积可以得到一个拟合评分矩阵，从而实现评分预测。矩阵分解模型是通过最小化目标函数L(R,U,V)得到低维特征矩阵：

式中，Iij是一个指示函数，如果用户i对物品j有过评分，为1，否则为0。U∈ℝn×d，V∈ℝm×d，d是用户和物品的潜在特征维度，d≪min(n,m)，λU和λV是正则化系数，通过随机梯度下降可以对目标函数进行求解。

3 基于异质信息网络的推荐算法

本文融合评分信息与物品属性信息，综合考虑元路径的权重与非对称相似性这两个因素对用户相似度的影响，提出一种基于异质信息网络的推荐算法。通过计算用户和物品的潜在特征表示，从而预测未知评分。本章将重点分析以下3 个问题：（1）如何基于元路径计算用户之间的非对称相似度；（2）如何度量不同元路径的权重；（3）如何利用评分信息与用户相似度信息预测未知评分。图3 为本文的算法流程图，表1 为本文使用的主要符号。

Fig.3 Flow chart of algorithm图3 算法流程图

3.1 用户之间非对称相似度的确定

本文首先利用均方差（mean squared difference，MSD）[19]相似度公式计算用户之间的对称相似度；然后根据非对称系数，计算用户之间的非对称相似度。具体包含以下两步：

Table 1 Main symbols used in this paper表1 本文用到的主要符号

（1）由于用户之间在不同的物品上存在评分差异，评分差异的大小反映了用户之间的相似程度，因此本文利用均方差相似度公式通过用户之间的评分差异来计算用户相似度，在给定元路径P的基础上，计算用户u和用户v之间的对称相似度：

（2）本文把共同评分项在用户已评分项中占的比例定义为非对称系数，该系数反映了上述对称相似度对于用户的参考程度。用户u对v在元路径P上的非对称系数为：

其中，Iu代表用户u的评分项。

根据非对称系数，用户u对v的非对称相似度：

3.2 元路径权重的确定

由于从不同元路径角度计算得到的用户相似度不同，为了相似度结果的统一，本文从元路径的特点出发，赋予各个元路径不同的权重。针对权重的确定，本文从两个角度进行分析：

（1）元路径的长度。元路径的长度指的是该条元路径的边数。直观上说，短的元路径比长的元路径具有更高的权重，因为短的元路径使对象之间关系更加直接，元路径应该被赋予更高的权重。具体用公式表示为：

其中，L代表所有的元路径的集合，len(P)代表元路径P的长度。

（2）元路径的路径数。元路径的路径数指的是在异质信息网络内满足该条元路径条件的路径数量。路径数多的元路径代表对象之间的联系更密切，元路径权重应该更高。用公式表示为：

其中，num(P)代表元路径P的路径数。

根据以上两方面，利用下式计算元路径P的权重：

结合不同的元路径权重和不同元路径计算的相似度结果，计算用户之间的相似度：

3.3 利用矩阵分解模型预测未知评分

已知用户-物品的评分信息和用户-用户的相似度信息，本文算法利用矩阵分解模型，同时将评分矩阵R和相似度矩阵S进行分解，得到用户特征矩阵U、物品特征矩阵V、用户相似特征矩阵Z。模型的目标函数为：

由于评分信息的取值范围为[1,5]，相似度信息的取值范围为[0,1]，为了统一评分信息和相似度信息的取值范围，本文利用函数f(x)将评分信息限制在[0,1]之间，f(x)=(x-1)/(Rmax-1) 。为了与上述取值范围统一，利用函数g(x)约束在[0,1]之间，g(x)=1/(1+exp(-x)) 。λS是平衡评分信息和相似度信息的系数，若λS=0，表示矩阵分解模型只利用评分信息，若λS＞0，表示矩阵分解模型同时考虑评分信息和相似度信息。

对目标函数进行求导，分别得到U、V、Z的梯度：

其中，g′(x)=exp(x)/(1+exp(x))2，代表g(x)的导函数。用随机梯度下降方法对U、V、Z进行迭代更新。经过有限次数迭代后，利用已经更新的用户潜在特征矩阵U和物品潜在特征矩阵V预测用户u对物品i的预测评分：

3.4 算法流程

基于以上对算法的介绍，本文所提算法描述如下：

输入：用户-物品评分矩阵R，评分矩阵和相似度矩阵的平衡因子λS，特征维度d，随机梯度下降学习率α，正则项系数λU、λV、λZ。

步骤1利用式（2）～式（4）计算不同元路径下用户之间的非对称相似度。

步骤2根据式（5）～式（7）计算每条元路径的权重。

步骤3利用式（8）结合不同元路径的相似度信息，得到用户之间总的相似度矩阵。

步骤4根据式（9）、式（10），利用随机梯度下降法对用户潜在特征矩阵U和物品潜在特征矩阵V进行迭代更新。

步骤5利用式（11）预测评分。

4 实验及结果分析

为验证本文所提算法的有效性，在数据集Movie-Lens100K、MovieLens1M 和MovieLens10M 上进行实验，并与其他推荐算法进行比较分析，最后通过实验结果分析本文所提算法中参数的选取对实验性能的影响。

4.1 数据集

本文用到的数据集都包括用户-电影评分信息，以及用户和电影的属性信息，包括用户性别、用户年龄、用户职业、电影名称、电影类别、上映时间等，评分值在1 到5 之间，且每个用户至少评分过20 部电影。MovieLens100K 数据集包含了943 位用户对1 682 部电影的100 000 条评分信息，MovieLens1M 数据集中包含6 040 位用户对3 900 部电影的1 000 209条评分数据。MovieLens10M 数据集包含71 567 位用户对10 681 部电影的10 000 054 条评分，本文从中随机抽取10 000 名用户对10 681 个物品的评分记录作为训练集和测试集的数据。表2 统计这3 个数据集的相关信息。

Table 2 Statistic information of 3 datasets表2 3 个数据集的统计信息

4.2 评价指标

本文在衡量推荐性能时，为体现预测评分的准确度，采用推荐系统中广泛使用的平均绝对误差（mean absolute error，MAE）和均方根误差（root mean squared error，RMSE）两个评价指标。这两个评价指标的值越小表示预测效果越好。

MAE的定义如下：

其中，Rtest表示测试集中的评分数量。

RMSE的定义如下：

4.3 实验设置

为了验证本文算法的有效性，在MAE、RMSE两个指标上，同以下算法进行比较：

（1）基于用户的协同过滤推荐算法（user-based collaborative filtering，UCF）。通过预先定义的相似度度量方法计算用户的相似用户集合，根据相似用户，计算出目标用户对目标物品的预测评分。

（2）基于物品的协同过滤推荐算法（item-based collaborative filtering，ICF）。与UCF 类似，根据预先定义的相似度度量方法计算物品之间的相似度，通过用户已评分的物品和目标物品的相似关系，预测用户对目标物品的评分。

（3）基于概率矩阵分解的推荐算法（probabilistic matrix factorization，PMF）[20]。它是以用户-项目评分矩阵为基准，利用矩阵分解模型计算用户和项目的潜在特征表示，通过这两个潜在特征表示的点积，可以得到对原始评分矩阵的一个拟合矩阵，从而对未知的评分进行预测。

（4）基于语义路径的个性化推荐算法（semantic path based recommendation，SemRec[4]）。该方法在利用PathSim 计算用户相似性的基础上，考虑不同元路径的权重对评分结果的影响，通过学习权重，得到不同元路径对用户评分影响的权值，最后预测评分。本文选取其中利用单条元路径计算用户相似度的算法SemRecSgl和针对所有用户的统一权重学习算法SemRecAll进行比较。

本文算法中，用户和项目的潜在特征维度d设置为5，λS值设置为15。λU=λV=λZ=0.001，随机梯度下降的学习率α=0.001。实验采用五折交叉验证方法，将数据集随机分为5 份，每次取其中1 份作为测试集，剩余4 份作为训练集，最终结果为5 次实验结果的平均值。本文选取的元路径是User→Movie→User和User→Movie→Type→Movie→User。

4.4 实验结果

实验结果如表3～表5 所示。参数λS的不同取值对评价指标MAE和RMSE的影响如图4、图5 所示。

Table 3 Experimental results on dataset MovieLens100K表3 在数据集MovieLens100K 上的实验结果

4.5 实验分析

由表3～表5 可以看到，基于异质信息网络的SemRecAll算法和SemRecSgl算法以及本文算法在各数据集上的表现均优于传统的协同过滤算法和概率矩阵分解算法，说明通过引入额外的属性信息确实有利于推荐算法准确性的提升。而且，对比基于单条元路径的异质信息网络算法（SemRecSgl算法）、基于多条元路径的异质信息网络算法（SemRecAll算法和本文算法）在各个数据集上都有比较好的表现。另外对比SemRecAll算法，由于在计算用户相似度时，本文算法考虑到用户之间的非对称情况，可以更加客观地反映用户之间的相似关系；而且与SemRecAll算法不同，本文算法将不同的元路径考虑为不同的权重，体现出不同元路径对于用户相似度的影响程度，使得融合不同元路径的相似度结果更加全面。在评价指标MAE和RMSE上要小于SemRecAll算法。

Table 4 Experimental results on dataset MovieLens1M表4 在数据集MovieLens1M 上的实验结果

Table 5 Experimental results on dataset MovieLens10M表5 在数据集MovieLens10M 上的实验结果

Fig.4 Influence of λS on MAE图4 λS 的取值对MAE 的影响

Fig.5 Influence of λS on RMSE图5 λS 的取值对RMSE 的影响

从图4、图5 可以看到，λS=0 时表示只利用评分信息。随着用户相似关系的引入，λS＞0 时，推荐效果逐渐提升，但在λS＞15 后推荐效果有所下降，说明适当引入相似度信息有利于推荐效果的提升，因此本文选取15 作为λS的取值。

5 结束语

本文提出了一种基于异质信息网络的推荐算法，该算法通过不同的元路径计算用户的非对称相似度，并且考虑将不同元路径的相似度结果加权融合，得到用户之间总的相似度信息。最后利用矩阵分解方法融合评分信息和相似度信息，计算用户对未评分物品的预测评分。实验结果表明，利用非对称性处理用户相似关系并且将相似度结果加权融合有助于推荐效果的提升。未来工作中，将考虑针对不同的用户引入不同的元路径权重，从用户角度进一步提升相似度的准确性。