融合潜在狄利克雷分布与元路径分析的用户相关性度量方法

徐红艳 王丹 王富海 王嵘冰

摘 要：用户相关性度量是异构信息网络研究的基础与核心。现有的用户相关性度量方法由于未充分开展多维度分析和链路分析，其准确性尚存在提升空间。为此，提出了一种融合狄利克雷分布（LDA）与元路径分析的用户相关性度量方法。首先利用LDA进行主题建模，通过分析网络中节点的内容来计算节点的相关性;然后，引入元路径来刻画节点间关系类型，通过关联度量（DPRel）方法对异构信息网络中的用户进行相关性测量;接着，将节点的相关性融入到用户相关性度量计算中;最后，采用IMDB真实电影数据集进行实验，将所提方法和嵌入LDA主题模型的协同过滤推荐方法（ULRCF）、基于元路径的相关性度量方法（PathSim）进行了对比分析。实验结果表明，所提方法能夠克服数据稀疏性弊端，提高用户相关性度量的准确性。

关键词：用户相关性;异构信息网络;主题模型;元路径;度量

中图分类号：TP302.1

文献标志码：A

User relevance measure method combining latent Dirichlet allocation and metapath analysis

XU Hongyan， WANG Dan， WANG Fuhai， WANG Rongbing*

School of Information， Liaoning University， Shenyang Liaoning 110036， China

Abstract：

User relevance measure is the foundation and core of heterogeneous information network research. The existing user relevance measure methods still have improvement space due to insufficient multidimensional analysis and link analysis. Aiming at the fact， a user relevance measure method combining Latent Dirichlet Allocation （LDA） and metapath analysis was proposed. Firstly， the LDA was used to model the topic， and the relevance of nodes was analyzed by the node contents in the network. Secondly， the metapath was introduced to describe the relationship type between nodes， and relevance measure was carried out for users in heterogeneous information network by relevance measure method （DPRel）. Thirdly， the relevance of nodes was incorporated into the calculation of user relevance measure. Finally， the experiment was carried out on IMDB real movie dataset， and the proposed method was compared with the collaborative filtering recommendation method embedded in LDA topic model ULRCF （Unifying LDA and Ratings Collaborative Filtering） and metapath based similarity method （PathSim）.The experimental results show that the proposed method can overcome the drawback of data sparsity and improve the accuracy of user relevance measure.

Key words：

user relevance; heterogeneous information network; topic model; metapath; measure

0 引言

信息网络由一系列节点以及连接节点的关系构成，按照网络中的节点类型和关系类型，可以分为同构信息网络和异构信息网络。由于异构信息网络比同构信息网络具有更加丰富的信息而更加贴近现实，如社交网络、新媒体网络、文献网络等。异构信息网络中节点的异构性、连接的复杂性以及数据的稀疏性等因素为用户相关性度量带来更大的难度，而用户相关性度量是开展异构信息网络相关研究的基础与核心。

近年来，众多学者对用户相关性度量方法进行深入研究以准确获取用户间的关联，其中余弦相似度和皮尔森相关系数[1]法仅需要用户对物品的评分来计算用户之间的相关性，但它无法解决冷启动问题，必须依赖大量用户历史数据。随着对信息网络的研究不断加深，学者们利用网络中的节点信息和链接进行用户相关性度量，提出基于节点特征的相关性度量方法[2-3]，将两个节点特征的排名结果之间的相关性定义为节点之间的相关性，解决了数据稀疏问题，但其缺点是度量精度不高。目前，异构信息网络的主流用户相关性度量方法是基于元路径进行相关性度量[4-5]，借助用户在网络中链接的方式来计算用户的相关性， 但此类方法并未挖掘网络路径中非用户节点的内容相关性，而非用户节点信息是用户偏好和需求的最直观表现， 故得到的用户相关性度量准确性仍有待提升。

