英语原文共 17 页，剩余内容已隐藏，支付完成后下载完整资料
Hadoop集群中基于Mapreduce的Apriori算法的性能优化
Sudhakar Singh,rakhi Garg,P K Mishra
摘要：已经有很多技术在MapReduce框架上实现了Apriori算法，但是只有少数技术是注重于性能改进的。FPC和DPC算法将Apriori的多次传递组合在一个MapReduce阶段来减少运行的时间。在这篇文章中，提出了将基于MapReduce的Apriori算法中的FPC和DPC改进为VFPC和ETDPC。通过跳过一些步骤中的剪枝步和提出优化的VFPC和优化的ETDPC算法，进一步优化了算法的多通道阶段。定量分析结果表明，当计算成本相同时，经过优化之后剪枝产生的候选项集要比未修剪产生的候选项集少。实验结果表明，VFPC和ETDPC比FPC和DPC更强大，更灵活，而优化后的版本在执行时间上更有效率。
关键词：算法；数据挖掘；大数据；频繁相集；Apriori； Hadoop；MapReduce
引言
由Agrawal和Srikant[1]提出的Apriori算法是最受欢迎和广泛使用的数据挖掘算法之一，它利用候选生成来挖掘频繁项集。Apriori是关联规则Min- ing (ARM)的基本算法，它的发现促进了数据挖掘的研究。Apriori是2006年由IEEE数据挖掘国际会议(ICDM)在研究委员会中确定的最具影响力的十大数据挖掘算法之一[2]。
数据不仅计算量大，而且还表现出其他特征如速度，运动和变化速率的等。近几年的趋势是大数据[3]，主要有大容量、高速度和高变化量的特点。传统的数据挖掘技术和工具在分析/挖掘数据方面是有效的，但在管理大数据方面却不具有扩展性和有效性，应该采用大数据结构和技术对数据进行分析。Hadoop是用于大型数据集群的并行处理[4]的一个大规模的分布式批量处理基础结构。MapReduce是Hadoop设计的并行编程模型，用于对大量数据进行并行处理。因此，需要在MapReduce框架上重新设计数据挖掘算法以挖掘大数据集[5]。
Apriori在MapReduce框架上的直接实现增加了调度和等待时间的总开销。由于Apriori的迭代性质，在上一份工作完成之前，每次为新迭代唤醒的新工作和下一个作业调用新任务都不能启动。Lin等[7]提出了Apriori在MapReduce上的三个版本，命名为Single。通过SPC，FPC和DPC算法，FPC和DPC大大提高了性能，是Apriori在MapReduce框架上用最少迭代次数达到的最高效的实现。SPC是Apriori在MapReduce上的直接实现。
而FPC和DPC组合生成和计算单个阶段/工作SPC的多个连续相/工作的候选项。FPC将SPC(通常为3个阶段)的连续相的固定数量组合成一个MapReduce阶段，减少调度调用的数量。DPC动态地合并几个连续相的候选项集来平衡阶段之间的工作负载[7]。现在假设我们在一个并行计算通道阶段组合了3个连续通过k，k 1, k 2的候选项，然后候选k项集由频繁的(k -1)-itemsets生成，候选项(k 1)项集由候选k项集和候选项(k 2)-itemsets从候选项(k 1)-项集中产生。当下一个层次的候选项目集是由候选项集本身而不是频繁的项目集生成时，就会产生一些假的候选项集[7]。FPC可能由于过度的假阳性结果而表现不佳，这是在FPC组合了所有阶段相同的固定次数之后发生的。DPC通过连续的动态组合来克服这个问题。DPC的缺点是它使用策略来确定要合并传递的动态数量。DPC直接依赖于前一阶段的执行时间来决定通过的组合。执行时间不可能是绝对参数，因为它可能在不同的大小和容量以及新的数据集上有所不同。
1.1贡献
在本文中，我们提出了四种算法，称为VFPC，ETDPC，优化- vfpc和优化-ETDPC，VFPC和ETDPC改进了现有的FPC和DPC算法[7]。众所周知FPC和DPC是Apriori在MapReduce框架有效的实现方式。VFPC组合了不同阶段连续通过的变量数。它结合较早阶段的少量通过次数(一般为2)，并增加后一阶段的通过次数(如4，6hellip;hellip;)。何时增加通道的数量是由连续阶段的前两次候选项集的数量来决定的。ETDPC组合了不同阶段连续通过的动态次数的候选项。要合并传递的数量，取决于连续两个阶段的运行时间。进一步地,如果省略了剪枝步，当候选项集由自己产生时，最后就会让一些不丢失频繁项集完整性的候选项集相结合。
因此，我们提出了优化的多通道阶段，在第一关使用剪枝步，在所有后面的阶段中跳过修剪。优化了的VFPC和ETDPC与VFPC和ETDPC相似，但具有了优化的阶段。我们已经在实际生活和合成数据集中实现了我们提出的算法，并且发现与FPC和DPC相比，VFPC和ETDPC对具有不同计算能力集群的新数据集比Hadoop更加健壮和灵活。在性能方面，与VFPC和ETDPC相比，优化-VFPC和优化-ETDPC的执行时间显著的降低。此外,我们提出的算法对长期频繁项集挖掘最有效，更频繁的项目集也会在密集的数据集中或在最低支持度中生成。
本文的其余部分的安排如下。第二节描述了Apriori算法的基本概念和Hadoop系统。第三节简要回顾了相关的工作。在第四节对我们提出的算法进行描述和分析。在第五节讨论实验结果。最后，第六节总结全文。
2 基本概念
2.1先验的算法
Apriori是一种迭代算法，它在两个重要任务之间交替进行，第一个任务是从以前迭代的频繁项集生成候选对象。第二个任务是对数据库进行扫描，以获得每个候选项的支持度计数。在k阶迭代(kge;2)中,从频繁项集L k - 1(k - 1)中产生候选k项集C k，然后对每Ck中的k 子集进行检查获得的支持度计数。候选项集C k是通过有条件地加入L k-1得到的，然后对不满足Apriori属性的项集进行修剪。根据该属性，如果k-1 -子集中的任何一个(k-1)-子集不在L k-1[1]中存在，那么C k的所有项集都可以从C k中删除。
2.2 Hadoop分布式文件系统和mapreduce
Hadoop将计算能力(MapReduce)与分布式存储(Hadoop分布式文件系统)结合起来，通过提供本地访问数据和本地计算数据来降低通信成本。Hadoop分布式文件系统(HDFS)是基于GFS(谷歌文件系统)部署在低成本硬件上的。它打破了固定大小块(默认块大小为64 MB)的文件，并且复制(默认的复制因子是3)集群中的多个机器上的块，以提供高可用性和容错[8]。
MapReduce[9]是一种高效的、可扩展的、简化的编程模型，用于大规模的分布式数据处理。它可以并行处理大量的数据，通过大量的机器将工作分解成独立的任务。MapReduce程序通常由映射器、组合器和减速器组成，这些任务在Hadoop集群中的所有机器上运行。这些函数的输入和输出必须以(键、值)对的形式出现[8]。以下是在我们的实现中所遵循的MapReduce范例的具体细节。
InputFormat类选择驻留在HDFS中的输入文件，定义了分割文件的InputSplit，并为单个映射器提供了每次读取分割的Recor- dreader。单个地图任务是MapReduce程序中的一个工作单元，该程序对应于一个InputSplit。RecordReader读取分割后的数据，并将其转换为map- per的(key, value)对。Mapper接收输入(k1, v1)对，定义执行用户的计算，并生成一个中间(k2, v2)对的列表。这些配对是由Partitioner类划分的。还原器取(k 2, list (v 2))对为输入，将列表中的值相加(v 2)并产生新的对(k 2, v 3)。每个减速器在HDFS单独的文件中写入输出，该文件由OutputFormat类指导。由于它在给定节点上映射任务所发出的所有(键、值)对上工作，因此被称为“迷你还原器”[8]。
3相关的工作
为了提高关联规则挖掘算法的性能和可扩展性，针对同质计算环境以及网格计算[10]等异构环境，开发了许多并行分布式算法。毫无疑问，这些并行和分布式算法提高了挖掘性能，但涉及管理并行和分布式系统的开销。这些开销包括计算分区、数据分区、同步、通信、调度、工作负载平衡和管理集群或网格中的节点故障[7,11]。所有这些问题都可以通过谷歌[9]引入的MapReduce框架来克服解决。
从Hadoop的基础上，就MapReduce框架提出了若干常见的项目集挖掘算法。在这些算法中，专业是先验的[6,7,12-16]，有些是基于fp增长的[17]，很少有基于Eclat[11]的。大多数基于Apriori的算法都是简单地直接在MapReduce框架上实现Apriori[12]。算法FPC和DPC[7]提出了一种创新的思想，将Apriori的多个连续迭代合并到一个MapReduce任务中，从而显著地提高了MapReduce算法的性能。Kovacs和 Illes[6]使用了减速器内部的组合器的功能，而不是Mapper。他们还提出了一种使用三角矩阵数据结构的方法，在一个步骤中计算1和2个项目集。Li和Zhang[13]提出了一种适用于由异构节点组成的Hadoop集群的数据集分布方法，并在Apriori算法中使用。由Riondato等[14]在MapReduce上提出一个并行随机算法，用于发现近似频繁项集。它在数据集上挖掘一个小的随机样本，并且独立于数据集大小。Jen等[15]使用了Apriori的垂直数据布局来减少一些操作，提高了可伸缩性和效率。在[16]中研究了三种数据结构哈希树、trie和哈希表trie (trie与哈希技术)，这对MapReduce算法的影响很大，并发现哈希表trie比trie和散列树的性能好得多。Xun等[18]在MapReduce上开发了一种并行频繁项集挖掘算法，称为FiDoop。它用FIU-tree(频繁项的超度量树)代替FP树[17]。它的扩展名FiDoop-HD也被设计用于处理高维数据。论文[19]详细描述了基于Apriori的MapReduce算法，并比较了各种基于MapReduce的Apriori算法的算法特性。
虽然本文的工作重点是基于Hadoop的MapReduce，但是在Hadoop之后出现了一些其他的平台。Apache的Mahout[20]提供了各种机器学习和数据最小算法的库。基于本文[17]，Mahout机器学习库和Spark (Spark)[21]仅提供并行fp增长算法的实现。Apache的Spark[21]在内存中处理数据，执行任务的速度比MapReduce快10到100倍。Spark在内存计算中使用了大量内存，因此它需要一个专用的高端物理机器，而Hadoop在一个商品机器上运行得很好。
此外，Spark还使用Map的概念，并随着其自身的其他功能减少功能。R-Apriori[22]是并行Apriori算法在Spark上的有效实现之一。
从事务中挖掘数据需要大数据流计算(BDSC)[23]，它可以实时处理大量数据。大数据流移动计算(BDSMC)的新范式已在[24]中正式化。它专注于管理BDSMC的计算通信平台的实时处理和能源效率。另一个相关领域，基于模糊系统的数据挖掘[25]能够识别数据库项目之间的不精确关系。基于MapReduce的算法也被设计用于挖掘模糊关联规则[26]。
4提出算法
在MapReduce中基于Apriori需要设计一个Mapper，它可以生成具有本地支持度计数的候选项集，用于分配数据库以及减少本地计数，并生成具有全局sup- port计数的频繁项集。可以使用一个组合器来最小化Mappers和reducer之间的通信成本。由于两种方法的主要功能是对局部计数进行求和，因此，在所有基于MapReduce的Apriori算法中，组合器和减速器的设计仍然是相同的。Mapper的设计取决于所需的计算。在频繁的1项集合生成中，Mapper会从分配给映射器的数据库调用它的映射方法。映射方法在事物中为每项输出配对。用于计算1项集的Mapper被命名为OneItem- setMapper，而组合器和减缩器分别被命名为ItemsetCombiner和ItemsetReducer。算法1为Mapper生成1个项目集的伪码以及组合器和减速器。ItemsetCombiner和ItemsetReducer的算法是相同的，只是前者不检查支持度计数和最小支持阈值。在[19]中描述了基于Apriori的MapReduce直接实现的一个非常详细的描述。
我们使用了两种类型的MapReduce作业，称为Job1和Job2。Job 1生成1个频繁项集，Job2生成k -itemsets (k 2)。Job1配置了OneItemsetMapper、ItemsetCombiner和ItemsetReducer，这对所有的算法都是一样的。单次计数(SPC)算法[7]是Apriori在MapReduce上的直接实现。我们将它的Mapper命名为SPCItemsetMapper，用于Job2。SPC的Job2配置为SPCItemsetMapper、ItemsetCombiner和ItemsetReducer。SPC每次都为Apriori的传递/迭代调用Job2的新实例。SPCItemsetMapper和SPC的伪代码显示在算法2中。SPCItemsetMapper使用apriorigen和Apriori[1]的子集方法来生成候选项集和支持度计数。在我们的实现中，在所有用于存储和生成候选对象的算法中我们使用了前缀树(Trie)数据结构[27]。频繁k-项集和候选k项集的前缀树分别由trieL k和trieC k表示。
现有的FPC和DPC算法[7]将SPC的连续MapReduce
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[21350]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
