基于异构信息网络的模糊贴近度推荐算法

朱 元，张九根，卢佳乐，陈 鑫

(南京工业大学 电气工程与控制科学学院，江苏 南京 211816)

0 引 言

目前，在个性化网络推荐领域[1,2]，传统协同过滤方法存在数据稀疏性、冷启动和可信度[3]等问题，相关国内外学者也就此提出了许多方法，包括矩阵降维、数据稀疏性填充、相似性度量改进等[4]。异构信息网络结构因其出色的拓扑结构搭建、属性关系连接多元化受到广大研究学者的关注[5]。文献[6]通过考虑用户与项目维度的相互作用关系，提出了一种基于资源分配过程的加权方法，在一定程度上可以提升推荐质量。文献[7]提出PathSim相似性度量方法，该算法的核心是通过异构网络的属性联系优化相似度计算方式，提高了推荐的可靠性。文献[8]基于异构信息网络，结合用户的隐式反馈信息和提出的信任相关性开发了用于推荐的随机游走算法，有效改善了数据稀疏性问题。但上述方法都只关注了异构信息网络中的部分信息，并未考虑到用户个体评分偏好以及时间维度对整个异构网络中元路径关系的权重影响。鉴于此，本文从用户属性角度考虑，在运用k-means[9]进行聚类的基础上搭建新的异构信息网络，采用模糊贴近度计算用户间相似度，提出了一种基于异构信息网络的模糊贴近度推荐算法。

1 异构信息网络

1.1 异构推荐系统

推荐网络中用户及项目是对象类型节点，对象及链接具有丰富的关系，如用户间和项目间可通过近邻关系有效链接、用户与项目间以行为从属关系进行连接等。令U和I分别表示用户和项目集合,其中U={U1,U2,…,Un}，I={I1,I2,…,Im}，n表示用户数量，m表示项目数量。G=〈V,E〉 表示用户和项目节点及链接关系构成的异构推荐网络模型。其中V(G)=U∪I,E(G)={〈oi,oj〉} 且oi,oj∈U∪I，V表示推荐网络中的对象类型，E表示关系链接，不同的链接对象具有不同的关系链接。以电影评分为例，用户与电影彼此间用实线链接，表示用户对项目的评分行为；用户间或电影间用短虚线链接，表示用户间或电影间的关系链接。由图1可知，用户a已评分电影为b、c，用户b已评分电影为a、b、e，用户c已评分电影为a、c、d，用户d已评分电影d、e，用户与电影的评分关系用实线连接。因对象节点较少，通过观察可以得到具有共同评分的用户关系对： 〈a,b〉、〈a,c〉、〈b,c〉、〈b,d〉、〈c,d〉， 此时认为上述用户关系对中的元素互为近邻用户，在图1中用长虚线进行连接，同理可得近邻项目关系对。

图1 异构推荐网络模型

1.2 异构信息网络

信息网络[10]一般采用有向加权图G=〈V,E,W〉 的形式表示，其中V表示网络中的对象节点，E表示对象间链接关系，W：E→R+是从边e∈E到实数w∈R+的权重映射。在网络中，有一个对象类型映射函数φ：V→A和一个链接类型映射函数φ：E→R, 即每个对象v∈V属于一个特定的对象类型φ(v)∈A， 每条链接e∈E属于特定的关系φ(e)⊂R。 当对象类型数|A|>1或关系类型数|R|>1， 称该网络为异构信息网络。

异构信息网络中，两个对象之间链接关系可以有多条不同路径，且对象之间的不同对应关系可以通过不同路径进行表示，如“用户-项目-用户”连接方式表示用户之间的共同评分联系，而更换链接方式为“用户-职业-项目-职业-用户”连接，表示共同职业的用户对同一项目的评分。上述能够将对象间关系链接映射表示出来的路径链接称为元路径，形式定义如下：