为解决非用户节点语义信息缺失带来的用户相关性度量不准确问题，本文引入狄利克雷分布（Latent Dirichlet Allocation， LDA）主题模型[6]挖掘网络中非用户节点特征;采用元路径分析用户节点间的关联关系，提出了融合LDA与元路径分析的用户相关性度量方法（User Relevance Measure Method Combining LDA and Meta Path Analysis，LPUSim）。该方法首先利用网络中非用户节点的语义信息挖掘用户偏好;然后，结合DPRel方法[7]计算元路径中用户节点间的关联度得到用户相关性;最后，使用归一化方法获得不同元路径的相应权值，对元路径进行加权整合，从而更全面地度量用户的相关性。对比实验表明，本文所提方法能更真实、更准确地分析用户相关性。

1 相关工作

1.1 文本特征提取

文本分析是机器学习算法的主要应用领域之一。它是将文本模型转换为机器可识别的格式以进行计算机处理，同时尽可能保留文本的原有语义信息[8]。Salton等[9]提出向量空间模型（Vector Space Model， VSM），把对文本内容的处理简化为向量空间中向量的运算，使问题的复杂性大为降低，但它只关注特征项的频率信息从而丢失了文本上下文的语义信息;Deepwester等[10]提出的隐语义分析（Latent Semantic Analysis， LSA）将词和文档映射到潜在语义空间，对词文档进行降维，从而提高了信息检索的精确度。相较于传统向量空间模型，潜在语义空间的维度更小，语义关系更明确，但存在多义词等问题。Blei等[6]提出的LDA主题模型是在LSA基础上进行了改进，可以被用于识别大规模文档集或语料库中潜藏的主题信息，同时考虑了上下文语义之间的关系，并在一定程度上解决一词多义问题。本文利用LDA可以获知用户的偏好主题，为非用户节点的特征提取提供支持。

1.2 用户相关性度量

相关性度量作为数据挖掘领域研究的重要方向之一，众多学者已经对其开展了较为深入的研究：面向同构信息网络，Jeh等[11]提出的个性化PageRank方法;Kusumoto等[12]在SimRank中提出的线性递归表达式能应用于并行计算，使得大规模图计算成为可能，但这些方法忽略了对象和链接的类型区别; Huang等[13]提出了基于元结构在大规模文献异构网络中的相关性度量方法; Meng等[14]提出了一种FSPG贪婪的方法来选择最相关的元路径进行相关性计算。这些方法都与异构信息网络的结构相关性度量有关，具有一定的局限性。Sun等[15]提出PathSim相关性度量方法可以系统地区分连接两个用户路径间的语义;Gupta等[7]提出的DPRel方法是一种比较新颖的、半度量的用户相关性度量方法，可用于相同和不同类型的节点。尽管这些方法已经取得了良好的应用效果，但它们并未考虑节点的内容，从而导致计算结果不够准确。

2 融合LDA与元路径的用户相关性度量

本文不仅考虑了网络中节点之间的直接关系，而且考虑了网络中非用户节点特征之间的潜在相关性。首先，利用网络中非用户节点特征挖掘出用户偏好，实现基于节点主题的用户相关性度量;然后，引入元路徑来刻画节点间关系类型，利用基于元路径的半度量DPRel方法[7]计算用户的相关性;最后，利用本文提出的LPUSim方法对非用户节点的相关性分数进行加权整合并应用到用户的相关性度量中。

2.1 基于节点主题的用户相关性度量

LDA是一种文档主题生成模型，它包含词、主题和文档三层结构，也称为一个三层贝叶斯概率模型。生成模型可以看成是一个文档的产生过程，即认为文章中的每个单词都是通过“选择具有一定概率的主题并以一定概率从主题中选择某个单词”的过程获得的。主题的文档遵循多项式分布，并且该单词的主题遵循多项式分布。因此，如果要生成一篇文档，则每个单词出现在其中的概率如式（1）所示：

