基于Hadoop的推荐算法研究

孙亭　贾元江　张永胜　侯秀艳　于鑫

摘 要：本文通过对云计算和推荐系统的研究，构建了一种基于Hadoop平台的混合推荐算法。文中介绍了改进的混合推进算法，并结合Hadoop平台的MapReduce编程模型来实现。通过实验验证，该算法能精确的预测用户的偏好，向用户推荐感兴趣的信息。其次，Hadoop能满足对大量数据处理的要求，结合改进的混合推荐算法，能够大大提高推荐系统的性能。

关键词：云计算；推荐算法；混合推荐算法

中图分类号：TP301.6 文献标识码：A

Abstract：In this paper，through studying the recommendation system and cloud computation，we established the hybrid recommendation algorithm based on Hadoop.In this paper，we introduces a improved hybrid recommended algorithm and combine MapReduce programming which is used on Hadoop platform.Through practices，the improved algorithm can accurately acquiring user preferences， provide the user with recommendation when the user browse the web page.Finally Hadoop can meet the demand of massive data processing，and achieve a highly performance system by making use of the data reprocessing method.

Keywords：cloud computing；recommended algorithm；hybrid algorithm

1 引言（Introduction）

随着互联网的迅速发展和Web2.0技术的普及，网络中的信息量急剧上升，从海量的数据中快速找到用户感兴趣或对其有价值的信息，无论对于消费者还是商家来说都是十分重要的，而推荐系统就是一个非常有效的工具。作为一项广泛应用的机器学习技术，推荐系统通过了解用户的历史行为推断用户的喜好，向用户推荐其感兴趣的书、电影、文章等未知项目。如今很多网站都提供了推荐服务，例如：新浪微博、优酷、Amazon、Youtube等。

与搜索引擎不同，推荐系统不需要用户提供明确的搜索要求，而是通过对用户历史行为的记录分析去挖掘其兴趣，从而主动的向用户推荐符合他们兴趣和要求的信息[1]。因此，推荐系统需要大量的数据为前提，云计算可以很好地解决大容量数据存储的问题。

Hadoop平台是Apache分布式计算编程系统下的一个开放资源，是目前使用最广泛的云计算平台[2]，它主要包含两大方面：分布式文件系统HDFS和分布式计算模型MapReduce[3]。由于Hadoop平台具有成本低、效率高等优势，基于Hadoop平台的应用已经在互联网领域迅速发展[4]。本文设计并实现了一种基于MapReduce编程模型的混合推荐算法并将其应用到推荐系统中。

2 系统架构设计（Architecture design of system）

2.1 Hadoop平台

Hadoop分布式系统的基础框架由HDFS、MapReduce和HBase组成。其中，HDFS是Hadoop软件框架中的分布式文件系统，MapReduce是用于大规模数据处理的分布式计算模型，HBase是一个高可靠性、高性能、面向列、可伸缩的分布式存储系统[5]。Hadoop分布式系统的主要结构如图1所示。

如图1所示，DataNode节点主要负责对Hadoop分布式文件系统的数据进行存储，NameNode节点主要负责管理Hadoop文件系统的命名空间，并控制外部用户对文件系统的访问[6]。总之，Hadoop分布式文件系统是一个真实可靠的分布式文件存储系统，用户可以在其中存储他们的信息数据。

2.2 推荐系统的体系结构

推荐系统主要包括三个部分：用户、推荐算法和推荐对象。推荐算法是推荐系统的核心。随着互联网的发展，推荐系统已经被应用到很多领域，它具有比搜索引擎更高的用户体验，推荐系统结合了搜索引擎的优势发现用户的历史搜索并对结果进行排序，根据用户的历史行为收集用户的偏好数据并向用户推荐其感兴趣的内容。一般推荐系统的架构如图2所示。

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

基于用户的协同过滤推荐算法的基本原理是通过收集用户的历史行为，根据用户之间的相似性进行推荐，具体过程[8]详见表1。

2.4 基于项目的推荐算法

基于项目的推荐是从项目之间的相似性中得出的，它与基于用户的推荐类似，具体过程[9]详见表2。

基于项目的推荐算法与基于用户的推荐算法类似，但不完全相同。两者之间最显著的差异在于：基于项目的推荐算法的时间复杂度主要取决于项目的数量，而基于用户的推荐算法的时间复杂度主要取决于用户的数量[10]。

3 混合推荐算法的设计（Design of hybrid recommendation algorithm）

通过对基于用户的协同过滤推荐算法和基于项目的推荐算法的比较发现，单纯使用一种推荐方法很难满足大数据量和高准确度的要求。混合推荐算法组合这两种不同的推荐算法并搭载hadoop平台。

如图3所示，混合推荐算法的基本思想是将基于用户的协同过滤推荐算法和基于项目的推荐算法相结合使用。首先，采用基于项目推荐算法来预测用户对目标项目的评分。然后根据预测填补基于用户的协同过滤中的稀疏矩阵，主要是填补矩阵中缺失的数据。这样就有效地解决了协同过滤算法中的数据稀疏问题。

