摘  要： 为解决AprioriTid算法对大数据执行效率不高的问题，根据Hadoop平台的MapReduce模型，分析了AprioriTid算法的并行化方法，给出了并行化的主要步骤和Map、Reduce函数的描述。与串行的AprioriTid算法相比，并行算法利用了多个节点的计算能力，缩短了从大数据集中挖掘关联规则的时间。对并行算法的性能进行了测试，实验结果表明，并行AprioriTid算法具有较高的执行效率和较好的可扩展性。

　　关键词： AprioriTid算法；MapReduce；Hadoop；关联规则

0 引言

　　AprioriTid算法[1]是AGRAWAL R等人提出的关联规则挖掘算法，该算法在迭代计算频繁k-项集的过程中使用Ck代替事务数据库，通过逐步缩小Ck的规模来减少I/O读取时间，进而提高算法的执行效率[2]。但是，AprioriTid算法的时间复杂度较高，对大数据而言，该算法在单机环境下的执行时间太长，难以取得较高的执行效率。云计算是解决这个问题的可行方法，由于云计算平台具有强大的计算能力，突破了单机计算能力的限制，为用户高效处理大数据提供了支持。MapReduce[3]是云计算环境下被广泛采用的并行编程模型。本文根据Hadoop平台[4]的MapReduce模型，给出了一种AprioriTid算法的并行化实现方法。并行算法利用计算机集群的多个节点并行计算候选项集的支持度，解决了单机环境下AprioriTid算法对大数据执行时间过长的问题，提高了挖掘关联规则的效率。

1 相关知识

　　1.1 AprioriTid算法分析

　　AprioriTid算法是在Apriori算法[1]的基础上改进而来的关联规则挖掘算法，参考文献[1]给出了该算法的描述和实例分析。AprioriTid算法计算频繁-1项集和生成候选k-项集的方法与Apriori算法是相同的，但是在发现频繁k-项集的过程中采用了Ck代替事务数据库D。对于所有的候选k-项集Ck，数据库D中的一个事务t在Ck中对应的记录表示为：<t.TID，{c∈Ck|c contained in t}。例如：k=2，C2={{1 3}，{1 4}，{1 5}，{3 4}，{3 5}，{4 5}}，D的一个事务t=<100，{1 2 3 4}>，则t在中C2对应的记录表示为<100，{{1 3}，{1 4}，{3 4}}>。

　　AprioriTid算法计算频繁k-项集（k≥2）的时间复杂度为O（|Ck|×|Ck-1|×|t|），其中，|t|是Ck-1的记录包含的候选（k-1）-项集的平均个数。在一般情况下，当k的取值较小时，Ck-1的规模会大于事务数据库的规模，算法的时间复杂度较高。可见，在单机环境下应用AprioriTid算法对大数据挖掘关联规则难以取得较高的执行效率。在并行条件下，利用多台计算机的处理能力能很好地解决运行效率低下的问题[5]。如果将Ck-1分解成p个子数据集，由p个节点对子数据集并行计算频繁k-项集，则在单个节点上的时间复杂度为O（|Ck|×|Ck-1|×|t|/p），这就提高了算法的执行效率，这也是本文实现AprioriTid算法并行化的基本思想。

　　1.2 Hadoop平台的MapReduce模型

　　MapReduce模型的基本思想是将处理的问题分解为映射和归约操作，由用户实现的Map和Reduce函数完成大规模的并行化计算[6]。开源的云计算平台Hadoop实现了MapReduce模型，MapReduce任务在Hadoop平台上的执行流程如图1所示。数据文件被切分成多个数据分片存储在Hadoop分布式文件系统HDFS中，在input阶段，MapReduce支持库将数据分片的记录解析为<key，value>对输入Map函数，Map函数对数据分片进行处理，产生一组新的<key，value>对中间结果。在shuffle阶段，相同key的value值被合并为values集合，以<key，values>对传递给Reduce函数。Reduce函数对<key，values>集合作进一步处理，将最终结果输出到HDFS中。

