kaiyun官方注册
您所在的位置: 首页> 嵌入式技术> 设计应用> AprioriTid算法的MapReduce并行化实现
AprioriTid算法的MapReduce并行化实现
(玉林师范学院 数学与信息科学学院,广西 玉林 537000)
周国军,梁燕红,唐 微
摘要:为解决AprioriTid算法对大数据执行效率不高的问题,根据Hadoop平台的MapReduce模型,分析了AprioriTid算法的并行化方法,给出了并行化的主要步骤和Map、Reduce函数的描述。与串行的AprioriTid算法相比,并行算法利用了多个节点的计算能力,缩短了从大数据集中挖掘关联规则的时间。对并行算法的性能进行了测试,实验结果表明,并行AprioriTid算法具有较高的执行效率和较好的可扩展性。
Abstract:
Key words :

摘 要: 为解决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在中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模型

001.jpg

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

  在实际的应用中,不同的数据文件通常采用不同的记录格式,为了将记录解析成合适的对,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分解出来,输出键/值对。Reduce函数统计项ij的支持度计数count,将满足最小支持度阈值minsup的项ij及其支持度计数输出到LPath1目录的文件中。Map、Reduce函数描述如下:

  map(key=TID,value=t){

  for each项ij of t

  emit();

  }

  reduce(key=ij,values={1,1,…}){

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

  if (count≥minsup)emit ();

  }

  (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以键/值对传递给Reduce函数。cleanup方法将Ck保存到CPathk目录的一个文件中。Reduce函数统计候选k-项集的支持度计数,将满足最小支持度阈值的频繁k-项集及其支持度计数输出到LPathk目录的文件中。

  Map函数描述如下:

  setup(){

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

  Ck=apriori-gen(Lk-1);

  Ck=}3]}T@WSWOWB92]K}(DD02I.jpg

  }

  map(key=TID,value=t){

  Ct=}3]}T@WSWOWB92]K}(DD02I.jpg;//初始化Ct

  Ct={c∈Ck|(c-c[k])∈t.set-of-itemsets∧(c-c[k-1])∈t.set-of-itemsets};

  if(Ct≠}3]}T@WSWOWB92]K}(DD02I.jpg){

  Ck+=

  for each 候选k-项集c∈Ct

  emit();

  }

  cleanup(){

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

  }

  Reduce函数描述如下:

  reduce(key=c,values={1,1,…}){

  count=|values|;

  if(count≥minsup)emit();

  }

  (6)如果Lk=}3]}T@WSWOWB92]K}(DD02I.jpg,则算法结束;否则,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%。

002.jpg

  在单机环境下,串行算法对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算法都取得了较好的可扩展性。

003.jpg

 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.


此内容为AET网站原创,未经授权禁止转载。
Baidu
map