pfponcantree一种基于mapreduce的并行频繁模式增量挖掘算法-肖文.pdf

《pfponcantree一种基于mapreduce的并行频繁模式增量挖掘算法-肖文.pdf》由会员分享，可在线阅读，更多相关《pfponcantree一种基于mapreduce的并行频繁模式增量挖掘算法-肖文.pdf（9页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、CN 431258TPISSN 1007130X计算机工程与科学Computer Engineering&Science第40卷第1期2018年1月V0140，No1，Jan2018文章编号：1007130X(2018)01001509PFPonCanTree：一种基于MapReduce的并行频繁模式增量挖掘算法肖 文，胡 娟，周晓峰(河海大学文天学院，安徽马鞍山243000)摘 要：频繁模式挖掘是最重要的数据挖掘任务之一，传统的频繁模式挖掘算法是以“批处理”方式执行的，即一次性对所有数据进行挖掘，无法满足不断增长的大数据挖掘的需要。MapReduce是一种流行的并行计算模式，在并行数据挖掘领

2、域已得到了广泛的应用。将传统频繁模式增量挖掘算法CanTree向MapReduce计算模型进行了迁移，实现了并行的频繁模式增量挖掘。实验结果表明，提出的算法实现了较好的负载均衡，执行效率有明显提升。关键词：数据挖掘；频繁模式挖掘；增量挖掘；MapReduce；Hadoop；PFP中图分类号：TP311 文献标志码：Adoi：103969jissn1007130X201801003PFPonCanTree：A parallel frequent patternsincremental mining algorithm based on MapReduceXIAO Wen，HU Juan，ZHOU

3、 Xiaofeng(Wentian College。Hohai University，Maanshan 243000，China)Abstract：Frequent pattern mining is one of the most important data mining tasksTraditional frequent pattern mining algorithmsare executed in a。batch”mode，that is，all the data are mined in onetime，SO they cannotmeet the needs of the eve

4、rgrowing bigdata miningMapReduce is a popular parallelcomputing modeland has been widely used in the field of parallel data miningIn this paper，we migratethe traditional frequent pattern incremental mining algorithm CanTree to the MapReduce computingmodel，achieving a parallel frequent pattern increm

5、ental miningalgorithmThe experimental results showthat the proposed algorithm achievesbetterload balancing and improvesthe execution efficiency significantlyKey words：data mining；frequent pattern mining；incremental mining；MapReduce；Hadoop；PFP引言频繁模式挖掘是最重要的数据挖掘任务之一，也是很多数据挖掘任务的基础性任务，自从它被提出以来口，受到了越来越多研究

6、者的关注。频繁模式挖掘的目的是发现事务数据中频繁出现的模式，从而发现事物项之间存在的隐含关联。已经提出的频繁模式挖掘算法大致可以分为三类：第一类是通过迭代产生候选频繁模式并对它们分别进行计数，将模式的支持度与最小支持度比较来获得频繁模式，典型的算法是Apriori2及其一系列的改进算法；第二类是不产生候选模式，通过将数据集压缩成一种特殊的数据结构(一般为树结构)，在特定结构上进行遍历来直接产生频繁模式，典型的算法有FPGrowthE 3|、LPTreeE4、FIUTc、IFP、FPLTPL71等；第三类是将水平格式的数据集转换成垂直格式，通过交运算来得到频繁模式，典型*收稿日期：2016-12

7、08；修回日期：2017-0215基金项目：安徽省高校自然科学研究项目(KJ2016A623)通信地址：243000安徽省马鞍山市河海大学文天学院Address：Wentian College，Hohai University，Maanshan 243000，Anhui，PRChina万方数据16 Computer Engineering 8L Science计算机工程与科学2018，40(1)的算法有Eclat等。上述列举的频繁模式挖掘算法都是基于被挖掘的数据集是“静态的、不变的”这样一个基本的假设，以“批处理”的方式对整个数据集进行挖掘。但是，在现实世界中，数据集却是始终变化的，不断有新的

