基于MapReduce的Apriori算法并行化研究

谢志明

摘 要： 针对目前传统的Apriori算法对硬件要求较高且运算效率低下的情形，提出将经典的数据挖掘关联规则算法Apriori移植到云计算平台，并结合MapReduce机制进行海量数据挖掘，有效地解决了传统Apriori算法存在的瓶颈问题以及对硬件要求高的依赖。通过数据和节点对比实验共同验证了移植后的Apriori算法的运算效率比传统的Apriori算法提高了许多倍，且随着数据量和节点数的增加效果愈发明显。由于改良后的Apriori算法具有高效性和可行性，这将为解决当前大数据挖掘问题提供了一种全新的、有效的解决方案，并且这一结论还可为其他数据挖掘算法的移植提供可靠的参考。

关键词： Apriori算法； 数据挖掘； 关联规则； 云计算； MapReduce机制

中图分类号： TP 399 文献标志码： A 文章编号： 1671-2153（2015）05-0076-05

0 引 言

传统Apriori算法是数据挖掘中研究最成熟、最活跃的关联规则算法之一，利用它可以发现数据中所蕴含的相互关系[1]。由于传统的数据挖掘算法大多是以单节点的机器为平台，所处理的数据对象也主要是小到中等规模的，当面对海量的、多维的、分散的数据集合时，现有的算法则往往显得力不从心[2]。

如何处理异构海量数据，选用那种高效的数据处理模式来提高运算速度并降低内存的消耗，已成为亟待解决的问题。随着云计算技术和大数据技术相继提出和应用，分布式大数据处理系统日渐被人们关注和研究。基于Hadoop搭建的云计算平台具有分布式大数据处理能力和海量的数据存储能力，这些都将为解决当前异构海量数据挖掘问题提供了一种全新的、有效的解决方案[3-4]。

1 Apriori算法描述及相关研究

Apriori算法原型是以用户事先设置好的最小支持度（min_support）和最小可信度（min_confidence）为条件，通过对需处理的事务数据集进行重复多次扫描，从中找出项与项之间所存在的并发关系，找到所需的关联规则和判断是否满足用户要求的过程，即发现频繁项集和产生规则的过程。如图1所示。

文献[5]中说到Apriori算法在扫描数据库时需经过自连接、剪枝生成频繁项集，并采用逐层迭代法直到无法产生新的频繁项集时才停止扫描。文献[6]解释了在处理大规模数据时，当设置的最小支持度偏小且产生的频繁项也较多时，发现该算法效率低下。随着研究的不断深入和扩大，人们发现在大规模数据量下传统Apriori算法的优势越来越不明显；相反，在实际应用中很多时候还达不到用户的要求。于是许多专家学者对该算法做了一些专门的改良实验，如文献[7]中提出了一种基于数据划分的思想用于提高Apriori算法处理海量数据挖掘的效率等。鉴于此，本文将结合分布式大数据处理系统Hadoop，对移植到云计算平台的Apriori算法进行实验验证，证明是否能有效提高数据挖掘效率。

2 Apriori算法并行化描述

Hadoop平台有自己的分布式文件系统（HDFS），它是Hadoop的核心子项目之一，能对海量数据进行存储和管理。当数据上传到HDFS上后，由命名节点（Namenode）统一管理对各个节点文件的访问。上传来的大文件将会被分割成一个或多个块（block），这些block存储在数据节点（Datanode）集合里，并由Datanode负责调用Map（）函数[8]。Hadoop平台中的Map（）函数负责处理局部的数据，对候选项集做本地统计后，然后把统计信息传到主节点，最后启动Reduce程序，它负责把Map（）函数局部统计统计结果汇总，然后判断那些是满足要求的候选项集，即形成频繁项集[9]。MapReduce Apriori（简称Apriori_MR）算法伪代码如下：

输入：D（HDFS上的数据）， min_support

（1）L1=find_frequent_1-itemsets（D）；

（2）for（k=2；Lk-1≠Φ；k++） {

（3）Map1（key，value，Lk-1，X.count），

Map2（key，value，Lk-1，X.count），……，

Mapi（key，value，Lk-1，X.count）

（4）Lk=Reduce（Lk-1，X.count，Lk-1，K.support）}