　　在实际的应用中，不同的数据文件通常采用不同的记录格式，为了将记录解析成合适的<key，value>对，Hadoop平台为用户提供了TextInputFormat、KeyValueTextInputFormat等类，使用这些类可以指定输入Map函数的key和value。在Hadoop的MapReduce模型中，执行Map函数的各个节点分别处理不同的数据分片，如果所有节点都能够读取相同的文件，就需要借助Hadoop的分布式缓存机制[7]。在主程序中将待分发到所有节点的文件设置为分布式缓存文件，各个节点便可以同时读取这些文件。

2 AprioriTid算法的MapReduce并行化

　　2.1 AprioriTid算法的并行化方法

　　AprioriTid算法的执行过程包括两个阶段：首先从事务数据库中找出所有频繁1-项集L1，然后采用迭代方法计算所有频繁k-项集Lk，每次迭代计算的输入数据是Lk-1和Ck-1，输出结果是Lk和Ck。按照Hadoop的MapReduce模型，结合分布式缓存机制，这两个阶段都能实现并行化，方法如下：

　　（1）将事务数据库切分成多个数据分片，多个节点并行对数据分片统计各个项的支持度计数，从而实现了L1的并行计算。

　　（2）将Lk-1设置为分布式缓存文件，Map函数读取Lk-1，通过执行Ck=apriori-gen（Lk-1）生成所有候选k-项集Ck，将Ck存放在节点的内存中。将Ck-1切分成多个数据分片，多个节点根据Ck对Ck-1的分片并行统计候选k-项集的支持度计数生成Ck，从而实现了Lk和Ck的并行计算。

　　2.2 AprioriTid算法并行化的主要步骤

　　为了便于描述，设定事务数据库D、Ck、频繁k-项集Lk在HDFS中的目录分别为DPath、CPathk、LPathk。在并行算法的执行过程中，需要多个MapReduce作业（Job）才能完成，第k个Job用Jobk表示，算法并行化的主要步骤描述如下。

　　（1）在主程序中设置Job1的输入路径为DPath，输出路径为LPath1。

　　（2）Map函数读取D的数据分片，将事务t的所有项ij分解出来，输出<ij，1>键/值对。Reduce函数统计项ij的支持度计数count，将满足最小支持度阈值minsup的项ij及其支持度计数输出到LPath1目录的文件中。Map、Reduce函数描述如下：

　　map（key=TID，value=t）{

　　for each项ij of t

　　emit（<ij，1>）；

　　}

　　reduce（key=ij，values={1，1，…}）{

　　count=|values|；  //|values|是集合中1的个数

　　if （count≥minsup）emit （<ij，count>）；

　　}

　　（3）k=2，C1=D。

　　（4）在主程序中将Lk-1设置为分布式缓存文件，设置Jobk的输入路径为CPathk-1，输出路径为LPathk。

　　（5）在Map函数中定义setup、map和cleanup方法。setup方法读取Lk-1，执行Ck=apriori-gen（Lk-1），初始化Ck。map方法读取Ck-1的分片，对于分片的每一个记录t，根据Ck计算t包含的候选k-项集集合Ct，将Ct添加到Ck中，并将Ct的每一个候选k-项集c以<c，l>键/值对传递给Reduce函数。cleanup方法将Ck保存到CPathk目录的一个文件中。Reduce函数统计候选k-项集的支持度计数，将满足最小支持度阈值的频繁k-项集及其支持度计数输出到LPathk目录的文件中。

　　Map函数描述如下：

　　setup（）{

　　从LPathk-1目录读取Lk-1；

　　Ck=apriori-gen（Lk-1）；

　　Ck=；

　　}

