基于用户的协同过滤推荐算法MapReduce并行化实现

李冲

摘要：基于用户的协同过滤推荐算法是应用范围广且应用效果较好的推荐算法之一。传统单机模式下运行的基于用户的协同过滤推荐算法在面对海量数据时存在严重的性能瓶颈问题，很难满足实际计算需求，而基于MapReduce的并行计算框架为解决该问题提供了新思路。MapReduce是Hadoop开源框架的核心计算编程模型， MapReduce的設计目标是方便编程人员在不熟悉分布式并行编程的情况下，可将自己的程序运行在分布式系统上。根据基于用户的协同过滤推荐算法特点，提出MapReduce并行化实现方法。实验结果表明，在MapReduce并行计算框架下实现的基于用户的协同过滤推荐算法在算法性能及稳定性方面都取得了理想效果。

关键词：MapReduce；Hadoop；分布式计算；推荐算法

DOIDOI：10.11907/rjdk.181108

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2018）010-0076-05

英文摘要Abstract：The recommended algorithm based on collaborative filtering of users is a recommended algorithm which has a wide range of applications and is effective in practical applications. However， the traditional recommendation algorithm based on user-based collaborative filtering running in stand-alone mode encounters a serious performance bottleneck in the case of massive data and is difficult to meet the actual computing requirements. The MapReduce-based parallel computing framework provides a new solution to this problem. MapReduce is a kernel computing programming model of Hadoop open source framework. MapReduce is designed to facilitate programmers to run their own programs on distributed systems without being familiar with distributed parallel programming. Based on the research of the characteristics of user-based collaborative filtering recommendation algorithm， this paper proposes a method based on MapReduce parallel computing framework. The experimental results show that the proposed user-based collaborative filtering algorithm based on MapReduce parallel computing framework achieves the desired performance in terms of performance and stability of the algorithm.

英文关键词Key Words：MapReduce；Hadoop；distributed computing；recommendation algorithm

0 引言

如今人们生活在一个信息超载的时代，生活各领域充斥着大量信息资源，如何从海量信息资源中快速高效地获取有用信息一直是研究人员的研究热点[1]。近年来各种推荐算法的出现为解决信息超载问题提供了解决方案，其中基于用户的协同过滤推荐算法是众多推荐算法中比较经典，且应用范围较广、实际应用效果较好的一个推荐算法[2]。算法基本思想是通过判断两个用户是否具有相似偏好，如果两人偏好相近，则可以将另一个用户评分较高的物品推荐给目标用户。但是随着数据量的爆炸式增长，传统基于单机模式运行的推荐算法在处理海量数据时存在严重的性能瓶颈问题，很难满足实际计算需求。文献[3]提出在Hadoop上实现基于用户的CF算法，解决了CF的扩展性问题，但其采用的利用Hadoop实现的推荐算法只是在过程中的个别阶段实现了并行化，算法性能仍有很多不足。本文在推荐算法实现过程中，通过将整个任务切分成6个任务串联的方式，对整个推荐过程进行并行化实现。近年来基于Hadoop的分布式计算开源框架的出现使各种推荐算法实现并行化计算成为可能，各种推荐算法可采用基于MapReduce的分布式计算框架实现算法并行化，从而为解决推荐算法面对海量数据时存在的性能瓶颈问题提供了新的思路。近年来，大量研究人员采用基于MapReduce的分布式计算框架对传统算法进行并行化实现并取得了良好效果，例如文献[4]针对FCM聚类集成算法随着数据量增加导致时间复杂度过高的问题，提出一种基于MapReduce框架的并行FCM聚类集成算法；文献[5]通过对传统单种群粒子群算法的分析，提出一种基于MapReduce模型的分布式粒子群算法，解决粒子群算法在求解大规模优化问题时求解效率与精度明显下降等问题；文献[6]针对传统单点串行的分类算法在面对新闻数据规模大、分类属性多时效率较低的问题，提出朴素贝叶斯分类算法在MapReduce下的并行实现方法。

Hadoop是一个开源云计算平台，用户可以充分利用集群的计算与存储能力在Hadoop平台上完成海量数据处理[7]。本文根据基于用户的协同过滤推荐算法特点以及MapReduce的运行机制对基于用户的协同过滤推荐算法进行并行化实现，并给出了具体步骤描述。最后通过实验对比并行化前后算法性能，表明本文采用的在MapReduce下实现的并行化推薦算法有更好的性能。

