基于Mahout分布式协同过滤推荐算法分析与实现.docx

    基于Mahout分布式协同过滤推荐算法分析与实现    曾志浩　张琼林　姚贝　孙琪摘要：随着信息技术和互联网的发展，在信息过载的时代，用户面对海量的信息，难以正确选择协同过滤推荐是个性化推荐中比较成熟的算法，但其稀疏性、冷启动、可扩展性问题仍然存在，尤其是不能应用于分布式推荐在Hadoop平台上，Mahout实现了分布式基于项目的协同过滤推荐算法，该算法能够有效解决传统算法的海量数据处理的效率问题和可扩展性问题实验结果表明，Mahout上基于项目的协同过滤推荐算法具有较好的计算高效性和可扩展性关键词：分布式协同过滤；Mahout；推荐系统：TP391 ：A1引言互联网和电子商务系统的兴起与发展，将人们带入了网络经济发展时代，同时网络中的信息量也在爆炸式地增长网络信息虽然给人们带来了更多的选择，但数量庞大及自身质量差异，越来越呈现一种信息过载的趋势，使得如何从这些海量信息中识别出真正有价值的信息变得越来越困难然而，推荐系统的出现改变了这一状况，尤其是个性化推荐服务技术的发展，成为解决信息过载问题最有效的工具，它能够收集和分析用户的信息，主动地推荐用户可能感兴趣的信息个性化推荐中的协同过滤推荐是比较成功的一种，它的概念是由Goldberg、Nicols、Oki以及Terry在1992年首次提出的，主要思想是，利用已有用户群过去的行为或意见预测当前用户最可能喜欢哪些东西或对哪些东西感兴趣。

不到两年，Grouplens系统展示了协同过滤方法既能跨网计算又能自动完成，该系统是基于用户评分的自动化协同过滤推荐系统，用于推荐电影和新闻麻省理工学院的Ringo系统针对音乐唱片和艺术家进行推荐虽然传统的协同过滤推荐算法在信息过滤方面呈现出了极大的优势，但随着信息量的增加，算法在不同领域的应用中出现了很多的问题，包括稀疏性问题、冷启动问题、可扩展性问题为了解决这些问题，文献基于动态规划思想，根据用户以及产品的相似性，自适应地选择预测目标的近邻对象作为推荐群，同时计算把握率较高的信任子群，提出了一种不确定近邻的协同过滤推荐算法，来对预测结果进行平衡的推荐，有效缓解了用户评分数据稀疏的情况文献在基于弱关系的微博类社交网络中，提出两阶段聚类的推荐算法GCCR，将图摘要方法和基于内容相似度的算法相结合，实现基于用户兴趣的主题推荐，有效缓解了矩阵稀疏性和冷启动问题文献采用传播的思想，提出了一种改进的基于内存的协同过滤推荐算法SPCF，该算法通过相似度传播，寻找到更多，更可靠的邻居，从用户和项目两方面信息考虑对用户进行推荐，缓解了数据稀疏性问题传统的协同过滤推荐算法虽然从一定程度上减少了矩阵稀疏和冷启动问题，但随着数据规模的不断扩大，可扩展性方面仍然表现的比较差，无法适应海量数据的处理，尤其是无法应用于分布式平台。

为此，国内外研究者进行了一系列的研究，这些研究大多是针对Hadoop平台和MapReduce并行编程模型，提出相关的分布式协同过滤算法文献提出了MapReduce范式可扩展的基于相似性的邻居算法，该算法中，针对分割数据设计出运行在并行处理平台上的基本比较对，并采用降低采用率的interaction-cut技术，处理“超级用户”的计算开销，有效地解决了用户或项目大规模增长的情况下扩展性和产生推荐的速度问题文献针对基于User-based的协同过滤算法的伸缩性问题，实现了基于Hadoop平台的User-based协同过滤算法，从而实现了算法的线性伸缩文献提出了Hadoop平台上扩展的Item-based协同过滤推荐算法，将单机上基于项目的协同过滤算法的三个最密集的计算分割为四个MapReduce阶段，有效地解决了文献提出的算法的扩展性和效率问题，但是MapReduce阶段的项目相似度计算要求两个项目在同一节点机器上，并且要求用户数量远大于项目数量，对于项目不断增长的情况下，会增加算法的计算量本文所要介绍的就是Mahout在Hadoop框架下基于项目的协同过滤推荐算法的实现，该算法是基于MapReduce并行编程模型，不仅有效地解决了在海量数据下算法处理的效率问题，而且解决了随着大量用户和项目的增加产生的可扩展性问题。

