基于Hadoop的2FP-Growth算法
2018-06-22 11:26:42王澤儒王紅梅李芬田
長春工業(yè)大學(xué)學(xué)報(bào) 2018年2期
王澤儒， 王紅梅， 李芬田
(長春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 吉林 長春 130012)
0 引 言
目前，在數(shù)據(jù)挖掘領(lǐng)域關(guān)聯(lián)規(guī)則[1]是比較重要的一個(gè)研究課題，它反映了大量數(shù)據(jù)中項(xiàng)目與項(xiàng)目之間的聯(lián)系或者關(guān)系。頻繁項(xiàng)集的產(chǎn)生是關(guān)聯(lián)規(guī)則挖掘應(yīng)用中的最重要一步。近年來，在頻繁項(xiàng)集挖掘中，許多學(xué)者先后提出了挖掘算法，例如： Apriori、FP-Growth、PARTITION 等挖掘算法，在眾多挖掘算法中，F(xiàn)P-Growth 算法最為著名，因?yàn)樗谇耙粋€(gè)算法Apriori的基礎(chǔ)上提出，并且在挖掘效率上有一個(gè)數(shù)量級(jí)的改善，F(xiàn)P-Growth算法的思想是：
1)將事務(wù)數(shù)據(jù)集壓縮成一棵FP樹;
2)根據(jù)FP樹產(chǎn)生后綴模式和項(xiàng)頭表，以此找出所有條件模式基，遍歷條件模式基構(gòu)造出類似頻繁項(xiàng) 1-項(xiàng)集合L的頻繁項(xiàng)集合L_i;
3)根據(jù)L_i再遍歷條件模式基從而構(gòu)造新的條件FP-tree，以此來進(jìn)行迭代挖掘。通過上述過程來看，F(xiàn)P-Growth算法每次構(gòu)造出新的 FP樹之前都要兩次遍歷條件模式基。
在大數(shù)據(jù)時(shí)代背景下，由于數(shù)據(jù)呈現(xiàn)指數(shù)增長趨勢，經(jīng)典的 FP-Growth 算法在生成新的條件FP樹時(shí)必須要遍歷條件模式基兩次，這樣使系統(tǒng)反復(fù)讀取數(shù)據(jù)庫服務(wù)器中相同的海量數(shù)據(jù)，有以下兩個(gè)缺點(diǎn)：
1)降低了算法的挖掘效率;
2)對數(shù)據(jù)庫服務(wù)器產(chǎn)生高負(fù)荷，不利于數(shù)據(jù)庫服務(wù)器正常運(yùn)作。
隨著數(shù)據(jù)發(fā)展趨勢，國內(nèi)外許多學(xué)者對FP-Growth算法進(jìn)行了改進(jìn)，如文獻(xiàn)[2]為了解決數(shù)據(jù)量指數(shù)增長趨勢，使得傳統(tǒng)FP-Growth算法受到限制，所以在PFP算法[3]的基礎(chǔ)上提出負(fù)載均衡的并行算法;文獻(xiàn)[4]在現(xiàn)有的并行FP-Growth算法基礎(chǔ)上，提出負(fù)載均衡的算法，并且伴隨著剪枝策略，可以解決并行分組數(shù)據(jù)冗余以及負(fù)載不均衡的問題;文獻(xiàn)[5]是將FP-tree的改進(jìn)算法Cantree在Hadoop平臺(tái)中Map/Reduce模式下進(jìn)行并行化計(jì)算;文獻(xiàn)[6]在提出并行FP-Growth算法的同時(shí)，對數(shù)據(jù)進(jìn)行分割，然后通過結(jié)合的方式對事務(wù)進(jìn)行分片實(shí)現(xiàn)并行化,解決了PFP在大數(shù)據(jù)下不能處理的問題;文獻(xiàn)[7]在并行算法PFP上，對挖掘子節(jié)點(diǎn)進(jìn)行剪枝來減少對數(shù)據(jù)的處理，以此來提高挖掘效率;文獻(xiàn)[8]直接對FP-Growth算法進(jìn)行改進(jìn)，提出一種只需要掃描一次數(shù)據(jù)庫的節(jié)點(diǎn)表算法，該算法不生成項(xiàng)目頭表，新增加一個(gè)與FP-tree相關(guān)聯(lián)的節(jié)點(diǎn)表，解決FP-Growth算法掃描兩次數(shù)據(jù)庫并且會(huì)產(chǎn)生大量模式基的問題;文獻(xiàn)[9]在不同于Hadoop平臺(tái)的spark平臺(tái)下進(jìn)行并行化處理，提出基于spark平臺(tái)的并行FP-Growth算法;文獻(xiàn)[10]先將數(shù)據(jù)按照垂直排列，然后通過掃描刪除不頻繁項(xiàng)，并且并行建立FP-Tree，最后通過迭代生成頻繁項(xiàng)集。
FP-Growth算法存在如下缺點(diǎn)[11]:
1)在第一次掃描數(shù)據(jù)庫時(shí)，只對頻繁1-項(xiàng)集進(jìn)行支持度計(jì)數(shù)統(tǒng)計(jì)，但是計(jì)算機(jī)掃描數(shù)據(jù)集時(shí)，時(shí)間消耗是很大的;
2)FP樹只是單純的將相同前綴的路徑進(jìn)行合并，并沒有考慮剪枝。
針對以上缺點(diǎn)，提出2FP-Growth算法。文中在改進(jìn)算法2FP-Growth基礎(chǔ)上設(shè)計(jì)并行運(yùn)算。最后通過實(shí)驗(yàn)對2FP-Grwoth、FP-Growth以及COFI進(jìn)行比對，驗(yàn)證并行2FP-Growth算法的高效性以及正確性。
1 相關(guān)理論
T為一個(gè)數(shù)據(jù)集，t1，t2，…，t10是數(shù)據(jù)集中的每一條事務(wù)，見表1。
表1 數(shù)據(jù)集T
1.1 2FP森林
定義1滿足下列特性的樹結(jié)構(gòu)稱為2-項(xiàng)集頻繁模式增長樹(2-items frequent-pattent growth tree，簡稱2FP樹)：
1)根結(jié)點(diǎn)是頻繁2-項(xiàng)集，其數(shù)據(jù)結(jié)構(gòu)為[2-項(xiàng)集:支持度計(jì)數(shù)]；
2)除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)均是頻繁1-項(xiàng)集，其數(shù)據(jù)結(jié)構(gòu)為[1-項(xiàng)集：支持度計(jì)數(shù)]；
3)設(shè)結(jié)點(diǎn)B的1-項(xiàng)集是{β}，對于結(jié)點(diǎn)B的任意非根祖先結(jié)點(diǎn)A的1-項(xiàng)集{α}，則2-項(xiàng)集{α,β}是頻繁的。
定義2由m(m≥0)個(gè)互不相交的2FP樹構(gòu)成的森林稱為2-項(xiàng)集頻繁模式增長森林(2-items frequent-pattent growth forest，簡稱2FP森林)。
設(shè)min_sup為2，對表1所示數(shù)據(jù)集T刪去非頻繁項(xiàng)G，構(gòu)建的2FP森林如圖1所示。
圖1 2FP森林
定理1如果項(xiàng)集X={x1,x2,…,xk}是頻繁的，?α∈X,則α一定是頻繁的。反之，?x∈α,如果α是非頻繁的，則項(xiàng)集X一定非頻繁的。
定理2如果項(xiàng)集X={x1,x2,…,xk}是頻繁的，?α∈X∧β∈X∧α≠β,則2-項(xiàng)集{α,β}一定是頻繁的。反之，?α∈X∧β∈X∧α≠β,如果2-項(xiàng)集{α,β}非頻繁，則項(xiàng)集X一定非頻繁的。
定理3設(shè)某事務(wù)包含的項(xiàng)集為X={x1,x2,…,xm},在x中刪去非頻繁項(xiàng)，并將剩余項(xiàng)按支持度非升序排列為項(xiàng)集Y={y1,y2,…,yk}(k≤m),?α∈Y-{yk},在該事務(wù)不存在2-項(xiàng)集{α,β}的頻繁項(xiàng)集。
2FP-Growth算法將提供頻繁項(xiàng)的數(shù)據(jù)集壓縮存儲(chǔ)到2FP樹中，其思想是將頻繁2-項(xiàng)集作為樹的根節(jié)點(diǎn)，然后利用剪枝策略對2FP樹進(jìn)行剪枝，最后把這些2FP樹構(gòu)成2FP森林。2FP-Growth算法過程如下(以表1為例)：
1)FP-Growth算法第一遍掃描數(shù)據(jù)集僅計(jì)算1-項(xiàng)集的支持度，考慮到對數(shù)據(jù)集掃描的時(shí)間代價(jià)，2FP-Growth 算法在掃描第一遍數(shù)據(jù)集時(shí)統(tǒng)計(jì)所有1-項(xiàng)集和2-項(xiàng)集的支持度計(jì)數(shù)。對于表1所示數(shù)據(jù)集T，掃描一遍數(shù)據(jù)集計(jì)算1-項(xiàng)集和2-項(xiàng)集的支持度,見表2。
表2 1-項(xiàng)集和2-項(xiàng)集的支持度計(jì)數(shù)
2)FP-Growth算法根據(jù)剪枝定理1刪去所有非頻繁模式，2FP-Growth算法根據(jù)剪枝定理2刪去了一定不會(huì)產(chǎn)生大于等于頻繁2-項(xiàng)集的頻繁模式。對于表1所示數(shù)據(jù)集T依據(jù)表2的統(tǒng)計(jì)結(jié)果，設(shè)min_sup=2，根據(jù)剪枝定理1刪去了項(xiàng)G(非頻繁模式)，根據(jù)剪枝定理2刪去了項(xiàng)F(所有包含F(xiàn)的2-項(xiàng)集均非頻繁)，將剩余的頻繁模式按支持度非升序排列，得到I′={D,A,B,E,C}。
3)FP-Growth算法中沒有2-項(xiàng)集對FP樹的剪枝作用，這樣由于剪枝不充分對FP樹的規(guī)?？刂戚^低，反而增加了后續(xù)遍歷FP樹及構(gòu)造條件FP樹的代價(jià)。由于2FP-Growth算法在第一次掃描數(shù)據(jù)集后得到了所有頻繁2-項(xiàng)集，在第二次掃描數(shù)據(jù)集時(shí)只需挖掘頻繁k-項(xiàng)集(k≥3)，因此，以頻繁2-項(xiàng)集為根結(jié)點(diǎn)，根據(jù)剪枝定理2，若某2-項(xiàng)集X非頻繁，無須建立以X為根結(jié)點(diǎn)的2FP樹。例如，2-項(xiàng)集{E,C}非頻繁，則所有以{E,C}為前綴的項(xiàng)集均非頻繁，則2FP森林中沒有以{E,C}為根結(jié)點(diǎn)的樹(見圖1)。
4)根據(jù)剪枝定理3，對于模式集I′，設(shè){γ}是I′的最后項(xiàng)，則不存在包含{γ}為根結(jié)點(diǎn)的2FP樹。例如I′={D,A,B,E,C}，則2FP森林無須建立以{D,C}、{A,C}、{B,C}和{E,C}為根結(jié)點(diǎn)的2FP樹(見圖1)。
5)根據(jù)剪枝定理2，在構(gòu)建2FP樹時(shí)剪掉所有非潛在頻繁3-項(xiàng)集對應(yīng)的項(xiàng)。例如，對事務(wù)t1={D,A,B,E,C}構(gòu)造以{A,B}為根結(jié)點(diǎn)的2FP樹時(shí)，對于項(xiàng)C，由于2-項(xiàng)集{B,C}非頻繁，則直接剪掉項(xiàng){C}，如圖2所示。
圖2 剪枝示例1
在構(gòu)建2FP樹時(shí)保證路徑上的所有結(jié)點(diǎn)均是頻繁2-項(xiàng)集。例如，對于事務(wù)t1={D,A,B,E,C}構(gòu)造以{D,A}為根結(jié)點(diǎn)的2FP樹時(shí)，對于項(xiàng)C，由于2-項(xiàng)集{B,C}非頻繁，則將{C}作為根結(jié)點(diǎn){D,A}的孩子，剪枝前后對比如圖3所示。
(a) 剪枝前
(b) 剪枝后的合并現(xiàn)象
將結(jié)點(diǎn){C}從路徑{DABEC}剪掉不僅減少了路徑長度，而且還可以與其他事務(wù)的相同前綴路徑進(jìn)行合并，例如，對于事務(wù)t9={D,A,C}，結(jié)點(diǎn){C}作為根結(jié)點(diǎn){D,A}的孩子，可以和t1路徑上的結(jié)點(diǎn)進(jìn)行合并。
6)根據(jù)剪枝定理3，對于每一個(gè)事務(wù)在構(gòu)建2FP樹時(shí)，并不需要組合最后一項(xiàng)，減少了組合次數(shù)，從而提高了構(gòu)建2FP森林的時(shí)間性能。例如，對于事務(wù)t5={D,A,B,E}，無須更新以{D,E}、{A,E}和{B,E}為根結(jié)點(diǎn)的2FP樹。
1.2 Map/Reduce模式
Map/Reduce模式是由Google公司基于Hadoop平臺(tái)下提出的編程模式，該模式的主要思想是：輸入一個(gè)
2 改進(jìn)著眼點(diǎn)
2.1 基于Map/Reduce下并行2FP-Growth算法
2FP-Growth算法在串行上體現(xiàn)出了優(yōu)勢，但是當(dāng)數(shù)據(jù)量過大時(shí)，2FP-Grwoth算法仍然是不能實(shí)現(xiàn)的。因此，文中提出并行2FP-Growth算法，解決2FP-Gtowth在大數(shù)據(jù)下進(jìn)行頻繁模式挖掘不能實(shí)現(xiàn)的問題。此算法在MapReduce編程模式下，對2FP-Grwoth算法進(jìn)行并行化挖掘。算法主要分為3個(gè)步驟：
1)統(tǒng)計(jì)頻繁1-項(xiàng)集與頻繁2-項(xiàng)集。計(jì)算數(shù)據(jù)集中1-頻繁項(xiàng)集和2-頻繁項(xiàng)集的支持度計(jì)數(shù)，運(yùn)行一個(gè)統(tǒng)計(jì)支持度計(jì)數(shù)的Map/Reduce 工程，并將結(jié)果保存到分布式緩存中。
2)建立2FP樹,獲取局部頻繁項(xiàng)集。這一步是整個(gè)并行挖掘算法的重要步驟,該過程設(shè)置一個(gè)Map/Reduce工程。其中，在Mapper函數(shù)中構(gòu)造局部2FP森林,并對其挖掘得到局部頻繁項(xiàng)集L2FPSeti。Reducer函數(shù)中,將會(huì)對所有L2FPSeti進(jìn)行合并操作，這樣將會(huì)得到全局頻繁項(xiàng)集GFPSet,并將剩下的不確定是否為全局頻繁項(xiàng)集集合中的元素保存到分布式文件中。
3)對存放的候選全局頻繁項(xiàng)集并行統(tǒng)計(jì)其支持度計(jì)數(shù)。設(shè)置一個(gè)Map/Reduce工程統(tǒng)計(jì)步驟2)中存放在系統(tǒng)分布式文件中的候選頻繁項(xiàng)集的支持度計(jì)數(shù),將滿足最小支持度計(jì)數(shù)的頻繁項(xiàng)集加入到全局頻繁集中。
最后將2)與3)所得到的結(jié)果合并生成的頻繁項(xiàng)集就是整個(gè)數(shù)據(jù)集的全部全局頻繁項(xiàng)集。
2.2 統(tǒng)計(jì)頻繁1-項(xiàng)集與頻繁2-項(xiàng)集
1-項(xiàng)集和2-項(xiàng)集的求解過程利用Map/Reduce來統(tǒng)計(jì)關(guān)鍵詞出現(xiàn)的次數(shù)的應(yīng)用，可以很容易實(shí)現(xiàn)。其偽代碼實(shí)現(xiàn)如下:
Mapper 過程:
map (key, value) {value為事務(wù)ti
1.for each aiεtido
2. output
3.end
4.}
Reduce過程:
Reduce(key,value){//key是1-項(xiàng)集與2-項(xiàng)集，value是其支持度計(jì)數(shù)列表
1.C=0;
2.For each viin value do
3. C+=vi;
4.End
5.If C≥minsup then
6. Output
7.End
8.}
2.3 建立2FP樹，獲取局部頻繁項(xiàng)集
在完成2-項(xiàng)集過程后，下面的任務(wù)就是建立2FP樹，并且對2FP樹進(jìn)行挖掘，得到局部的頻繁項(xiàng)集。該過程是由另一個(gè)Map/Reduce實(shí)現(xiàn)。Map過程首先構(gòu)造并挖掘局部2FP樹，將挖掘得到局部頻繁集保存在L2FPSet中。Reduce過程是用來把存到L2FPSet中的局部頻繁項(xiàng)集合并，并且對其進(jìn)行支持度計(jì)數(shù)，將所有合并后大于等于minsup的項(xiàng)集輸出，支持度小于minsup的項(xiàng)集將會(huì)寫入分布式文件，供進(jìn)一步使用。偽代碼如下：
Mapper過程:
Map(key，value){ value 為事務(wù)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項(xiàng)集，value是其支持度計(jì)數(shù)列表
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; //不確定是否為全局頻繁項(xiàng)集，則寫入分布式文件
9.end
10.}
2.4 并行計(jì)算部分候選全局頻繁項(xiàng)集的支持度計(jì)數(shù)
對于步驟2)寫入到分布式文件中的項(xiàng)目集，因?yàn)椴荒芘袛嗍欠駷槿诸l繁項(xiàng)集，所以要多建立一次Map/Reduce過程來計(jì)算這些候選項(xiàng)集的支持度計(jì)數(shù)，并且判斷是否為全局頻繁項(xiàng)集。Mapper過程中，readset()函數(shù)主要是為了讀取這些項(xiàng)集，map函數(shù)則是統(tǒng)計(jì)支持度計(jì)數(shù)。偽代碼如下:
Mapper過程:
Readset(){
1.LFPSets = loadLFP(); //讀取部分頻繁項(xiàng)集;
2. }
Map(key,value){ //value為事務(wù)ti
1.for each lfp in LFPSets do
2. If lfp in value then
3. Output
4.End
5.}
Reducer過程：
Reduce(key，value){ //key為全局候選項(xiàng)集，value為其支持度計(jì)數(shù)列表
1.C =0;
2.For each viinvalue do
3. C+= vi;
4.End
5.If C ≥ minsup then
6. Output
7.End
8.}
3 實(shí)驗(yàn)結(jié)果與分析
為了驗(yàn)證算法的正確性和高效性，在ubuntu16.04操作系統(tǒng)、主頻2.5 GHz、內(nèi)存4 G，使用基于Map/Reduce模型的Hadoop1.2.1作為平臺(tái)搭建3臺(tái)服務(wù)器實(shí)驗(yàn)集群，對數(shù)據(jù)集進(jìn)行了如下3個(gè)實(shí)驗(yàn)。
實(shí)驗(yàn)1：在數(shù)據(jù)集mushroom上驗(yàn)證基于Hadoop的2FP-Growth算法的正確性，實(shí)驗(yàn)結(jié)果見表3。
實(shí)驗(yàn)1結(jié)果表明，基于Hadoop的2FP-Growth算法的頻繁項(xiàng)集挖掘結(jié)果與FP-Growth算法的挖掘結(jié)果完全一致(誤差小于1%)，表明并行2FP-Growth算法的正確性。
實(shí)驗(yàn)2：在數(shù)據(jù)集T10I4D100K上考察在相同支持度閾值下數(shù)據(jù)規(guī)模對算法效率的影響，實(shí)驗(yàn)結(jié)果如圖4所示。
圖4 算法運(yùn)行時(shí)間對比
實(shí)驗(yàn)2結(jié)果表明，在數(shù)據(jù)集T10I4D100K上基于Hadoop的2FP-Growth算法在時(shí)間消耗上明顯小于FP-Growth、2FP-Grwoth以及COFI算法，說明基于Hadoop的2FP-Growth算法的高效性。
實(shí)驗(yàn)3：在最小支持度5%下，不同大規(guī)模數(shù)據(jù)集下算法運(yùn)行結(jié)果的比較見表4。
表4 在大規(guī)模數(shù)據(jù)集下運(yùn)行結(jié)果
實(shí)驗(yàn)3結(jié)果表明，當(dāng)輸入的數(shù)據(jù)集規(guī)模較大時(shí)，F(xiàn)P-Growth算法及其改進(jìn)算法會(huì)造成內(nèi)存溢出，當(dāng)Hadoop集群下建立3個(gè)計(jì)算機(jī)節(jié)點(diǎn)，表中的數(shù)據(jù)集將會(huì)解決內(nèi)存溢出問題，因此，文中提出的基于Hadoop的2FP-Growth算法根據(jù)數(shù)據(jù)集的規(guī)模進(jìn)行調(diào)整節(jié)點(diǎn)數(shù)是有效的。
4 結(jié) 語
提出基于Hadoop的2FP-Growth算法，并且在Hadoop平臺(tái)下實(shí)現(xiàn)，取得了較好的實(shí)驗(yàn)結(jié)果。通過與FP-Growth、COFI以及2FP-Grwoth算法在數(shù)據(jù)集Mmushroom以及T10I4D100K比較正確性和挖掘效率可以看出，基于Hadoop的2FP-Growth算法明顯高于FP-Growth、COFI以及2FP-Grwoth。實(shí)驗(yàn)結(jié)果表明,基于Hadoop的2FP-Growth算法在數(shù)據(jù)規(guī)模較大調(diào)整計(jì)算機(jī)節(jié)點(diǎn)數(shù)有較好的高效性、正確性以及算法的應(yīng)用價(jià)值。
參考文獻(xiàn)：
[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] 劉祥哲,劉培玉,任敏,等.基于負(fù)載均衡和冗余剪枝的并行FP-Growth算法[J].數(shù)據(jù)采集與處理,2016,31(1):223-230.
[5] 肖文,胡娟,周曉峰.PFPonCanTree:一種基于MapReduce的并行頻繁模式增量挖掘算法[J].計(jì)算機(jī)工程與科學(xué),2018,40(1):15-23.
[6] 厙向陽,張玲.基于Hadoop的FP-Growth關(guān)聯(lián)規(guī)則并行改進(jìn)算法[J].計(jì)算機(jī)應(yīng)用研究,2018,35(1):109-112.
[7] 施亮,錢雪忠.基于Hadoop的并行FP-Growth算法的研究與實(shí)現(xiàn)[J].微電子學(xué)與計(jì)算機(jī),2015,32(4):150-154.
[8] 王建明,袁偉.基于節(jié)點(diǎn)表的FP-Growth算法改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì),2018,39(1):140-145.
[9] 張穩(wěn),羅可.一種基于Spark框架的并行FP-Growth挖掘算法[J].計(jì)算機(jī)工程與科學(xué),2017,39(8):1403-1409.
[10] 邵梁,何星舟,尚俊娜.基于Spark框架的FP-Growth大數(shù)據(jù)頻繁項(xiàng)集挖掘算法[J].計(jì)算機(jī)應(yīng)用研究,2018(10):1-6.
[11] 王紅梅，李芬田，王澤儒.基于滑動(dòng)窗口數(shù)據(jù)流頻繁集挖掘模型綜述[J].長春工業(yè)大學(xué)學(xué)報(bào)，2017，38(5)：484-490.