（5）return L=LUkLk；

输出：频繁项目集L

MapReduce Apriori算法处理过程如图2所示。

3 Apriori_MR算法设计

该算法在MapReduce编程模式中是以键值对（Key/Value）的形式进行计算的，计算完毕后也是以键值对的形式输出。在进行MapReduce处理的过程中，Map（）函数和Reduce（）函数是最为关键的两个函数。如需要实现某些特定功能，可以通过改写Map（）和Reduce（）函数来完成。

3.1 Key/Value的设计

表1为定义的Key/Value类型情况。表1中，Map（）函数是以Key/Value键值对输入的，期间会产生一系列Key/Value键值对并作为中间结果输出写入到本地磁盘。MapReduce框架则按照Key值自动聚集原则将具有相同的Key值统一交给Reduce（）函数处理。Reduce（）函数将这些具有相同的Key进行合并得到相应的Value值，最终产生一个全新的系列Key/Value键值对并将结果写入到HDFS中。

3.2 Map的设计

在Hadoop中，用远程过程调用（RPC，Remote Procedures Call）的方式来实现各个节点的通信[8]。RPC协议主要作用是将消息编码为二进制流，该过程是通过序列化方式实现的。在MapReduce编程模型中，用户的输入与输出数据要求Key和Value都必须是序列化的。

Hadoop的序列化核心是Writable，它提供了两个接口方法来实现二进制格式数据流的写入和读出，其特点是快速和紧凑。MapReduce的数据路径传递中最重要的就是Writables，通过重新定义该接口能控制二进制值表示和排序等功能。当使用这个经重新定义过的扩展Writables接口的Frequent类，可以把每次生成的频繁Lk存储到类Frequent里面，然后通过算法Apriori_gen（Lk）得到候选项集Ck，最后可以扫描局部的数据得到各个候选项项集Ck中各个项的个数。其伪代码如下：

map（key， value， Lk， X.count）

{

Ck= Apriori_gen（Lk）；

for（i=1；i<=Ck .size（）；i++） {

if（value中含有Ck中的项）

Ck .item的计算记录为1；

write（Ck .item， 1）； }

}

3.3 Reduce的设计

Reduce的主要工作是将由Map过程所生成的候选项集中每一项的计数通过Reduce函数将相同项的局部计数进行相加，并把满足用户最小支持度的那部分写入到文件中的过程，如图3所示。

由图3可以看出，Map（）函数在处理数据的过程时，它首先统计每个项的数量，再对每个存在的项记录一次；而Reduce（）函数则仅用于汇总候选集项的数量，其伪代码为：

public void reduce（Candidate key， Iterablevalues， Context context） throws IOException， InterruptedException {

IntWritable result = new IntWritable（）；

int sum = 0；

对候选集中相同的项进行计数

for （IntWritable val ： values） {

sum += val.get（）； }

if （（double） sum >= supportCount） {

result.set（sum）；

context.write（key， result）； }

}

4 Apriori_MR实验和结果分析

以下所用到的实验数据是由人工数据合成工具（IBM Quest Market-Basket Synthetic Data Generator）生成的，它是关联规则数据挖掘实验中经常用到的工具。通过数据对比实验和节点对比实验来验证该算法是否具有高效性。

4.1 数据对比实验

本研究使用了集群里的9个节点做数据测试，数据记录以文件的形式进行存放，其最小支持度均设为70%，在计算节点不变而数据量变化的情况下进行多组实验后两种算法的对照结果如图4所示。

由图4可以看出，当数据量在一百万条记录期间时，基于MapReduce框架的Apriori算法和经典的Apriori算法所用时间相差不大，然而，随着数据量的增加，程序运行的时间差距逐渐拉大。产生这种现象的主要原因是，当数据量较少时，通信开销所占总运行时间比例相对较大，随着数据量的增多，处理数据的时间占总运行时间比例上升，通信开销则可以忽略不计。而且在集群环境下可以并发处理数据，加快了数据处理速度。根据数据对比实验可以得出以下结论：Apriori_MR比传统的Apriori更适合处理海量数据，且随着数据量的增加相对单机的优势愈发显得明显。

