基于Hadoop的2FP-Growth算法

王泽儒， 王红梅， 李芬田

(长春工业大学 计算机科学与工程学院， 吉林 长春 130012)

0 引 言

目前，在数据挖掘领域关联规则[1]是比较重要的一个研究课题，它反映了大量数据中项目与项目之间的联系或者关系。频繁项集的产生是关联规则挖掘应用中的最重要一步。近年来，在频繁项集挖掘中，许多学者先后提出了挖掘算法，例如： Apriori、FP-Growth、PARTITION 等挖掘算法，在众多挖掘算法中，FP-Growth 算法最为著名，因为它在前一个算法Apriori的基础上提出，并且在挖掘效率上有一个数量级的改善，FP-Growth算法的思想是：

1)将事务数据集压缩成一棵FP树;

2)根据FP树产生后缀模式和项头表，以此找出所有条件模式基，遍历条件模式基构造出类似频繁项 1-项集合L的频繁项集合L_i;

3)根据L_i再遍历条件模式基从而构造新的条件FP-tree，以此来进行迭代挖掘。通过上述过程来看，FP-Growth算法每次构造出新的 FP树之前都要两次遍历条件模式基。

在大数据时代背景下，由于数据呈现指数增长趋势，经典的 FP-Growth 算法在生成新的条件FP树时必须要遍历条件模式基两次，这样使系统反复读取数据库服务器中相同的海量数据，有以下两个缺点：

1)降低了算法的挖掘效率;

2)对数据库服务器产生高负荷，不利于数据库服务器正常运作。

随着数据发展趋势，国内外许多学者对FP-Growth算法进行了改进，如文献[2]为了解决数据量指数增长趋势，使得传统FP-Growth算法受到限制，所以在PFP算法[3]的基础上提出负载均衡的并行算法;文献[4]在现有的并行FP-Growth算法基础上，提出负载均衡的算法，并且伴随着剪枝策略，可以解决并行分组数据冗余以及负载不均衡的问题;文献[5]是将FP-tree的改进算法Cantree在Hadoop平台中Map/Reduce模式下进行并行化计算;文献[6]在提出并行FP-Growth算法的同时，对数据进行分割，然后通过结合的方式对事务进行分片实现并行化,解决了PFP在大数据下不能处理的问题;文献[7]在并行算法PFP上，对挖掘子节点进行剪枝来减少对数据的处理，以此来提高挖掘效率;文献[8]直接对FP-Growth算法进行改进，提出一种只需要扫描一次数据库的节点表算法，该算法不生成项目头表，新增加一个与FP-tree相关联的节点表，解决FP-Growth算法扫描两次数据库并且会产生大量模式基的问题;文献[9]在不同于Hadoop平台的spark平台下进行并行化处理，提出基于spark平台的并行FP-Growth算法;文献[10]先将数据按照垂直排列，然后通过扫描删除不频繁项，并且并行建立FP-Tree，最后通过迭代生成频繁项集。

FP-Growth算法存在如下缺点[11]:

1)在第一次扫描数据库时，只对频繁1-项集进行支持度计数统计，但是计算机扫描数据集时，时间消耗是很大的;

2)FP树只是单纯的将相同前缀的路径进行合并，并没有考虑剪枝。

针对以上缺点，提出2FP-Growth算法。文中在改进算法2FP-Growth基础上设计并行运算。最后通过实验对2FP-Grwoth、FP-Growth以及COFI进行比对，验证并行2FP-Growth算法的高效性以及正确性。

1 相关理论

T为一个数据集，t1，t2，…，t10是数据集中的每一条事务，见表1。

表1 数据集T

1.1 2FP森林

定义1满足下列特性的树结构称为2-项集频繁模式增长树(2-items frequent-pattent growth tree，简称2FP树)：

1)根结点是频繁2-项集，其数据结构为[2-项集:支持度计数]；

2)除根结点外，其余结点均是频繁1-项集，其数据结构为[1-项集：支持度计数]；

3)设结点B的1-项集是{β}，对于结点B的任意非根祖先结点A的1-项集{α}，则2-项集{α,β}是频繁的。

定义2由m(m≥0)个互不相交的2FP树构成的森林称为2-项集频繁模式增长森林(2-items frequent-pattent growth forest，简称2FP森林)。