1 基于用户的协同过滤推荐算法

基于用户的协同过滤推荐算法基本思想是根据用户对有过行为的物品评分刻画两个用户是否是具有相似偏好，如果两人偏好相近，则可以将另一个用户评分较高的物品推荐给目标用户[8]。

（1）map阶段：①系统根据设置的块大小，对全部数据进行分块，每块数据被一个map任务加以执行，map端对数据逐条进行处理，并将处理结果以键值对形式存储在一个环形缓冲区中。当环形缓冲区内的数据量达到一个阈值（默认为缓冲区大小的80%），此时环形缓冲区会将数据写出到本地临时文件中[11]；②在写出数据之前，系统会根据设置的分区策略进行分区，对属于相同分区的数据进行排序，并且如果有设置combiner，则会将结果先combiner之后再放到相同的临时文件中；③map端将属于同一分区的临时文件进行合并，当端处理完所有数据并合并完成所有临时文件时，map端会通知相应的reduce端收集数据[12]。

（2）reduce阶段：①reduce端会从各个map端将属于该reduce的数据拉取过来；②reduce端将拉取过来的所有数据进行合并，并且根据设置的分组策略对key值进行排序，此时reduce端会将具有相等key值的数据放在一个分区；③reduce端根据设置的二次排序策略对数据进行二次排序，并将最终处理结果以键值对形式输出[13]。

3 基于用户的协同过滤推荐算法并行化实现

基于用户的协同过滤推荐算法是指根据用户与物品行为信息得到目标用户的近邻用户，根据近邻用户对物品行为信息为目标用户作推荐。具体步骤如下：①根据用户对物品的行为信息计算用户之间相似度；②根据相似度高低得到目标用户的近邻用户；③根据近邻用户对物品的行为信息，得到目标用户的候选推荐列表；④从候选推荐列表中去除用户已经有过行为的物品。

基于用户的协同过滤推荐算法采用6个并行化任务加以实现，整体流程如图2所示。

从图2可以看出，任务之间通过上一个任务的输入作为下一个任务输出的形式进行连接。从最初的将用户与物品行为信息作为输入，经过6个任务的处理，最后输出为每个用户进行推荐的推荐列表。其中每个任务具体流程如下：

任务1：将用户与物品行为信息作为任务输入，得到每个用户产生行为的物品数量，并将物品Id（itemId）作为key，用户Id与物品数量组合（userId：itemSize）作为value。

map阶段：map端将用户与物品行为信息作为输入，map端对数据进行分割，将用户Id作为key值，物品Id作为value输出。

reduce阶段：对map阶段发送的数据进行处理，并根据key值进行聚合，计算一个用户发生行为的物品数量itenSize，并将物品（itemId）作为key，用户Id与物品数量组合（userId：itemSize）作为value。

任务2：将任务1的输出结果作为输入，得到对同一物品发生行为的所有用户以及两两组合结果。

map阶段：将数据分割并输出。

reduce阶段：对map端发送的数据进行处理，并根据key值进行分组，计算对同一物品发生行为的所有用户以及两两组合结果。

任务3：将任务2的输出作为任务的输入，计算两两用户之间的相似度。

map阶段：将数据的value作为输出的key，NullWritable作为输出的value。

reduce阶段：根据map端发送的数据，与key值（两两用户之间的组合）进行聚合，计算用户之间相似度。

任务4：将任务3的输出作为任务的输出，计算用户的k近邻用户。

（1）map阶段：将数据分割后直接输出。

（2）自定义分区策略：为了计算用户u1的k近邻用户，需要将用户u1与其他具有一定相似度的用户进行相似度对比，并对两两用户组合<（u1：u2），similarity>中的第一个用户u1进行分区，以保证用户u1与其他具有一定相似度的用户能够被同一个reduce处理。

（3）自定义分组策略：在步骤（2）中保证了用户u1与其他具有一定相似度的用户能够被同一个reduce处理，要将用户u1与其他用户的相似度进行对比，需要将这些用户放在同一个迭代器中，所以还需要根据<（u1：u2），similarity>中的第一个用户u1定义分组策略。

（4）reduce阶段：根据自定义的分区与分组策略在同一个迭代器中计算目标用户的k近邻用户。

任务5：将输入分为两部分，一部分是任务4的输出，另一部分是用户与物品的行为信息，最终计算目标用户的候选推荐列表。

map1阶段：将任务4的输出作为输入，并将近邻用户作为key值、目标用户作为value值进行输出。