p（词语|文档）=

∑主题p（词语|主题）×p（主题|文档）（1）

为更好地说明所提方法，本文以IMDB电影数据集为例，该数据集中不仅包含用户对电影的评分记录，还包含了电影的剧情信息。为了能够方便地计算出用户所关注的电影主题，即用户偏好特征，本文利用LDA主题模型把文本信息转化为了易于建模的数字信息。用户看过由同一导演执导的电影，但这些电影的主题可能有很大差异，以往只考虑了元路径对用户相关性的影响，并没有考虑电影主题也会对用户的相关性产生影响。假设所有电影的文档主题概率分布向量集合为T= [T1 ，T2，T3，…]，则节点主题相关度采用余弦相似度对同一个演员饰演电影的文档主题概率分布向量进行计算，如式（2）：

SimL（u，v）=Sim（Tau，Tav）=∑|A|a=1COS（Tau，Tav）N（2）

其中：Tau表示用户u看演员a演过的所有电影主题概率分布向量集合，N表示Tau和Tav集合中元素数量的最小值，A表示演员的数量。

本文基于用户观看同一个演员饰演的电影评分来求用户相关性计算公式如式（3）：

SimS（u，v）=∑|A|a=1Simscore（u，v）（3）

其中，Simscore（u，v）为基于用户属性和评分的协同过滤推荐算法[16]中提出的相似度计算公式，避免了传统相似度计算的弊端，提高了用户相关度的区分性，有利于评分预测和推荐。

用户看了相同主题的电影并且对它们的评分相似才能够说明是喜欢这些电影，即他们的兴趣偏好相似，因此，基于电影主题与用户评分共同度量用户相关性的公式如式（4）：

SimLS（u，v）=SimL（u，v）×SimS（u，v）（4）

2.2 基于元路径的用户相关性度量

2.2.1 基本定義

建立在Sun等[15]描述的框架之上，首先给出构建异构信息网络中相关性度量所需的一些定义。

定义1 信息网络是一个带有对象类型映射函数τ：V→A和连接类型映射函数φ：ε→R的有向图G（V，ε）其中每个对象v∈V属于一个特定的对象类型τ（v）∈A，每个链接e∈ε属于一个特定的关系Φ（e）∈R。

当对象的类型A>1或关系类型R>1，网络是异构信息网络;否则它是一个同构信息网络。

为更好地描述所提方法，本文以IMDB电影信息网络为例。该网络为异构信息网络，其中节点和边均符合异质信息网络的定义，图1显示了IMDB信息网络的实体关联。网络中包含5种类型节点，分别为用户（U）、电影（M）、演员（A）、导演（D）、电影类型（G）。4种类型的链接关系分别为演员和电影之间的参演（act）关系、用户和电影之间的评分（rate）关系及电影类型和电影之间的属于（attribute）关系、导演和电影之间的指导（direct）关系。

定义2 元路径P是在网络模式TG=（A，R）的图上的一条路径，它的形式是A1→R1A2→R2…→RlAl+1，定义了类型A1和类型Al+1间的复合关系R=R1R2…Rl，其中，代表关系上的复合运算。

在异构信息网络中，可以通过不同的路径连接两个对象，这些路径将具有不同的语义含义。例如，IMDB网络模式中两个元路径UMU（用户电影用户）和UMAMU（用户电影演员电影用户）分别如图2（a）和（b）所示。

定义3 给定网络G=（V，ε）及其网络模式TG，本文将元路径P=（A1→A2→…→Al）下的邻接矩阵称作关系矩阵，并定义M=WA1A2WA2A3…WAl-1Al，其中WAiAj为类型Ai和类型Aj间的邻接矩阵。M（i，j）代表元路径P上对象xi∈A1和对象yi∈Al之间的路径实例的数目。