8、事务数据插入到数据集中，导致产生新的频繁模式，或是使原来频繁的模式不再频繁。对于更新后的新数据集，如果仍以批处理的方式对其进行重新挖掘，其效率十分低下。在不断变化的数据集中进行频繁模式挖掘，需要充分利用前一阶段的挖掘结果，以“增量挖掘”的方式进行，提高挖掘效率。为实现频繁模式的增量挖掘，研究者已经提出了一些解决的方法，如基于Apriori算法的增量挖掘算法FUP(Fast Update)L8J、FUP2(Fast Update2)E、UWEP(UpdateWithEarly Pruning)1、GSP(Generalized Sequential Patterns)11|、PreLarge12

9、等，基于树结构的AFPIM(AdjustingFrequent Pattern Tree Structures)1 3|、FELINE(基于CATS-Tree(Compressed&Arraged Tran-scation Sequence Tree)结构)14、CanTree(Canonicalorder Tree)Ds3、BIT(BatchlncrementalTree)161算法等。基于Apriori的增量挖掘算法虽然充分利用了对原始数据库挖掘过程中产生的所有计数和挖掘结果，但仍需要迭代产生候选模式并进行多次计数，不适合大量数据集的增量挖掘任务。基于树的增量挖掘方法虽然在一定程度上解决了

10、增量挖掘的问题，但需要将所有数据以树的形式存储在内存中，对于存储空间需求量很大。频繁模式挖掘是一种计算、存储密集型计算任务，在当前大数据时代，传统增量挖掘算法无法满足海量数据挖掘的需要，主要体现在：在单一计算机上无法存储所需要挖掘的所有数据及挖掘过程中产生的中间结果，所需要的内存远远超过单一机器的存储量，计算时间太长无法忍受等。需要开发分布式、并行的增量关联规则挖掘算法解决大数据中频繁模式增量挖掘的问题。MapReduce是一种由Google提出的易用且功能强大的并行编程模型，具有使用简单、自动容错、负载均衡、伸缩性好等优点，已经有了很多将传统频繁模式挖掘算法向MapReduce模型进行迁移的

11、研究173 6|，很大程度上解决了大数据中频繁模式挖掘的问题。在MapReduce计算模型中，一个计算任务被分为Map和Reduce两个方法。Map方法在多个结点上运行，处理一个或多个本地的数据分片；Reduce方法处理Map方法输出的中间结果，也可以多个Reduce方法并行执行；所有Reduce方法的输出合并后得到最后的结果。MapReduce计算模型流程图如图1所示。Inputs Map tasks Reduce tasks OutputsFigure 1 MapReduce parallel programming model图1 MapReduce并行编程模型HadoopE 371是M

12、apReduce的一个开源实现，同时提供了一个分布式文件系统HDFS(HadoopDistribtued File System)。HDFS是一个用来存储超大文件的文件系统，可以自动地对超大文件进行分片及负载均衡。HDFS将分片存储在不同的结点上，同时在存储分片的结点上执行MapReduce计算任务，通过数据本地化、减少IO来提高运行效率。一个Hadoop集群可以运行在普通的商用计算机上，包括一个Master结点和多个Slave结点。本文主要贡献为：(1)提出了PFPonCanTree算法，将传统频繁模式增量挖掘算法CanTree向MapReduce计算模型进行了迁移，实现了并行、分布式的频繁

13、模式增量挖掘。(2)设计了并行计算中各结点的负载均衡策略，使得每个结点计算量相对平衡，提高整个算法运行效率。(3)对算法的执行效率进行了定量分析，并通过实验验证了分析结果。本文的组织如下：第2节对有关工作进行了综述；第3节提出基于MapReduce计算模型的并行频繁模式增量挖掘算法PFPoncanTree，并进行了效率分析；第4节介绍了实验环境和方案，并对实验结果进行了分析；第5节对全文进行了总结，并对下一步工作进行了展望。2 问题定义与相关研究21 问题描述与符号定义设J一i。，iz，i。)为项的集合；P是一个模式，P一i，i：，i。)j，包含k个项的模式称为是一模式；一个事务丁的定义为T一

