一种基于Hadoop的并行关联规则算法.pdf

第27卷第1期天津理工大学学报Vol．27No．1
2011年2月JOURNALOFTIANJINUNIVERSITYOFTECHNOLOGYFeB．2011

文章编号:1673-095X(2011)01-0025-04

一种基于Hadoop的并行关联规则算法

余楚礼1，肖迎元1，尹波2
(1．天津理工大学计算机与通信工程学院，天津300384;2．21世纪恒丰环保节能工程有限公司，天津300384)

摘要:在挖掘大型数据库的关联规则时，使用并行计算是必需的．针对传统的并行计算，存在不能处理节点失效，
难以处理负载均衡等问题，提出基于Hadoop架构实现并行关联规则计算的设计．理论和实验证明，基于Hadoop的并
行关联规则计算，能处理节点失效，并且能做到节点负载均衡．
关键词:关联规则;Hadoop;云计算;数据挖掘
中图分类号:TP312文献标识码:Adoi:10．3969/j．issn．1673-095X．2011．01．007

AparallelalgorithmforminingfrequentitemsetsonHadoop

YUChu-li1，XIAOYing-yuan1，YINBo2
(1．SchoolofComputerandCommunicationsEngineering，TianjinUniversityofTechnology，Tianjin300384，China;
2．21stCentruyHengfengEnvironmentalConservtionEngineeringCo．，Ltd，Tianjin300384，China)

ABstract:ParallelcomputeisrequiredinminingfrequentitemsetsonlargedataBases．MPIcan＇thandlenodefailure，andit
＇sdifficulttosolveloadBalance．SoweproposeparallelminingfrequentitemsetsonHadoop．Theoreticalandexperimental
resultsshowparallelminingfrequentitemsetsonHadoopcanhandlenodefailureandcansolveloadBalance．
Keywords:associationrules;Hadoop;cloudcompute;datamining

关联规则是用来描述事物之间的联系，是用来
1Hadoop简介
挖掘事物之间的相关性．挖掘关联规则的核心是通
过统计数据项获得频繁项集，现有的算法主要有Hadoop［7］是一个分布式基础架构，可以在不了
Apriori［1］，PARTITION［2］、FP2growth［3］及抽样算法解分布式底层细节的情况下，开发分布式或并行应
等，这些算法是基于单节点的算法．但是，现在的数用程序，充分利用集群的威力高速运算和存储，它也
据库越来越大，达到了TB级甚至更大，采用传统的是云计算的主要架构之一．Hadoop具有以下一些
算法将非常缓慢，甚至不能服务于有时限性的问题．特点:
为此，研究人员提出了多种并行挖掘算法，主要有1)扩容能力:能可靠地存储和处理PB级别
CD(countdistriBution)、DD(datadistriBution)、CaD数据．
(candidatedistriBution)［4］、FDM［5］和FMAGF［6］等．这2)成本低:可以通过普通微机组成的集群来分
些算法解决了挖掘效率的问题，但是由于并行计算发以及处理数据．这些服务器群总计可达数千个
是由很多计算节点组成，节点失效、负载不易均衡带节点．
3):，Hadoop
来的问题仍然会给计算带来很多阻碍．高效率通过分发数据可以并行地
的处理数据，这使得处理非常的快速．4可靠性:Ha-

收稿日期:2010-11-10．
基金项目:国家863基金(2009AA01Z152);天津市自然科学基金(08JCYBJC12400);中小企业创新基金(08ZXCXGX15000)．
作者简介:余楚礼(1981—)，男，硕士研究生．
通讯作者:肖迎元(1969—)，男，博士，副教授，E-mail:[e-mail]．
·26·天津理工大学学报第27卷第1期

doop能自动地维护数据的多份复制，并且在任务失CD算法有两个缺陷:
败后能自动地重新部署计算任务．1)某个计算节点失败，会导致整个计算失败．
2)计算节点的速度存在差异时，计算时间由计
算性能差的节点决定，这样会导致计算资源的浪费．
基于Hadoop来改进CD算法，可以解决上述的
问题:
1)在Hadoop上运