基于MapReduce的DHP算法并行化研究
2016-07-19周国军吴庆军
周国军 吴庆军
(玉林师范学院数学与信息科学学院 广西 玉林 537000)
基于MapReduce的DHP算法并行化研究
周国军吴庆军
(玉林师范学院数学与信息科学学院广西 玉林 537000)
摘要针对DHP(direct hashing and pruning)算法对大数据挖掘关联规则存在执行时间过长、效率不高的问题，对DHP算法的并行化策略进行了研究。根据云计算平台Hadoop的MapReduce并行编程模型，设计了一种并行DHP算法，给出了算法的总体流程和Map函数、Reduce函数的算法描述。与DHP算法相比，并行算法利用了Hadoop集群强大的计算能力，提高了从大数据集中挖掘关联规则的效率。通过实例分析了并行DHP算法的执行过程，在多个数据集上进行了实验。实验结果表明：并行DHP算法对大数据具有较好的加速比和可扩展性。
关键词MapReduce Hadoop DHP算法关联规则
0引言
关联规则挖掘是数据挖掘领域的一个重要研究方向，其目标是从事务数据库中发现项与项之间的相关联系。如何高效地找出所有的频繁项集是关联规则挖掘算法要解决的主要问题。DHP算法[1]在Apriori算法[2]的基础上利用哈希技术修剪候选项集和事务数据库，提高了生成频繁项集的效率，是公认的非常有效的算法。由于DHP算法具有很好的性能，在文本数据挖掘[3]、Web遍历路径挖掘[4]等方面得到了广泛应用。已经有较多的文献对DHP算法的Hash函数选取、Hash表结构优化、冗余事务的修剪策略等进行了研究和改进，这些改进算法进一步提高了发现频繁项集的效率。但是，DHP算法是一种时间复杂度较高的算法，受单机存储空间和计算能力的限制，DHP算法及其改进的串行算法对大数据集挖掘关联规则存在执行时间太长、效率较低的性能瓶颈问题。
云计算[5]是近年来兴起的一种计算模式，优势是提供了海量的存储空间和强大的计算能力，将云计算技术应用于数据挖掘领域是一个新的发展趋势[6]。Google公司提出的MapReduce[7]是一种简洁高效的并行编程模型，该模型屏蔽了底层实现细节，降低了编程难度。MapReduce模型将复杂的处理任务抽象成Map函数和Reduce函数，Map、Reduce函数在分布式集群的节点上并行执行，从而达到了对大规模计算任务进行高效处理的要求[8]。Apache软件基金会开发的Hadoop[9]是一个开源的分布式计算平台，该平台以高可靠性、高扩展性等优点得到了学术界的认可和工业界的广泛应用。Hadoop实现了MapReduce模型，用户可以在大量廉价设备组成的Hadoop集群上运行MapReduce应用程序。
本文根据Hadoop平台的MapReduce模型，对DHP算法的并行化方法进行了分析，设计了一种并行DHP算法。该算法利用Hadoop集群中各节点的计算能力，缩短了对大数据集挖掘关联规则的时间，具有较好的加速比和可扩展性。最后，通过实验验证了并行DHP算法的性能。
1Hadoop平台的MapReduce模型
Hadoop的MapReduce框架处理大数据集的一般过程是：将大数据集分解成许多数据分片，JobTracker进程将MapReduce任务分配给TaskTracker节点，TaskTracker进程读取一个(或多个)数据分片、并执行MapReduce任务。
在Hadoop中,MapReduce应用程序的基本结构包括主函数、Map函数和Reduce函数。主函数对每个MapReduce作业所需的参数进行配置，并在作业启动后对程序的执行流程进行控制。Map函数定义为一个类(称为Mapper类)，在Mapper类中可以定义setup、map和cleanup等方法。对于每个Map任务，setup方法只在任务开始之前调用一次，cleanup方法只在任务结束之前调用一次。相应地，Reduce函数定义为一个称为Reducer的类，在Reducer类中可以定义setup、reduce和cleanup等方法，对于每个Reduce任务，setup和cleanup方法只调用一次。map、reduce方法的一般形式[10]表示如下：
map：(K1,V1) →list(K2,V2)
reduce：(K2,list(V2)) →list(K3,V3)
其中，(K1,V1)是数据分片的一条记录经过MapReduce框架解析后的键/值对表示形式，list(K2,V2)、list(K3,V3)分别是map和reduce方法输出的键/值对列表。
2DHP算法的并行化策略
文献[1]给出了DHP算法的详细描述，DHP算法的三个部分都能采用MapReduce模型将其并行化，说明如下：
第一部分对候选1-项集的支持度计数、哈希表的桶计数进行并行化。与词频统计方法相似，Map函数对数据分片的每个事务t分解出所有项ij，计算出所有2-项子集x的哈希桶地址addr=h2[x]，输出
第二部分对事务数据库Dk的修剪、候选k-项集的支持度计数和哈希表的桶计数进行并行化。该部分是一个迭代计算频繁k项集Lk的过程，每次迭代过程由一个MapReduce任务完成，需要解决3个主要问题。①控制迭代次数。简单的方法是在主函数中由循环条件 (|{x|Hk[x]≥s}|≥LARGE) 控制MapReduce任务迭代的次数。②Map函数如何读取所有频繁(k-1)-项集Lk-1和哈希表Hk以生成所有候选k-项集Ck。在主函数中将Lk-1和Hk设置为分布式缓存文件，由Hadoop的MapReduce框架将Lk-1和Hk分发到执行Map任务的TaskTracker节点就解决了这个问题。③如何输出修剪后的事务数据库Dk+1。简单的方法是在Hadoop的文件系统HDFS中创建一个目录，Map函数将修剪后的数据分片以文件形式写入到HDFS中。该方法的优点是：第k+1次迭代只需在主函数中设置MapReduce任务的输入路径为Dk+1的目录，Map函数便可读取Dk+1的数据分片。
第三部分对事务数据库Dk的修剪和候选k-项集的支持度计数进行并行化。在该部分中，主函数除了控制程序流程之外，还需要完成以下计算：在第一个MapReduce任务执行前生成所有候选k-项集Ck,即执行gen_candidate(Lk-1,Hk,Ck)，并将Ck分发给执行Map任务的节点。在每个MapReduce任务结束后执行Ck+1=apriori_gen(Lk)，并在下一次迭代前分发Ck+1。
3并行DHP算法设计与描述
3.1算法的总体流程及描述
并行DHP算法的总体流程如图1所示，其中s是最小支持度阈值，LARGE是预定义的阈值。
图1 并行DHP算法流程图
与DHP算法相对应，并行DHP算法也分为三部分。算法的流程控制由主函数实现，各部分的并行计算由Map和Reduce函数实现。Map函数和Reduce函数描述如下：
Part1的Map函数：
//TID是事务编号，t是事务的项列表
map(key=TID,value=t){
foreach项ij∈t
output(
foreach2-项子集x∈t{
addr=h2(x);
//“*”是哈希地址addr的前缀字符
output(<*addr,1>);
}
}
Part1的Reduce函数：
reduce(key=ij或key=*addr,values=list(1)){
count=0;
foreach1invalues
count++;
/* 输出满足条件的频繁1-项集及支持度、
输出哈希表的桶地址及计数值 */
if(count≥s)output(
}
Part2的Map函数：
setup(){
//生成候选k-项集
gen_candidate(Lk-1,Hk,Ck);
Dk+1= ?;
}
map(key=TID,value=t){
foreacht的k-项子集c(=ti1...tik)
if(c∈Ck) {
output(
for(j=1;j≤k;j++)a[ij]++;
}
//删除t中不必要的项
for(i=0,j=0;i<|t|;i++)
if(x的所有k-项子集y都满足Hk[hk(y)]≥s){
addr=hk+1(x);
output(<*addr,1>);
for(j=1;j≤k+1;j++)a[ij]++;
}
}
//删除数据分片中不必要的事务
}
}
cleanup(){
在HDFS中创建一个目录inputk+1；
将Dk+1分片保存在inputk+1目录的一个文件中；
}
Part2的Reduce函数：
reduce(key=c或key=*addr,values=list(1)){
count=0;
foreach1invalues
count++;
/* 输出满足条件的频繁k-项集及支持度、
输出哈希表的桶地址及计数值 */
if(count≥s)output(
}
Part3的Map函数：
setup(){
读取Ck;
Dk+1= ?;
}
map(key=TID,value=t){
foreacht的k-项子集c(=ti1...tik)
if(c∈Ck) {
output(
for(j=1;j≤k;j++)a[ij]++;
}
//删除t中不必要的项
for(i=0,j=0;i<|t|;i++)
//删除数据分片中不必要的事务
}
cleanup(){
在HDFS中创建一个目录inputk+1；
将Dk+1分片保存在inputk+1目录的一个文件中；
}
Part3的Reduce函数：
reduce(key=c,values=list(1)){
count=0;
foreach1invalues
count++;
//输出满足条件的频繁k-项集及支持度
if(count≥s)output(
}
3.2算法的实例分析
下面通过一个实例来说明并行DHP算法的执行过程，如图2所示。
图2 并行DHP算法执行过程示例
在该实例中，使用文献[1]给出的示例数据库。假定Map、Reduce任务数各为2，选取s=2、LARGE=3，选取的Hash函数定义如下：
hk({i1,i2,…,ik})=((order(i1)+order(i2)+…+order(ik-1))×10+order(ik))modp
对于该实例，算法的执行过程需要3个MapReduce任务去完成。第1个MapReduce任务执行Part1的过程，得到L1和H2。由于条件 |{x|H2[x]≥s}|≥LARGE成立，第2个MapReduce任务执行Part2的过程，得到L2、H3和D3。由于条件 |{x|H3[x]≥s}|≥LARGE不成立，第3个MapReduce任务执行Part3的过程，得到L3和D4。由于|D4|=0，算法结束。
算法的执行结果与文献[1]的结果相同，可见，本文设计的并行DHP算法是正确的。
4实验结果及分析
4.1实验环境与实验数据
实验环境是7台配置相同的计算机组成的Hadoop集群，其中1台作为JobTracker节点,6台作为TaskTracker节点。计算机的配置是：双核2.93GHzCPU、2GB内存和100M网卡。使用的软件是：Ubuntu12.04LTS、Hadoop1.2.1、JDK1.7.0_51。
使用Java语言实现了文献[1]提出的DHP算法和本文设计的并行DHP算法，并对数据集进行了3组实验，分别测试算法的运行时间、加速比和可扩展性。实验选取的数据集来自网站http://fimi.ua.ac.be/data/。为了便于测试算法的可扩展性，从数据集webdocs中分别随机抽取1×105、2×105、3×105、4×105、5×105、6×105条记录作为6个实验数据集。
4.2算法的运行时间测试
使用4个数据集测试算法的运行时间，retail、kosarak是稀疏型数据集，设置了较小的支持度阈值，accidents、pumsb是稠密型数据集，设置了较大的支持度阈值。为了便于与DHP算法比较，分别使用1个和2个TaskTracker节点测试并行DHP算法的运行时间。实验结果如表1所示。
表1 DHP算法与并行DHP算法的执行时间
从表1可以看出，使用1个TaskTracker节点，并行DHP算法在4个数据集上的运行时间都大于DHP算法；使用2个节点，除retail之外，并行DHP算法在其余3个数据集上的运行时间均小于DHP算法。retail是一个较小(4.2MB)的稀疏型数据集，对该数据集挖掘频繁项集的计算时间较小。但是，并行DHP算法需要5个MapReduce任务才能完成对retail的数据处理，每个任务的初始化和启动所用的时间相对于计算时间有较大的比重，所以总的运行时间要大于DHP算法。
由此可见，并行DHP算法不适合对计算量小的数据集挖掘频繁项集；对于计算规模较大的数据集，并行DHP算法显著减少了挖掘频繁项集的时间，提高了算法的执行效率。
4.3算法的加速比测试
加速比是评价并行算法性能的重要指标之一，文献[11]给出了加速比的计算公式，定义如下：
Sp=t1/tp
(1)
其中，t1、tp分别表示在1个节点和p个节点上的执行时间。
使用表1列出的4个数据集和最小支持度测试并行DHP算法的加速比，实验结果如图3所示。从图3可以看出，对于计算规模较小的数据集retail和kosarak，算法表现出很低的加速比，这是因为随着计算节点数的增加，在节点之间的通信开销相对于计算时间的比重显著增大，不能取得较好的加速比；对于计算规模较大的数据集accidents和pumsb，算法取得了较好的加速比。
图3 并行DHP算法的加速比
4.4算法的可扩展性测试
可扩展性是指算法能否随节点数的增加而按比例提高。文献[12]给出了等速度可扩展性的计算公式，定义如下：
(2)
其中，w、p是问题规模和处理机规模，w′、p′是扩展后的问题规模和处理机规模。
对从webdocs中随机抽取的6个数据集(数据规模成倍增加)进行可扩展性测试，实验结果如图4所示。实验结果表明，对于两种不同的最小支持度，并行DHP算法都能取得较好的可扩展性。
图4 并行DHP算法的可扩展性
5结语
DHP算法是一种经典的关联规则挖掘算法，受单机计算能力和内存的限制，DHP算法对大数据挖掘频繁项集存在执行时间过长、效率不高的问题。针对该问题，本文根据Hadoop平台的MapReduce并行编程模型对DHP算法的并行化策略进行了研究，设计了一种基于MapReduce模型的并行DHP算法，通过实例分析了算法的执行过程和正确性。与DHP算法相比，本文设计的并行算法利用了Hadoop集群强大的计算能力，缩短了对大数据集挖掘频繁项集的时间，具有较高的执行效率。在多个数据集上对算法进行了测试，实验结果表明：并行DHP算法对大数据集具有较好的加速比和可扩展性。
参考文献
[1]ParkJS,ChenMS,YuPS.Aneffectivehash-basedalgorithmforminingassociationrules[C]//Proceedingsofthe1995ACMSIGMODInternationalConferenceonManagementofData.NewYork:ACM,1995,24(2):175-186.
[2]AgrawalR,SrikantR.Fastalgorithmsforminingassociationrules[C]//Proceedingsofthe20thInternationalConferenceonVeryLargeDataBases.Santiago,Chile,1994:487-499.
[3]HoltJD,ChungSM.Efficientminingofassociationrulesintextdatabases[C]//ProceedingsoftheEighthInternationalConferenceonInformationandKnowledgeManagement.NewYork:ACM,1999:234-242.
[4] 王涛伟,周必水.基于DHP的频繁遍历路径挖掘算法[J].杭州电子科技大学学报,2005,25(5):60-63.
[5]ArmbrustM,FoxA,GriffithR,etal.Abovetheclouds:aBerkeleyviewofcloudcomputing[R/OL].2009-02-10[2015-02-15].http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-28.html.
[6] 周丽娟,王翔.云环境下关联规则算法的研究[J].计算机工程与设计,2014,35(2):499-503.
[7]DeanJ,GhemawatS.MapReduce:simplifieddataprocessingonlargeclusters[J].CommunicationsoftheACM,2008,51(1):107-113.
[8] 李建江,崔健,王聃,等.MapReduce并行编程模型研究综述[J].电子学报,2011,39(11):2635-2642.
[9]TheApacheSoftwareFoundation.Hadoop[EB/OL].2014-12-12[2015-02-15].http://hadoop.apache.org/.
[10] 黄立勤,柳燕煌.基于MapReduce并行的Apriori算法改进研究[J].福州大学学报(自然科学版),2011,39(5):680-685.
[11] 陈兴蜀,张帅,童浩,等.基于布尔矩阵和MapReduce的FP-Growth算法[J].华南理工大学学报(自然科学版),2014,42(1):135-141.
[12] 陈军,莫则尧,李晓梅,等.大规模并行应用程序的可扩展性研究[J].计算机研究与发展,2000,37(11):1382-1388.
RESEARCH ON PARALLELISATION OF DHP ALGORITHM BASED ON MAPREDUCE
Zhou GuojunWu Qingjun
(School of Mathematics and Information Science,Yulin Normal University,Yulin 537000,Guangxi,China)
AbstractDHP algorithm is confronted with the problems in association rules mining for big data such as long execution time and low efficiency,etc.In order to solve the problems,we studied the parallelisation strategy of DHP algorithm.According to MapReduce parallel programming model of cloud computing platform Hadoop,we designed a parallel DHP algorithm,presented the overall flow of the algorithm and the algorithm descriptions of Map function and Reduce function.Compared with DHP algorithm,the parallel DHP algorithm makes use of the powerful computing capacity of Hadoop cluster,improves the efficiency of mining association rules from big data.We analysed the execution process of parallel DHP algorithm by example,and carried out experiments on a couple of datasets.Experimental results showed that the parallel DHP algorithm has good speedup and scalability on big data.
KeywordsMapReduceHadoopDHP algorithmAssociation rules
收稿日期：2015-03-03。广西高校科学技术研究立项项目(LX20 14300)。周国军，讲师，主研领域：数据挖掘，云计算。吴庆军，副教授。
中图分类号TP311.1
文献标识码A
DOI:10.3969/j.issn.1000-386x.2016.06.012