设min_sup为2，对表1所示数据集T删去非频繁项G，构建的2FP森林如图1所示。

图1 2FP森林

定理1如果项集X={x1,x2,…,xk}是频繁的，∀α∈X,则α一定是频繁的。反之，∃x∈α,如果α是非频繁的，则项集X一定非频繁的。

定理2如果项集X={x1,x2,…,xk}是频繁的，∀α∈X∧β∈X∧α≠β,则2-项集{α,β}一定是频繁的。反之，∃α∈X∧β∈X∧α≠β,如果2-项集{α,β}非频繁，则项集X一定非频繁的。

定理3设某事务包含的项集为X={x1,x2,…,xm},在x中删去非频繁项，并将剩余项按支持度非升序排列为项集Y={y1,y2,…,yk}(k≤m),∀α∈Y-{yk},在该事务不存在2-项集{α,β}的频繁项集。

2FP-Growth算法将提供频繁项的数据集压缩存储到2FP树中，其思想是将频繁2-项集作为树的根节点，然后利用剪枝策略对2FP树进行剪枝，最后把这些2FP树构成2FP森林。2FP-Growth算法过程如下(以表1为例)：

1)FP-Growth算法第一遍扫描数据集仅计算1-项集的支持度，考虑到对数据集扫描的时间代价，2FP-Growth 算法在扫描第一遍数据集时统计所有1-项集和2-项集的支持度计数。对于表1所示数据集T，扫描一遍数据集计算1-项集和2-项集的支持度,见表2。

表2 1-项集和2-项集的支持度计数

2)FP-Growth算法根据剪枝定理1删去所有非频繁模式，2FP-Growth算法根据剪枝定理2删去了一定不会产生大于等于频繁2-项集的频繁模式。对于表1所示数据集T依据表2的统计结果，设min_sup=2，根据剪枝定理1删去了项G(非频繁模式)，根据剪枝定理2删去了项F(所有包含F的2-项集均非频繁)，将剩余的频繁模式按支持度非升序排列，得到I′={D,A,B,E,C}。

3)FP-Growth算法中没有2-项集对FP树的剪枝作用，这样由于剪枝不充分对FP树的规模控制较低，反而增加了后续遍历FP树及构造条件FP树的代价。由于2FP-Growth算法在第一次扫描数据集后得到了所有频繁2-项集，在第二次扫描数据集时只需挖掘频繁k-项集(k≥3)，因此，以频繁2-项集为根结点，根据剪枝定理2，若某2-项集X非频繁，无须建立以X为根结点的2FP树。例如，2-项集{E,C}非频繁，则所有以{E,C}为前缀的项集均非频繁，则2FP森林中没有以{E,C}为根结点的树(见图1)。

4)根据剪枝定理3，对于模式集I′，设{γ}是I′的最后项，则不存在包含{γ}为根结点的2FP树。例如I′={D,A,B,E,C}，则2FP森林无须建立以{D,C}、{A,C}、{B,C}和{E,C}为根结点的2FP树(见图1)。

5)根据剪枝定理2，在构建2FP树时剪掉所有非潜在频繁3-项集对应的项。例如，对事务t1={D,A,B,E,C}构造以{A,B}为根结点的2FP树时，对于项C，由于2-项集{B,C}非频繁，则直接剪掉项{C}，如图2所示。

图2 剪枝示例1

在构建2FP树时保证路径上的所有结点均是频繁2-项集。例如，对于事务t1={D,A,B,E,C}构造以{D,A}为根结点的2FP树时，对于项C，由于2-项集{B,C}非频繁，则将{C}作为根结点{D,A}的孩子，剪枝前后对比如图3所示。

(a) 剪枝前

(b) 剪枝后的合并现象

将结点{C}从路径{DABEC}剪掉不仅减少了路径长度，而且还可以与其他事务的相同前缀路径进行合并，例如，对于事务t9={D,A,C}，结点{C}作为根结点{D,A}的孩子，可以和t1路径上的结点进行合并。

6)根据剪枝定理3，对于每一个事务在构建2FP树时，并不需要组合最后一项，减少了组合次数，从而提高了构建2FP森林的时间性能。例如，对于事务t5={D,A,B,E}，无须更新以{D,E}、{A,E}和{B,E}为根结点的2FP树。