14、(tid，X)，其中tid为事务标识，X为一个模式；一个事务数据库D是多个T的集合。万方数据肖 文等：PFPonCanTree：一种基于MapReduce的并行频繁模式增量挖掘算法 17模式y在事务数据库D中的支持度为D中包含模式y事务的比例。定义为：Sup。(y)一地到羔型染警卫皇叫 u如果一个模式被称为是频繁的，则其支持度不小于用户给定的一个阈值(盯)，这个阈值也称为最小支持度(rainsup)。频繁模式具有单调特性，即：如果一个模式是频繁的，则其所有子模式都是频繁的。相应地，如果一个模式不是频繁的，则其所有的超模式都是不频繁的。对于频繁模式的增量挖掘问题，定义如表1所示的符号。Table

15、 1 Symbol description表1符号说明符号 意义原始事务数据库D中事务数新插入的事务集T中的事务数更新事务数据库，DUTU中的事务数增量挖掘，即是要充分利用对D的已有挖掘结果，对T进行分析挖掘，提高对【，进行挖掘的效率。22 FELINE(CATs-Tree)Cheung等141于2003年设计了一种特殊的树结构CATSTree用于实现增量模式挖掘。构造D的CATS-Tree只需要扫描数据集一次，依次将每一条事务T中的所有项插入树中。在插入事务T时，从root节点开始，将丁中的项和当前节点的每一个孩子比较，如果相同就合并，将当前节点改变为合并的节点，并比较下一项；如果没有相同的

16、项，则将T中的项做为一条新的路径插入CATSTree中。如果树中一个节点的支持度比它的祖先高，则将它与其祖先交换，保证每一个节点的支持度都不大于它的祖先。构造CATS-Tree完成后，可以使用传统的FPGrowth算法在CATS-Tree上进行频繁模式挖掘。虽然CATSTree具有构造简单、保存了D中的所有信息、插入新事务方便等特点，但它存在两个明显的缺点：一是CATSTree的构造过程中存在搜索公共项，随着局部支持度的变化交换和合并节点等操作，增加了额外的系统开销；二是根据CATS-Tree的特点，在使用FPGrwoth算法进行挖掘阶段时从向上和向下两个方向遍历才能得到一个项的条件模式基，会

17、造成大量的系统负载。Z3 CanTree为了克服CATS-Tree的缺点，Leung等口53在2007年提出了CanTree。CanTree与CATS-Tree相同，也是将事务中的所有项都插入到树中，但在插入事务之前，会将事务中的项按照一个预先定义的顺序(可以为字典或字母表顺序，也可以使用项的某一种属性)进行排列，使得树中的节点顺序与局部支持度无关，不需要进行额外的交换操作，且大大减少了搜索公共项的系统消耗，并且获得项的条件模式基只需要向上的顺序进行遍历，减小了系统负载。对于新插入的事务集，可使用上述方法很容易地将新事务插入树中，实现增量挖掘。构造完CanTree后，也可以使用类似FPGrow

18、th算法进行挖掘。Hoseini等在2015年提出了一种在CanTree上进行挖掘的新方法3 8|，方法与FP-Growth类似，只不过在创建项的条件模式基时只选择路径上频繁的项，减少了构造的条件树的节点数。从CanTree的特点来分析，它保存了D中的所有信息，插入新事务也非常方便，十分适合用于增量频繁模式挖掘；构造CanTree只需要扫描D一次，且构造过程中没有交换节点的额外操作，搜索公共项的效率也十分高，构造CanTree效率高；对CanTree挖掘的方法与FPGrowth类似，可以对所有项进行分组，将不同分组及组相关事务分发给不同的结点并行执行，可以很方便地将CanTree的构造和挖掘移

19、植到MapReduce计算模型及其开源实现平台Hadoop上，通过并行化实现在大数据集中的频繁模式增量挖掘。24 PFPLi等241在2010年提出了并行FP-Growth算法PFP，实现了将FPGrowth算法向MapReduce计算模型上的移植。PFP算法使用了三个MapReduce任务完成整个并行挖掘工作。使用HDFS将大数据进行自动分片，在第一个任务中对所有项进行并行计数，得到所有频繁项的集合(FList)。将FList进行分组后得到组列表(GList)。第二个任务的主要目的是得到“组相关事务集”，即包含该组中项的所有事务的集合。每个Mapper启动时，加载GList以及本结点所存储的

