基于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.