1.2 Map/Reduce模式

Map/Reduce模式是由Google公司基于Hadoop平台下提出的编程模式，该模式的主要思想是：输入一个的输入键值对，然后产生一个的结果键值对。这个过程需要定义Map和Reduce函数，其中Map函数用来对输入的键值对进行分片，然后产生中间键值对。Reduce函数是将相同键值对进行组合生成最终结果。

2 改进着眼点

2.1 基于Map/Reduce下并行2FP-Growth算法

2FP-Growth算法在串行上体现出了优势，但是当数据量过大时，2FP-Grwoth算法仍然是不能实现的。因此，文中提出并行2FP-Growth算法，解决2FP-Gtowth在大数据下进行频繁模式挖掘不能实现的问题。此算法在MapReduce编程模式下，对2FP-Grwoth算法进行并行化挖掘。算法主要分为3个步骤：

1)统计频繁1-项集与频繁2-项集。计算数据集中1-频繁项集和2-频繁项集的支持度计数，运行一个统计支持度计数的Map/Reduce 工程，并将结果保存到分布式缓存中。

2)建立2FP树,获取局部频繁项集。这一步是整个并行挖掘算法的重要步骤,该过程设置一个Map/Reduce工程。其中，在Mapper函数中构造局部2FP森林,并对其挖掘得到局部频繁项集L2FPSeti。Reducer函数中,将会对所有L2FPSeti进行合并操作，这样将会得到全局频繁项集GFPSet,并将剩下的不确定是否为全局频繁项集集合中的元素保存到分布式文件中。

3)对存放的候选全局频繁项集并行统计其支持度计数。设置一个Map/Reduce工程统计步骤2)中存放在系统分布式文件中的候选频繁项集的支持度计数,将满足最小支持度计数的频繁项集加入到全局频繁集中。

最后将2)与3)所得到的结果合并生成的频繁项集就是整个数据集的全部全局频繁项集。

2.2 统计频繁1-项集与频繁2-项集

1-项集和2-项集的求解过程利用Map/Reduce来统计关键词出现的次数的应用，可以很容易实现。其伪代码实现如下:

Mapper 过程:

map (key, value) {value为事务ti

1.for each aiεtido

2. output;

3.end

4.}

Reduce过程:

Reduce(key,value){//key是1-项集与2-项集，value是其支持度计数列表

1.C=0;

2.For each viin value do

3. C+=vi;

4.End

5.If C≥minsup then

6. Output;//输出该1-项集频繁集和支持度计数

7.End

8.}

2.3 建立2FP树，获取局部频繁项集

在完成2-项集过程后，下面的任务就是建立2FP树，并且对2FP树进行挖掘，得到局部的频繁项集。该过程是由另一个Map/Reduce实现。Map过程首先构造并挖掘局部2FP树，将挖掘得到局部频繁集保存在L2FPSet中。Reduce过程是用来把存到L2FPSet中的局部频繁项集合并，并且对其进行支持度计数，将所有合并后大于等于minsup的项集输出，支持度小于minsup的项集将会写入分布式文件，供进一步使用。伪代码如下：

Mapper过程:

Map(key，value){ value 为事务ti

1.insert_2FP(2FPT,ti); //针对ti更新局部2FP树

2.}

Createup(){

1.local2FPGrowth(2FPT,L2FPSet);

2.For each lfp in LFPSet do

3.Out;

4.End

5.}

Reducer过程:

Reduce(key,value){//key项集，value是其支持度计数列表

1.C=0;

2.For each viin value do

3. C+=vi;

4.End

5.If C≥minsup then

6. Output;//输出该项集频繁集和支持度计数

7.else

8. Write key into a distribute file; //不确定是否为全局频繁项集，则写入分布式文件

9.end

10.}

2.4 并行计算部分候选全局频繁项集的支持度计数

对于步骤2)写入到分布式文件中的项目集，因为不能判断是否为全局频繁项集，所以要多建立一次Map/Reduce过程来计算这些候选项集的支持度计数，并且判断是否为全局频繁项集。Mapper过程中，readset()函数主要是为了读取这些项集，map函数则是统计支持度计数。伪代码如下:

Mapper过程:

Readset(){

1.LFPSets = loadLFP(); //读取部分频繁项集;

2. }