20、数据分片，输出每一组相关联的事务T，在Reduce阶段进行合并，得到每一组相关联的所有事务T的集合。第三个任务的Map函数对组及组相关联事务使用传统的FP-Growth算法进行挖掘，Reduce函数将所有局部频繁项集合并得到全万方数据18 Computer Engineering&Science计算机工程与科学2018，40(1)局频繁项集。PFP算法执行流程见图2。烈惦聚筲忻7：_P个结点 曩良乏印M印P个结点 霄再覃：Reduco频繁项的集合【HbI)圆t组，4表(G出)叫 数据集分片 卜蘸蚺步胁。害嚣皋Map：l 全局频繁项集l&2数据分区及并行计数，得到频繁项的集合FList4并行和分

21、布式FPGrowth挖掘Figure 2 Flow chart of PFP algorithm图2 PFP算法流程图PFP算法最显著的优点是：多个组及组相关事务之间是相互独立的，不同的组可以在不同的计算结点上独立运算，结点之间不需要相互等待和通信，最合适分布式运算。但是，缺点也很明显：频繁项的分组没有考虑负载均衡，可能会造成有的计算结点计算任务很重，而有的结点计算任务很轻；与一个项相关联的事务可能非常多，无法在一个计算结点上构造FPTree进行频繁项集挖掘；将项和相关事务分发到单独结点时，会产生很大的通信量。3 PFPonCanTree算法31 PFPonCanTree算法概述给定一个原始数

22、据集D及一批新的事务集T，PFPonCanTree算法分两个阶段分别对它们进行处理，共需要4个MapReduce任务完成并行挖掘任务。算法简要描述如下：第一阶段：对D进行并行挖掘。Setp 1 D-分片。将数据集D分割为i个连续部分，并分别存储在P个计算结点上，每一个部分称为一个数据分片。这个过程可以通过将数据集D存储在Hadoop的分布式文件系统HDFS上，由HDFS自动完成。Setp 2 D一并行计数。使用一个MapReduce任务来统计D中所有的项及其支持度。每个Mapper输入一个或多个本结点上存储的数据分片，分片中的所有项以(item，1)的键值对形式发送给Reducer，Reduc

23、er汇总相同项的计数，得到D中所有项的集合I及其支持度。Setp 3-平衡分组。将J中的所有项根据支持度降序排列后，将J分成Q组。设I，是I中的第i个项，Q。为J：的组号，使用负载均衡的分组策略：Q；一?二三iQm，oed。Q一。很显然，支持度越高的项其相关联的事务也越多。将项根据其支持度进行均衡分组，使得每一个组的相关事务集的数量相对均衡，有利于在分布式构造CanTree及挖掘时实现负载均衡。平衡分组可以在一个计算结点上完成，保存每个项及其组号的对应关系。Setp 4 D一并行挖掘。这个步骤是第一阶段的关键步骤。这一阶段使用一个MapReduce任务来完成。Map阶段根据项的分组情况，生成本

24、地数据分片中的组相关事务，根据组号发送给对应计算节点。Reduce阶段构造组相关事务的CanTree，并在CanTree上使用传统的FPGrowth算法进行挖掘。Reduce阶段构造的组相关CanTree及HeaderTable在挖掘完毕后存储在计算结点中，作为下一步增量挖掘的基础。有关实验表明，由于树的构造是一种递归计算任务，基于树的频繁模式挖掘算法构造树的时间要远远大于在树上进行遍历挖掘的时间，因此在增量挖掘阶段复用已经构造的树可以大大减少挖掘的时间，免去重新构造树的系统开销。Setp 5 D一聚集。如有需要，将Step 4中每个Reduce产生的频繁模式进行汇总，输出数据集D的频繁模式。

25、至此，第一阶段对原始数据集D的并行频繁模式挖掘就结束了。可以看到，这一阶段的执行与PFP算法十分相似，区别在于三点：一是对项的分组考虑到了负载均衡的要求，依据项的支持度进行万方数据肖 文等：PFPonCanTree：一种基于MapReduce的并行频繁模式增量挖掘算法 19分组；二是在构造组相关事务集的树时，构造的是CanTree而不是FPTree；三是挖掘结束后，CanTree和对应的HeaderTable并不丢弃，而是做为下一阶段增量挖掘的基础。第二阶段：对T进行并行增量挖掘。Setp 6 T-分片。将新事务集T分割为i个连续部分，将数据分片存储在P个计算节点上。这个过程同样可以由HDFS

