基于组合类别空间的随机游走推荐算法

樊玮 谢聪 肖春景 曹淑燕

摘 要：傳统的类别驱动方法只考虑类别间的关联或是将其组织成扁平或层次结构，而项目和类别对应关系复杂，其他信息容易被忽略。针对这个问题提出基于组合类别空间的随机游走推荐算法，更好地组织了项目类别信息、缓解了数据稀疏。首先，建立一个用哈斯图表示的项目组合类别空间，将项目和类别复杂的一对多关系映射成一对一的简单关系，并表示用户上下层次、同层次及跨层次的项目类别间的跳转;接着，定义组合类别空间的语义关系及链接、偏好两种语义距离，更好地定性、定量描述用户动态偏好的变化;然后，结合组合类别空间上用户浏览图的语义关系、语义距离、用户行为跳转、跳转次数、时序、评分等各种信息，利用随机游走建立用户个性化类别偏好模型;最后，根据用户个性化偏好完成基于用户的协同过滤项目推荐。在MovieLens数据集上的实验显示，与基于用户的协同过滤（UCF）、基于类别关联的推荐模型（UBGC和GENC）相比，所提算法推荐的F1-score提高了6～9个百分点，平均绝对误差（MAE）减小了20%～30%;与基于类别层次潜在因子模型（CHLF）相比，所提算法推荐的F1-score提高了10%。实验结果表明，所提算法在排序推荐上优于传统基于类别的推荐算法。

关键词：偏好相似度;梯度下降;随机游走;协同过滤;推荐算法

中图分类号：TP301.6

文献标志码：A

文章编号：1001-9081（2019）04-0984-05

Abstract： The traditional category-driven approaches only consider the association between categories or organize them into flat or hierarchical structure， but the relationships between items and categories are complex， making other information be ignored. Aiming at this problem， a random walk recommendation algorithm based on combinational category space was proposed to better organize the category information of items and alleviate data sparsity. Firstly， a combinational category space of items represented by Hasse diagrams was constructed to map the one-to-many relationship between items and categories into one-to-one simple relationships， and represent the user's jumps between items in higher and lower levels， the same level and the cross-levels. Then the semantic relationships and two types of semantic distances — the links and the preferences were defined to better describe the changes of the user's dynamic preferences qualitatively and quantitatively. Afterwards，the user personalized category preference model was constructed based on random walking and combination of the semantic relationship， semantic distance， user behavior jumping， jumping times， time sequence and scores of the user's browsing graph in the combinatorial category space. Finally， the items were recommended to users by collaborative filtering based on the user's personalized category preference. Experimental results on MovieLens dataset show that compared with User-based Collaborative Filtering （UCF） model and category-based recommendation models （UBGC and GENC）， the recommended F1-score was improved by 6 to 9 percentage points， the Mean Absolute Error （MAE） was reduced by 20% to 30%; compared with Category Hierarchy Latent Factor （CHLF） model， the recommended F1-score was improved by 10%. Therefore， the proposed algorithm has advantage in ranking recommendation and is superior to other category-based recommendation algorithms.

Key words： preference similarity; gradient descent; random walk; collaborative filtering; recommendation algorithm

0 引言

协同过滤是目前推荐系统中最成功的推荐算法，它认为具有相似偏好的用户应该喜欢相似的项目，因此它的核心是为用户寻找最相似近邻。它利用用户与项目的交互信息，将用户项目评分看成向量，利用余弦、皮尔逊相关系数等相似性度量来发现近邻，通过近邻对项目评分预测目标用户的喜好。但是一方面计算相似性时的评分向量维度和系统中的项目数一致，向量维度较高;另一方面由于用户自身特点，将产生很多相同评分，由此得到的评分向量信息冗余且不全面，它的性能在数据稀疏或冷启动的情况下受到严重制约。

当游走步数趋于无穷大时，基于图的随机游走算法能够返回图中节点重要性的排序。它能从全局挖掘用户/项目关系，已被广泛应用到推荐过程中缓解数据稀疏问题[1-6]。由于项目类别（类型）作为附加信息时，属性值相对稳定、与项目内容相关性强，同时一个项目往往与多个类别相关等特性，项目类别作为重要附加信息引入推荐系统能够有效缓解数据稀疏、解决冷启动问题。

目前基于类别的推荐系统主要分为四类：一类是直接将项目信息加入到传统协同过滤中[7]。

二是挖掘用户偏好和项目类别间的关联，如：Ren等[8]利用项目类别信息，建立用户动态偏好模型，但是计算量较大;Manzato等[9]分解用户类型矩阵得到类别的隐向量解决冷启动问题。