P的路径长度表示在路径上组合关系的数量。若仅突出关系连接而忽略连接属性权重，可将用路径的类型名称对元路径属性关系链接简单表示。例如，元路径可用于表示评分链接中的用户-项目的评分关系，记为UIU。在网络G中，设a1和al+1之间存在元路径链接关系p=(a1a2…al+1)， 如果对于∀i，φ(ai)=Ai且每条路径链接ei=〈aiai+1〉 属于P中的每个关系Ri， 则称路径p严格遵循元路径P，并称这些路径是元路径P的路径实例，表示为p∈P。

如果在TG中，若p是P的反向路径，则称p是P的反元路径，表示为P-1， 它定义了P的反向关系。类似的，p的反路径实例被定义为p的反向路径，表示为p-1。 当且仅当Al=A1时，元路径P1=(A1A2…Al) 与P2=(A1A2…Ak) 可以直接进行连接，连接组合后新的元路径记为P=(P1P2)， 该路径的属性关系链接记为 (A1A2…AlA2…Ak)。 得到元路径的链接后，采用PathSim算法[11]来进行两个对象x和y之间的相似性

(1)

其中，px∶y是x和y之间的路径实例，px∶x是x和x之间的路径实例，py∶y是y和y之间的路径实例。

1.3 属性聚类及元路径关系抽取

1.3.1 异构信息网络属性聚类

异构信息网络中对象类型或链接类型呈现多样化，对聚类结果有很大影响。例如针对两个不同对象节点而言，选择不同的元路径关系链接在语义层面的解释意义将大不相同，聚类结果也将具有很大误差。具体实例如下：

如图2所示该异构信息网络实例中包含3种类型对象：职业(occupation，O)、用户(user，U)以及评分项目产生的时间(time，T)。此外，包含两种链接类型：用户和职业之间的从属关系用实线表示，用户和评分时间的关系用虚线表示。用户彼此间联系采用不同的元路径连接表示。如用户之间(属于同一职业)通过职业进行连接可表示为元路径U-O-U，而根据用户评分时间段进行连接(同一时间区间内对项目的评分)可表示为元路径U-T-U。在用户聚类过程中选择何种连接方式进行聚类是解决问题的关键。

图2 职业、用户和时间的一个异构信息网络实例

用户间的链接方式可通过不同元路径连接，必将导致不同的聚类结果。图3(a)以职业作为关系链接权重将用户聚类结果分为两组： {1,2,3,4} 和 {5,6,7,8}； 图3(b)中以评分时间段作为关系链接权重将用户连接分为不同于图3(a)的两组； {1,3,5,7} 和 {2,4,6,8}； 图3(c)将职业和评分时间段关系权重共同考虑将聚类结果分为4组： {1,3}、 {2,4}、 {5,7}、 {6,8}。

图3 元路径权重划分聚类

不同聚类方式都具有其合理性，但语义解释层面却大不相同。用户选取元路径或元路径的权重组合时需要以聚类结果为选择依据，但由用户自己筛选聚类依据难以实现，因此在聚类过程中为用户提供指导信息将提升结果的准确性。例如，用户指定聚类结果中分别包含为{1}和{5}两个元素且目标聚类数划分为两类，若将元路径关系链接权重A-O-A作为聚类标准，可将聚类结果分为 {1,2,3,4} 和 {5,6,7,8}； 当聚类目标要求划分为4类，且要求4类结果分别含有对象 {1}，{2}，{5}，{6} 时，提供选择元路径A-O-A和A-T-A参考，聚类结果为 {1,3}， {2,4}， {5,7}， {6,8}。