4.2 节点对比实验

在此实验中以加速比（Speedup）作为一个重要的衡量标准。加速比，指的是运用单处理器系统和并行处理器系统来处理同一任务所消耗时间的比对关系，并通过这一对比结果衡量出串行系统与并行系统的性能差。加速比Sp定义如下：

Sp=Ts / Tp，

式中：Ts为串行处理时间；Tp为并行处理时间。在实验中把单一节点机上运行的时间看做Ts，多个节点机上运行的时间看做Tp。根据文献[10]所提到的MapReduce所具有优点之一是Hadoop集群有很好的伸缩性，能非常方便的将具有计算能力的PC机接入到集群。本实验将通过改变计算节点来测试移植后的Apriori_MR算法在进行等量数据挖掘的时间差，分析其加速比情况。图5显示了1000万条记录在不同节点数集群上的测试情况，测试中数据量与支持度一直保持不变。

由图5可以看出，当节点数小于等于3时，消耗时间的差距不大，主要原因是要考虑到集群的通信开销。然而，随着节点数的增加，所花费的时间越来越少，加速比之间的差距也越来越小，按照这种趋势，加速比曲线会慢慢趋于平稳上升并保持下去。根据节点对比实验可以得出如下结论：在数据量不变的情况下，当数据节点大于一定数量时，节点数越多，处理速度越快，效率越高。

根据上述两个对比实验，在数据量的持续增加和节点数扩展过程中，Apriori_MR算法在数据处理效率和扩展方面表现出良好的性能以及良好的外延性。因此，可以得出如下结论，将传统的Apriori算法移植到云计算平台上进行大数据挖掘处理不仅是高效的而且也是行得通的。

5 结束语

云计算目前已经是全球最具有发展潜力的信息类技术之一，如何高效地将传统的数据挖掘算法移植到云计算平台上，已成为时下最流行研究的核心领域之一。本文从分析经典的Apriori算法基础入手，结合云计算平台和大数据分布式处理技术对该算法加以改进并移植，能有效地解决传统意义上Apriori算法在数据挖掘过程中遇到的诸多客观问题。并通过实验数据、图形分析证实了Apriori_MR算法要比传统的Apriori算法在性能上优越许多，该算法的成功移植还进一步为移植更高效的数据挖掘算法提供了可靠的参考。

参考文献：

[1] 习慧丹. 关联规则挖掘优化方法研究[J]. 计算机与数字工程，2012，40（5）：31-33.

[2] 涂新莉，刘波，林伟伟. 大数据研究综述[J]. 计算机应用研究，2014，31（6）：1612-1616，1623.

[3] 张滨，陈吉荣，乐嘉锦. 大数据管理技术研究综述[J]. 计算机应用与软件，2014，31（11）：1-5，11.

[4] GONCALVES C，ASSUNCAO L，CUNHA J. Data analytics in the cloud with flexible MapReduce workflows[C]//Proceeding of the 2012 IEEE 4th International Conference on Cloud Computing Technology and Science. Taipei：[s.n.]，2012：427-434.

[5] 毛国君，段立娟，王实，等. 数据挖掘原理与算法[M]. 北京：清华大学出版社，2007.

[6] 刘丽. 基于关联规则的数据挖掘技术综述[J]. 现代计算机，2011，32（7）：25-27.

[7] 段艳明，肖辉辉. 改进Apriori算法处理海量数据的研究[J]. 电脑与信息技术，2013，21（1）：22-24.

[8] 董西成. Hadoop技术内幕-深入解析MapReduce架构设计与实现原理[M]. 北京：机械工业出版社，2013.

[9] KOVACS F，ILLES J.Frequent itemset mining on hadoop[C]//Proceeding of the 2013 IEEE 9th International Conference on Computational Cybernetics. Tihany，Hungary，2013：241-245.

[10] 丁祥武，李清炳，乐嘉锦. 使用MapReduce构建列存储数据的索引[J]. 计算机应用与软件，2014，31（2）：24-28.