2协同过滤推荐算法协同过滤推荐算法主要包括基于用户和项目的推荐，其中基于项目的协同过滤推荐算法是目前业界应用最多的算法，所以本节内容以基于项目的协同过滤推荐算法为介绍对象，它主要分析用户的行为记录来计算项目之问的相似度推荐系统首先建立基于项目的数据模型，然后针对目标项目计算项目与项目之间的相似性，得到目标项目的若干最近邻，最后根据最近邻来预测用户对项目的评分，产生对应的推荐列表2.1相似性度量方法相似性度量方法是计算用户或项目问的相似性计算，本节内容是以项目之问的相似的研究为例，即基于项目的协同过滤算法基于项目i和项目j通常有3种相似性度量方法：标准的余弦相似性（式（1））、修正的余弦相似性（式（2））、相关相似性（式（3））其中，Ru，i表示用户u对项目i的评分，Ri和Rj分别表示项目i和项目j上所有用户的平均评分，Uij为项目i和项目j共同评分的用户集合，Ui和Uj分别为项目i和项目j评分的用户集合2.2产生推荐基于项目i的k个最近邻居，采用基于项目均值的加权平均值Pu，i，来预测用户u对其未评分或浏览项目的评分其中，kNNi表示项目i的k最近邻居集合，Ri，Ri分别表示项目i和j上所有用户打分的平均值。

3Mahout中分布式协同过滤推荐算法实现 3.1Hadoop和Mahout开源框架Hadoop是Apache软件基金会旗下的一个开源分布式计算平台Hadoop以分布式文件系统HDFS和MapReduce为核心，为用户提供了系统底层细节透明的分布式基础架构HDFS的高容错性、高伸缩性等优点允许用户将Hadoop部署在低廉的硬件上，形成分布式系统；MapReduce分布式编程模型允许用户在不了解分布式系统底层细节的情况下开发并行应用程序所以用户可以利用Hadoop轻松地组织计算机资源，从而搭建自己的分布式计算平台，并且可以充分利用集群的计算和存储能力，完成海量数据的处理Mahout是2008年作为Apache Lucene的子项目出现的，到2010年4月成为了Apache的顶级开源项目Apache Mahout的分布式计算的主要目标是建立可伸缩性的机器学习算法，通过Map Reduce模式运行在Hadoop平台上目前Apache Mahout项目包含聚类、分类、协同过滤推荐、频繁子项挖掘和频繁模式挖掘五个部分本文意在结合Hadoop平台和Mahout开源框架，对Mahout中分布式基于项目的协同过滤推荐算法进行分析并通过实验实现其算法。

3.2算法实现在Mahout中，实现的是基于项目的分布式协同过滤算法，该算法一共包含6个过程，这个6个过程使用了7个Map Reduce的Job任务来进行数据处理数据流程图如图1所示：1）用户矩阵用户矩阵的求解过程，就是针对图1的用户一项目评分矩阵的一个数据抽取过程，把同一个用户评价过的所有项目进行整合，针对每个用户，形成用户分向量itemid：pref，含义为项目ID：用户评价，然后形成每个用户的用户向量，最终形成用户矩阵Mahout中使用了一个Job任务来进行形成用户向量的数据处理，输出key/value对的格式是，其中的Long Writable和Vector Writable分别对应的是itemid和用户向量的格式2）项目矩阵项目矩阵的求解过程和用户矩阵的求解过程很相似，但两者抽取的规则不一样，针对每个项目，形成项目分向量userid：pref同样在Mahout中也使用了一个Job任务来进行形成项目矩阵的数据处理，输出的key/value对的格式是，其中的IntWritable和VectorWritable分别对应的是userid和项目向量的格式3）项目矩阵平方和在Mahout中使用了一个Job任务来对4.2中的项目矩阵求解平方和，针对每个项目的项目向量，项目矩阵平方和的求解方法为求解项目向量的模的平方。