三是计算项目类别间的关联，根据用户偏好类别完成项目推荐[10-11]，但此类方法要求系统必须输入用户喜好类别。

最后一类是利用矩阵分解等潜语义模型根据项目类别的扁平或层次结构，建立用户和项目k维向量表示的潜语义模型，来完成项目推荐的过程[12-14]。Sun等[15]根据类别层次建立用户和项目隐语义模型并以线性复杂度自动学习不同类别的权值。但它们仅用到项目类别的扁平结构或上下层次关系，并不能应用同层次类别间的关系;而且用户和项目的k维向量的维度往往是随机设定的，并没有明确的语义含义。

针对以上问题，本文提出基于类别组合空间的随机游走推荐算法CCSRank（Combinational Category Space Rank）。

首先，提出组合类别空间来组织项目类别信息，它是一种哈斯图表示结构，能将一对多的项目类别映射到一对一组合类别空间，它比层次结构具有更丰富的信息;其次在组合类别空间上给出用户浏览图，并定义了描述用户动态偏好的五种语义关系及链接和偏好距离，更好地描述了用户偏好的动态变化过程及变化程度;然后在用户浏览图上根据用户浏览序列、跳转语义关系、链接距离和偏好距离、跳转次数及时序等信息，利用随机游走得到组合类别空间上的用户类别偏好，表示为具有实际含义的用户偏好向量;最后根据用户的类别偏好计算用户间相似性，并完成基于用户的协同过滤推荐。通过在真实数据集上进行大量实验结果表明，本文方法效果优于传统基于类别推荐的方法。

1 组合类别空间

项目类别（类型）属性是非常重要且不同于其他属性的附加信息，同一类别的项目往往具有相似内容。如，对于电影推荐系统，电影类型（动作、浪漫、喜剧等）一般是由专家来进行分配、指定的，同一类型的电影中能找到一定的相似性，用户可以通过电影类型猜测电影的故事情节、氛围、场景等，决定是否去观看电影，因此可以吸引具有相同偏好的用户。此外，一个电影能属于多个类型，每个项目类别表示一个特定的主题。也即项目和类别是一对多的关系，对应关系复杂，关系不易被挖掘。为了更好地组织项目类别信息，提出组合类别空间，它把项目所属的多个类别看成一个类别集合，将项目和类别间一对多的关系通过哈斯图表示结构映射成一对一的关系，它能表示项目类别间上下、同层、跳跃关系，丰富了项目的信息密度，使项目和类别间的关系更容易表示，更容易挖掘用户偏好。

2 组合类别空间上的五种语义关系及距离

每个用户的消费行为表示成在组合类别空间的节点上的跳转序列，它暗含着用户的动态偏好，为了挖掘用户的偏好变化，从跳转节点间的语义关系及语义距离两个角度描述用户的偏好变化剧烈程度。

2.1 五种语义关系

定义2 浏览行为语义关系。

2.2 语义距离

五种关系定性描述了用户行为在CCS上的跳转，及它表示的兴趣偏好变化。要利用这种跳转行为建模用户的动态偏好，还必须能定量衡量它。

在组合类别空间上用户浏览行为的跳转可由两个方面衡量：1）组合类别在哈斯图上跳转的实际物理距离大小，可用在哈斯图上的层次距离表示，层次跨度小的两个组合类别表示用户兴趣变化小，兴趣越趋于稳定，距离越小;2）组合类别包含基本类别元素的差别，可从包含基本类别元素的个数和公共元素的个数两个角度考虑。包含基本类别元素越多、公共基本类别越少的组合类别表示的兴趣变化越大，距离也应大。

基于上述的考虑，分别定义链接距离和偏好距离表示组合类别间的距离大小。

定义3 链接距离。

它表示两个组合類别在组合空间哈斯图上实际的物理距离大小。

两个组合类别包含的元素越多，相同的基本类别数目越少，则链接距离越大，说明组合类别复杂、差异度大;

每个类型组包含类别数少，相同类别数越多，则链接距离越小，表明类型组合自身简单且差异小;

如果两个组合类别完全一致时，链接距离为0。

按照偏好距离的定义可知，当用户跳转的组合类别没有变化时，也即兴趣稳定时，偏好距离最小为0。其次为兴趣缩小的情况，接着是兴趣扩张的情况，而兴趣不可比较时，用户偏好变化最为剧烈，偏好距离最大。

