基于MapReduce的频繁项集并行挖掘算法.pdfVIP

第32卷第9期 计算机应用与软件 Vo1．32 No．9 2015年9月 ComputerApplicationsandSoftware Sep．2015 基于MapReduce的频繁项集并行挖掘算法 马 强 杨金民 (湖南大学信息科学与工程学院 湖南 长沙410083) 摘 要 现有FP-growth频繁集挖掘算法在处理大数据时存在时空效率不高的问题，且内存的使用随着数据的增加 已经无法满足 把待挖掘数据压缩存储在单个内存中，为此，提出一种基于 MapReduce模型的频繁项集并行挖掘算法。该算法采用一种基于key／ value键值对直接扫描value寻找条件模式基的方式，同时通过在原有FP—tree树节点中新增一个带频繁项前缀的域空间来构建一颗 新的条件模式树 NFP—tree，使得对一项频繁项的条件模式基进行一次建树一次遍历就可以得到相应的频繁项集。对所提出的算法 在Hadoop平台进行了验证与分析，实验结果表明该算法效率较传统FP—growth算法平均提高16．6％。 关键词 频繁项集 FP—rgowth MapReduce 条件模式基 NFP—tree 并行 中图分类号 TP3 文献标识码 A DOI：10．3969／j．issn．1000—386x．2015．09．004 APARALLELFREQUENTITEMSETSMININGALGORITHM BASEDoNMAPREDUCE MaQiang YangJinming (CollegeofInformationScience0 Engineering，HunanUniversity，Changsha410083，Hunan，China) Abstract ExistingminingalgorithmsofFP-growthfrequentitemsethaslow timeandspaceefficiencyproblem whendealingwith large data，andwiththedataincreasethememo~usagecallnolongersatisfytocompressandstorethedatatobemindedinasin~ememo~． Therefore，thepaperproposesaMapReducemodel—basedparallelminingalgorithm forfrequentitemset．Thealgorithm adoptsawaywhich directlyscansvaluebasedonkey·valuepairstolookfortheconditional patternbase．Meanwhile，italsoconstructsanew conditionpattern treeNFP—treebyaddingadomainspacewithfrequentitem prefixinori~nalFP—treetreenode，andhtatmakesitpossibletogetthe correspondingfrequentitemsetsbyconstructinghtetreeonceandtraverseonceonhteconditionpattern baseofafrequentitem．Th isalgorithm isverifiedandanalysedon Hadoopplatform ，experimental resultsshow thatthealgorithm ismoreefficienthtan htetraditional FP—rgowth algorithm byna averageincreaseof16．6％ ． Keywords Frequentitemsets FP--rgowth MapReduce Conditionalpattern NFP·t·ree Parallel