4）项目相似度矩阵项目相似度矩阵的求解在Mahout中是由两个Job任务共同处理完成的，第一个Job任务是计算项目与项目之问的相似度，假设有N个项目，首先计算项目1和项目2的相似度，以此类推，最后计算项目1与项目N的相似度，但要注意的是，在计算项目2与项目1的相似度时，因为在计算项目1与其它项目相似度时已经计算过与项目2的相似度了，所以项目2只需计算除项目1以外的与其它项目的相似度第二个Job任务是续接，所谓续接就是把没有计算相似度的项目加入到其它项目中去，例如在第一个Job任务中，计算项目2与其它项目相似度时是没有计算与项目1的相似度，所以必须将项目1与项目2的相似度续接到项目2中，最后输出形成项目相似度矩阵表项目相似度的计算公式如下：其中，i1，i2分别代表项目1和项目2，U代表两个项目共同有过平方的用户集，Pui1，代表用户u对项目1的评分，Pui2代表用户u对项目2的评分，Sim代表的是两个项目的相似度，squssub>i1是对应的项目1的平方和5）用户一项目相似度矩阵用户一项目相似度矩阵是结合用户矩阵和项目相似度矩阵，为每一个用户生成用户一项目向量，Mahout使用了一个Job任务来对这些矩阵进行处理，输出key/value对的格式为，IntWritable和VectorAndPrefsWritable分别是用户和用户一项目相似度矩阵对应的格式。

6）用户推荐矩阵用户推荐矩阵是由Mahout中的一个Job任务根据用户一项目相似度矩阵计算产生的，推荐矩阵中为每一个用户产生一个推荐向量，推荐向量由多个推荐项目及其预测评分组成，计算公式如下：其中，simiIm是用户U1针对项目Im的相似度矩阵，M为用户评价过的项目集，prefIm是用户U1针对项目Im的评分，公式（7）只是求用户U1的推荐向量，然而，可以用公式（7）为所有用户求得推荐矩阵4实验结果及其分析4.1实验配置和数据集经分析，在小数据集条件下通过伪分布式模式或小集群的Hadoop分布式模式调试的工程，可以胜任完全分布式模式下的大数据集分布式计算的任务本实验在一台台式机上建立三台虚拟机，并通过这三台虚拟机建立3个节点的Hadoop集群，其中包括1个Master节点，2个Slave节点，台式机具体配置信息如下：Intel（R）Pentium（R）CPUG2030@3.00GHz，6GRAM，80G硬盘虚拟机操作系统为Ubuntu12.04，Hadoop版本为1.1.2，Mahout版本为Mahout-0.8在我们的实验中，将每个Slave节点的map和reduce任务支持的最大数都设置为4，由于map和reduce任务不是同时执行，所以整个集群可以支持8个map和8个reduce任务，实验中将这些map和reduce任务视为计算节点数。

本实验采用MovieLens数据集（http：//grou-plens.org/datasets/movielens）MovieLens是一个基于Web的研究型推荐系统，用于接收用户对电影的评分并提供相应的电影推荐列表我们选取的数据集包含6040个用户对3952部电影上的1000209条评分记录，其中，每个用户至少对20部电影进行了评分另外，引入了稀疏等级的概念，其定义为用户评分数据矩阵中未评分条目所占的百分比，实验数据集的稀疏等级为1-1000209/（6040*3952）-0.95814.2性能评估首先，在相同的数据集上针对不同等级的用户数量，比较单机和分布式的基于项目协同过滤推荐算法的推荐时间，并评估算法效率；然后利用分布式的推荐算法的加速比，随着计算节点数的增加，评估固定数据规模下。