3 基于随机游走的个性化类别偏好建模

为了更好地对用户组合类别偏好进行建模，首先定义了用户浏览图，融合了语义关系、链接与偏好距离、跳转次数、评分、时序等信息;利用PageRank对用户组合类别的偏好进行建模，并优化求解得到用户对组合类别的个性化偏好。

3.1 用户浏览图

根据用户历史浏览行为来定义用户浏览图，并建模用户个性化组合类别偏好。

迭代优化得到用户对所有组合类别的评分向量π=（π1，π2，…，πn）T，也即用户的个性化类别偏好向量，它是一种低维的用户偏好向量的表示，但相对于潜语义类模型，个性化类别偏好向量的每个维度都具有很清楚的含义。

4 项目推荐

得到用户对组合类别的个性化偏好矢量，利用余弦相似性度量用户间相似性（式（9）），并选择与用户ui最相似的k个用户来预测评分，如式（10）所示。

本文所提出的基于组合类别空间的随机游走推荐算法具体如算法1所示。

算法1 基于组合类别空间的随机游走推荐算法。

5 实验结果及分析

5.1 实验数据及评估标准

实验中采用MovieLens提供的1M数据集，包括6040个用户，3952个电影项目，共1000209条有效评论，时间区间从2000年05月26日至2003年03月01日，数据稀疏度为95.8%。项目共包含18种基本电影类型，如表1所示，共组成301種组合类型，组合类别中最多包含6个基本类型。实验过程中，随机抽取80%的数据作为训练集，余下的20%作为测试集，采用5折交叉验证。

对结果的评估，用平均绝对误差（Mean Absolute Error， MAE）和均方根误差（Root Mean Squared Error， RMSE）作为评分预测的评价标准，采用准确率、召回率和F1-score以及AUC（Area Under Curve）曲线来评估Top-N推荐结果。

5.2 对比方法

为了评估本文提出的基于类别组合空间的随机游走推荐算法（CCSRank）的有效性，将其与以下相关算法进行了对比：1）基于用户的协同过滤（User-based Collarative Filtering， UCF）[16]：采用余弦相似性计算用户间相似性。

2）基于用户在类别中关联的协同过滤（User-Based collarative filtering by Genre Correlations， UBGC）[11]：计算电影类型的关联度，根据电影的类型及类型间的关联对电影分类，最后根据用户偏好类型及电影分类完成推荐。

3）类别层次潜在因子模型（Category Hierarchy Latent Factor model， CHLF）[15]： 建立项目的类别层次并建立用户和项目隐语义模型进行推荐。

4）使用类别的分类模型（using genre to classification model， GENC）[10]：计算项目类别间的关联度，完成项目分类与推荐任务。

5.3 实验结果及分析

近邻选取是UCF提高推荐性能的关键。图2给出了MAE和RMSE随近邻数的变化情况。从图2可知，随着近邻数增加MAE和RMSE迅速下降后缓慢增加，近邻数为40和60时MAE和RMSE达到最小，在后续实验中近邻选取最佳值。

实验中首先计算了各方法的指标如表2所示。从表2可知，CCSRank和CHLF的全部四项性能都好于UCF、UBGC和GENC，特别是F1-score提高了6～9个百分点;而且CCSRank的性能要好于CHLF，F1-score提高了10%，CCSRank模型更加稳定。

这主要是因为CCSRank和CHLF都很好地利用和组织了项目类别信息，而组合类别空间比层次类别结构的信息更为丰富。UBGC和GENC的效果相当，且好于UCF是由于UBGC和GENC都利用了项目类型间的关联，因此效果好于UCF，但项目类型关联所包含信息不如层次类别和组合类别空间丰富，因此效果差于CHLF和CCSRank。

图3对比了各种方法的MAE和RMSE。从图3可知，CCSRank效果优于UCF、UBGC和GENC，其中MAE减小了20%～30%，但却不如CHLF。这主要是因为CCSRank虽利用了信息更为丰富的组合类别空间，但在推荐过程中简单地利用个性化类别编号进行了相似性计算，而CHLF则采用层次类别结构建立了用户和项目的隐语义模型。CCSRank虽在评分预测的效果上差于CHLF，但CCSRank提出的组合类别空间结构，实现项目和类别一对一的映射关系，且比CHLF的层次结构更方便地描述用户浏览行为地跳转过程，对于用户喜欢项目的排序比CHLF更准确，因此CCSRank更适合于排序推荐。

6 结语