Map(key,value){ //value为事务ti

1.for each lfp in LFPSets do

2. If lfp in value then

3. Output;

4.End

5.}

Reducer过程：

Reduce(key，value){ //key为全局候选项集，value为其支持度计数列表

1.C =0;

2.For each viinvalue do

3. C+= vi;

4.End

5.If C ≥ minsup then

6. Output;

7.End

8.}

3 实验结果与分析

为了验证算法的正确性和高效性，在ubuntu16.04操作系统、主频2.5 GHz、内存4 G，使用基于Map/Reduce模型的Hadoop1.2.1作为平台搭建3台服务器实验集群，对数据集进行了如下3个实验。

实验1：在数据集mushroom上验证基于Hadoop的2FP-Growth算法的正确性，实验结果见表3。

实验1结果表明，基于Hadoop的2FP-Growth算法的频繁项集挖掘结果与FP-Growth算法的挖掘结果完全一致(误差小于1%)，表明并行2FP-Growth算法的正确性。

实验2：在数据集T10I4D100K上考察在相同支持度阈值下数据规模对算法效率的影响，实验结果如图4所示。

图4 算法运行时间对比

实验2结果表明，在数据集T10I4D100K上基于Hadoop的2FP-Growth算法在时间消耗上明显小于FP-Growth、2FP-Grwoth以及COFI算法，说明基于Hadoop的2FP-Growth算法的高效性。

实验3：在最小支持度5%下，不同大规模数据集下算法运行结果的比较见表4。

表4 在大规模数据集下运行结果

实验3结果表明，当输入的数据集规模较大时，FP-Growth算法及其改进算法会造成内存溢出，当Hadoop集群下建立3个计算机节点，表中的数据集将会解决内存溢出问题，因此，文中提出的基于Hadoop的2FP-Growth算法根据数据集的规模进行调整节点数是有效的。

4 结 语

提出基于Hadoop的2FP-Growth算法，并且在Hadoop平台下实现，取得了较好的实验结果。通过与FP-Growth、COFI以及2FP-Grwoth算法在数据集Mmushroom以及T10I4D100K比较正确性和挖掘效率可以看出，基于Hadoop的2FP-Growth算法明显高于FP-Growth、COFI以及2FP-Grwoth。实验结果表明,基于Hadoop的2FP-Growth算法在数据规模较大调整计算机节点数有较好的高效性、正确性以及算法的应用价值。

参考文献：

[1] Agrawal R， Srikant． Fast algorithms for mining association rules[C]//Proceedings of the 20th Intemational Conference on Very Large DataBases. Santiago: Chile,1994：487-499.

[2] Zhou L, Zhong Z, Chang J, et al. Balanced parallel FP-growth with MapReduce[C]//Information Computing and Telecommunications.2011:243-246.

[3] Mao W, Guo W. An improved association rules mining algorithm based on power set and hadoop[C]//International Conference on Information Science and Cloud Computing Companion. [S.l.]: IEEE,2014:236-241.

[4] 刘祥哲,刘培玉,任敏,等.基于负载均衡和冗余剪枝的并行FP-Growth算法[J].数据采集与处理,2016,31(1):223-230.

[5] 肖文,胡娟,周晓峰.PFPonCanTree:一种基于MapReduce的并行频繁模式增量挖掘算法[J].计算机工程与科学,2018,40(1):15-23.

[6] 厍向阳,张玲.基于Hadoop的FP-Growth关联规则并行改进算法[J].计算机应用研究,2018,35(1):109-112.

[7] 施亮,钱雪忠.基于Hadoop的并行FP-Growth算法的研究与实现[J].微电子学与计算机,2015,32(4):150-154.

[8] 王建明,袁伟.基于节点表的FP-Growth算法改进[J].计算机工程与设计,2018,39(1):140-145.

[9] 张稳,罗可.一种基于Spark框架的并行FP-Growth挖掘算法[J].计算机工程与科学,2017,39(8):1403-1409.

[10] 邵梁,何星舟,尚俊娜.基于Spark框架的FP-Growth大数据频繁项集挖掘算法[J].计算机应用研究,2018(10):1-6.

[11] 王红梅，李芬田，王泽儒.基于滑动窗口数据流频繁集挖掘模型综述[J].长春工业大学学报，2017，38(5)：484-490.