基于MapReduce的购物篮分析算法外文翻译资料

英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料

基于MapReduce的购物篮分析算法

摘要

自从谷歌公司在其分布式文件系统(GFS)上搭建了MapReduce平台，MapReduce方法便成为计算大规模数据的流行方法，紧跟其后的是亚马逊网络服务(AWS)提供的基于低成本计算结点的Apache Hadoop平台。映射/归约鼓励在MapReduce上重新设计和改造已有的串行算法，变为受限的并行化编程，所以本文提出了基于先验概率的MapReduce购物篮分析算法。两个算法用来适应已经存在的Apriori-algorithm（Apriori-algorithm是关联规则里一项基本算法）和建立一个简单的算法来对数据集进行排序并转化成（键，值）对形式以适应MapReduce。算法在亚马逊EC2 Map/Reduce平台上运行。实验结果表明Apriori-algorithm的性能并不如这个简单算法。使用该简单算法，基于Map/Reduce后程序通过增加更多的节点可提高计算性能，但在某种程度上存在一个瓶颈，不允许进一步的性能改善。文章认为分布式操作、聚合、在Map / Reduce上归约数据是导致性能瓶颈的原因。（2013 John Wiley amp; Sons, Ltd.）

1.介绍

随着像社交媒体、智能手机和传感器网络每时每刻产生TB或PB规模的数据，使用传统系统来存储这些数据变得更加困难。而且，这些数据都是非结构化的大数据。例如，谷歌受到持续存储大数据并发现现有的文件系统不足以有效地处理这些数据的问题的困扰。此外，传统系统的计算能力和平台对大数据无效，这也迫使谷歌搭建谷歌文件系统(GFS)和Map / Reduce并行计算平台，这促进了Apache Hadoop项目的产生。

Hadoop是一个并行编程平台，建立在Hadoop分布式文件系统和映射/归约计算模型之上，用来处理像（键，值）对这样的数据。Hadoop受到了商业计算的褒奖，因为全球商业事务拥有如网络交易日志文件这样的大规模数据。在过去的几年中，Hadoop已经在利用数据挖掘处理商业智能方面的大数据。在Hadoop时代意味着那些执行串行计算的传统算法需要重新设计或转换为MapReduce算法。因此，在本文中，提出了两个基于MapReduce的购物篮分析（MBA）算法，并分别在而弹性计算云(EC2)和亚马逊网络服务(AWS)的简单存储服务(S3)平台上运行。

云计算已经被认为是已使用多年的服务，包括主机服务、web邮件服务、文档共享服务、地图API服务。它分为软件即服务（SaaS），平台即服务（PaaS）和基础设施即服务（IaaS）。SaaS通过网络来提供服务而不是事先安装或维护软件。例如，web邮件服务归类到SaaS里。采用PaaS提供计算和存储服务不需要采购硬件或软件，例如托管服务。IaaS是效用计算服务，类似于SaaS，但需要购买服务的时间，比如AWS。AWS为采用Map / Reduce计算模型的商用计算机提供S3、EC2和弹性的MapReduce服务，就像IaaS和SaaS在云计算中所做的那样，这让普通组织能够以很低的成本获得超算能力。

以下章节关注相关性的工作，主要描述了Map / Reduce和Hadoop以及其他相关项目，提出了Apriori（先验的）MapReduce算法，并提出简单的基于MapReduce的购物篮分析算法。最后一部分给出了实验结果。

2.相关工作

关联规则或关联分析是最基本的数据挖掘分析技术，其旨在发现像顾客购买行为等活动的共生关系。这种分析是标准的顺序计算，并在许多关于数据挖掘的书籍都讨论过了。

Aster数据公司有一个采用SQL MapReduce框架的一个产品。Aster提供nPath SQL处理存储在数据库中大数据。购物篮分析算法也执行在该框架下，但它是基于SQL API的MapReduce数据库。

Jongwook等人使用/规则项目对/集合的/先验属性/实现MBA算法。本文的目的是提出和比较两个算法，然后将数据转换成(键，值)对在Map / Reduce平台上执行算法程序。

3.Hadoop平台上的Map/Reduce

