第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·
·748· 智能系统学报 第14卷 具体过程如下： 式中：N表示预测评分记录数量，”表示该条记录 1)读入用户行为数据，构建RDD: 的预测评分，'表示该条记录的实际评分。 2)将RDD,转换成(ua,(S,ra》形式的RDD2, 准确率precision反映了推荐的准确度，准确 (1≤a≤n,1≤i≤m)按照用户ID进行聚集得到 率越高，表明推荐的准确度越高。准确率的计算 RDD,(ua,Iterable[(s,ra),使用flatMap算子计算每 公式为 个用户的中间变量Q,并按照项目D进行聚集得 ∑R(w)nT(ul 到RDD; precision= (12) R(u) 3)根据RDD,计算用户w。和用户4的 式中：R(训表示推荐给用户的所有项目个数； Qa×Qa,得到形如(a,4,(Q,1,toNum)的RDDs, R(w)nT(w训表示推荐给用户的项目中推荐正确的 其中的1和toNum是为了便于计算交占比系数而 项目个数。 设置的： 以加速比作为可扩展性的实验指标，加速 4)将3)的RDD,使用ReduceByKey算子统计 比为 其共同评分项，计算结合交占比系数的相似度， (13) 得到形如(a,),simb)的RDD6; 5)利用4)的相似度RDD6,构造用户相似度 式中：T,表示使用1个节点时任务执行时间；T。 矩阵userMatrixRDD,使用Spark中的线性代数库 表示使用p个节点时任务执行时间；S。表示加速 Breeze,调用其库函数inv()计算userMat- 比，反映了并行后运行效率的提升情况。S。=p rixRDD的逆矩阵invMatrixRDD,进一步通过式 时为线性加速比，加速比越接近线性加速比时， (7)和(8)求得得间接相似度，重建相似度矩阵得 算法的可扩展性越好。 到RDD: 5.1 相似度交占比系数的有效性验证实验 6)根据RDD,按用户划分得到RDDg,并进一 在原始的皮尔逊相关相似度的基础上，为了 步得到目标用户的近邻用户集合RDD,最后进行 比较加入交占比(YPCC)和未加入交占比 推荐。 (PCC)对预测评分误差的影响进行本次实验。此 次实验使用Movielens-100k数据集，共943用户， 5实验与评价 1682个项目，共10万条评分记录，稀疏度为94.12%， 实验使用Movielens数据集和IPTV数据集o 训练集和测试集按8：2分割。实验结果如图4。 进行实验。Movielens是一个基于Web的研究型 图4中，Top-K表示近邻用户选取的个数， 推荐系统，用于接收用户对电影的评分并提供电 MAE表示评分预测的平均绝对误差，PCC表示未 影的推荐列表，Movielens数据集在协同过滤研究 加入交占比系数计算用户相似度进行评分预测的 领域得到了广泛研究，也是使用最多的数据集之 误差曲线，YPCC表示加人交占比系数计算用户 一。PTV数据集来源于天津市PTV电视用户的 相似度进行推荐的误差曲线。 0.90 收视日志数据，经过对日志数据进行预处理和隐 式评分处理，形成IPTV数据集。相比于Movielens 0.88 c 数据集，IPTV数据集应用性更高。Movielens- 0.86 100k数据集包含943用户，1682项目，共10万条 0.84 评分记录；Movielens-.lM数据集包含6040个用户 0.82 和3952个项目，共计100万条评分记录。IPTV 0.80 数据集选取193用户，8200项目，共计43175条 0.78 评分记录。 20 406080100 使用平均绝对误差MAE和准确率precision Top-K 作为衡量推荐准确度的指标。MAE反映了评分 图4交占比系数有效性验证实验 预测误差的大小，误差越小表明推荐准确度越 Fig.4 Trial ratio validity validation experiment 高，计算公式(11)如下： 从图4中可以看出，协同过滤推荐算法的预 测评分误差受到近邻用户个数Top-K的影响。随 - 着近邻用户个数Top-K的增加，PCC和YPCC曲 MAE= (11) 线均呈现下降趋势并最终趋于稳定，但是YP
具体过程如下： 1) 读入用户行为数据，构建 RDD1； (ua,(si ,rai)) (1 ⩽ a ⩽ n,1 ⩽ i ⩽ m) (ua,Iterable[(si ,rai)]) Q 2) 将 RDD1 转换成 形式的 RDD2， 按照用 户 I D 进行聚集得 到 RDD3 ，使用 flatMap 算子计算每 个用户的中间变量 ，并按照项目 ID 进行聚集得 到 RDD4； ua ub Qai × Qbi ((ua,ub),(Qab,1,toNum)) 3) 根 据 RDD 4 计算用户 和用户 的 ，得到形如 的 RDD5 , 其中的 1 和 toNum 是为了便于计算交占比系数而 设置的； ((ua,ub),simab) 4) 将 3) 的 RDD5 使用 ReduceByKey 算子统计 其共同评分项，计算结合交占比系数的相似度， 得到形如 的 RDD6； 5) 利用 4) 的相似度 RDD6，构造用户相似度 矩阵 userMatrixRDD，使用 Spark 中的线性代数库 Breeze ，调用其库函 数 inv() 计 算 userMatrixRDD 的逆矩阵 invMatrixRDD，进一步通过式 (7) 和 (8) 求得得间接相似度，重建相似度矩阵得 到 RDD7； 6) 根据 RDD7 按用户划分得到 RDD8，并进一 步得到目标用户的近邻用户集合 RDD9，最后进行 推荐。 5 实验与评价 实验使用 Movielens 数据集和 IPTV 数据集[20] 进行实验。Movielens 是一个基于 Web 的研究型 推荐系统，用于接收用户对电影的评分并提供电 影的推荐列表，Movielens 数据集在协同过滤研究 领域得到了广泛研究，也是使用最多的数据集之 一。IPTV 数据集来源于天津市 IPTV 电视用户的 收视日志数据，经过对日志数据进行预处理和隐 式评分处理，形成 IPTV 数据集。相比于 Movielens 数据集，IPTV 数据集应用性更高。Movielens- 100k 数据集包含 943 用户，1 682 项目，共 10 万条 评分记录；Movielens-1M 数据集包含 6 040 个用户 和 3 952 个项目， 共计 100 万条评分记录。IPTV 数据集选取 193 用户，8 200 项目，共计 43 175 条 评分记录。 MAE precision MAE 使用平均绝对误差 和准确率 作为衡量推荐准确度的指标。 反映了评分 预测误差的大小，误差越小表明推荐准确度越 高，计算公式 (11) 如下： MAE = ∑N i=1 ri −r ′ i N (11) N ri ri ′ 式中： 表示预测评分记录数量， 表示该条记录 的预测评分， 表示该条记录的实际评分。 准确率 precision 反映了推荐的准确度，准确 率越高，表明推荐的准确度越高。准确率的计算 公式为 precision = ∑ u∈U |R(u)∩T (u)| |R(u)| (12) |R(u)| |R(u)∩T(u)| 式中： 表示推荐给用户的所有项目个数； 表示推荐给用户的项目中推荐正确的 项目个数。 以加速比作为可扩展性的实验指标，加速 比为 Sp = T1 Tp (13) T1 Tp p S p S p = p 式中： 表示使用 1 个节点时任务执行时间； 表示使用 个节点时任务执行时间； 表示加速 比，反映了并行后运行效率的提升情况。 时为线性加速比，加速比越接近线性加速比时， 算法的可扩展性越好。 5.1 相似度交占比系数的有效性验证实验 在原始的皮尔逊相关相似度的基础上，为了 比较加入交占 比 (YPCC ) 和未加入交占 比 (PCC) 对预测评分误差的影响进行本次实验。此 次实验使用 Movielens-100k 数据集，共 943 用户， 1 682 个项目，共 10 万条评分记录，稀疏度为 94.12%， 训练集和测试集按 8:2 分割。实验结果如图 4。 MAE 图 4 中 ，Top-K 表示近邻用户选取的个数， 表示评分预测的平均绝对误差，PCC 表示未 加入交占比系数计算用户相似度进行评分预测的 误差曲线，YPCC 表示加入交占比系数计算用户 相似度进行推荐的误差曲线。 0.88 0.90 0.86 0.84 0.82 0.80 0.78 MAE 20 40 60 80 100 Top−K PCC YPCC 图 4 交占比系数有效性验证实验 Fig. 4 Trial ratio validity validation experiment 从图 4 中可以看出，协同过滤推荐算法的预 测评分误差受到近邻用户个数 Top-K 的影响。随 着近邻用户个数 Top-K 的增加，PCC 和 YPCC 曲 线均呈现下降趋势并最终趋于稳定，但是 YP- ·748· 智 能 系 统 学 报 第 14 卷
第4期 顾军华，等：基于图游走的并行协同过滤推荐算法 ·749· CC曲线明显低于PCC曲线，尤其Top-K在[40， 0.88 60]时差距最明显。实验结果表明，无论近邻用 0.86 --GW CF -+-K-means CF 户个数如何选取，在皮尔逊相关相似度上加入交 0.84 -BSCF 占比系数均可以有效地减小评分预测误差。 5.2基于图游走方法的有效性验证实验 0 0.80 5.2.1 Movielens数据集实验 0.78 --￥---子 为了验证基于图游走方法在降低评分预测误 0.76 差和提高推荐准确率上的有效性，本次实验使用 020406080100120140160180 Movielens-100k数据集，训练集和测试集按8：2分 Top-K 割。先通过实验确定用户直接近邻个数T的最优 图6图游走效果图 取值，然后比较在不同的推荐近邻个数Top-K Fig.6 Random walk effect graph 下，本文方法和基于用户的协同过滤推荐算法 (BSCF)与基于聚类的协同过滤推荐算法(k- 0.090 ◆-GWCF 0.088 means CF)的MAE和precision。 -BSCF 0.086 图5为选取不同直接近邻个数时的评分预测 怒0.084 误差曲线，T表示直接近邻用户选取的个数。图5 是0.082 表明，当T>60时，MAE趋于稳定。 0.080 0.86 0.078 0.076 0.84 20304050607080 0.82 Top-K 20.80 图7准确率对比图 0.78 Fig.7 Accuracy comparison chart 0.76 5.2.2IPTV隐式评分数据集实验 010203040506070 为了验证基于图游走方法在降低评分预测误 差和提高推荐准确率上的有效性，本次实验使用 图5参数T测试图 PTV数据集，训练集和测试集按8：2分割。先通 Fig.5 Parameter T test chart 过实验确定用户直接近邻个数T的最优取值，然 图6的实验中T=60。推荐时近邻用户个数 后比较在不同的推荐近邻个数Top-K下，基于图 Top-K作为单一变量，对基于图游走的协同过滤 游走的协同过滤推荐算法(GWC℉)和基于用户 推荐算法(GWCF)、基于用户的协同过滤推荐算 法(BSCF)、基于聚类的协同过滤推荐算法(k- 的协同过滤推荐算法(BSCF)的MAE和precision。 means CF)进行对比实验。图6Top-K表示推荐 图8为选取不同直接近邻个数时的评分预测 时近邻用户选取的个数，MAE表示评分预测的平 误差曲线。图8表明，当T>20时，MAE趋于稳定。 均绝对误差。从图中可以看出，随着近邻用户个 0.315 数ToP-K的增加，3条曲线均呈下降趋势， 0.310 0.305 BSCF曲线和k-means CF曲线比较接近， 0.300 GWCF曲线明显低于另两条曲线，当Top-K 里0.295 大于80时更加明显。实验结果表明：GWCF算 三0.290 法在降低评分预测误差方面是有效的。 0.285 0.280 图7中虚线反映了使用GWCF推荐的准确 0.275 度，实线反映了使用BSCF推荐的准确度。生成 51015202530 推荐列表时推荐项目数为10，从图中可以看出， 随着近邻用户个数Top-K的增加，两条曲线呈上 图8参数T测试图 升趋势，GWCF准确率曲线高于BSCF曲线。实 Fig.8 Parameter T test chart 验结果表明，基于图游走的协同过滤推荐算法 图9的实验中T=20,推荐近邻用户Top-K GWCF可以有效地提高推荐准确率。 作为单一变量，对基于图游走的协同过滤推荐算
CC 曲线明显低于 PCC 曲线，尤其 Top-K 在 [40, 60] 时差距最明显。实验结果表明，无论近邻用 户个数如何选取，在皮尔逊相关相似度上加入交 占比系数均可以有效地减小评分预测误差。 5.2 基于图游走方法的有效性验证实验 5.2.1 Movielens 数据集实验 MAE precision 为了验证基于图游走方法在降低评分预测误 差和提高推荐准确率上的有效性，本次实验使用 Movielens-100k 数据集，训练集和测试集按 8:2 分 割。先通过实验确定用户直接近邻个数 T 的最优 取值，然后比较在不同的推荐近邻个数 Top-K 下，本文方法和基于用户的协同过滤推荐算法 (BSCF) 与基于聚类的协同过滤推荐算法 (kmeans_CF) 的 和 。 MAE 图 5 为选取不同直接近邻个数时的评分预测 误差曲线，T 表示直接近邻用户选取的个数。图 5 表明，当 T＞60 时， 趋于稳定。 0.86 0.84 0.82 MAE 0.80 0.78 0.76 T 0 10 20 30 40 50 60 70 图 5 参数 T 测试图 Fig. 5 Parameter T test chart MAE 图 6 的实验中 T=60。推荐时近邻用户个数 Top-K 作为单一变量，对基于图游走的协同过滤 推荐算法 (GW_CF)、基于用户的协同过滤推荐算 法 (BSCF)、基于聚类的协同过滤推荐算法 (kmeans_CF) 进行对比实验。图 6Top-K 表示推荐 时近邻用户选取的个数， 表示评分预测的平 均绝对误差。从图中可以看出，随着近邻用户个 数 Top- K 的增加， 3 条曲线均呈下降趋势， BSC F 曲 线 和 k-means_C F 曲线比较接近， GW_CF 曲线明显低于另两条曲线，当 Top-K 大于 80 时更加明显。实验结果表明：GW_CF 算 法在降低评分预测误差方面是有效的。 图 7 中虚线反映了使用 GW_CF 推荐的准确 度，实线反映了使用 BSCF 推荐的准确度。生成 推荐列表时推荐项目数为 10，从图中可以看出， 随着近邻用户个数 Top-K 的增加，两条曲线呈上 升趋势，GW_CF 准确率曲线高于 BSCF 曲线。实 验结果表明，基于图游走的协同过滤推荐算法 GW_CF 可以有效地提高推荐准确率。 0.86 0.88 0.84 0.82 0.80 0.78 0.76 MAE 0 40 60 80 100 120 140 160 180 20 Top−K GW_CF K−means_CF BSCF 图 6 图游走效果图 Fig. 6 Random walk effect graph 0.090 0.088 0.086 0.084 0.082 0.080 0.078 0.076 准确率 20 30 40 50 60 70 80 Top−K GW_CF BSCF 图 7 准确率对比图 Fig. 7 Accuracy comparison chart 5.2.2 IPTV 隐式评分数据集实验 MAE precision 为了验证基于图游走方法在降低评分预测误 差和提高推荐准确率上的有效性，本次实验使用 IPTV 数据集，训练集和测试集按 8:2 分割。先通 过实验确定用户直接近邻个数 T 的最优取值，然 后比较在不同的推荐近邻个数 Top-K 下，基于图 游走的协同过滤推荐算法 (GW_CF) 和基于用户 的协同过滤推荐算法 (BSCF) 的 和 。 MAE 图 8 为选取不同直接近邻个数时的评分预测 误差曲线。 图 8 表明，当 T＞20 时， 趋于稳定。 0.315 0.310 0.305 0.300 0.295 0.290 0.285 0.275 0.280 MAE 5 10 15 20 25 30 T 图 8 参数 T 测试图 Fig. 8 Parameter T test chart 图 9 的实验中 T=20，推荐近邻用户 Top-K 作为单一变量，对基于图游走的协同过滤推荐算 第 4 期 顾军华，等：基于图游走的并行协同过滤推荐算法 ·749·
·750· 智能系统学报 第14卷 法(GWCF)和基于用户的协同过滤推荐算法 5.0 (BSCF)进行对比实验。从图9中可以看出，随着 1000000 4.5 ◆-100000 近邻用户个数Top-K的增加，两条曲线均呈下降 40 ■线性 趋势，GWCF曲线明显低于BSCF曲线。实验结 果表明：GWCF算法在降低评分预测误差方面是 ◆ ◆ 有效的。 2.0 1.5 0.33 -◆BSCF 0.32 1.0 152.02.53.03.54.04.55.0 -◆-GWCF worker节点数量/个 0.31 图11加速比示意图 030 Fig.11 Speed-up ratio graph 0.29 从图11中可以看出，随着节点个数的增加， 一◆◆ 0.28 加速比呈现上升趋势，100万数据集更逼近线性 加速比。实验结果表明，并行协同过滤推荐算法 051015202530354045 Top-K 在大规模数据集的情况下有较好的可扩展性。 图9图游走效果图 6结束语 Fig.9 Random Walk Effect Graph 图10中生成推荐列表时推荐项目数为10，随 本文针对协同过滤推荐算法中的数据稀疏性 着近邻用户个数Top-K的增加，两条曲线呈上升 问题和可扩展性问题进行研究。针对稀疏性问 趋势，GWCF准确率曲线趋势更明显并且高于BSCF 题，在基于用户的协同过滤推荐算法的基础上， 曲线。实验结果表明，在一般情况下，GWCF比 首先为传统的皮尔逊相关相似度引人交占比系数 BSCF拥有更高的推荐准确率。 来计算用户的直接相似度，其次提出一种基于图 0.200 游走方法来计算用户间接相似度，并重建相似度 ·-GWCF 0.175 -BSCF 矩阵和进行推荐。针对可扩展性问题，在Spark 0.150 平台上实现本文方法的并行化。通过在Movielens 鲸0.125 --◆“- 美o100 数据集和IPTV数据集上进行实验，先后验证了 0.075 加入交占比系数和基于图游走的方法在提高推荐 0.050 准确度上的有效性，以及本文方法的可扩展性。 0.025 实验结果表明，本文的方法在提高推荐准确度上 0.00 0510 1520 253035 是有效的，并且在大规模数据上拥有较好的可扩 Top-K 展性。 图10准确率对比图 Fig.10 Accuracy comparison chart 参考文献： 5.3基于图游走的并行协同过滤推荐算法可扩 [1]黄立威，江碧涛，吕守业，等基于深度学习的推荐系统研 展性实验 究综述J计算机学报，2018.41(7)：1619-1647. HUANG Liwei,LIU Yanbo,LI Deyi.Deep learning based 为了验证基于图游走的并行协同过滤推荐算 recommender systems[J].Chinese journal of computers 法的可扩展性，使用Movielens-lM和Movielens- 2018.41(07:1619-1647. I00k数据集在Spark平台进行实验。其中IM数 [2]孙光福，吴乐，刘淇，等.基于时序行为的协同过滤推荐 算法.软件学报，2013,24(11)：2721-2733 据集包含6040个用户和3952个项目，共计 SUN Guangfu,WU Le,LIU Qi,et al.Recommendations 100万条评分记录；100k数据集包含943用户， based on collaborative filtering by exploiting sequential be- 1682项目，共10万条评分记录。实验在Spark集 haviors[J].Journal of software,2013,24(11):2721-2733. [3]许智宏，蒋新字，董永峰，等.一种基于Spark的改进协同 群上实现，集群环境包括6个节点，一个Mas- 过滤算法研究[).计算机应用与软件，2017,34(5)： ter节点，5个worker节点，每个节点的配置相同， 247-254.278. 且处在同一个局域网内，操作系统为CentOs6.5, XU Zhihong,JIANG Xinyu,DONG Yongfeng,et al.An CPU为E5-2620v4,核心频率2.10GHz,节点内存 improved collaborative filtering algorithm based on Spark[J].Computer applications and software,2017,34(5): 32GB。加速比结果如图11。 247-254.278
法 (GW_CF) 和基于用户的协同过滤推荐算法 (BSCF) 进行对比实验。从图 9 中可以看出，随着 近邻用户个数 Top-K 的增加，两条曲线均呈下降 趋势，GW_CF 曲线明显低于 BSCF 曲线。实验结 果表明：GW_CF 算法在降低评分预测误差方面是 有效的。 0.32 0.33 0.31 0.30 0.29 0.28 MAE 0 5 10 15 20 25 30 35 40 45 Top−K BSCF GW_CF 图 9 图游走效果图 Fig. 9 Random Walk Effect Graph 图 10 中生成推荐列表时推荐项目数为 10，随 着近邻用户个数 Top-K 的增加，两条曲线呈上升 趋势，GW_CF 准确率曲线趋势更明显并且高于 BSCF 曲线。实验结果表明，在一般情况下，GW_CF 比 BSCF 拥有更高的推荐准确率。 0.200 0.175 0.150 0.125 0.100 0.075 0.050 0.025 0.000 准确率 0 10 15 20 25 30 35 5 Top−K GW_CF BSCF 图 10 准确率对比图 Fig. 10 Accuracy comparison chart 5.3 基于图游走的并行协同过滤推荐算法可扩 展性实验 为了验证基于图游走的并行协同过滤推荐算 法的可扩展性，使用 Movielens-1M 和 Movielens- 100k 数据集在 Spark 平台进行实验。其中 1M 数 据集包含 6 040 个用户和 3 952 个项目，共计 100 万条评分记录；100k 数据集包含 943 用户， 1 682 项目，共 10 万条评分记录。实验在 Spark 集 群上实现，集群环境包括 6 个节点，一个 Master 节点，5 个 worker 节点，每个节点的配置相同， 且处在同一个局域网内，操作系统为 CentOs6.5， CPU 为 E5-2620 v4，核心频率 2.10 GHz，节点内存 32 GB。加速比结果如图 11。 5.0 4.5 4.0 3.0 2.0 3.5 2.5 1.5 加速比 1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0 worker 节点数量/个 1 000 000 100 000 线性 图 11 加速比示意图 Fig. 11 Speed-up ratio graph 从图 11 中可以看出，随着节点个数的增加， 加速比呈现上升趋势，100 万数据集更逼近线性 加速比。实验结果表明，并行协同过滤推荐算法 在大规模数据集的情况下有较好的可扩展性。 6 结束语 本文针对协同过滤推荐算法中的数据稀疏性 问题和可扩展性问题进行研究。针对稀疏性问 题，在基于用户的协同过滤推荐算法的基础上， 首先为传统的皮尔逊相关相似度引入交占比系数 来计算用户的直接相似度，其次提出一种基于图 游走方法来计算用户间接相似度，并重建相似度 矩阵和进行推荐。针对可扩展性问题，在 Spark 平台上实现本文方法的并行化。通过在 Movielens 数据集和 IPTV 数据集上进行实验，先后验证了 加入交占比系数和基于图游走的方法在提高推荐 准确度上的有效性，以及本文方法的可扩展性。 实验结果表明，本文的方法在提高推荐准确度上 是有效的，并且在大规模数据上拥有较好的可扩 展性。 参考文献： 黄立威,江碧涛,吕守业,等.基于深度学习的推荐系统研 究综述 [J].计算机学报,2018,41(7):1619-1647. HUANG Liwei, LIU Yanbo, LI Deyi. Deep learning based recommender systems[J].Chinese journal of computers. 2018,41(07):1619-1647. [1] 孙光福, 吴乐, 刘淇, 等. 基于时序行为的协同过滤推荐 算法 [J]. 软件学报, 2013, 24(11): 2721–2733. SUN Guangfu, WU Le, LIU Qi, et al. Recommendations based on collaborative filtering by exploiting sequential behaviors[J]. Journal of software, 2013, 24(11): 2721–2733. [2] 许智宏, 蒋新宇, 董永峰, 等. 一种基于 Spark 的改进协同 过滤算法研究 [J]. 计算机应用与软件, 2017, 34(5): 247–254, 278. XU Zhihong, JIANG Xinyu, DONG Yongfeng, et al. An improved collaborative filtering algorithm based on Spark[J]. Computer applications and software, 2017, 34(5): 247–254, 278. [3] ·750· 智 能 系 统 学 报 第 14 卷
第4期 顾军华，等：基于图游走的并行协同过滤推荐算法 ·751· [4]SUN Baoshan,DONG Lingyu.Dynamic model adaptive to 2018,35(8):23042307 user interest drift based on cluster and nearest neighbors[J]. [16]王鹤，邬春学.基于图结构和项目类型的协同过滤推荐 IEEE access.2017,5:1682-1691 算法[J.数据通信，2016(5)：44-47. [5]彭宏伟，靳远远，吕晓强，等.一种基于矩阵分解的上下 WANG He,WU Chunxue.Collaborative filtering recom- 文感知POI推荐算法J/OL1.计算机学报：(2018-05 menddation algorithm based on graph structure and item 14)[2018-05-301.http://kns.cnki.net/kcms/detail/11.1826.TP. type[J].Data communications,2016(5):44-47. 20180512.2150.008.html. [17]宫秀文，张佩云.基于PageRank的社交网络影响最大 PENG Hongwei,JIN Yuanyuan,LU Xiaogiang,et al.Con- 化传播模型与算法研究几.计算机科学，2013,40(S1): text-aware POI recommendation based on matrix factoriza- 136-140. tion[J].Chinese Journal of Computers:(2018-05-14)[2018- GONG Xiuwen,ZHANG Peiyun.Research on propaga- 05-301.http://kns.cnki.net/kcms/detail/11.1826.TP.20180512. tion model and algorithm for influence maximization in 2150.008.html social network based on pageRank[J].Computer science, [6]WU Jibing,YU Lianfei,ZHANG Qun,et al.Multityped 2013,40(S1136-140 community discovery in time-evolving heterogeneous in- [18]HU Yan,PENG Qimin,HU Xiaohui,et al.Time aware formation networks based on tensor decomposition[J]. Complexity,2018,2018:9653404. and data sparsity tolerant web service recommendation based on improved collaborative filtering[J].IEEE trans- [7]MA Wenping,WU Yue,GONG Maoguo,et al.Local probabilistic matrix factorization for personal recommend- actions on services computing,2015,8(5):782-794. [19]黄筱云，董国海，常佳夫，等.Level set函数快速步进重 ation[C]//Proceedings of the 13th International Conference 构并行算法的改进[J].哈尔滨工程大学学报，2017 on Computational Intelligence and Security.Hong Kong, 38(6:836-842 China.2017:97-101. [8]杨志文，刘波.基于Hadoop平台协同过滤推荐算法仞. HUANG Xiaoyun,DONG Guohuai,CHANG Jiafu,et al. 计算机系统应用，2013,22(7)：108-112 Improvement of parallel fast marching method for recon- YANG Zhiwen,LIU Bo.Hadoop-based collaborative fil- struction of level set function[J].Journal of Harbin Engin- tering recommendation algorithm[J].Computer systems eering University,2017,38(6):836-842. and applications,2013,22(7):108-112. [20]LIU Tiantian,FANG Zhiyi,ZHAO Chen,et al.Paralleliz- [9]LU F.HONG L.CHANGFENG L.The improvement and ation of a series of extreme learning machine algorithms implementation of distributed item-based collaborative fil- based on spark[C]//Proceedings of the IEEE/ACIS 15th tering algorithm on Hadoop[C]//Proceedings of the 34th International Conference on Computer and Information Chinese Control Conference.Hangzhou,China,2015: Science.Okayama,Japan,2016. 9078-9083 [21]顾军华，官磊，张建，等.基于Hadoop的PTV隐式评分 [10]KUPISZ B,UNOLD O.Collaborative filtering recom- 模型].计算机应用，2017,37(11)：3188-3193 mendation algorithm based on Hadoop and Spark[C]// GU Junhua,GUAN Lei,ZHANG Jian,et al.IPTV impli- Proceedings of 2015 IEEE International Conference on cit scoring model based on Hadoop[J].Journal of com Industrial Technology.Seville,Spain,2015:1510-1514. puter applications,2017,37(11):3188-3193. [11]冷亚军，陆青，梁昌勇.协同过滤推荐技术综述).模式 识别与人工智能，2014,27(8)：720-734. 作者简介： LENG Yajun,LU Qing,LIANG Changyong.Survey of 顾军华，男，1966年生，教授，博 recommendation based on collaborative filtering[J].Pat- 士生导师，CC℉会员，中国离散数学学 tern recognition and artificial intelligence,2014,27(8): 会常务理事，河北省计算机学会副理 720-734. 事长。主要研究方向为数据挖掘、智 [12]范波，程久军.用户间多相似度协同过滤推荐算法) 能信息处理等。完成科研项目30余 计算机科学，2012,391少：23-26 项，发表学术论文50余篇。 FAN Bo.CHENG Jiujun.Collaborative filtering recom- mendation algorithm based on user's multi-similarity[J]. Computer Science,2012,39(1):23-26. [13]徐堃，朱小柯，荆晓远.基于改进协同过滤的个性化 谢志坚，男，1995年生，硕士研究 web服务推荐方法研究].计算机技术与发展，2018， 生，主要研究方向为数据挖掘与机器 28(1:64-68. 学习。 XU Kun,ZHU Xiaoke,JING Xiaoyuan.Research on per- sonalized web service recommendation based on im- proved collaborative filtering[J].Computer technology and development,2018,28(1):64-68. [14]WU Xiaokun,CHENG Bo,CHEN Junliang.Collaborat- ive filtering service recommendation based on a novel 武君艳，女，1994年生，硕士研究 similarity computation method[J].IEEE transactions on 生，主要研究方向为数据挖掘与计算 services computing,2017,10(3):352-365. 机仿真。 [15]肖春景，夏克文，乔永卫.基于时序逆影响的随机游走 推荐算法).计算机应用研究，2018,35(8)2304-2307. XIAO Chunjing,XIA Kewen,QIAO Yongwei.Temporal inverse influence based recommendation method by us- ing random walk[J].Application research of computers
SUN Baoshan, DONG Lingyu. Dynamic model adaptive to user interest drift based on cluster and nearest neighbors[J]. IEEE access, 2017, 5: 1682–1691. [4] 彭宏伟, 靳远远, 吕晓强, 等. 一种基于矩阵分解的上下 文感知 POI 推荐算法 [J/OL]. 计算机学报: (2018-05- 14)[2018-05-30]. http://kns.cnki.net/kcms/detail/11.1826.TP. 20180512.2150.008.html. PENG Hongwei, JIN Yuanyuan, LÜ Xiaoqiang, et al. Context-aware POI recommendation based on matrix factorization[J]. Chinese Journal of Computers: (2018-05-14)[2018- 05-30]. http://kns.cnki.net/kcms/detail/11.1826.TP.20180512. 2150.008.html. [5] WU Jibing, YU Lianfei, ZHANG Qun, et al. Multityped community discovery in time-evolving heterogeneous information networks based on tensor decomposition[J]. Complexity, 2018, 2018: 9653404. [6] MA Wenping, WU Yue, GONG Maoguo, et al. Local probabilistic matrix factorization for personal recommendation[C]//Proceedings of the 13th International Conference on Computational Intelligence and Security. Hong Kong, China, 2017: 97–101. [7] 杨志文, 刘波. 基于 Hadoop 平台协同过滤推荐算法 [J]. 计算机系统应用, 2013, 22(7): 108–112. YANG Zhiwen, LIU Bo. Hadoop-based collaborative filtering recommendation algorithm[J]. Computer systems and applications, 2013, 22(7): 108–112. [8] LU F, HONG L, CHANGFENG L. The improvement and implementation of distributed item-based collaborative filtering algorithm on Hadoop[C]//Proceedings of the 34th Chinese Control Conference. Hangzhou, China, 2015: 9078–9083. [9] KUPISZ B, UNOLD O. Collaborative filtering recommendation algorithm based on Hadoop and Spark[C]// Proceedings of 2015 IEEE International Conference on Industrial Technology. Seville, Spain, 2015: 1510–1514. [10] 冷亚军, 陆青, 梁昌勇. 协同过滤推荐技术综述 [J]. 模式 识别与人工智能, 2014, 27(8): 720–734. LENG Yajun, LU Qing, LIANG Changyong. Survey of recommendation based on collaborative filtering[J]. Pattern recognition and artificial intelligence, 2014, 27(8): 720–734. [11] 范波, 程久军. 用户间多相似度协同过滤推荐算法 [J]. 计算机科学, 2012, 39(1): 23–26. FAN Bo, CHENG Jiujun. Collaborative filtering recommendation algorithm based on user’s multi-similarity[J]. Computer Science, 2012, 39(1): 23–26. [12] 徐堃, 朱小柯, 荆晓远. 基于改进协同过滤的个性化 web 服务推荐方法研究 [J]. 计算机技术与发展, 2018, 28(1): 64–68. XU Kun, ZHU Xiaoke, JING Xiaoyuan. Research on personalized web service recommendation based on improved collaborative filtering[J]. Computer technology and development, 2018, 28(1): 64–68. [13] WU Xiaokun, CHENG Bo, CHEN Junliang. Collaborative filtering service recommendation based on a novel similarity computation method[J]. IEEE transactions on services computing, 2017, 10(3): 352–365. [14] 肖春景, 夏克文, 乔永卫. 基于时序逆影响的随机游走 推荐算法 [J]. 计算机应用研究, 2018, 35(8): 2304–2307. XIAO Chunjing, XIA Kewen, QIAO Yongwei. Temporal inverse influence based recommendation method by using random walk[J]. Application research of computers, [15] 2018, 35(8): 2304–2307. 王鹤, 邬春学. 基于图结构和项目类型的协同过滤推荐 算法 [J]. 数据通信, 2016(5): 44–47. WANG He, WU Chunxue. Collaborative filtering recommenddation algorithm based on graph structure and item type[J]. Data communications, 2016(5): 44–47. [16] 宫秀文, 张佩云. 基于 PageRank 的社交网络影响最大 化传播模型与算法研究 [J]. 计算机科学, 2013, 40(S1): 136–140. GONG Xiuwen, ZHANG Peiyun. Research on propagation model and algorithm for influence maximization in social network based on pageRank[J]. Computer science, 2013, 40(S1): 136–140. [17] HU Yan, PENG Qimin, HU Xiaohui, et al. Time aware and data sparsity tolerant web service recommendation based on improved collaborative filtering[J]. IEEE transactions on services computing, 2015, 8(5): 782–794. [18] 黄筱云, 董国海, 常佳夫, 等. Level set 函数快速步进重 构并行算法的改进 [J]. 哈尔滨工程大学学报, 2017, 38(6): 836–842. HUANG Xiaoyun, DONG Guohuai, CHANG Jiafu, et al. Improvement of parallel fast marching method for reconstruction of level set function[J]. Journal of Harbin Engineering University, 2017, 38(6): 836–842. [19] LIU Tiantian, FANG Zhiyi, ZHAO Chen, et al. Parallelization of a series of extreme learning machine algorithms based on spark[C]//Proceedings of the IEEE/ACIS 15th International Conference on Computer and Information Science. Okayama, Japan, 2016. [20] 顾军华, 官磊, 张建, 等. 基于 Hadoop 的 IPTV 隐式评分 模型 [J]. 计算机应用, 2017, 37(11): 3188–3193. GU Junhua, GUAN Lei, ZHANG Jian, et al. IPTV implicit scoring model based on Hadoop[J]. Journal of computer applications, 2017, 37(11): 3188–3193. [21] 作者简介： 顾军华，男，1966 年生，教授，博 士生导师，CCF 会员，中国离散数学学 会常务理事，河北省计算机学会副理 事长。主要研究方向为数据挖掘、智 能信息处理等。完成科研项目 30 余 项，发表学术论文 50 余篇。 谢志坚，男，1995 年生，硕士研究 生，主要研究方向为数据挖掘与机器 学习。 武君艳，女，1994 年生，硕士研究 生，主要研究方向为数据挖掘与计算 机仿真。 第 4 期 顾军华，等：基于图游走的并行协同过滤推荐算法 ·751·