map2阶段：将用户与物品的行为信息作为输入，并将用户作为key值、物品作为value值输出。

reduce阶段：根据map1阶段与map2阶段的输出，利用key值进行聚合，并为目标用户作推荐。

任务6：将输入分为两部分，一部分是任务5的输出，另一部分是用户与物品行为信息，从任务5产生的候选推荐列表中去除用户已经产生行为的物品。

map1阶段：将任务5的输出作为输入，并将用户Id作为key值、候选推荐列表作为value值进行输出。

map2阶段：将用户与物品行为信息作为输入，并将用户作为key值，物品作为value值输出。

reduce阶段：根据map1与map2阶段的输出，利用key值进行聚合，从用户候选推荐列表中去除用户已经产生过行为的物品。

4 實验及结果分析

通过实验对MapReduce并行计算框架下实现的基于用户的协同过滤推荐算法进行性能评估。

4.1 实验环境

该实验在北京邮电大学实验室集群上运行，集群由10台机器组成，其中一台机器为主节点，其它机器均为从节点，网络采用万兆网络，操作系统为centos，Hadoop版本为2.6.4，JDK为1.7.0_25。硬件配置为每台机器CPU主频3.3GHz，内存8GB，硬盘1TB。

4.2 实验数据

本次实验以北京邮电大学图书馆的读者借阅信息作为实验数据，数据量包括2013年1月～2017年6月的读者借阅记录。

4.3 结果分析

实验从数据量以及节点数两个维度衡量并行化后的推荐算法性能。

从图3中可以看到，单机运行的协同过滤推荐算法在处理2013年全年数据时需要耗时653s，而采用并行化后的推荐算法随着节点数增加，运行时间大幅减少。

从图4中可以看到，当实验数据增加1倍时，基于单机模型下运行时间从原来的653s增加到了1 544s，增幅超过2倍，基于并行计算模型下运行的推荐算法则在运行时间上增幅较小。

从实验结果可以看出，并行模式下运行的基于用户的协同过滤推荐算法相比于单机模式，在性能上具有很大优势。

5 结语

本文针对单机模型下基于用户的协同过滤推荐算法面对海量数据时存在的严重性能瓶颈问题，提出MapReduce并行计算框架下的基于用户的协同过滤推荐算法。实验结果表明，并行化后的基于用户的协同过滤推荐算法在处理海量数据时，相比于传统单机模式在性能上有着巨大优势。

参考文献：

[1] 张宇，程久军.基于MapReduce的矩阵分解推荐算法研究[J].计算机科学， 2013（1）：19-21，36.

[2] 杨博，赵鹏飞.推荐算法综述[J].山西大学学报：自然科学版，2011，34（3）：337-350.

[3] 王斯锋，祝永志，刘文超.运行在Hadoop上的基于用户的协同过滤推荐算法研究[J].电子技术，2017，46（11）：73-75.

[4] 马自堂，苟杰.基于MapReduce的FCM聚类集成算法[J].计算机应用研究， 2016（12）： 3554-3558.

[5] 范德斌，邓长寿，袁斯昊，等.基于MapReduce模型的分布式粒子群算法 [J]. 山东大学学报：工学版，2016（6）：23-30，61.

[6] 徐保鑫，怀丽波，崔荣一.基于MapReduce的朴素贝叶斯算法在新闻分类中的应用[J]. 延边大学学报：自然科学版， 2017（1）： 55-59.

[7] 符彩珍，周国军，莫丽清，等.基于Hadoop的排序算法并行化改进[J].软件导刊， 2016（4）： 68-71.

[8] 王兴茂.基于用户的协同过滤推荐算法研究[D].郑州：解放军信息工程大学，2015.

[9] 刘辉.基于用户的协同过滤推荐算法的改进研究[D].泉州：华侨大学，2016.

[10] 李建江，崔健，王聃，等.MapReduce并行编程模型研究综述[J].电子学报，2011，39（11）：2635-2642.

[11] 宋杰，徐澍，郭朝鹏， 等.一种优化MapReduce系统能耗的任务分发算法[J].计算机学报，2016，39（2）：323-338.

[12] 郝树魁.Hadoop HDFS和MapReduce架构浅析[J].邮电设计技术，2012（7）：37-42.

[13] 王晟，赵壁芳.云计算中MapReduce技术研究[J].通信技术，2011，44（12）：159-161.

（责任编辑：黄 健）