26、自动完成。Setp 7 T_并行计数。使用一个MapReduce任务来统计T中所有的项及其支持度。每个Mapper输入一个或多个本节点上存储的T的数据分片，分片中的项以(item，1的键值对形式发送给Reducer，Reducer汇总相同项的计数，得到T中所有项的集合J及其支持度。Setp 8 f，-更新项分组。将J7更新到Q个项分组中去。设F是工7中的第i个项，如果f；已经存在Q，中，则更新Ql中该项的支持度。如果F不在任何一个Q。中，则保留。将所有不在原分组中的项按Step 3的均衡负载原则，更新到Q个分组中去，得到U一项分组信息。Setp 9 U一并行挖掘：该步骤是第二阶段的关键步骤。这

27、一阶段使用一个MapReduce任务来完成。Map阶段根据U一项分组信息和计算结点的对应关系，将T的组相关事务发送给相应的计算结点。Reduce阶段将新的事务更新到原CanTree上，更新完毕后使用FPGrowth算法进行挖掘。传统的FPGrowth算法从HeaderTable的最后一项(即支持度最低的项)开始构造条件模式基础，由于CanTree中存储了所有项的信息，有些项可能并不频繁，因此在挖掘过程中可以稍加改进，只需要考虑支持度大于minsup的项即可。Setp 10 U一聚集：将Step 9中每个Reduce产生的频繁模式进行汇总，作为最终的结果。两阶段完成后，U可以被看做是下一次增量挖

28、掘的D。当有新的事务集T7到来时，重复算法的第二阶段即可实现对新加入的T7进行挖掘，得到整个更新数据集U7的频繁模式。两阶段流程图如图3所示。32 PFPonCanTree效率分析将提出的算法与批处理并行算法PFP进行比较分析。设有数据集为D，新事务集为T，更新后的数据集为U，I D Id，I丁It，I UIU，“一d+t；每条事务包含项的平均数为挖，D被分为i个分片存储在P个计算结点上，丁被分为个分片存储r11蕊r二弄二Zl Marl Mar 【Mar ste一-z：豆享蚕工三享二，聿j=；l Redum ReduceII ReduceL=!兰三至耋兰=童，中的频繁模式Figure 3 Fl

29、ow chart of PFPonCanlree algorithm图3 PFPonCanTree算法流程图在P个节结上，平均频繁项的比例为s。PFP不是增量挖掘算法，当T加入D更新得到U后，只能对U重新进行并行挖掘，其执行时间主要由6部分组成：tpFp一分片+并行计敷+项分组+t分布式挖掘+数据传输而若使用PFPonCanTree算法，对T可以进行增量挖掘，增量挖掘除第一次挖掘外，其余只执行算法的第二阶段，则增量挖掘的执行时间也主要由6部分组成：tpvp。ca。T，。一，分片+z，并行计敷+，项分组+，分布式挖掘+，数据传输数据分片由HDFS自动完成，项分组都是简单操作，因此两个算法这两部分

30、差异较小，可以忽略其差异。两个算法的执行时间主要取决于项并行计数、分布式挖掘两个环节及数据传输的时间。由于对数据的操作时间要远远低于数据传输的时间，特别是在分布式计算的条件下，数据传输的时间对算法效率更有显著的影响。在相同集群条件下，数据传输时间的差异即是需要传输数据量的差异。(1)对并行计数环节来说，两个算法都需要一万方数据20 Computer EngineeringScience计算机工程与科学2018，40(1)个MapReduce任务，使用相同的方式进行。两者的差别在于需要处理的事务数及需要在Map和Reduce之间传输的项的数量。很明显，PFP算法需要处理U个事务，而PFPonCa

31、nTree算法需要处理t个事务；U个事务会产生U*九个需要传输的项，而PFPonCanTree算法为t*竹个。这一阶段的加速比为：s并一手(2)对分布式挖掘环节来说，两个算法都需要一个MapReduce任务，使用类似的方式进行。该环节主要包含三个阶段：生成组相关事务、构造树结构、使用FPGrowth算法进行挖掘。由于挖掘使用的方法一致(都是使用FPGrowth算法)，挖掘的对象一致(都是【，的CanTree)，因此两个算法效率的差别主要在第一和第二阶段。PFP算法最多需要传输I I I*U条事务，而PFPonCanTree最多需要传输I j7 l*t条事务。在构造树结构阶段，PFP需要重新构造

32、FPTree，而PFPonTree算法只需要将新的事务更新到原有的CanTree上去。由于CanTree中存储事务所有的项而非只有频繁的项，因此CanTree比FPTree需要更多的存储空间。这一阶段的加速比为：S分布式挖掘一l f I*u(1 J7 I*f)(ut)2从上述分析可以看到，伴随着数据集的不断增长，U和t的差值会越来越大，PFPonCanTree会越来越体现出更好的效率，由于增量挖掘的特性，提出的算法只需要处理新增的T即可，比重新开始挖掘【，数据集有明显的性能优势。4实验方案结果分析使用基于MapReduce计算模型的开源系统Hadoop 121做为平台搭建实验集群，具体方案如下

33、：使用1台计算机做为Master结点，CPU为i74790 360 GHz 8核，内存8 GB，操作系统为Red Hat Enterprise Linux Server 66，Java平台为Java 16；使用6台计算机做为Slave结点，CPU为i34150 350 GHz 4核，内存4 GB，操作系统为Red Hat Enterprise Linux Server 66，Java平台为Java 16。集群计算机之间使用百兆以太网相互连接；使用Java语言编写PFP和PFPonCanTree算法，将两个算法效率进行对比。所使用的实验数据集具体属性如表2所示。Table 2 Specific

34、attributes of experimental data sets表2实验数据集具体属性41负载均衡实验算法的负载均衡主要取决于分布式挖掘阶段各计算结点的处理数据量。使用来自Frequenthemset Mining Dataset Repository3叼中的Mushroom数据集做为实验数据集，使用算法Step 3负载均衡项分组策略，将所有项依次分为6、12、18组，每一组的组独立事务数量如图4图6所示。i组相关事务集数量Figure 4 Number of related transactions in each groupwhen all items are divided in

35、to 6 groups图4 将所有项分为6组时每个组相关事务集数量；I人秀氍教tFigure 5 Number of related transactions in each groupwhen all items are divided into 1 2 groups图5将所有项分为12组时每个组相关事务集数量从图4图6可以看出，本文提出的项分组策略取得了很好的效果，使得在分布式挖掘阶段每一个计算结点所处理的数据量十分接近，实现了较好的负载均衡。另外还可以看出，随着分组数的不断蝴娜啷蚴蜘啪77777765432I伞骄删拿：似m抛螂锄姗饼触川删555555555555万方数据肖 文等：PFPo

36、nCanTree：一种基于MapReduce的并行频繁模式增量挖掘算法 21组材I炎事务集数鲢Figure 6 Number of related transactions in each groupwhen all items are divided into 18 groups图6 将所有项分为18组时每个组相关事务集数量增加，每一组所包含的事务数随之减少，因此可以通过尽可能地扩大分组数，使分布式挖掘阶段启动更多的Reduce方法，提高并行化程度。设集群中有P个计算结点，每个结点能够运行的最大Reduce方法数为r，则最大分组数Q可以由以下公式计算得到：QP*r这样可以充分利用每一个计算结

37、点的计算能力，同时也可以使Map方法的输出发送到更多的结点，有利于实现网络通信的负载均衡。42算法执行效率实验设计三组实验，使用PFP算法对更新数据集进行批处理挖掘，使用PFPonCanTree算法对增量数据进行增量挖掘，最低支持度为0025，三组实验数据如表3所示。Table 3 Three groups of experimental data表3三组实验数据三组实验的执行时间如图7所示。x102141210芒幂8最6删4夕1 306赢-厂一Vr 774763 +Z一2实验组号批处理挖掘增量挖掘Figure 7 Run time of three groups of experimenta

38、l data图7三组实验数据运行时间从实验结果可以发现：(1)增量挖掘算法实现了较好的效率提高，其执行时间减少主要是因为两点：一是增量挖掘阶段不用重新生成D的组相关事务，大大减少了分布式挖掘阶段Map方法的输出和网络上的I0传输数据量；二是构造树是一种递归计算，需要大量的计算资源。增量挖掘阶段更新原CanTree要远远快于重新构造更新数据集U的CanTree，提高了效率。(2)提出的PFPonCanTree算法具有较好的线性加速度，适合于进行进一步扩展。5 结束语本文提出了一种基于MapReduce计算模型的并行频繁模式增量挖掘算法PFPonCanTree。算法基于传统的增量挖掘CanTree

39、数据结构及并行频繁模式挖掘算法PFP的基本思想，使用均衡负载对项进行了平衡分组，减少了增量挖掘阶段IO数据量及构造CanTree的计算量。实验结果表明，提出的算法在负载均衡及执行效率上都有较好的表现。下一步的工作可以进一步优化Hadoop运行环境，提高分布式挖掘阶段Map方法的并行度，进一步提高算法的执行效率。参考文献：13 Agrawal RImielinski T，Swami A NMining associationrules between sets of items in large databasesCl Proc ofthe ACMSIGMOD Conference on Man

40、agement of Data，1993：207-216E2Agrawal R，Srikant RFast algorithm for mining associationrules in large databases-CProc of the 20th InternationalConference on Very Large Data Bases，1994：4874993Han Jia-wei，Pei Jian，Yin Yiwen，et a1Mining frequent patterns without candidate generation：A frequentpattern tr

41、eeapproachJData Mining and Knowledge Discovery，2004，8(1)：53-874-1 Pyuna G，Yun U，Ryu K HEfficient frequent pattern mining based on linear prefix treeJKnowledge-Based Systerns，2014，55：125-139E5TsayY J，HsuT J，Yu J RFIuT；A newmethodformining frequent itemsetsJInformation Sciences，2009，179(1I)：1724一17376

42、Lin Ke-chung，Liao I-en，Chen ZhishengAn improved frequent pattern growth method for mining association rulesEJ3Expert Systems with Applications，2011，38(5)：5154516173 Tseng FanchenAn adaptive approach tO mining frequent哪懈m瞄啪m量!抛捌拼ls抛瑚伽444444444444444447539753卟卿万方数据22 Computer Engineering&Science计算机工程与

43、科学2018，40(1)89101112131415316171819320321itemsets efficientlyJExpert Systems with Applications，2012，39(39)：1316613172 223Cheung D W，Han J，Ng V T，et a1Maintenance of diseovered association rules in large databases：An incremental updating approachC1Proc of the 20th IEEE InternationalConference on Data

44、 Engineering，1996：106114Cheung D W，Lee S D，Kao BA general incremental technique for maintaining discovered association rulescProcof International Conference on Databases Systems for Advanced Applications，1997：1851 94Ayan N F。Tansel A U，Arkun EAn efficient algorithm toupdate large itemsets with early

45、 pruningCProc of Acmsigkdd International Conference on Knowledge Discovery&Data Mining，1999：287291Srikant R，Agrawal RMining sequential patterns：Generalizations and performance improvementsC1Proc of the 5thConference on Extending Database Technology，1996：3-17Hong T P，Wang C Y。Tao Y HA new incremental

46、 datamining algorithm using pre-large itemsetsJIntelligentData Analysis，2001，5(2)：111-129Koh J L，Shieh S FAn efficient approach for maintainingassociation rules based on adjusting FPtree structuresMf Database Systems for Advanced ApplicationsBerlin：Springer Berlin Heidelberg，2004：417-424Cheung W，Zai

47、ane O RIncremental mining of frequentpatterns without candidate gneration or support constraintcProc of the 2003 International Database Engineeringand Applications Symposium，2003：11 1-1 1 6Leung K S，Khan Q I，Hoque TCantree：A tree structurefor efficient incremental mining of frequent patternscProc of

48、 the 5th IEEE International Conference on Data Mining，2005：8Totad S G，Geeta R B G，Reddy P PBatchprocessing forincremental fp-tree constructionJInternational Journal ofComputer Applications，2010，5(5)：2832Li N，Zeng L，He Q，et a1Parallel implementation of apriorialgorithm based on mapreduceClProc of Acis International Conference on Software Engineering，Artificial Intelligence，Networking and ParallelDistributed Computing2012：236241Huang Liqin，Liu YahhuangResearch on improved parallel Apriori with MapReduc