定义4 给定一个元路径P=（A1→A2→…→Am→…→Al→Al+1），若A1与Al+1是不同的对象类型，那么将异构网络用只有A1与Al+1对象类型的二分网络表示，源对象a1i∈A1与目标对象b（l+1）j∈Al+1之间的相关性如式（5）：

DPRel（a1i，b（l+1）j|PRel）=

ω（a1i，b（l+1）j）1deg（a1i）+1deg（b（l+1）j）1deg（a1i）∑ jω（a1i，b（l+1）j）+1deg（b（l+1）j）∑ iω（a1i，b（l+1）j）（5）

其中：ω（a1i，b（l+1）j）是来自交换矩阵M（a1i，b（l+1）j）中的值，即表示在指定元路径中实体类型a1i∈A1与b（l+1）j∈Al+1之间的路径实例条数，deg（a1i）与deg（b（l+1）j）是a1i和b（l+1）j分别在二分网络中节点的度。

在本文的工作中，需要测量相同类型对象之间的相关性，即元路径的源和目标对象类型是相同的。计算公式如式（6）：

SimP（u，v）=DPRel（a1i，b（l+1）j|PRel）=

X·Y‖X‖2+‖Y‖2-X·Y（6）

其中：对于PLRel=（A1A2…Am）， X=DPRel（a1i，bmk|PLRel）用来计算源节点a1i和所有中间对象之间的相关度，bmk∈Am，k。同样地，对于P-1RRel=（Al+1Al…Am），Y=DPRel（a（l+1）j，bmk|P-1RRel），用来计算目标对象a（l+1）j和所有中间对象之的相关度，bmk∈Am，k。

2.2.2 元路径的生成与选择

如何生成所有可能的和有效的元路径是基于元路径的相关性度量工作中的重要环节。本文探索异构信息网络的网络模式，以生成从目标对象类型开始和结束的所有元路径。生成元路径过程如图3所示。

本文中要研究的元路径是由起点和终点均是用户类型的节点组成的路径。根据无限长度元路径下PathSim的有限行为定理[15]可以推断，无限增加元路径长度不会提升相关性度量效果，于是本文采用了长度限制在4以内的元路径结合式（6）进行相关度计算。如表1所示，考虑了4条元路径，从一定程度上解决了数据稀疏问题，从而提高了信息推荐的准确性。

2.3 LPUSim相关性度量方法

本文考虑了元路径UMAMU对用户相关性度量影响的基础上，同时也考虑了电影主题信息对挖掘结果的影响。设想一些用户看来同一个演员饰演的电影，但是电影主题风格迥异，如用户U1和U2分别看了演员A1饰演的以爱情和惊悚为主题的电影。因此，本文将求得用户偏好的相关性得分作为节点间路径权重，与基于元路径计算获得的用户相关度相融合计算用户相关性。

为了方便后续计算，本文将元路径UMGMU、UMAMU、UMDMU、UMU依次编号为1、2、3、4。本文计算第i（i=1，2，3，4）条元路径的相关度方法如式（7）：

Simi（u，v）=SimLS（u，v）×SimP（u，v）（7）

其中SimP表示基于元路径的用户相关度。

为防止式（7）求得的相关度过小而失去相似度比较的特征，本文对式（7）所得的相关度进行同比放大，放大策略如式（8）：

Simi′（u，v）=Simi（u，v）Max（S1，S2，S3，S4）（8）

其中：Si表示第i条元路径所有用户相关度集合， Max（S1，S2，S3，S4）表示4条元路径所有用户相关度集合中的最大值。本文将式（7）中计算出的相关度值进行同比放大后，虽然用户相关度的值会发生变化，但每个相关度的排序顺序是不变的。这样既解决了因相关度过小而失去相似度比较特征的问题，同时也保证了相关度依旧在[0，1]。

2.3.1 多重元路径的组合

