第14卷第4期 智能系统学报 Vol.14 No.4 2019年7月 CAAI Transactions on Intelligent Systems Jul.2019 D0:10.11992/tis.201806002 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180629.1153.004html 基于图游走的并行协同过滤推荐算法 顾军华2，谢志坚2，武君艳2，许馨匀2，张素琪 (1.河北工业大学人工智能与数据科学学院，天津300401；2.河北工业大学河北省大数据计算重点实验室，天 津300401：3.天津商业大学信息工程学院，天津300134) 摘要：针对目前协同过滤推荐算法存在的数据稀疏性问题和可扩展性问题，本文进行了相关研究。针对稀疏 性问题，在传统的皮尔逊相关相似度中引入交占比系数计算用户间直接相似度，该方法缓解了用户间共同评分 项的占比问题：提出一种基于图游走的间接相似度计算方法，该方法根据用户间的直接相似度建立用户网络 图，在用户网络图上通过游走计算用户间的间接相似度，并进行推荐。在Spak平台上实现本文方法的并行 化，缓解了数据规模增加带来的可扩展性问题。实验结果表明：本文提出的算法在不同数据集上均取得了良好 效果，有效地提高了推荐准确度，并且在分布式环境下具有良好的可扩展性。 关键词：协同过滤：推荐；用户网络图；游走：相似度；间接相似度：并行；Spak平台 中图分类号：TP391 文献标志码：A文章编号：1673-4785(201904-0743-09 中文引用格式：顾军华，谢志坚，武君艳，等.基于图游走的并行协同过滤推荐算法.智能系统学报，2019,14(4)：743-751. 英文引用格式：GU Junhua,XIE Zhijian,.VU Junyan,etal.Parallel collaborative filtering recommendation algorithm based on graph walkJ].CAAI transactions on intelligent systems,2019,14(4):743-751. Parallel collaborative filtering recommendation algorithm based on graph walk GU Junhua,XIE Zhijian,WU Junyan,XU Xinyun,ZHANG Suqi' (1.School of Artificial Intelligence,Hebei University of Technology,Tianjin 300401,China;2.Hebei Province Key Laboratory of Big Data Computing,Tianjin 300401,China;3.School of Information Engineering,Tianjin University of Commerce,Tianjin 300134,China) Abstract:This study aims to solve the problem of data sparsity and scalability of collaborative filtering recommenda- tion algorithms.For the sparseness problem,the traditional Pearson correlation similarity is introduced to calculate the direct similarity between the users using the cross-ratio coefficients.This method alleviates the proportion of common scoring items among users.An indirect similarity calculation method based on graph walk is proposed in the paper.This method builds a user network map based on the direct similarity between users,calculates the indirect similarity between users by walking on the user network map,and makes recommendations.The parallelization of this method on the Spark platform mitigates the scalability problem caused by increase of the data size.Experimental results on Movielens data- set and IPTV dataset show that the proposed algorithm achieves good results on different datasets,effectively improves the recommendation accuracy rate,and has good scalability in a distributed environment. Keywords:collaborative filtering;recommendation;user network map;walk;similarity;indirect similarity,parallel; Spark platform 近年来随着互联网科技的发展，大数据在促 如何快速从海量数据中获取有价值的信息成为当 进社会进步的同时，也带来了“信息过载”问题。 前大数据发展的关键性问题。为满足人们在大 收稿日期：2018-06-01.网络出版日期：2018-07-02. 数据中快速获取有价值信息的需求，推荐系统应 基金项目：河北省科技计划项目(17210305D:天津市科技计划 项目(I6 ZXHLSF0023):天津市自然科学基金项目 运而生。推荐系统的目标是根据用户的个性化需 (15 JCONJC00600). 通信作者：张素琪.E-mail:zhangsuqie(@163.com. 求将最符合用户喜好的信息挑选出来并推荐给用
DOI: 10.11992/tis.201806002 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180629.1153.004.html 基于图游走的并行协同过滤推荐算法 顾军华1,2，谢志坚1,2，武君艳1,2，许馨匀1,2，张素琪3 （1. 河北工业大学 人工智能与数据科学学院，天津 300401; 2. 河北工业大学 河北省大数据计算重点实验室，天 津 300401; 3. 天津商业大学 信息工程学院，天津 300134） 摘 要：针对目前协同过滤推荐算法存在的数据稀疏性问题和可扩展性问题，本文进行了相关研究。针对稀疏 性问题，在传统的皮尔逊相关相似度中引入交占比系数计算用户间直接相似度，该方法缓解了用户间共同评分 项的占比问题；提出一种基于图游走的间接相似度计算方法，该方法根据用户间的直接相似度建立用户网络 图，在用户网络图上通过游走计算用户间的间接相似度，并进行推荐。在 Spark 平台上实现本文方法的并行 化，缓解了数据规模增加带来的可扩展性问题。实验结果表明：本文提出的算法在不同数据集上均取得了良好 效果，有效地提高了推荐准确度，并且在分布式环境下具有良好的可扩展性。 关键词：协同过滤；推荐；用户网络图；游走；相似度；间接相似度；并行；Spark 平台 中图分类号：TP391 文献标志码：A 文章编号：1673−4785(2019)04−0743−09 中文引用格式：顾军华, 谢志坚, 武君艳, 等. 基于图游走的并行协同过滤推荐算法 [J]. 智能系统学报, 2019, 14(4): 743–751. 英文引用格式：GU Junhua, XIE Zhijian, WU Junyan, et al. Parallel collaborative filtering recommendation algorithm based on graph walk[J]. CAAI transactions on intelligent systems, 2019, 14(4): 743–751. Parallel collaborative filtering recommendation algorithm based on graph walk GU Junhua1,2 ，XIE Zhijian1,2 ，WU Junyan1,2 ，XU Xinyun1,2 ，ZHANG Suqi3 (1. School of Artificial Intelligence, Hebei University of Technology, Tianjin 300401, China; 2. Hebei Province Key Laboratory of Big Data Computing, Tianjin 300401, China; 3. School of Information Engineering, Tianjin University of Commerce, Tianjin 300134, China) Abstract: This study aims to solve the problem of data sparsity and scalability of collaborative filtering recommendation algorithms. For the sparseness problem, the traditional Pearson correlation similarity is introduced to calculate the direct similarity between the users using the cross-ratio coefficients. This method alleviates the proportion of common scoring items among users. An indirect similarity calculation method based on graph walk is proposed in the paper. This method builds a user network map based on the direct similarity between users, calculates the indirect similarity between users by walking on the user network map, and makes recommendations. The parallelization of this method on the Spark platform mitigates the scalability problem caused by increase of the data size. Experimental results on Movielens dataset and IPTV dataset show that the proposed algorithm achieves good results on different datasets, effectively improves the recommendation accuracy rate, and has good scalability in a distributed environment. Keywords: collaborative filtering; recommendation; user network map; walk; similarity; indirect similarity; parallel; Spark platform 近年来随着互联网科技的发展，大数据在促 进社会进步的同时，也带来了“信息过载”问题。 如何快速从海量数据中获取有价值的信息成为当 前大数据发展的关键性问题[1]。为满足人们在大 数据中快速获取有价值信息的需求，推荐系统应 运而生。推荐系统的目标是根据用户的个性化需 求将最符合用户喜好的信息挑选出来并推荐给用 收稿日期：2018−06−01. 网络出版日期：2018−07−02. 基金项目：河北省科技计划项目 (17210305D)；天津市科技计划 项目 (16ZXHLSF0023)；天津市自然科学基金项目 (15JCQNJC00600). 通信作者：张素琪. E-mail：zhangsuqie@163.com. 第 14 卷第 4 期 智 能 系 统 学 报 Vol.14 No.4 2019 年 7 月 CAAI Transactions on Intelligent Systems Jul. 2019
·744· 智能系统学报 第14卷 户，以减轻用户的选择负担。协同过滤推荐算法 荐算法的流程：1)根据评分矩阵R计算用户的相 是一种目前应用最广泛的推荐算法，可以在用 似度；2)计算目标用户的近邻用户集合；3)根据 户没有明确提出自己需求的情况下，根据用户的 近邻用户的评分预测目标用户对未评分项目的评 行为对用户进行推荐。但由于大数据环境下用户 分，从而生成推荐列表。 和项目的数量不断增长，协同过滤推荐算法面临 1.2用户相似度 着严重的数据稀疏性和可扩展性问题。 用户相似度指用户与用户之间行为中表现出 针对稀疏性问题，许多学者从不同角度进行 的相似程度，皮尔逊相关相似度是一种常用的计 了相关研究。SUN等刊采用聚类和时间影响因子 算相似度的方法，反映了两个用户的偏好信息的 矩阵来监测用户兴趣漂移程度，更准确的预测项 线性相关程度。用户。和用户的皮尔逊相关 目的评分。彭宏伟等提出一种基于矩阵分解的 相似度计算公式2如下： 上下文感知POI推荐模型，有效地缓解稀疏性问 ∑(a-ia)(rbi-i) SESab 题。WU等将异构信息网络建模为张量，并提出 sim(a,b)= (1) 两种随机梯度下降方法同时进行分解。MA等可 Va-历√及m- 提出了一种局部概率矩阵分解的方法，降低稀疏 式中：sb为用户“和用户4。共同评分项目的集 性的同时有效地缓解了每个局部模型的过拟合问 合；ra为用户w。对项目s的评分；ia为用户wn对 题。以上的方法均通过缓解数据稀疏性问题来提 集合sb中项目评分的平均值。sim(a,b)的值域为 高推荐的准确度。 [-1,1,sim(a,b)越大，表示两个用户的相似度越高。 针对协同过滤推荐算法在处理大规模数据所 1.3近邻用户 遇到的可扩展性问题，许多学者在并行方法上进 近邻用户表示与目标用户偏好信息最相似的 行了相关研究。杨志文、LUF、KUPISZ0等 一组用户，可以通过式()计算用户的相似度，然 将协同过滤推荐算法部署在Hadoop和Spark并 后计算目标用户的近邻用户。目标用户的多个近 行平台上，取得了良好的执行效率。 邻用户组成目标用户的近邻用户集合，常用的计 本文针对协同过滤推荐算法的数据稀疏性问 算近邻用户集合的方法分为两类：基于数量的近 题和可扩展性问题进行研究。针对稀疏性问题， 邻用户集合和基于阈值的近邻用户集合。 在皮尔逊相关相似度的基础上引入交占比系数来 基于阈值的近邻用户集合包含以目标用户为 计算用户的直接相似度，提出了一种基于图游走 中心，与目标用户的相似度大于Value的用户。 的协同过滤推荐算法(GWCF),使用图游走的方 基于数量的近邻用户集合包含与目标相似度最大 法计算用户的间接相似度，然后根据直接相似度 的TopK个近邻用户。 和间接相似度重建用户的相似度矩阵，最后进行 1.4个性化推荐 推荐。在Movielens-100k数据集和IPTV 首先计算目标用户的近邻用户集合，然后对 数据集上实验，验证GWCF在提高推荐准确度 目标用户进行推荐。目标用户u对未评分项目s 上的有效性。针对可扩展性问题，在Spark平台 预测评分的计算公式如式(2)，最后将预测评 上实现GWCF算法，并使用Movielens-lM和 分最大的K个项目推荐给目标用户。 Movielens-l0ok数据集进行实验，验证GWCF算 ∑sim(a,b)x(r-ia) 法的可扩展性。 (2) ∑sim(a,b) 1相关工作 式中：。表示用户w已评项目的平均评分；表 示用户已评项目的平均评分；N表示用户w 1.1问题定义 的近邻用户集合；sim(a,b)表示目标用户u。与近 基于近邻的协同过滤问题可以描述为：已 邻用户，的相似度。 知用户集合表示为U={,2,…,a,…,…,}, 项目集合表示为S={s,2,…,5,…,5…3n,用户. 2改进的皮尔逊相关相似度 广1m r21 T22 皮尔逊相关相似度计算方法如式(1)，仅仅考 项目评分矩阵R= 表示用 虑了用户的共同评分项，而忽视了共同评分项目 Tnlr2… 与每个用户所有评分项的比例关系。这会导致如 户。对项目s,的评分。基于近邻的协同过滤推 果两个用户仅有极少数共同评分项目，并且两个
户，以减轻用户的选择负担。协同过滤推荐算法 是一种目前应用最广泛的推荐算法[2] ，可以在用 户没有明确提出自己需求的情况下，根据用户的 行为对用户进行推荐。但由于大数据环境下用户 和项目的数量不断增长，协同过滤推荐算法面临 着严重的数据稀疏性和可扩展性问题[3]。 针对稀疏性问题，许多学者从不同角度进行 了相关研究。SUN 等 [4] 采用聚类和时间影响因子 矩阵来监测用户兴趣漂移程度，更准确的预测项 目的评分。彭宏伟等[5] 提出一种基于矩阵分解的 上下文感知 POI推荐模型，有效地缓解稀疏性问 题。WU 等 [6]将异构信息网络建模为张量，并提出 两种随机梯度下降方法同时进行分解。MA 等 [7] 提出了一种局部概率矩阵分解的方法，降低稀疏 性的同时有效地缓解了每个局部模型的过拟合问 题。以上的方法均通过缓解数据稀疏性问题来提 高推荐的准确度。 针对协同过滤推荐算法在处理大规模数据所 遇到的可扩展性问题，许多学者在并行方法上进 行了相关研究。杨志文[8] 、LU F[9] 、KUPISZ[10] 等 将协同过滤推荐算法部署在 Hadoop 和 Spark 并 行平台上，取得了良好的执行效率。 本文针对协同过滤推荐算法的数据稀疏性问 题和可扩展性问题进行研究。针对稀疏性问题， 在皮尔逊相关相似度的基础上引入交占比系数来 计算用户的直接相似度，提出了一种基于图游走 的协同过滤推荐算法 (GW_CF)，使用图游走的方 法计算用户的间接相似度，然后根据直接相似度 和间接相似度重建用户的相似度矩阵，最后进行 推荐。 在 Movielens-100 k 数据集 和 IPTV 数据集上实验，验证 GW_CF 在提高推荐准确度 上的有效性。针对可扩展性问题，在 Spark 平台 上实现 GW_CF 算法，并使用 Movielens-1M 和 Movielens-100k 数据集进行实验，验证 GW_CF 算 法的可扩展性。 1 相关工作 1.1 问题定义 U = {u1,u2,··· ,ua,···ub,··· ,un} S = { s1,s2,··· ,si ,··· ,sj ,···sm } R = r11 r12 ··· r1m r21 r22 ··· r2m . . . . . . . . . rn1 rn2 ··· rnm rai ua si 基于近邻的协同过滤问题可以描述为[11] ：已 知用户集合表示为 ， 项目集合表示为 ，用户- 项目评分矩阵 ， 表示用 户 对项目 的评分。基于近邻的协同过滤推 荐算法的流程：1) 根据评分矩阵 R 计算用户的相 似度；2) 计算目标用户的近邻用户集合；3) 根据 近邻用户的评分预测目标用户对未评分项目的评 分，从而生成推荐列表。 1.2 用户相似度 ua ub 用户相似度指用户与用户之间行为中表现出 的相似程度，皮尔逊相关相似度是一种常用的计 算相似度的方法，反映了两个用户的偏好信息的 线性相关程度。用户 和用户 的皮尔逊相关 相似度计算公式[12-13] 如下： sim(a,b) = ∑ si∈sab (rai −r¯a) (rbi −r¯b) √ ∑ si∈sab (rai −r¯a) √ ∑ si∈sab (rbi −r¯b) (1) sab ua ub rai ua si r¯a ua sab sim(a,b) [−1,1] sim(a,b) 式中： 为用户 和用户 共同评分项目的集 合； 为用户 对项目 的评分； 为用户 对 集合 中项目评分的平均值。 的值域为 ， 越大，表示两个用户的相似度越高。 1.3 近邻用户 近邻用户表示与目标用户偏好信息最相似的 一组用户，可以通过式 (1) 计算用户的相似度，然 后计算目标用户的近邻用户。目标用户的多个近 邻用户组成目标用户的近邻用户集合，常用的计 算近邻用户集合的方法分为两类：基于数量的近 邻用户集合和基于阈值的近邻用户集合。 基于阈值的近邻用户集合包含以目标用户为 中心，与目标用户的相似度大于 Value 的用户。 基于数量的近邻用户集合包含与目标相似度最大 的 Top-K 个近邻用户。 1.4 个性化推荐 ua si 首先计算目标用户的近邻用户集合，然后对 目标用户进行推荐。目标用户 对未评分项目 预测评分的计算公式[14] 如式（2），最后将预测评 分最大的 K 个项目推荐给目标用户。 rai = r¯a + ∑ ub∈Nua sim(a,b)×(rbi −r¯b) ∑ ub∈Nua sim(a,b) (2) r¯a ua r¯b ub Nua ua sim(a,b) ua ub 式中： 表示用户 已评项目的平均评分； 表 示用户 已评项目的平均评分； 表示用户 的近邻用户集合； 表示目标用户 与近 邻用户 的相似度。 2 改进的皮尔逊相关相似度 皮尔逊相关相似度计算方法如式 (1)，仅仅考 虑了用户的共同评分项，而忽视了共同评分项目 与每个用户所有评分项的比例关系。这会导致如 果两个用户仅有极少数共同评分项目，并且两个 ·744· 智 能 系 统 学 报 第 14 卷
第4期 顾军华，等：基于图游走的并行协同过滤推荐算法 ·745· 用户对共同评分项目的评分极度相似，使用皮尔 (3)计算用户山和用户的相似度，由于用户4 逊相关相似度计算得到的用户的相似度，远远大 和用户没有共同评分项，所以sim(1,3)=0。但 于用户的真实相似度，降低了推荐的准确度。例 是用户山和2拥有共同评分项目s4和55，那么 如，用户w曾对200个项目进行了评分，用户 sim(1,2)>0,同理sim(2,3)>0。由于相似性具有 对300个项目进行了评分，两个用户仅拥有10个 传递性，因此用户山，和可以通过共同的相似用 共同评分项目，且两个用户对每个共同评分项目 户2建立间接相似度，使得sim(1,3)>0。如果两 的评分均相同。使用传统皮尔逊相关相似度计算 个用户没有共同评分项目，但间接相似度大于0 两者的相似度为1（两个用户完全相似）。但实际 称这两个用户为间接近邻用户。在数据稀疏时， 上，除了10个共同评分项目以外，用户。和用户 为用户寻找间接近邻用户能够有效地提高推荐的 4,还各自拥有大量的非共同评分项目，两个用户 准确度。本文提出了基于图游走的方法，首先根 的喜好并不完全相同，利用皮尔逊相关相似度得 据用户的直接相似度矩阵建立用户网络图，其次 到的结果远远大于两个用户的真实相似度。针对 在用户网络图上进行游走计算间接相似度，然后 这个问题，本文在皮尔逊相关相似度基础上，引 根据间接相似度和直接相似度重建用户的相似度 入交占比系数来缓解共同评分项占比的问题，交 矩阵，最后进行推荐。 占比反映了两个用户的共同评分项在两个用户评 表1用户评分示例表 分中的占比，加入交占比系数的皮尔逊相关相似 Table 1 User rating 度计算公式如下： 用户 S2 S3 S4 S5 S6 S7 S8 ∑(Tai-ia)(i-i) 4 2351 4 sim(a,b)= 2×l小sbl (3) Isal+I56l 3235 3 式中：sbl表示用户W。和用户山，共同评分项目的 个数；s.表示用户w的评分项目个数；sl表示用 用户4 用户助 户w的评分项个数；其他变量的含义和式(1) 相同。 5im(1,2=0.8 表1为用户评分示例，山1、和出表示3个用 户，51,52…，58表示8个项目，表中的值表示用户 对项目的评分，表中的空值（一）表示该用户未曾 对该项目评分。根据式(1)计算用户山和用户2 sim(1,3=02 sim(2,3=0.7 的相似度，山和西2的共同评分项集合 6 s2={s3,S4,s,山1和出对s12的评分均为[2,3,5，得 用户山 到sim(1,2)=1,显然这并不能准确的反映用户 和用户2的相似程度。使用加入交占比的式 (3)计算用户4和用户的相似度，s2l=3, 图1间接相似度关系图 lsl=6,ls2=5,得到sim(1,2)≈0.545，显然0.545更 Fig.1 Indirect similarity diagram 符合用户山，和用户山的真实相似度。 3.1构建用户网络图 使用用户网络图来说明用户间的相似关 基于图游走的协同过滤推荐算法 (GW CF) 系，从目标用户开始游走后停留在某个用户的概 率越高意味着它与目标用户更相似。为了建立用 相似度计算是协同过滤推荐算法的关键部 户网络图，首先使用式(3)计算用户间的直接相 分，得到用户相似度之后可以确定用户的近邻用 似度，然后根据直接相似度建立用户近邻矩阵。 户集合。但以往计算用户的相似度时只考虑用户 为每个用户选择T个直接近邻用户，其他非T用 的直接相似相似度，这样将会遗失目标用户的间 户的相似度置0，得到的近邻矩阵如式(4)所示： 接近邻用户s-1。例如图1所示，山1、和山表示 su11su12· SUim 3个用户，51,52，…表示用户41的评分项目， SU21 SU2m SU= (4) 54,5,…5g表示用户的评分项目，56,57，…，S0表 示用户4的评分项目。sim(1,2)、sim(2,3)、 sunl Su2· Sun sim(1,3)表示用户41、山2和3的相似度。依据式 式中：对每个用户建立T近邻集合N;如果用
ua ub ua ub 用户对共同评分项目的评分极度相似，使用皮尔 逊相关相似度计算得到的用户的相似度，远远大 于用户的真实相似度，降低了推荐的准确度。例 如，用户 曾对 200 个项目进行了评分，用户 对 300 个项目进行了评分，两个用户仅拥有 10 个 共同评分项目，且两个用户对每个共同评分项目 的评分均相同。使用传统皮尔逊相关相似度计算 两者的相似度为 1(两个用户完全相似)。但实际 上，除了 10 个共同评分项目以外，用户 和用户 还各自拥有大量的非共同评分项目，两个用户 的喜好并不完全相同，利用皮尔逊相关相似度得 到的结果远远大于两个用户的真实相似度。针对 这个问题，本文在皮尔逊相关相似度基础上，引 入交占比系数来缓解共同评分项占比的问题，交 占比反映了两个用户的共同评分项在两个用户评 分中的占比，加入交占比系数的皮尔逊相关相似 度计算公式如下： sim(a,b) = 2×|sab| |sa|+|sb| × ∑ si∈sab (rai −r¯a) (rbi −r¯b) √ ∑ si∈sab (rai −r¯a) √ ∑ si∈sab (rbi −r¯b) (3) |sab| ua ub |sa| ua |sb| ub 式中： 表示用户 和用户 共同评分项目的 个数； 表示用户 的评分项目个数； 表示用 户 的评分项个数；其他变量的含义和式 (1) 相同。 u1 u2 u3 s1,s2 ··· ,s8 u1 u2 u1 u2 s12 = {s3,s4,s5} u1 u2 s12 [2,3,5] sim(1,2) = 1 u1 u2 u1 u2 |s12| = 3 |s1| = 6 |s2| = 5 sim(1,2) ≈ 0.545 0.545 u1 u2 表 1 为用户评分示例， 、 和 表示 3 个用 户， 表示 8 个项目，表中的值表示用户 对项目的评分，表中的空值 (—) 表示该用户未曾 对该项目评分。根据式 (1) 计算用户 和用户 的相似度， 和 的共同评分项集合 ， 和 对 的评分均为 ，得 到 ，显然这并不能准确的反映用户 和用户 的相似程度。使用加入交占比的式 ( 3 ) 计算用户 和用户 的相似度， ， ， ，得到 ，显然 更 符合用户 和用户 的真实相似度。 3 基于图游走的协同过滤推荐算法 (GW_CF) u1 u2 u3 s1,s2,··· ,s5 u1 s4,s5,···s8 u2 s6,s7,··· ,s10 u3 sim(1,2) sim(2,3) sim(1,3) u1 u2 u3 相似度计算是协同过滤推荐算法的关键部 分，得到用户相似度之后可以确定用户的近邻用 户集合。但以往计算用户的相似度时只考虑用户 的直接相似相似度，这样将会遗失目标用户的间 接近邻用户[15-16]。例如图 1 所示， 、 和 表示 3 个用户， 表示用户 的评分项目， 表示用户 的评分项目， 表 示用户 的评分项目。 、 、 表示用户 、 和 的相似度。依据式 u1 u3 u1 u3 sim(1,3) = 0 u1 u2 s4 s5 sim(1,2) > 0 sim(2,3) > 0 u1 u3 u2 sim(1,3) > 0 (3) 计算用户 和用户 的相似度，由于用户 和用户 没有共同评分项，所以 。但 是用户 和 拥有共同评分项目 和 ，那么 ，同理 。由于相似性具有 传递性，因此用户 和 可以通过共同的相似用 户 建立间接相似度，使得 。如果两 个用户没有共同评分项目，但间接相似度大于 0， 称这两个用户为间接近邻用户。在数据稀疏时， 为用户寻找间接近邻用户能够有效地提高推荐的 准确度。本文提出了基于图游走的方法，首先根 据用户的直接相似度矩阵建立用户网络图，其次 在用户网络图上进行游走计算间接相似度，然后 根据间接相似度和直接相似度重建用户的相似度 矩阵，最后进行推荐。 表 1 用户评分示例表 Table 1 User rating 用户 s1 s2 s3 s4 s5 s6 s7 s8 u1 4 — 2 3 5 1 — 4 u2 — 3 2 3 5 — 2 — u3 — 3 4 3 — 1 — 4 s1 s2 s4 s5 s3 s4 s5 s6 用户u1 用户u2 s7 s8 用户u3 s7 s6 s8 s10 s9 sim (1,2)=0.8 sim (1,3)=0? sim (2,3)=0.7 图 1 间接相似度关系图 Fig. 1 Indirect similarity diagram 3.1 构建用户网络图 使用用户网络图来说明用户间的相似关 系,从目标用户开始游走后停留在某个用户的概 率越高意味着它与目标用户更相似。为了建立用 户网络图，首先使用式 (3) 计算用户间的直接相 似度，然后根据直接相似度建立用户近邻矩阵。 为每个用户选择 T 个直接近邻用户，其他非 T 用 户的相似度置 0，得到的近邻矩阵如式 (4) 所示： SU = su11 su12 ··· su1n su21 su22 ··· su2n . . . . . . . . . sun1 sun2 ··· sunn (4) 式中：对每个用户 ua 建立 T 近邻集合 Nua；如果用 第 4 期 顾军华，等：基于图游走的并行协同过滤推荐算法 ·745·
·746· 智能系统学报 第14卷 户不是用户a的T近邻用户，则sub=0;若用 户和用户的相对相似程度。不考虑用户和 户wb是用户wa的T近邻用户，则sub=sim(a,b)。 它本身的相似度，因此令r=a=0。r越大，表示用 在游走过程中不考虑用户和自身的相似度，所以 户4。和目标用户4，的间接相似度越高。 令sua=0。 然后对矩阵SU按列进行归一化，得到矩阵 SU°，以矩阵SU作为邻接矩阵建立用户网络图。 矩阵SU中的SU表示从当前用户节点。下一 D 步游走到用户节点4的概率。 3.2基于用户网络图游走 图2非强连通用户网络示例图 Fig.2 Non-strong connected user network 用向量=[…]中表示第k次游走 3.3 重建相似度矩阵 之后停留在节点的概率，向量su。=[su1… sub…sum]中sub=SU,则向量+1=su×()T为 向量，反映了各个用户与目标用户的相似程 k+1次游走后停留在节点u的概率。整个用户网 度相对大小，游走过程中的多次累加导致过 络图的游走过程公式如下： 大，进行推荐之前需要将向量r映射到直接相似 度同一个数量级上，因此需要重建相似度矩阵。 ()"=sUx() (5) 集合N={u∈Nsub≠O}表示直接近邻集 式中：SU为用户网络图的邻接矩阵：为第k次 合N中和目标用户相似度大于0的用户集合。 游走后停留在各个节点的概率向量；= 利用该集合中用户与目标用户的直接相似度和向 。的。其中b=口表示从用户节点以开始游走。 量，对应元素的映射关系，将向量，转化为目标 在用户网络图中存在着与其他用户的相似度 用户和其他用户的间接相似度向量，重建的相似 都很低甚至可以忽略不计的特殊用户节点。在用 度计算公式为： 户网络图中此类节点只有入度，没有出度，如图2 SU 中节点D,此时由于图中D节点只有入度，没有 sim(a,b)= N' Xra,6生N (8) 出度，用户网络图演变为非强连通图，以式（⑤）的 subh,eN”u 方法游走到图中节点D时将无法跳转到其他节 式中：sim(a,b)表示目标用户wa和用户的重建 点。整个用户网络图的游走最终停留在类似节 相似度；sub表示目标用户。和用户，的直接相 点D的死节点，无法求得用户的间接相似度，因 似度；W表示集合N中用户个数。 此对式（⑤）进行变形如下： 3.4生成推荐结果 ()'=pxSU×()+(1-p)x (6) 以每个用户顶点为起点进行游走查找其间接 式中：p表示n次游走后在当前节点继续游走的 相似用户，得到重建的用户相似度矩阵，进一步 概率；(1-p)表示随机远程跳转到目标节点的概 得到目标用户的近邻用户集合。然后利用式 率。p的大小与式(6)的收敛速度成反比，p太大 (2)对目标用户的未评分项目进行评分预测，并将 会导致收敛速度太慢从而影响算法的性能，p如 评分最高的Top-K个项目推荐给目标用户。 果太小则无法反映游走的效果，因此令p=0.85。 向量t=…]表示远程跳转的目标节点， 4基于图游走的并行协同过滤推荐 6=1,b=a 算法 0,b≠a° 当式(6)经过有限次迭代后，向量收敛。 4.1 Spark介绍 在理想情况下，当k趋于无穷大时，+1==r, Spark是基于内存的分布式并行计算平台， 那么式(6可以表示为rr=p×SU×rF+(1-p)×tF。 它拥有Hadoop平台和MapReduce框架的全部优 对式(6)进一步变形得到式(7)，在从不同用户顶 点，并且Spark运算的中间结果能存储在内存中， 点开始游走查找它的间接相似用户时，(1-p)× 提高了并行计算的速度，因此Spark更适合进行 (I-p×SU)1只需要计算一次。相对于式(6)的多 数据挖掘与机器学习等需要迭代处理算法的实 次迭代，式（⑦大大降低了计算的复杂度。 现9：2。Spark集群启动时包括一个Master节点 r=(1-p)×(I-p×S)'×t (7) 和若干个Worker节点，其中Master节点主要负责 式中：向量r=[n…%…rJ中rb表示从用户a 集群资源的管理，Worker节点主要负责数据的计 开始游走最终停留在用户山，的概率；。被视作用 算。当在Master节点使用spark-submit命令提交
ub ua suab = 0 ub ua suab = sim(a,b) suaa = 0 户 不是用户 的 T 近邻用户，则 ；若用 户 是用户 的 T 近邻用户，则 。 在游走过程中不考虑用户和自身的相似度，所以 令 。 SU SU∗ SU∗ SU∗ SU∗ ab ub ua 然后对矩阵 按列进行归一化，得到矩阵 ，以矩阵 作为邻接矩阵建立用户网络图。 矩阵 中的 表示从当前用户节点 下一 步游走到用户节点 的概率。 3.2 基于用户网络图游走 r k = [ r k 1 r k 2 ...r k b ...r k n ] r k b ub sua = [sua1 ··· suab ··· suan] suab = SU∗ ab r k+1 a =sua × ( r k )T ua 用向量 中 表示第 k 次游走 之后停留在节点 的概率，向量 中 ，则向量 为 k+1 次游走后停留在节点 的概率。整个用户网 络图的游走过程公式如下： ( r k+1 )T = SU∗ × ( r k )T (5) SU∗ r k k r 0 b = { 1,b = a 0,b , a b = a ua 式中： 为用户网络图的邻接矩阵； 为第 次 游走后停留在各个节点的概率向量； ，其中 表示从用户节点 开始游走。 在用户网络图中存在着与其他用户的相似度 都很低甚至可以忽略不计的特殊用户节点。在用 户网络图中此类节点只有入度，没有出度，如图 2 中节点 D，此时由于图中 D 节点只有入度，没有 出度，用户网络图演变为非强连通图，以式 (5) 的 方法游走到图中节点 D 时将无法跳转到其他节 点。整个用户网络图的游走最终停留在类似节 点 D 的死节点，无法求得用户的间接相似度，因 此对式 (5) 进行变形如下： ( r k+1 )T = p×SU∗ × ( r k )T +(1− p)× t T (6) p n (1− p) p p p p = 0.85 t = [t1 t2 ···tn] tb = { 1,b = a 0,b , a 式中： 表示 次游走后在当前节点继续游走的 概率； 表示随机远程跳转到目标节点的概 率。 的大小与式 (6) 的收敛速度成反比， 太大 会导致收敛速度太慢从而影响算法的性能， 如 果太小则无法反映游走的效果，因此令 。 向 量 表示远程跳转的目标节点， 。 r k k r k+1 = r k = r r T = p×SU∗ × r T +(1− p )× t T (1− p)× (I− p×SU∗ ) −1 当式 (6) 经过有限次迭代后，向量 收敛[17-18]。 在理想情况下，当 趋于无穷大时， ， 那么式 (6) 可以表示为 。 对式 (6) 进一步变形得到式 (7)，在从不同用户顶 点开始游走查找它的间接相似用户时， 只需要计算一次。相对于式 (6) 的多 次迭代，式 (7) 大大降低了计算的复杂度。 r T = (1− p)×(I− p×S ∗ ) −1 × t T (7) r = [r1 ··· rb ··· rn] rb ua ub rb 式中：向量 中 表示从用户 开始游走最终停留在用户 的概率； 被视作用 ua ub rb=a= 0 rb ua ub 户 和用户 的相对相似程度。不考虑用户和 它本身的相似度，因此令 。 越大，表示用 户 和目标用户 的间接相似度越高。 A B D C 图 2 非强连通用户网络示例图 Fig. 2 Non-strong connected user network 3.3 重建相似度矩阵 r rb 向量 反映了各个用户与目标用户的相似程 度相对大小，游走过程中的多次累加导致 过 大，进行推荐之前需要将向量 r 映射到直接相似 度同一个数量级上，因此需要重建相似度矩阵。 N ′ ua = { ub|ub ∈ Nua suab , 0 } Nua r r 集合 表示直接近邻集 合 中和目标用户相似度大于 0 的用户集合。 利用该集合中用户与目标用户的直接相似度和向 量 对应元素的映射关系，将向量 转化为目标 用户和其他用户的间接相似度向量，重建的相似 度计算公式为： sim(a,b) = ∑ ub ∈N′ ua suak rk N′ ua ×ra suab ub ∈ N ′ ua , ub < N ′ ua (8) sim(a,b) ua ub suab ua ub N ′ ua N ′ ua 式中： 表示目标用户 和用户 的重建 相似度； 表示目标用户 和用户 的直接相 似度； 表示集合 中用户个数。 3.4 生成推荐结果 以每个用户顶点为起点进行游走查找其间接 相似用户，得到重建的用户相似度矩阵，进一步 得到目标用户的近邻用户集合。然后利用式 (2) 对目标用户的未评分项目进行评分预测，并将 评分最高的 Top-K 个项目推荐给目标用户。 4 基于图游走的并行协同过滤推荐 算法 4.1 Spark 介绍 Spark 是基于内存的分布式并行计算平台[19] ， 它拥有 Hadoop 平台和 MapReduce 框架的全部优 点，并且 Spark 运算的中间结果能存储在内存中， 提高了并行计算的速度，因此 Spark 更适合进行 数据挖掘与机器学习等需要迭代处理算法的实 现 [19-21]。Spark 集群启动时包括一个 Master 节点 和若干个 Worker 节点，其中 Master 节点主要负责 集群资源的管理，Worker 节点主要负责数据的计 算。当在 Master 节点使用 spark-submit 命令提交 ·746· 智 能 系 统 学 报 第 14 卷
第4期 顾军华，等：基于图游走的并行协同过滤推荐算法 ·747· 作业时，首先在本地客户端启动一个Driver进程； 式中：rm表示用户w对项目的评分；下。表示用户 Driver进程会根据设置的参数向Master节点申请 “的评分均值。皮尔逊相关相似度公式可以变形为 相应的集群资源，主要有Worker节点个数、每个 Worker节点上Executor的内存和CPU数量；Mas- sim(a,b)= .x (10) SEsd ter节点与Worker节点进行通信，通知Worker节 因此，求用户ua和用户的相似度sim(a,b) 点启动Executor并向Driver进程注册；Driver进 的过程转化为5步：1)对于用户4和用户，的共 程与Worker节点连接起来，将需要执行的任务分 配给集群中的各个Worker节点，Worker节点按 同评分项s:∈sb,计算中间变量Qa和Qa;2)求用 照任务分配从HDFS上读取数据并缓存到内存 户。和用户6的Q乘积Qm×Q;3)计算 中，Driver进程对各个Worker节点处理完的结果 ∑Qm×Q得到皮尔逊相关相似度；4)交占比系数 进行收集和汇总。在Spark平台实现基于图游走 得到用户的直接相似度；5)使用游走的方法求得 的协同过滤算法能够有效地提高算法的时间 用户的间接相似度并重建相似度。 效率。 4.2相似性计算的并行化 4.3基于图游走的协同过滤算法并行化流程 由于皮尔逊相关相似度计算公式较为复杂， 基于图游走的协同过滤推荐算法在Spark平 全局搜索较多，因此在实现本文方法并行化时引 台上的并行化包括3部分，分别是读入数据创建 入中间变量Q,Qm反映了用户。在项目s:上的 RDD、计算用户的相似度以及生成推荐列表，该 相似度权重，计算公式如下： 算法的并行化主要体现在计算用户相似度和生成 Cai=- (rai-Fa) (9) 推荐列表。基于图游走的并行协同过滤推荐算法 示意图如图3所示。 开始 读人评分数据 按用户划分不同分区 分区1计算Q, 分区2：计算Q2 分区m1:计算O 分区x计算Q 1≤i≤m 1≤i≤m 1≤i≤m 1≤i≤m 分区1计算Q×Q 分区P:计算Q-w×Qm 1≤i≤m I≤i≤m 分区1：计算sim(1,2) 分区：计算sim(广l,) 直接相似度矩阵 userMatrixRDD 分区1：用户山，的间接 分区r用户u的间接 相似度向量r 相似度向量r。 重建用户相似度矩阵 t 按用户划分不同分区 分区1上计算u的 分区m:计算u的 近邻集合N(I) 近邻集合N(n) 分区1：计算4，的 分区m:计算u的 推荐列表 推荐列表 结柬 图3基于图游走的并行协同过滤示意图 Fig.3 Parallel collaboration filtering based on graph walk schematic
作业时，首先在本地客户端启动一个 Driver 进程； Driver 进程会根据设置的参数向 Master 节点申请 相应的集群资源，主要有 Worker 节点个数、每个 Worker 节点上 Executor 的内存和 CPU 数量；Master 节点与 Worker 节点进行通信，通知 Worker 节 点启动 Executor 并向 Driver 进程注册；Driver 进 程与 Worker 节点连接起来，将需要执行的任务分 配给集群中的各个 Worker 节点，Worker 节点按 照任务分配从 HDFS 上读取数据并缓存到内存 中，Driver 进程对各个 Worker 节点处理完的结果 进行收集和汇总。在 Spark 平台实现基于图游走 的协同过滤算法能够有效地提高算法的时间 效率。 4.2 相似性计算的并行化 Q Qai ua si 由于皮尔逊相关相似度计算公式较为复杂， 全局搜索较多，因此在实现本文方法并行化时引 入中间变量 ， 反映了用户 在项目 上的 相似度权重，计算公式如下： Qai = (rai −r¯a) √∑ a (rai −r¯a) (9) rai ua si r¯a ua 式中： 表示用户 对项目 的评分； 表示用户 的评分均值。皮尔逊相关相似度公式可以变形为 sim(a,b) = 2×|sab| |sa|+|sb| × ∑ si∈sab Qai × Qbi (10) ua ub sim(a,b) ua ub si ∈ sab Qai Qbi ua ub Q Qai × Qbi ∑ si∈sabQai×Qbi 因此，求用户 和用户 的相似度 的过程转化为 5 步：1）对于用户 和用户 的共 同评分项 ，计算中间变量 和 ；2）求用 户 和用户 的 乘 积 ； 3 ）计算 得到皮尔逊相关相似度；4）交占比系数 得到用户的直接相似度；5）使用游走的方法求得 用户的间接相似度并重建相似度。 4.3 基于图游走的协同过滤算法并行化流程 基于图游走的协同过滤推荐算法在 Spark 平 台上的并行化包括 3 部分，分别是读入数据创建 RDD、计算用户的相似度以及生成推荐列表，该 算法的并行化主要体现在计算用户相似度和生成 推荐列表。基于图游走的并行协同过滤推荐算法 示意图如图 3 所示。 开始 按用户划分不同分区 按用户划分不同分区 重建用户相似度矩阵 结束 直接相似度矩阵 userMatrixRDD … … … … … … 读入评分数据 分区1:计算Q1i 1≤i≤m 分区2:计算Q2i 1≤i≤m 分区n:计算Qni 1≤i≤m 分区n−1:计算Q(n−1)i 1≤i≤m 分区1:计算Q1i×Q2i 1≤i≤m 分区1:计算sim(1,2) 分区n 2 :计算Qa(n−1)i×Qni 1≤i≤m 分区n 2 :计算sim(n−1,n) 分区1:用户u1的间接 相似度向量r1 分区n:用户un的间接 相似度向量rn 分区1:计算u1的 近邻集合N(1) 分区n:计算un的 近邻集合N(n) 分区1：计算u1的 推荐列表 分区n:计算un的 推荐列表 图 3 基于图游走的并行协同过滤示意图 Fig. 3 Parallel collaboration filtering based on graph walk schematic 第 4 期 顾军华，等：基于图游走的并行协同过滤推荐算法 ·747·