本文中混合推荐算法是结合MapReduce编程模型实现的，MapReduce被用于分布式计算，输入和输出采用键—值对的形式。我们使用三组MapReduce计算最终得分以此得到推荐项目名单，详见表3。

该算法共进行了三组MapReduce，每一个过程是MapReduce并行执行的一个周期。与传统的协同过滤算法相比，虽然形式大致相同，但加入的混合推荐技术显著提高了推荐的准确性，并能在大型集群环境中运行。

4 实验和评估（Experimentation and evaluation）

MAE绝对偏差公式表示实际值与预测值之间平均绝对偏差。通过MAE可以在评估推荐算法的质量。

从图6中可以看出，混合推荐算法的MAE值基本稳定在0.63，与其两种推荐算法的MAE值相比较，混合推荐算法可以有效地提高推荐系统的推荐质量。

图7显示的是随着输入数据的增加算法响应时间的变化情况。在实验过程中，输入用户数量从100k到1M被划分为10等份，可见，发现算法的执行时间随着用户数量的增加缓慢增加，并且该算法的效率随着数据规模的增大而提高。上文提到的Hadoop云平台处理海量数据时优势明显。为了确保实验准确顺利完成，Hadoop能够动态地处理数据冗余及存储节点，以此提高数据的处理速度和计算效率。当数据量较小时，算法消耗时间增长的幅度较快；随着数据规模的增大，算法消耗时间的增幅可逐渐被忽略。

图8显示的是，在伪分布式环境中，混合算法响应时间随机器数量增加的变化情况。可以看出，随着节点数量的增加，响应时间显著降低，达到两台机器后，响应时间继续降低，但降低的幅度减小。这是因为在伪分布式环境，利用单一的PC同时作为主节点和从属节点时存在计算量大的问题，而利用两台PC充分体现了分布式环境的优势，可以更好地解决这个问题。通过实验的曲线变化趋势我们可以得出，Hadoop的分布式计算环境显著提高了算法的性能。同时我们还可以发现，从一台PC到多台PC算法的性能变化更加明显，这都归功于分布式计算。因此Hadoop集群环境可以使分布式计算取得显著效果。

5 结论（Conclusion）

当今云计算已成为学术界关注的焦点，它是未来计算机研究的主要方向。随着云计算技术在各个领域的成熟发展，云计算平台的优势越来越明显，应用也越来越广泛。开源平台，如Hadoop，已成为现在的最理想的数据处理平台，学术界越来越重视对Hadoop的研究，Hadoop已成为云平台的典型代表。

通过对Hadoop架构特点的学习与研究，我们将开发一个基于Hadoop平台的推荐系统，充分利用Hadoop平台的优势，为用户提供良好的推荐服务。同时在推荐系统的设计中，我们设计了一种混合推荐算法，通过与其他不同推荐算法的比较，验证了基于MapReduce的混合推荐算法的优势。

但是，本文系统也有存在的缺陷，实验仅利用的集群环境中仅有三台PC，将来我们会考虑增加更多的机器。另外，实验数据直接保存在分布式文件系统HDFS，没有仔细考虑输入数据的形式，也没有在用户界面上做出太多的设计，所以用户体验度不高。如何解决这些问题，将是今后重点研究的问题。

参考文献（References）

[1] 项亮.推荐系统实践[M].北京：人民邮电出版社，2012.

[2] Jeffrey Dean，Sanjay Ghemawat.MapReduce：simplified data processing on large clusters[J].Commun.2008，51（1）：107-113.

[3] Sean Owen，Robin Anil，Ted Dunning，Ellen Friedman.Mahoutin Action.Manning Publications[M].2010，11：12-108.

[4] Badrul Sarwar，George Karypis，Joseph Konstan，et al.Analysis of Recommendation Algorithms for E-Commerce[C].Proceedings of EC'00，2000：158-167.

[5] 孙少陵，罗治国，徐萌.云计算及应用的研究与实现[J].电信工程技术与标准化，2009（11）：2-7.

[6] 吴吉义，傅建庆，平玲娣.一种对等的云存储系统研究[J].电子学报.2011，39（5）：1100-1107.

[7] R.D.Lawrence，G.S.Almasi，V.Kotlyar.Personalization ofSupermarket Product Recommendations[J].Data Mining and Knowledge Discovery.2001，5（1）：11-32.

[8] Wei-Po Lee，Chih-Hung Liu，Cheng-Che Lu.IntelligentAgent-Based Systems for Personalized Recommendations[J].Expert Systems with Applications.2002，22（2）：275-284.

[9] 邓爱林，朱扬勇，施伯乐.基于项目评分预测的协同过滤推荐算法[J].软件学报，2003，14（9）：1621-1628.

[10] 孙远帅，陈垚，刘向荣.基于项目层次相似性的推荐算法[J].山东大学学报，2014，44（3）：8-14.

作者简介：

孙 亭（1989-），女，硕士生.研究领域：软件工程.

贾元江（1968-），男，学士.高级工程师.研究领域：计算机应用.

张永胜（1962-），男，硕士，教授，硕士生导师.研究领域：数据库技术，网络信息安全.

侯秀艳（1990-），女，硕士生.研究领域：信息安全.

于 鑫（1994-），女，学士生.研究领域：通信工程.