由于在异构信息网络中，可能存在具有不同语义的若干条元路径。不同元路径度量的用户相关度不同，因此，应该将较高的权重分配给具有重要关系的元路径。此外，仅遵循一条元路径，可能会错过其他语义上有意义的元路径。因此，考虑到对以上分析得到的4条元路径进行组合可以更全面、更准确地度量用户相关性。本文通过按比例分配的原则计算元路径的权重，第i条元路径的权重如式（9）：

ωi=Simi∑4i=1Simi（9）

其中Simi表示第i条元路径下所有用户的相关度之和。

在获得元路径的权重之后，最终两个用户的相关度如式（10）：

Sim（u，v）=∑4i=1ωi×Simi′（u，v）（10）

2.3.2 LPUSim方法在推荐中的应用

综上，现将融合LDA与元路径的分析用户相关性度量方法应用于推荐的流程描述如下，其中，u表示目标用户u0评分过的项目评分均值，v表示邻居用户v评分过的项目评分均值，rv，i表示用户v对项目i的实际评分。

输入 IMDB电影信息网络，元路径集L={P1，P2，P3，P4}，目标用户u0;

输出 对目标用户的TopN推荐结果。

1）通过IMDB电影数据集中5种节点、4种边类型构建异质信息网络，提取两个用户之间长度在4以内的元路径集P。

2）为了提高查询效率本文引用文献[17]中剪枝策略。从L中任选一条元路径pi，以UMAM为例，如果两个用户没有看同一个演员演的电影则必定不相关，返回步骤2）重新选择，否则执行步骤3）。

3）构建用户电影评分矩阵Rm×n，用式（3）求用户相关性。

4）根据式（4），利用节点主题与用户评分共同度量用户相关性。

5）根据式（6）的DPRel相关性度量方法求取基于元路径的相关度。

6）根据式（7）计算总的相关度。

7）根据归一化方法获取权重，拟合4条元路径相关性，获得最终的用户相关度。

8）利用步骤7）中的用户相关度选择与其最相似的K个邻居作为目标用户u的最近邻居集Neighbor（u）。

9）根据目标用户的相似用户集合，用式（11）为目标用户的未知项目预测评分，最后生成TopN推荐集。

u，i=u+∑ v∈Neighbor（u）Sim（u，v）（rv，i-v）∑ v∈Neighbor（u）Sim（u，v）（11）

假设该网络中有n个用户，m部电影，k表示实例路径数，融合LDA与元路径分析的用户相关性度量方法复杂度分析如下：步骤3）～4）过程计算用户兴趣偏好，假设有t（t

3 实验分析

3.1 数据集和实验环境描述

本文使用themoviesdataset数据集，它是IMDB电影数据集的子集。该数据集是从https：//www.kaggle.com/rounakbanik/themoviesdataset网站下载的。该数据集包含了从1995—-2017年发布的电影信息。本文实验使用的IMDB电影数据集包含45-000部电影、19种电影类型、5-741名演员、10-656名用户、1-398名导演和16-198个链接。

根据实验需要将整个实验数据集进一步地划分为训练集和测试集，随机抽取数据集75%作为训练集，另外25%作为测试集。本文的实验环境：操作系统为 Windows XP，处理器为Intel core i5和8GB内存，代码使用Python语言实现。

3.2 评价指标

本文选取3个在推荐方法测评中应用最为广泛的评价指标：准确率（precision）、召回率（recall）和综合值F，如式（12）～（14）所示：

Precision=∑u∈UR（u）∩T（u）∑u∈UR（u）（12）

Recall=∑u∈UR（u）∩T（u）∑u∈UT（u）（13）

F=2×Precision×RecallPrecision+Recall（14）

其中：R（u）是用户在训练集上的行为给用户给出的推荐列表，而T（u）是用户在测试集上的行为列表。

3.3 实验结果与分析

为了验证本文提出的融合LDA与元路径分析的用户相关性度量方法的有效性，将它与当前主流用户相关性度量方法：ULRCF方法[18]与PathSim方法[15]进行比较。图4描述了隨着TopN（5，10，20）的变化，各方法的准确率、召回率及综合指标F值的变化趋势。