Map / Reduce是人工智能领域的函数式编程算法。谷歌公司为了解决分布式计算环境下大规模数据集的分析问题而重新引入Map/Reduce，它再一次被突出强调了。具体来说，它由两个函数组成，“映射”和“归约”。这两个函数都处理(键，值)对这样的结构化数据。

4.并行计算下的Map/Reduce

Map / Reduce编程平台实现于Apache Hadoop项目中，是Hadoop项目的产品之一，该项目的目标是开发可靠的、可伸缩的和分布式计算的开源软件。Hadoop可以组合成千上万个节点一起来处理和计算PB或TB规模的数据。Hadoop项目的灵感来自谷歌公司的MapReduce和GFS，这两个项目的诞生是因为此时谷歌已经需要处理大数据集的信息检索和分析。它被一个全球性的开源社区如雅虎、Facebook和twitter所使用。Hadoop的子项目包括Hadoop Common，HDFS， MapReduce， Avro， Chukwa， HBase， Hive，Mahout， Pig，和ZooKeeper 等等。

Map和Reduce函数并行地运行在分布式节点上。每个map操作都可以在每个节点上独立地进行，而所有的操作都可以并行地实现。但实际上，这也受到数据源和（或）数据源附近的CPU数目的限制。Reduce函数也是相似的情况，因为归约操作依赖于map操作。然而，Map/Reduce可以处理非常巨大的数据集，这些数据可以分布在HDFS上，并且操作越靠近数据源其性能越好。

Hadoop或部分并行编程平台是受到限制的，因为需要把输入变成（关键字，值）对的形式然后并行地计算和由map / reduce函数生成的(键，值)对输出列表。在Map函数中，主节点将输入分成规模更小的子问题，并分配下面的工人节点。这些工人节点处理相似的问题，然后将结果返回给主节点。具体是这样的，Map函数将输入的键值对（k1，v1）并产生lt;k2，v2gt;（其中“lt; gt;”代表列表或集合）。在Map和Reduce操作之间，有一个合并器驻留在map节点上，它负责接收输入（k2,lt;v2gt;）和产生lt;k2,v2gt;。

在Reduce操作里，主节点将所有子问题的结果以某种形式组合并产生输入，也就是最终问题的结果。也就是说，Reduce操作接收输入（k2,lt;v2gt;）并产生lt;k3,v3gt;。图6表示Map/Reduce控制流，其中每个Value_mm的值是1，累计发生在MBA算法的项目数。

5.大数据数据库

输入/输出文件在HDFS（Hadoop分布式文件系统(HDFS)）上执行，而不是本文中使用的HBase数据库。但是，HBase是有意思的并且在未来将被集成于算法中，本节简要介绍一下HBase。

使用RDBMS来处理大量的数据时缺点包括不容易删除，缓慢的插入和随机性失败操作。基于HDFS的Hbase是一个分布式数据库，它支持对水平扩展表的结构化数据的存储。这是一个面向列的半结构化数据存储。

Hbase很容易集成Hadoop的 Map/Reduce计算模型，因为HBase由一个组合了键和值的核心映射组成的——每个关键字都与一个值关联。用户们存储数据行到标签表中，一个数据行有一个可排序的关键字和任意数量的列。整张表稀疏存储，所以同一表中的行可以有不同的列。

使用传统的编程语言如Java、PHP和Ruby，任何一个都可以把数据映射为Java JDBC对RDBMS的形式。数据在参与节点之间复制。当数据表建立，表中列族也会同时生成。也就能够根据完整的列名以某种形式从HBase中检索数据，然后HBase就能根据给定查询返回结果，就像使用SQL在RDBMS中进行查询一样。

6.Map/Reduce存在的问题

虽然Map / Reduce对一些研究人员和教育工作者来说有很多优点，但其也存在一些不足：

1. 对大规模数据密集型应用程序的编程范式来说，这是一个巨大的倒退。
2. 没有一点新意——它仅仅是对以前开发的众所周知的技术的具体的实施，尤其是人工智能领域的技术。
3. 数据被转换成（关键字，真值）对的形式以满足Map/Reduce的要求，这就失去了通常包含在当前的DBMS中大部分的特征。
4. 不兼容当前已经建好的所有的工具或算法。