元路径关系链接权重差异性使得异构信息网络的结构模式呈现多元化，不同选择结果对聚类结果的影响巨大。此外，大多情况下仅通过一种属性链接权重作为衡量标准无法满足用户的聚类需求，会直接影响后续推荐工作。例如在社交网络中，不同用户所具有的朋友数量差异明显，某些用户朋友数量基数庞大而相应的一些用户朋友数量较少。针对这种情况，仅使用某一特定的元路径连接方式将造成聚类结果的偏差，此外，用户朋友数量随时间变化也呈动态变化趋势。因此，在聚类阶段，首先采用k-means聚类算法，对用户属性的依赖性及时间维度进行聚类，基于此再对元路径的关系进行选择。k-means算法步骤如下：

(1)定义一个用户数据集合Ω(n为样本数，xi为一个m维向量，表示第i个数据m个属性)

Ω={xi|xi=(xi1,xi2,xi3,…xim),i=1,2,…,n}

(2)

用C表示簇中心，k为簇中心个数

C={ci|ci=(cj1,cj2,cj3,…cjm),j=1,2,…,k}

(3)

(2)计算各用户到簇中心的欧式距离

(4)

(3)迭代更新n簇的中心至其不再变化，最后将用户分为n簇。

1.3.2 元路径关系抽取

在k-means聚类算法的基础上，对用户相关属性的联系及时间维度进行过滤筛选，构建异构信息网络模型，之后采用线性回归的多关系抽取算法对不同社区内的元路径关系进行选取，算法的基本步骤如下：

(1)建立新的目标关系矩阵。采用k-means聚类算法对用户进行聚类后，建立异构网络模型并以此构建新的目标关系矩阵，为了衡量不同属性的元路径权重把权重值标准化到[0,1]区间

(5)

(6)

(7)

(3)系数向量的解表示不同元路径关系链接的权重高低。用W来表示权重向量矩阵。

2 基于异构信息网络的模糊贴近度推荐算法

2.1 模糊贴近度

模糊数学作为一门学科从数学角度对客观事物的类属不确定性进行研究并加以引用。模糊数学并非把数学概念变得模糊不堪，而是应用合理的数学分析、统计学等方法完成必然性现象到偶然性领域的跨越。推荐算法中用户对某个物品或项目的评价值，以5个阶梯评价划分可分为(讨厌，不喜欢，一般，较为喜欢，很喜欢)，而这种评价往往带有模糊的不确定性。因此，选择用模糊数学来衡量两个用户的偏好相似度，对寻找目标用户的近邻相似用户具有很大帮助且具备技术的可行性和科学性。

根据上述分析，先计算相似度的测量，对于用户间相似度进行排序，选出相似度最高的近邻用户之后进行推荐。对相似度进行计算时，根据元路径关系权重矩阵，来进行指标量化，即基本测算思路如图4所示：确立异构网络→元路径权重值→计算相似度。

图4 异构网络模糊贴近度应用

2.2 用户属性指标的隶属度计算

设用户集合U=(u1,u2,…,un) 中每个用户均存在m个固有属性，据此可确定用户固有属性集U(Pi,Xm)， 其中Xm为用户的具体属性。由式(7)可得，元路径权重集合W，表示异构网络中元路径边的权重程度；由此得到U和W这两个非空集合的直积

μR∶=U×W→[0，1]

(8)

μR表示序偶 〈u,w〉 的隶属权重程度映射到隶属区间。不同元路径连接的链接权重值都可以用隶属度来进行表示且链接权重符合概率分布，即元路径连接权重隶属函数。

对于数值中权重越高的元路径权重边，代表该属性权重边在异构网络模型中占有更高的权重影响，隶属权重函数采用中间型梯形分布函数。

将m项评分的各级临界值表示为

B=(bij)m×n

(9)

则可计算异构网络中每个用户各项属性的元路径隶属值权重矩阵

F=(fij)m×nF=μR·B

(10)

其中，bij和fij分别为矩阵B和F在i行j列的取值。在运用式(10)所计算出的隶属权重矩阵F中，不同元路径链接关系权重取值均在[0,1]，而n个用户的元路径链接隶属权重向量则分别为F1,F2,…,Fn。

2.3 用户贴近度计算

