ISSN 
-
协同过滤(collaborative filtering)[1]是推荐系统发展史上发展最快、应用最广的一类算法，其基本思想是相似的用户对商品的选取也是相似的，根据与目标用户最相似的K个邻居对目标项目的评分来进行推荐。但是传统的相似度度量方式只考虑了用户评分这一个因素，评分矩阵是极其稀疏的，这种情况下得到的用户相似性是不准确的，最终推荐精度自然不高。
近年来，社交网络朝异质性方向发展：网络中包含多种实体(entity)，实体间存在多种关系(relation)，这种网络被称为异构信息网络[2](heterogeneous information network, HIN)。大数据时代的HIN中包含丰富的语义信息，对其进行深度挖掘分析能够得到非常有意义的知识[3-4]，而HIN中包含的更多的有效信息会带来更好的推荐效果[5-6]，所以近年来开始兴起在HIN上做推荐问题的研究。HIN中包含多种类型的实体和多种多样的边信息。为了更好地利用异构网络中所蕴含的多样性内容，可以用元路径(meta path)表示不同的关系[7]。两实体之间的语义信息路径为一条元路径，两节点间不同的元路径代表不同的语义联系。基于元路径开展了大量的工作，相似度度量是其中最重要和基础的一个方向，基于对称元路径的PathSim[7]和基于任意元路径的PCRW[8]与HeteSim[9]等算法相继被提出。但这3种算法都是建立在无权异构网络基础上，忽略了HIN中的边属性信息，因此都不能被直接应用到加权HIN上的推荐工作中。利用元路径的概念可以灵活地运用HIN中丰富的信息来做推荐[9]。
目前基于HIN的推荐工作还处于起步阶段，文献[10]结合用户评分和多种实体相似度度量方式提出了一种新的矩阵分解推荐框架Hete-MF；文献[11]引入异构网络信息提出了一种基于协同过滤的社会化推荐方法Hete-CF，该方法将社会网络中的异构关系融合进了协同过滤推荐算法中，改善了原算法中数据稀疏和冷启动问题；文献[12]利用用户的隐式反馈信息结合用户不同的异构关系提出了一种新的个性化推荐方法Hete-Rec。一方面，上述方法都旨在融合异构网络中的多元信息并且只考虑了HIN中的部分信息；另一方面，上述方法并没有考虑网络中的边属性问题，没有关注由用户两极化评分造成的本质差别。以电影推荐网络为例，5分表示喜欢，1分表示讨厌；同样，一部电影被贴上某种标签的次数越多代表该电影越偏向于此类型。如果在推荐过程中不考虑此边属性问题，很可能会使推荐结果有所偏差。文献[6]提出了加权HIN的概念，通过区分网络中边上的不同属性值来探索更全面的元路径语义信息以实现更准确的推荐，但该方法并没有提出新的相似度度量方法，而是将有权元路径分解为有确定属性值限定的原子元路径，利用的还是原有的相似度度量方法。本文引入加权HIN的概念，充分考虑HIN中的节点类型信息和多种边属性信息，并且对用户评分进行了两极化映射处理，提出了一种引入加权异构信息的改进协同过滤算法。
-
定义 1 加权异构信息网络(weighted heterogeneous information network, WHIN)[7, 9]：可以用一个有向图$ G = (V, E, \mathit{\mathbb{W}}) $表示，且节点类型映射函数$ \emptyset :V \to B $，表示每一个$ v \in V $属于节点类型集合B，即$ \emptyset (v) \in B $；ψ表示边类型映射函数，$ \psi {\rm{(}}e{\rm{)}} \in R $表示每一个e∈E属于边类型集合R；映射函数$ \varphi :\mathit{\mathbb{W}} \to W $表示每条边的权重$ w \in \mathit{\mathbb{W}} $属于集合W，即φ(w)∈W。只要|W| > 0且满足|B| > 1或|R| > 1，该信息网络即为WHIN。图 1为一个典型的WHIN，网络中包含7种节点类型和12种实体间的关系。
图 1 加权HIN示例
-
定义 2 加权网络模式：WHIN可以用加权网络模式[7, 9] $ S = (B, R, W) $来简化表示，其中B表示网络中的节点类型，R表示网络中的边类型，W表示网络中边的权重。加权网络模式对网络中节点和边的类型进行了限制，正是这种限制导致了网络的半结构化，指导了网络的语义内涵探索。
对于图 1中的网络，其加权网络模式如图 2所示，该网络模式清晰地表现了图 1中WHIN中所有的节点类型和节点间带权重的关系。通过此网络模式，研究者可以清楚地分辨复杂的HIN中本质上存在的节点类型以及各节点类型间可能存在的关系。
图 2 加权异构信息网络的加权网络模式图
-
定义 3 加权元路径：加权元路径[7, 9]P定义在加权网络模式$ S = (B, R, W) $上，在不引起歧义的情况下，可以直接用节点类型和节点间边上的权重来表示加权元路径$ P = {B_1}({W_1}){B_2}({W_2}) \cdots ({W_{l - 1}}){B_l} $。如元路径$ U\xrightarrow{\rm{Rate}5}M\xrightarrow{\rm{Rate}2\rm{ by}}U $表示观看同一部电影(M)的两个用户(U)，用元路径可直接表示为$ U(5)M(2)U $。否则，加权元路径表示为：$ P = {B_1}\mathop \to \limits^{{R_1}} {B_2}\mathop \to \limits^{{R_2}} {B_3} \cdots \mathop \to \limits^{{R_l}} {B_{l + 1}} $，表示从实体类型Bl到实体类型Bl+1之间的复杂关系$ R = {R_1} \circ {R_2} \circ \cdots \circ {R_l} $，其中，ο代表关系上的连接操作，加权元路径P的长度为R的个数。
-
本文引入加权异构信息计算用户间的相似度，并提出了一种新的改进协同过滤算法。接下来说明如何综合考虑该网络中用户在电影体裁、主演、导演、电影标签类型等多方面的偏好度，从而相对全面地度量两用户间的相似度。
定义 4 用户对某影响因素的偏好度。加权异构电影网络中，基于元路径$ P = {B_1}({W_1}){B_2}({W_2}) \cdots ({W_{l - 1}}){B_l} $，U为用户类型，Bl为导演、演员、电影体裁等某一类型，用户ui对影响因素$ y \in {B_l} $的偏好度定义为：
$$ t({u_i}, y) = \sum {\left| {\left\{ {{p_{{u_i}\mathop \to \limits^w y}}:{p_{{u_i}\mathop \to \limits^w y}} \in P} \right\}} \right|} $$ 式中，ui表示用户；$ {p_{{u_i}\mathop \to \limits^w y}} $为从ui到y的一个加权路径实例；$ \left| {{p_{{u_i}\mathop \to \limits^w y}}} \right| $为ui到y的所有路径实例上的权重值；$ t({u_i}, y) $为ui到y的所有路径实例上的权重值之和。
用该公式可以推算出所有用户对所有演员基于该元路径的偏好度。如果两用户对所有演员的偏好度越接近，则两用户的喜好越相似。
定义 5 扩展交换矩阵。若一个WHIN为$ G = (V, E, \mathit{\mathbb{W}}) $，其网络模式为$ S = (B, R, W) $，对于加权元路径$ P = {B_1}({W_1}){B_2}({W_2}) \cdots ({W_{l - 1}}){B_l} $的扩展交换矩阵$ \mathit{\boldsymbol{\mathcal{M}}} $定义为：
$$ \mathit{\boldsymbol{\mathcal{M}}} = {\mathit{\boldsymbol{\mathcal{W}}}_{{B_1}({W_1}){B_2}}}{\mathit{\boldsymbol{\mathcal{W}}}_{{B_2}({W_2}){B_3}}} \cdots {\mathit{\boldsymbol{\mathcal{W}}}_{{B_{l - 1}}({W_{l - 1}}){B_l}}} $$ 式中，$ {\mathit{\boldsymbol{\mathcal{W}}}_{{B_i}({W_i}){B_j}}} $为节点类型Bj到类型Bj的扩展邻接矩阵。其中，扩展邻接矩阵$ {\mathit{\boldsymbol{\mathcal{W}}}_{{B_i}({W_i}){B_j}}} $定义为：
$$ \begin{array}{l} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\mathit{\boldsymbol{\mathcal{W}}}_{{B_i}{\rm{(}}{W_i}{\rm{)}}{B_j}}}{\rm{ = }}\\ \left\{ \begin{array}{l} {w_{ij}}\begin{array}{*{20}{c}} {}&{节点{B_i}与{B_j}间边上有权重且权重为{w_{ij}}} \end{array}\\ {\rm{1\;\;\;\;\;}}\begin{array}{*{20}{c}} {}&{节点{B_i}与{B_j}间有连边但边上无权重} \end{array}\\ {\rm{0\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;}}\begin{array}{*{20}{c}} {}&{节点{B_i}与{B_j}间无连边} \end{array} \end{array} \right. \end{array} $$ 所以，$ {\mathcal{M}_{i, j}} = \mathcal{M}(i, j) $表示xi∈Bi, yj∈Bj在元路径$ P = {B_1}({W_1}){B_2}({W_2}) \cdots ({W_{l - 1}}){B_l} $下xi到yj的所有路径实例的权重之和，即xi对yj的偏好度。
$ {\mathit{\boldsymbol{\mathcal{M}}}_{U({W_1})M({W_2})A}} $的每一行元素为该行对应的用户对网络中所有演员的偏好度。行归一化后，每一行数据代表此用户在电影主演方面的偏好，可得任意两用户ui与uj间在演员方面的相似度：
$$ {\rm{sim(}}{u_i}, {u_j}{\rm{)}} = \cos ({u_i}, {u_j}) = \frac{{{u_i}{u_j}}}{{|{u_i}||{u_j}|}} = \frac{{{\mathit{\mathcal{M}}_{i, :}}{\mathit{\mathcal{M}}_{j, :}}}}{{\left| {{\mathit{\mathcal{M}}_{i, :}}} \right|\left| {{\mathit{\mathcal{M}}_{j, :}}} \right|}} $$ 式中，sim(ui, uj)可能为负值，用公式$ {\rm{sim(}}{u_i}, {u_j}{\rm{)}} = 0.5 + 0.5{\rm{sim(}}{u_i}, {u_j}{\rm{)}} $修正，使其值位于0~1之间，值越大表明两用户越相似。如表 1所示，不同的元路径蕴含不同的语义信息，某用户喜欢一部电影可能是因为喜欢该电影的主演或导演，也可能是因为喜欢电影体裁。
表 1 电影推荐网络中典型的元路径及其语义信息
元路径 语义信息 P1 = UMU 与目标用户(U)看过同一部电影(M)的用户(U) P2 = UMAMU 与目标用户(U)看过同一个主演(A)演过的电影(M)的用户(U) P3 = UMCMU 与目标用户(U)看过在同一个国家(C)上映的电影(M)的用户(U) P4 = UMDMU 与目标用户(U)看过由同一个导演(D)执导的电影(M)的用户(U) P5 = UMGMU 与目标用户(U)看过属于同一个电影体裁(G)的电影(M)的用户(U) P6 = UMTMU 与目标用户(U)看过被贴上同一个类型标签(T)的电影(M)的用户(U) 基于表 1中的6条元路径求得两用户在导演、体裁、标签等方面的6个相似度值，并将各相似度应用到基于用户的协同过滤推荐算法中。在基于用户的协同过滤推荐系统中用户u对项目i的评分[13]为：
$$ {r_{u,i}}{\rm{ = }}{\bar r_u}{\rm{ + }}k\sum\limits_{u \in U} {{\rm{sim}}(} u,u)({r_{u,i}} - {\bar r_u}) $$ 式中，ru, i为用户u对项目i的评分；U为与用户u最相似的用户集合；$ {\bar r_{u, i}} $为用户u的平均打分值，可消除用户打分偏好对最后结果的影响；k为标准化因子，$ k = 1/\sum\limits_{u \in U} {\left| {{\rm{sim}}\left( {u,u} \right)} \right|} $。
得到6个受不同影响因素即不同元路径影响的用户对电影的评分值。然后采用线性回归方法为每一个基于单一元路径的预测评分值赋予不同的权重，融合为最终的预测评分。
-
实验环境具体配置如下：Intel® Core(TM)i7-4710MQ CPU，2.50 GHz，8 GB内存。实验中算法均用Python语言实现。
-
本文所用数据集为MovieLens10M扩展数据集。数据集中包含7种不同的节点类型，如表 2所示，其加权网络模式如图 2所示。
表 2 MovieLens扩展数据集简介
实体类型 数目 用户U 2 113 电影M 10 197 演员A 21 185 导演D 4 060 国家C 72 体裁G 20 标签T 13 222 -
如果以用户和电影间已有的评分关系占所有可能存在的评分关系的比例来衡量系统的稀疏性，那么扩展MovieLens数据集的稀疏度是3.97%。如图 3所示，仅有不超过7%的用户对10%以上的电影有评价关系，而超过一半的用户评价的电影数目低于总电影数量的4%。传统的协同过滤算法仅利用评分信息计算用户间的相似度来确定最近邻，在评分信息如此稀疏的情况下必然使得推荐准确度不高。
图 3 用户评价过的电影数目与用户数目间的关系
-
评价指标选用评分预测准确度中最经典的两种评价指标：平均绝对误差(mean absolute error, MAE)和均方根误差(root mean square error, RMSE)。
1) MAE
MAE[14]即为所有单个预测值与真实值的偏差的绝对值的平均数。在推荐系统中通过计算预测的用户评分与实际的用户评分之间的误差来度量，为：
$$ {\rm{MAE}} = \frac{{\sum\nolimits_{(u, i) \in D} {\left| {{r_{ui}} - {{\hat r}_{ui}}} \right|} }}{{\left| D \right|}} $$ 式中，u代表测试集中的用户；i代表测试集中的项目；rui代表用户对项目的实际评分数据；$ {\hat r_{ui}} $代表系统预测的用户对项目的评分；D代表训练集；|D|代表训练集中(u, i)对个数。
2) RMSE
RMSE的平方值为所有单个预测值与真实值的偏差的平方的平均数，为：
$$ {\rm{RMSE}} = \sqrt {\frac{{\sum\nolimits_{(u, i) \in D} {{{({r_{ui}} - {{\hat r}_{ui}})}^2}} }}{{\left| D \right|}}} $$ 式中各符号的意义与MAE相同。MAE和RMSE都是用系统预测打分值与用户实际打分值的误差来表征一个推荐系统的准确率，两个值都在0 ~ 1之间。若为0，则代表该推荐系统预测用户评分准确率为100%，反之，值越大准确率越差。
-
传统的基于用户的协同过滤推荐算法中最常用的相似度度量方式为Cosine相似度和Pearson相关系数，在HIN中最经典的计算两节点间相似度的方式是PathSim和HeteSim算法。
接下来将比较本文提出的算法和基于上述4种相似度度量方式的协同过滤算法在不同近邻数K影响下的MAE值和RMSE值。实验采用5折交叉验证方法，最终结果为5次实验结果的平均值。
-
当近邻数K为20、30、40、50和60时，在扩展MovieLens数据集下比较基于Cosine相似度、Pearson相关系数、PathSim和HeteSim的协同过滤算法和本文引入加权异构信息的改进协同过滤算法的MAE和RMSE大小。实验结果如图 4所示。
图 4 近邻数K对5种算法的MAE和RMSE影响
随着邻居数的变化，基于Cosine相似度和Pearson相关系数的协同过滤算法的MAE值始终大于其他3种算法，推测原因可能是因为本数据集稀疏度很高，用户的共同评分项目很少导致最终评分预测准确度低。基于Cosine相似度和Pearson相关系数的协同过滤算法的MAE值随着K的增加明显下降，但是当K≥40时其MAE值变化极微，稍有下降。
基于HeteSim的协同过滤算法在K=30时MAE略小于K=20时的MAE，当K > 30时MAE变化极小，有些许增加；而基于PathSim的协同过滤算法的MAE随着K的增加变化不大，但始终大于本文所提出的改进协同过滤算法。本文算法通过分析用户间相似度的多种因素已捕捉到相对全面的语义信息，当K较小时，随着K的增加，MAE几乎没有变化，当K=50或60时，由于所取近邻中掺杂了与目标用户不那么相似的用户，反而会使得MAE有所增加。如图 4b所示，随着K的增加，3种算法的RMSE变化趋势与图 3中MAE的变化趋势大致相同，都是在K=30时表现最优，综上所述，取K=30。
-
当近邻数K=30时，比较3种算法预测用户对电影评分数据的精度，实验结果如图 5所示。
图 5 K=30时5种算法的MAE和RMSE比较
由于融合了HIN中多条元路径携带的不同语义信息的综合影响，并考虑了两用户间不同关系上的权重值和用户评分的两极化影响，本文所提的改进协同过滤算法表现优于基于Cosine相似度、Pearson相关系数、PathSim和HeteSim的协同过滤算法，其预测评分准确度在MAE和RMSE两种评价指标上均明显小于另外两种算法。
-
本文在引入加权异构网络信息的基础上，提出了一种基于元路径计算用户间相似度的新的协同过滤推荐算法，全面考虑了电影推荐网络中可能影响到用户对电影评分的多种影响因素。实验结果表明本文提出的方法使得推荐算法中两大经典评价指标MAE和RMSE值明显减小，显著地改善了预测用户评分的准确率。在今后的工作中，可以引入用户间的社会网络信息，考虑用户之间的朋友关系、兴趣小组关系等，以此提升计算用户间相似性的可靠度。
An Improved Collaborative Filtering Recommendation Algorithm with Weighted Heterogeneous Information
-
摘要: 协同过滤作为当前应用最成功的推荐技术之一，其推荐质量在很大程度上取决于近邻用户选取的准确性，而数据的稀疏性问题（sparsity）和相似度度量方式（similarity metrics）严重影响着最近邻的选择。该文提出了一种引入加权异构信息的改进协同过滤算法。首先利用异构网络中丰富的语义信息和边属性信息，得到用户之间基于不同元路径的相似度；然后将相似度分别应用到典型的基于用户的协同过滤推荐算法中，得到基于每个相似度的用户评分值；最后采用监督学习算法为每个打分值分配不同的权重，融合为用户最终评分。在扩展MovieLens经典数据集上的实验结果表明，本文所提算法在精确度上较传统算法有显著提高。Abstract: Collaborative filtering is oneofthe most successful recommendation technologies, and the quality of collaborative filtering is determinedby the accuracy of the nearest neighbors. Data sparsity problem and similarity metricsseriously affect the choice of the nearest neighbors. Different from traditional recommendation tasks, in this paper, we propose an improved meta path-based collaborative filtering algorithm for weighted heterogeneous information networks. Firstly, we calculate the similarity among users based on different meta path by utilizing the rich semantic information and attribute information in weighted heterogeneous networks. Then we apply the similarity to user-based collaborative filtering algorithm and get multiple predicted rating scores based on different similarity. Finally we calculate the final predicted scores by combining various meta path information using supervised machine learning algorithms. The method is evaluated with the extended MovieLens dataset and experimental results show that our approach outperforms several traditional algorithms and make the result of recommendation more accurate in terms of accuracy.
-
表 1 电影推荐网络中典型的元路径及其语义信息
元路径 语义信息 P1 = UMU 与目标用户(U)看过同一部电影(M)的用户(U) P2 = UMAMU 与目标用户(U)看过同一个主演(A)演过的电影(M)的用户(U) P3 = UMCMU 与目标用户(U)看过在同一个国家(C)上映的电影(M)的用户(U) P4 = UMDMU 与目标用户(U)看过由同一个导演(D)执导的电影(M)的用户(U) P5 = UMGMU 与目标用户(U)看过属于同一个电影体裁(G)的电影(M)的用户(U) P6 = UMTMU 与目标用户(U)看过被贴上同一个类型标签(T)的电影(M)的用户(U) 
下载: 导出CSV
表 2 MovieLens扩展数据集简介
实体类型 数目 用户U 2 113 电影M 10 197 演员A 21 185 导演D 4 060 国家C 72 体裁G 20 标签T 13 222
下载: 导出CSV
-
[1] SU X, KHOSHGOFTAAR T M. A survey of collaborative filtering techniques[J]. Advances in Artificial Intelligence, 2009(12):4. doi: 10.1155/2009/421425 [2] SUN Y, HAN J, YAN X, et al. Mining knowledge from interconnected data:a heterogeneous information network analysis approach[J]. Proceedings of the VLDB Endowment, 2012, 5(12):2022-2023. doi: 10.14778/2367502 [3] SUN Y, HAN J. Mining heterogeneous information networks:a structural analysis approach[J]. ACM SIGKDD Explorations Newsletter, 2013, 14(2):20-28. doi: 10.1145/2481244 [4] SUN Y, HAN J. Mining heterogeneous information networks:Principles and methodologies[J]. Synthesis Lectures on Data Mining and Knowledge Discovery, 2012, 3(2):1-159. doi: 10.2200/S00433ED1V01Y201207DMK005 [5] YANG B, LEI Y, LIU D, et al. Social collaborative filtering by trust[C]//Proceedings of the 23th International Joint Conference on Artificial Intelligence. [S. l. ]: AAAI Press, 2013: 2747-2753. [6] SHI C, ZHANG Z, LUO P, et al. Semantic path based personalized recommendation on weighted heterogeneous information networks[C]//Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. [S. l. ]: ACM, 2015: 453-462. [7] SUN Y, HAN J, YAN X, et al. Pathsim:Meta path-based top-K similarity search in heterogeneous information networks[J]. Proceedings of the VLDB Endowment, 2011, 4(11):992-1003. http://www.docin.com/p-831273031.html [8] LAO N, COHEN W W. Fast query execution for retrieval models based on path-constrained random walks[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. [S. l. ]: ACM, 2010: 881-888. [9] SUN J, QU H, CHAKRABARTI D, et al. Relevance search and anomaly detection in bipartite graphs[J]. ACM SIGKDD Explorations Newsletter, 2005, 7(2):48-55. doi: 10.1145/1117454 [10] YU X, REN X, GU Q, et al. Collaborative filtering with entity similarity regularization in heterogeneous information networks[C]//International Joint Conference on Artificial Intelligence-Heterogeneous Information Network Analysis (IJCAI-HINA Workshop). Beijing: [s. n. ], 2013. [11] LUO C, PANG W, WANG Z. Hete-cf: Social-based collaborative filtering recommendation using heterogeneous relations[C]//IEEE International Conference on Data Mining. Shenzhen: IEEE, 2014: 917-922. [12] YU X, REN X, SUN Y, et al. Personalized entity recommendation: a heterogeneous information network approach[C]//Proceedings of the 7th ACM International Conference on Web Search and Data Mining. [S. l. ]: ACM, 2014: 283-292. [13] ADOMAVICIUS G, TUZHILIN A. Toward the next generation of recommender systems:a survey of the state-of-the-art and possible extensions[J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(6):734-749. doi: 10.1109/TKDE.2005.99 [14] SHI Y, LARSON M, HANJALIC A. Mining mood-specific movie similarity with matrix factorization for contextaware recommendation[C]//Proceedings of the Workshop on Context-Aware Movie Recommendation. [S. l. ]: ACM, 2010: 34-40. -
点击查看大图
图(5) / 表(2)
计量
- 文章访问数: 4834
- HTML全文浏览量: 1268
- PDF下载量: 292
- 被引次数: 0