本文提出基于组合类别空间的随机游走推荐算法可缓解数据稀疏、解决冷启动问题，提高推荐系统性能。该方法在组合类别空间中记录用户浏览行为，学习用户类别偏好特征，最终完成推荐。 首先定义了组合类别空间，它是一种高效哈斯图结构;其次定义了五种语义关系和两种偏好距离，在组合类别空间上定性和定量度量用户行为序列和动态偏好;接着提出基于随机游走的个性化类别偏好模型，充分利用了语义关系、语义距离、用户行为跳转、跳转次数、时序、评分等各种信息，学习得到一种低维的个性化用户类别偏好表示，且每个维度的含义清楚;最后以此对用户进行个性化推荐。实验结果说明该方法能提高推荐性能，特别是项目排序推荐。

参考文献（References）

[1] ZHANG Z， ZENG D D， ABBASI A， et al. A random walk model for item recommendation in social tagging systems[J]. ACM Transactions on Management Information Systems， 2013， 4（2）： 8.

[2] FENG S， CAO J. Improving group recommendations via detecting comprehensive correlative information[J]. Multimedia Tools and Applications， 2017， 76（1）： 1355-1377.

[3] XU G， FU B， GU Y. Point-of-interest recommendations via a supervised random walk algorithm[J]. IEEE Intelligent Systems， 2016， 31（1）： 15-23.

[4] 劉梦娟， 王巍， 李杨曦， 等. AttentionRank+： 一种基于关注关系与多用户行为的图推荐算法 [J]. 计算机学报， 2017， 40（3）： 634-648. （LIU M J， WANG W， LI Y X， et al. AttentionRank+： a graph-based recommendation combining attention relationship and multi-behaviors [J]. Chinese Journal of Computers， 2017， 40（3）： 634-648.）

[5] XIA F， CHEN Z， WANG W， et al. MVCWalker： random walk-based most valuable collaborators recommendation exploiting academic factors[J]. IEEE Transactions on Emerging Topics in Computing， 2014， 2（3）： 364-375.

[6] YAO W， HE J， HUANG G， et al. A graph-based model for context-aware recommendation using implicit feedback data[J]. World Wide Web， 2015， 18（5）： 1351-1371.

[7] WENG L T， XU Y， LI Y， et al. Exploiting item taxonomy for solving cold-start problem in recommendation making[C]// ICTAI 2008： Proceedings of the 20th IEEE International Conference on Tools with Artificial Intelligence. Piscataway， NJ： IEEE， 2008： 113-120.

[8] REN Y， LI G， ZHOU W. Modelling personal preferences for Top-N movie recommendations[J]. Web Intelligence and Agent Systems： an International Journal， 2014， 12（3）： 289-307.

[9] MANZATO M G. Discovering latent factors from movies genres for enhanced recommendation[C]// RecSys 2012： Proceedings of the Sixth ACM Conference on Recommender Systems. New York： ACM， 2012： 249-252.

[10] CHOI S M， KO S K， HAN Y S. A movie recommendation algorithm based on genre correlations[J]. Expert Systems with Applications， 2012， 39（9）： 8079-8085.

[11] HWANG T G， PARK C S， HONG J H， et al. An algorithm for movie classification and recommendation using genre correlation[J]. Multimedia Tools and Applications， 2016， 75（20）： 12843-12858.

[12] HU L， SUN A， LIU Y. Your neighbors affect your ratings： on geographical neighborhood influence to rating prediction[C]// SIGIR 2014： Proceedings of the 37th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM， 2014： 345-354.

[13] YANG J， SUN Z， BOZZON A， et al. Learning hierarchical feature influence for recommendation by recursive regularization[C]// RecSys 2016： Proceedings of the 10th ACM Conference on Recommender Systems. New York： ACM， 2016： 51-58.

[14] ZHANG Y， AHMED A， JOSIFOVSKI V， et al. Taxonomy discovery for personalized recommendation[C]// WSDM 2014： Proceedings of the 7th ACM International Conference on Web Search and Data Mining. New York： ACM， 2014： 243-252.

[15] SUN Z， GUO G， ZHANG J. Learning hierarchical category influence on both users and items for effective recommendation[C]// SAC 2017： Proceedings of the 32nd ACM SIGAPP Symposium on Applied Computing. New York： ACM， 2017： 1679-1684.

[16] SARWAR B， KARYPIS G， KONSTAN J， et al. Analysis of recommendation algorithms for e-commerce[C]// EC 2000： Proceedings of the 2nd ACM Conference on Electronic Commerce. New York： ACM， 2000： 158-167.