　　map（key=TID，value=t）{

　　Ct=；//初始化Ct

　　Ct={c∈Ck|（c-c[k]）∈t.set-of-itemsets∧（c-c[k-1]）∈t.set-of-itemsets}；

　　if（Ct≠）{

　　Ck+=<TID，Ct>；

　　for each 候选k-项集c∈Ct

　　emit（<c，1>）；

　　}

　　cleanup（）{

　　将Ck作为一个文件保存到CPathk目录；

　　}

　　Reduce函数描述如下：

　　reduce（key=c，values={1，1，…}）{

　　count=|values|；

　　if（count≥minsup）emit（<c，count>）；

　　}

　　（6）如果Lk=，则算法结束；否则，k=k+1，转向执行步骤（4）。

3 实验与结果分析

　　使用6台配置相同的计算机和一台100 M交换机搭建Hadoop集群，操作系统是Ubuntu Linux 12.04，安装的软件是Hadoop 1.2.1、JDK 1.7.0_51。从Frequent Itemset Mining Dataset Repository网站（http：//fimi.ua.ac.be/data/）下载了6个数据集：chess、mushroom、pumsb_star、kosarak、retail和accidents，由于这些数据集的事务没有TID，通过编写程序给事务添加了从0开始顺序编号的TID。

　　3.1算法的执行时间测试

　　使用Java实现了AprioriTid的串行算法和并行算法，使用4个数据集测试算法的执行时间。由于数据集的稠密程度不同，对这些数据集设置了不同的最小支持度，retail、kosarak、pumsb_star、chess的最小支持度阈值分别设置为0.3%、0.8%、45%、75%。

　　在单机环境下，串行算法对retail、kosarak、pumsb_star、chess的执行时间分别为1 879 s、721 s、906 s、3 265 s。在Hadoop平台上，并行AprioriTid算法的执行时间如图2所示。当节点数为2时，并行算法对4个数据集的执行时间都小于串行算法的执行时间，随着节点数的增加，并行算法的执行时间不断减少。由此可见，并行AprioriTid算法能取得较高的执行效率。

　　3.2 算法的可扩展性测试

　　使用1个节点对DB规模的数据执行算法的时间表示为t1×DB，使用m个节点对m×DB规模的数据执行算法的时间表示为tm×m×DB，则算法的可扩展性[8]定义为：scaleup（DB，m）=t1×DB/tm×m×DB。

　　对数据集mushroom和accidents测试并行AprioriTid算法的可扩展性。mushroom、accidents的最小支持度阈值分别设置为25%、70%，当使用m个节点时，将数据集复制m份上传到HDFS，实验结果如图3所示。从实验结果可以看出，对于两个数据集，并行AprioriTid算法都取得了较好的可扩展性。

　　4 结论

　　AprioriTid算法是一种时间复杂度较高的关联规则挖掘算法，在单机环境下对大数据的执行效率不高。针对这个问题，本文给出了一种AprioriTid算法的MapReduce并行化方法，该方法利用多个节点对数据分片并行计算候选项集的支持度，缩短了发现频繁项集的时间。使用多个数据集测试了算法的性能，实验结果表明，并行AprioriTid算法具有较高的执行效率，适合云计算环境下对大数据挖掘关联规则。

　　参考文献

　　[1] AGRAWAL R， SRIKANT R. Fast algorithms for mining association rules[C]. Proceedings of the 20th International Conference on Very Large Data Bases. Santiago，Chile， 1994： 487-499.

　　[2] 向程冠，姜季春，陈梅，等.AprioriTid算法的改进[J].计算机工程与设计，2009，30（15）：3581-3583.

　　[3] DEAN J， GHEMAWAT S. MapReduce： simplified data processing on large clusters[J]. Communications of the ACM， 2008，51（1）：107-113.

　　[4] The apache software foundation. Hadoop[EB/OL]. （2015-07-08） [2015-08-16]. http：//hadoop.apache.org/.

　　[5] 廖宝魁，孙隽枫.基于MapReduce的增量数据挖掘研究[J].微型机与应用，2014，33（1）：67-70.

　　[6] 亢丽芸，王效岳，白如江.MapReduce原理及其主要实现平台分析[J].现代图书情报技术，2012（2）：60-67.

　　[7] CHUCK L. Hadoop实战[M].韩冀中，译.北京：人民邮电出版社，2011.

　　[8] 杨勇，王伟.一种基于MapReduce的并行FP-growth算法[J].重庆邮电大学学报（自然科学版），2013，25（5）：651-657.