然而，这些问题不仅清楚地表明我们的问题，也提供给我们实现基于Map / Reduce方法的算法的机会，尤其是对大数据集合。它给人们提供了开发新系统和在并行计算环境不断发展信息技术（IT）的可能。从几年前开始，在各州，许多公司的IT部门已经转向对Map / Reduce方法的研究。

7.“购物篮”分析算法

MBA 是分析数据集关联关系的众多数据挖掘方法中的一个。基本思想是在已存储的有关交易记录的数据集中找到关联的项目，如图1所示:

图1. 商店交易数据

图2. 10对频繁出现在商店的物品

如果店主售货记录中两项商品频繁地出现，他/她可以更有效地控制库存，安排货架上商品的摆放或者推销绑定商品。因此，他/她通过控制产品和营销的顺序来增加获利的可能性。

例如，人们已经构造并成功运行 MBA 代码 —— 串行执行的代码 — — 计算得出十大最经常发生的交易组合，如图2所示。在商店，当客户购买一块饼干时，他们也会购买啤酒，这总共出现 了6836 次，而同时购买波本威士忌则有 5299 次。因此，所有者可以根据这些数据来经营自己的商店。

8.数据结构和转换

图 1 中的数据由交易记录组成，其中包含交易的数目和相应的产品列表。对于Map/Reduce操作要求，数据集应该转化为（关键字，值）对的形式。在本文中，我们将项目作为关键字并把对应项目发生的数目作为值放在篮子里，这样对所有的交易，不需要知道交易的数量。因此，图1可以重构为图3假设的项目对形式，将两项作为一个键值对。

图3.用于Map/Reduce的数据集

然而，如果我们将两个项目放在一个篮子里来作为一个关键字，就不能正确地计算项目对出现的频数。如图4所示，交易n和m拥有项目(cracker,icecream, beer) 和(icecream, beer, cracker))，这两者拥有相同类别却顺序不同的项目。也就是说对于项目(cracker, icecream, beer)，可能的键值对形式有(cracker, icecream), 1),，(cracker,beer), 1)， (icecream, beer), 1)。还有，对于项目( icecream, beer, cracker)可能的键值对形式有(icecream,beer), 1), (icecream, cracker), 1), (beer, cracker), 1)。

因此，我们就有总共6对不同的键值对，而这些键值对中有重复的，除去重复应该只有3对不同的键值对。也就得出结果，关键字(cracker , icecream)和(icecream , cracker )是不同的，而这是不正确的。

图4.对同一列表进行调整的数据集

如果在生成(键，值)对之前按字母顺序对交易中的项目进行排序，就可以避免这种问题（就把项目一致但顺序不一致的现象给消除了）。如图5所示。现在，每个交易都有3组不同的项目对((beer, cracker),1)，((beer, icecream), 1)，((cracker, icecream), 1)。这是两个不同的项目且分别出现了两次，则这两个交易事务表现出的积累值如下所示：((beer, cracker), 2)， ((beer, icecream), 2)， ((cracker,icecream), 2)，这样就能正确的统计所有发生的交易项目了。

图5.数据集的重组与排列

9.Aproiri的MapReduce算法

9.1 Hadoop平台上的Map/Reduce

Map / Reduce是人工智能领域的函数式编程算法。自从谷歌公司为了解决大数据分析问题而重新引入该算法，他就一直受到了巨大的关注。所谓大数据就是在分布式环境下的PB规模级的数据。Map/Reduce由两个特殊的函数组成，lsquo;Maprsquo;和lsquo;Reducersquo;。这两个函数都被定义为处理像（键，值）此类数据。

受到谷歌公司的MapReduce和GFS的刺激，Map / Reduce平台是作为Apache Hadoop项目开发实现的，该项目的目标是实现可靠的、可伸缩的和分布式计算开源软件。Hadoop可以组合成千上万个节点用来处理大数据。Hadoop已经被全球贡献者社区所使用，如雅虎，脸谱，推特，和Cloudera。Hadoop产生了许多子项目，包括Hadoop Common, HDFS, MapReduce, Avro, Chukwa,HBase, Hive, Mahout, Pig, ZooKeeper等等。

Map和Reduce函数并行地运行在分布式节点上。每个Map和Redu

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[148723]，资料为PDF文档或Word文档，PDF文档可免费转换为Word