模糊贴近度计算一般采用最大值最小值贴近度，计算公式如下

(11)

其中，σ(U1,U2) 表示模糊集U1和U2的贴近度，UU1(u)和UU2(u)分别为U1和U2的固有属性集的隶属权重程度。在这里隶属权重程度表示异构网络中不同的元路径关系链接权重边属于该用户的隶属程度，权重值大小刻画了属性对用户所属的隶属程度的高低。

对于某数据集内n个用户的属性隶属权重向量F1,F2,…,Fn， 隶属权重矩阵如下所示

(12)

其中，fnm表示第n个用户的第m个属性的隶属权重值。

将关系权重矩阵代入式(11)，即可得到任意两个用户之间的贴近度，即用户间相似程度。对得出的用户间相似度进行Top-N排序，得到最近邻用户，之后采用评分预测方式进行项目推荐，并验证推荐结果的准确性。

3 实验结果与分析

3.1 实验环境搭建

实验硬件环境为：Intel(R) Core(TM) i5-5257U处理器，Windows10，64位操作系统；所使用的软件环境为：Pycharm平台开发环境，数据库选取Mysql。

3.2 实验数据集

本次实验数据集选用Epinions数据集[12]作为实验数据源，Epinions是一个着名的产品评论网，其中包括49 290名用户，139 738个不同的项目，用户可以对产品进行评分并提交他们的个人评论, 评分标准通过1至5之间的整数值表示。随机从数据集中抽取80%作为训练集，其余作为测试集。为了验证该推荐算法在不同稀疏程度数据集上的效果，本文对数据集以单个用户信任记录数T和单个商品评分数为标准进行数据筛选，得到稀疏性不同的Epinions-A(T>11,I>11)和Epinions-B(T>21,I>21)。数据集的相关统计见表1。

表1 Epinions数据集信息

3.3 评价指标

本次实验对提出推荐算法的有效性评估以平均绝对误差(mean absolute error，MAE)以及均方根误差(root mean square error，RMSE)为度量标准，具体公式如下

(13)

(14)

3.4 实验结果分析

常用的相似度计算包括余弦相似性(Cosine)和皮尔森相似性(Pearson)，在异构信息网络中HeteSim[13]算法也尤为经典，为验证本文所提出算法的有效性，将本文提出的算法(HNCR)分别与这3种算法进行对比，同时以MAE和RMSE值为度量标准，近邻用户数量为自变量，实验结果如图5、图6所示。

图5 Epinions数据集MAE结果

图6 Epinions数据集RMSE结果

由图5图6可以看出：

(1)算法的MAE值和RMSE值随着近邻用户数的增加大致呈减小的趋势，即算法精度随近邻用户数先增大而有所提高。

(2)相比其它3种算法，基于异构网络贴近度的推荐算法HNCR在MAE和RMSE两种指标上的值均达到最小，具有最优推荐效果。

图7～图9是稀疏程度存在差异的数据集上4种算法的实验结果，以近邻用户数为自变量，MAE值为准确度度量标准。可以看出，数据集稀疏程度的差异同样对准确度也有一定的影响，Epinions-B上的准确度达到最大。总体而言，数据集越稀疏，准确度越低；越稠密，准确度越高。

图7 Epinions数据集

图8 Epinions-A数据集

图9 Epinions-B数据集

4 结束语

本文首先对推荐系统中基于异构信息网络的算法进行了总结，为解决推荐算法数据稀疏性等问题，在引入异构信息网络的基础上，采用模糊数学贴近度的方式来进行用户之间相似度的计算，从而提出了基于异构信息网络的模糊贴近度推荐算法。通过与其它算法进行对比，实验结果表明基于异构网络的推荐算法具有更低的MAE和RMAE值，推荐准确性更高。此外，关于异构信息网络推荐算法如何降低时间复杂度以及与真实网络的实时交互将是下一步研究的方向。