由图4（a）和图4（b）可以看出，无论N取何值，ULRCF方法的准确率、召回率普遍低于替他推荐方法，原因是该方法基于传统协同过滤推荐算法，并结合LDA主题模型挖掘电影本身特征来生成推荐列表，但由于电影本身特征提取的精确度原因，导致推荐效果不太理想;PathSim基于多条元路径获取更多用户信息，进而计算用户相关度，在一定程度上化解了协同过滤推荐中数据稀疏的问题，进而得到相对较高的准确率和召回率，说明引入元路径可以在很大程度上提高推荐质量;而本文提出的LPUSim相关性度量方法，一方面引入LDA主题模型，挖掘了电影本身所携带的语义信息，考虑了用户主题偏好，另一方面引入元路径来度量用户的相关性，并且对多条元路径进行加权整合后能够更加全面度量用户相关性，因此准确率、召回率指标上的表现都远远超过了其他两个方法。从图4（a）可看出，所提方法在最近邻居数为10时，取得最大的准确率，推荐效果最好，充分说明综合元路径分析和引入LDA模型可以显著提高推荐的质量。而图4（c）也进一步证实了本文所提方法的可行性，确实在一定程度上改善了推荐系统的推荐效果。

[12]  KUSUMOTO M， MAEHARA T， KAWARABAYASHI K I. Scalable similarity search for SimRank[C]// Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2014： 325-336.

[13]  HUANG Z， ZHENG Y， CHENG R， et al. Meta structure： computing relevance in large heterogeneous information networks[C]// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2016： 1595-1604.

[14]  MENG C， CHENG R， MANIU S， et al. Discovering metapaths in large heterogeneous information networks[C]// Proceedings of the 24th International Conference on World Wide Web. Republic and Canton of Geneva， Switzerland： International World Wide Web Conferences Steering Committee， 2015：754-764.

[15]  SUN Y， HAN J， YAN X， et a. PathSim： meta pathbased topKsimilarity search in heterogeneous information networks[J]. Proceedings of the VLDB Endowment， 2011， 4（11）： 992-1003.

[16]  丁少衡，姬東鸿，王路路. 基于用户属性和评分的协同过滤推荐算法[J]. 计算机工程与设计， 2015， 36（2）：487-491. （DING S H， JI D H， WANG L L， et al. Collaborative filtering recommendation algorithm based on user attributes and scores[J]. Computer Engineering and Design， 2015， 36（2）：487-491.）

[17]  邱庆羽，李婧，全兵，等. 基于文献信息网络语义特征的相似性搜索[J]. 计算机应用， 2018， 38（5）：1327-1333. （QIU Q Y， LI J， QUAN B， et al. Similarity search based on semantic features of bibliographic information network[J]. Journal of Computer Applications， 2018， 38（5）：1327-1333.）

[18]  高娜，杨明. 嵌入LDA主题模型的协同过滤推荐算法[J]. 计算机科学， 2016， 43（3）：57-61. （GAO N， YANG M. Topic model embedded in collaborative filtering recommendation algorithm[J]. Computer Science， 2016， 43（3）：57-61.）

This work is partially supported by the National Natural Science Foundation of China （71771110）， theSocial Science Planning Foundation of Liaoning Province of China （L18AGL007）， the Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education in Jilin University （93K172018K01）.

XU Hongyan， born in 1972， M. S.， associate professor. Her research interests include deep Web， personal recommendation， data mining.

WANG Dan， born in 1994， M. S. candidate. Her research interests include personal recommendation， data mining.

WANG Fuhai， born in 1990， M.S. candidate. His research interests include deep learning， personal recommendation.

WANG Rongbing， born in 1979， Ph. D.， associate professor. His research interests include big data analysis， cloud computing.