面向大數(shù)據(jù)的數(shù)據(jù)庫劃分FP-Growth改進算法

張 樂，魏昕怡，徐 蘇,林兩位

(1.南昌大學(xué)數(shù)學(xué)與計算機學(xué)院,江西 南昌 330031;2.南昌大學(xué)際鑾書院,江西 南昌 330031;3.數(shù)字福建氣象大數(shù)據(jù)研究所(閩南師范大學(xué))，福建 漳州 363000)

在傳統(tǒng)的數(shù)據(jù)挖掘領(lǐng)域，對數(shù)據(jù)集進行頻繁項集挖掘，可以采用經(jīng)典的Apriori算法[1]和FP-growth算法[2]及一些改進算法。其中，Apriori算法需要多次掃描事務(wù)數(shù)據(jù)庫，一來產(chǎn)生很大的I/O負(fù)載，二來會產(chǎn)生龐大的候選集，從而占用大量內(nèi)存空間；FP-growth算法雖然只需兩次掃描事務(wù)數(shù)據(jù)庫，大大降低了I/O負(fù)載，且不產(chǎn)生候選集，從而使算法效率更高[3]，但其算法的基礎(chǔ)是需要生成FP樹，所生成的FP樹同樣占用了大量內(nèi)存空間。

在大數(shù)據(jù)時代，面對大規(guī)模海量數(shù)據(jù)，單機環(huán)境下的存儲和計算能力將成為數(shù)據(jù)挖掘的瓶頸[4]，因此，對傳統(tǒng)算法進行改進，利用大數(shù)據(jù)、并行計算技術(shù)等進行頻繁項集挖掘成為人們研究的重點。

文獻[5-12]都是基于FP-growth算法的采用不同并行處理技術(shù)進行頻繁項集挖掘的改進的算法，算法效率有所提升。但它們都面臨著同一個問題，即在大數(shù)據(jù)環(huán)境下，面對海量事務(wù)數(shù)據(jù)庫，在單機中無法存儲所生成的FP樹，從而導(dǎo)致算法失效。文獻[13]采用了投影數(shù)據(jù)庫技術(shù)，并通過MapReduce編程模型和并行處理技術(shù)實現(xiàn)，在一定程度上解決了以上問題。但在實際應(yīng)用中，常常會遇到實際可用節(jié)點機資源有限及單個節(jié)點機內(nèi)存不足的情況，使該算法的應(yīng)用有一定局限性；在某些極端情況下還有可能出現(xiàn)某個投影數(shù)據(jù)庫的規(guī)模同樣很大，甚至接近原始事務(wù)數(shù)據(jù)庫的規(guī)模，從而同樣會導(dǎo)致算法失效的問題。為此，本文提出一種劃分?jǐn)?shù)據(jù)庫的方法，允許用戶自行設(shè)置所劃分的子數(shù)據(jù)庫的規(guī)模，從而有效解決實際應(yīng)用環(huán)境中因受單機內(nèi)存資源的限制而算法失效的問題。

1 傳統(tǒng)的FP-growth算法

FP-growth算法使用了一種稱為頻繁模式樹(FP樹)的數(shù)據(jù)結(jié)構(gòu)，F(xiàn)P樹是一種特殊的前綴樹，由頻繁項頭表和項前綴樹構(gòu)成。算法分兩個階段進行，第一個階段是將整個事務(wù)數(shù)據(jù)庫壓縮到一顆頻繁模式樹上，第二個階段是通過對頻繁模式樹進行挖掘，生成所有的頻繁項集。

我們通過一個例子來說明FP-growth算法的過程。假設(shè)事務(wù)數(shù)據(jù)庫如表1所示，該事務(wù)數(shù)據(jù)庫共有10個事務(wù)，其中包含a，b，c，d，e，f，g，h共8個項，設(shè)定最小支持度計數(shù)為min-support=2。

表1 事務(wù)數(shù)據(jù)庫DTable 1 Transaction database D

其算法的主要步驟如下：

(1)第一次掃描事務(wù)數(shù)據(jù)庫D，得到所有頻繁1項集，并對頻繁1項按支持度計數(shù)的降序排序，得到頻繁1項頭表L(如表2所示)。其中，f，g和h支持度計數(shù)為1，小于最小支持度計數(shù)，屬于非頻繁項，因此它們不會出現(xiàn)在頻繁1項集頭表L中。

表2 頻繁1項集頭表LTable 2 Frequent 1-item set

(2)FP樹構(gòu)造：首先創(chuàng)建樹的根節(jié)點，用“null”標(biāo)記。第二次掃描數(shù)據(jù)庫D，在FP樹中為每個事務(wù)創(chuàng)建一個分枝，分枝中的每個節(jié)點對應(yīng)該事務(wù)的每一個項(刪除非頻繁項)，且按表L中的順序鏈接，同時分枝中的每個項計數(shù)加1。最后，建立頻繁1項頭表與FP樹的關(guān)聯(lián)，得到如下圖1所示的FP樹。

圖1 FP樹Fig.1 FP Tree

(3)對以上生成的FP樹進行挖掘，得到全部頻繁項集。挖掘的過程是通過調(diào)用以下過程遞歸實現(xiàn)的：

Procedure FP-growth(tree,α)

IF tree含單個路徑P THEN

FOR each路徑P中節(jié)點的每個組合(記作β)

產(chǎn)生模式β∪α，其支持度等于β中節(jié)點的

最小支持度計數(shù)；

ELSE

FOR tree的頭表中的每個αi

{產(chǎn)生模式β=αi∪α，其支持度等于αi；

構(gòu)造β的條件模式基，然后構(gòu)造β的條件FP樹treeβ；

IF treeβ≠Φ THEN

調(diào)用FP-growth(treeβ,β)；

}

2 FP-growth算法的改進

FP-growth算法在事務(wù)數(shù)據(jù)庫規(guī)模不是很大，F(xiàn)P樹能夠在單機內(nèi)存中存儲下的情況下是有效的。但在大數(shù)據(jù)環(huán)境下，面對海量數(shù)據(jù)庫，所構(gòu)建的FP樹根本無法在單機內(nèi)存中存儲，這種方法也就失效了。為此，我們對傳統(tǒng)的FP-growth算法進行改進。我們?nèi)匀灰郧懊娴氖聞?wù)數(shù)據(jù)庫D為例，說明具體的改進方法。本算法的運行環(huán)境是一個由一臺mater主機和多臺slave節(jié)點機組成的并行計算環(huán)境。在這種運行環(huán)境下，改進后的算法的實現(xiàn)過程如下：

(1)第一次掃描事務(wù)數(shù)據(jù)庫D，得到所有頻繁1項集，并對頻繁1項按支持度計數(shù)的降序排序，得到頻繁1項頭表L(如表2所示)。這一步跟傳統(tǒng)FP-growth算法相同。

(2)對事務(wù)數(shù)據(jù)庫D進行數(shù)據(jù)清理，將D中的所有非頻繁1項刪除。然后對D按每個頻繁1項(表L中第一個項b除外)進行抽取，為每個頻繁1項建立一個所有事務(wù)均含該項的投影數(shù)據(jù)庫。a，c，d，e對應(yīng)的投影數(shù)據(jù)庫分別如表3～表6所示。

(3)由投影數(shù)據(jù)庫去直接生成的FP樹仍然有可能規(guī)模龐大，在單機內(nèi)存中無法存放。為此，我們對以上投影數(shù)據(jù)庫進行進一步的劃分，按預(yù)先設(shè)定所含最大事務(wù)數(shù)的方式，將投影數(shù)據(jù)庫分成一個個投影子數(shù)據(jù)庫。例如，上例中我們設(shè)定所有劃分后的投影子數(shù)據(jù)庫中包含的事務(wù)數(shù)最大為4，則a和c的投影數(shù)據(jù)庫各被進一步劃分成兩個投影子數(shù)據(jù)庫Da:1，Da:2和Dc:1，Dc:2，如表7～表10所示。

表3 a對應(yīng)的投影數(shù)據(jù)庫DaTable 3 The corresponding projection database Da with a

表4 c對應(yīng)的投影數(shù)據(jù)庫DcTable 4 The corresponding projection database Dc with c

表5 d對應(yīng)的投影數(shù)據(jù)庫DdTable 5 The corresponding projection database Dd with d

表6 e對應(yīng)的投影數(shù)據(jù)庫DeTable 6 The corresponding projection database De with e

表7 a對應(yīng)的投影子數(shù)據(jù)庫Da:1Table 7 The corresponding projection sub-database Da:1 with a

這些投影子數(shù)據(jù)庫被分發(fā)在一個個節(jié)點機上。

(4)每個節(jié)點機對投影子數(shù)據(jù)庫進行掃描，構(gòu)造對應(yīng)項的投影FP子樹。在這里我們需要對傳統(tǒng)FP-growth構(gòu)造FP樹的算法加以改進。設(shè)第k個節(jié)點機處理的是頻繁1項m對應(yīng)的投影子數(shù)據(jù)庫Dm:i。在對Dm:i中的每個事務(wù)處理時，首先將每個事務(wù)中的項按表L的次序排序，并將m以及其后的所有項全部刪除，只將剩余的項在擬構(gòu)造的FP子樹中生成分枝。具體算法如下：

① 創(chuàng)建FP子樹的根節(jié)點，以“null”標(biāo)記。

② 遍歷數(shù)據(jù)庫Dm:i，對Dm:i中的每個事務(wù)執(zhí)行：

a.將事務(wù)中的項按L中的次序排序，并將m以及其后的所有項全部刪除，形成事務(wù)項列表記為[p│P]，其中p為第一個項元素，而P為剩余項元素的列表。

b.調(diào)用insert_tree([p│P]，T)。insert_tree([p│P]，T)執(zhí)行過程如下：如果T有一個子女N使得N.item-name=p.item-name，則N的計數(shù)增1，同時頭表中其對應(yīng)項支持度計數(shù)增1；否則創(chuàng)建一個新節(jié)點N，將其計數(shù)設(shè)置為1，鏈接到它的父節(jié)點T，同時頭表中添加一項，支持度計數(shù)設(shè)置為1。如果P非空，遞歸地調(diào)用insert_tree([p│P]，T)。

表8 a對應(yīng)的投影子數(shù)據(jù)庫Da:2Table 8 The corresponding projection sub-database Da:2 with a

表9 c對應(yīng)的投影數(shù)據(jù)庫Dc:1Table 9 The corresponding projection sub-database Dc:1 with c

表10 c對應(yīng)的投影數(shù)據(jù)庫Dc:2Table 10 The corresponding projection sub-database Dc:1 with c

由此改進算法生成的FP樹稱為頻繁1項m所對應(yīng)的投影子數(shù)據(jù)庫的FP子樹Tm:i，為a，c，d，e構(gòu)建的投影FP子樹分別如圖2～圖7所示。

(5)每個節(jié)點機對所構(gòu)建的FP子樹進行挖掘，產(chǎn)生局部頻繁項集。設(shè)某節(jié)點機處理生成的m的FP子樹為Tm:i，則由條件FP子樹挖掘頻繁項集的算法如下：

圖2 a的投影FP子樹Ta:1Fig.2 Projection FP subtree Ta:1 with a

圖3 a的投影FP子樹Ta:2Fig.3 Projection FP subtree Ta:2 with a

圖4 c的投影FP子樹Tc:1Fig.4 Projection FP subtree Tc:1 with c

圖5 c的投影FP子樹Tc:2Fig.5 Projection FP subtree Tc:2 with c

圖6 d的投影FP子樹Td:1Fig.6 Projection FP subtree Td:1 with d

FOR從樹Tm:i根節(jié)點null開始的每一條路徑R

FOR路徑R中的每個節(jié)點p

產(chǎn)生模式C=p∪m，其支持度計數(shù)等于C中各節(jié)點支持度計數(shù)的最小值

FOR路徑R中的每個節(jié)點組合P

局部頻繁模式=P∪m，其支持度計數(shù)等于C的支持度計數(shù)

(6)將同一個頻繁1項的投影子數(shù)據(jù)庫生成的局部頻繁項集匯聚到同一個節(jié)點機進行歸并，產(chǎn)生該頻繁1項的頻繁項集。

(7)最后匯總所有節(jié)點機生成的頻繁1項對應(yīng)的頻繁項集，從而得到全部的頻繁項集。

圖7 e的投影FP子樹Te:1Fig.7 Projection FP subtree Te:1 with e

3 并行頻繁項集挖掘?qū)崿F(xiàn)

改進后的頻繁項集挖掘分為兩個階段：第一階段生成全部的頻繁1項集，并構(gòu)建頻繁1項頭表L，我們可以使用MapReduce編程模型并行實現(xiàn)[14,15]；第二階段由多個節(jié)點機并行挖掘頻繁項集，最后匯總得到全部的頻繁項集。

第一階段實現(xiàn)過程如下：

(1)在master主機上將事務(wù)數(shù)據(jù)庫中的事務(wù)分成相同的n個數(shù)據(jù)塊，然后把n個數(shù)據(jù)塊發(fā)送到n個slave節(jié)點機。

(2)每個slave節(jié)點機進行并行Map處理，計算出局部的1項集及其支持度計數(shù)；然后通過Combiner函數(shù)合并相同項，并把結(jié)果發(fā)送給master主機。

(3)master主機進行Reduce處理，將所有slave節(jié)點發(fā)送來的結(jié)果進行匯總，計算出全局頻繁1項集及其支持度計數(shù)，然后按支持度計數(shù)值對頻繁1項集降序排序，最終得到排序后的結(jié)果頭表L(如表2所示)。

由于采用MapReduce模式并行實現(xiàn)，這一過程所花費的時間將比傳統(tǒng)FP-growth算法更少。

第二階段實現(xiàn)過程如下：

(1)首先每個節(jié)點機對此前master分發(fā)來的數(shù)據(jù)塊進行數(shù)據(jù)清理，將數(shù)據(jù)塊中的所有非頻繁1項刪除。然后對數(shù)據(jù)塊進行頻繁1項抽取，為每個頻繁1項生成部分投影數(shù)據(jù)庫，同一頻繁1項的所有部分投影數(shù)據(jù)庫被匯聚到同一節(jié)點機，生成所有記錄都包含該頻繁1項的投影數(shù)據(jù)庫。

(2)由slave節(jié)點機對每個投影數(shù)據(jù)庫進行進一步的劃分，按預(yù)先設(shè)定所含最大事務(wù)記錄數(shù)的方式，將投影數(shù)據(jù)庫分成一個個投影子數(shù)據(jù)庫。

(3)每個slave節(jié)點機為投影子數(shù)據(jù)庫生成對應(yīng)的FP子樹，并對這些FP子樹進行挖掘生成局部頻繁項集。

(4)同一投影數(shù)據(jù)庫對應(yīng)的所有子數(shù)據(jù)庫生成的局部頻繁項匯聚到同一節(jié)點機上，生成該投影數(shù)據(jù)庫對應(yīng)的頻繁項集，然后將結(jié)果發(fā)送給master主機。

(5)master主機將所有結(jié)果匯總后得到的就是全部的頻繁項集。

4 算法實驗分析

傳統(tǒng)的FP-Growth算法在面對海量事務(wù)數(shù)據(jù)庫時將會遇到因所生成的FP樹規(guī)模龐大而無法在單機內(nèi)存中存儲從而導(dǎo)致算法失效這一問題已在文獻[12]中進行了驗證。本文所提出的算法因為采用了數(shù)據(jù)庫劃分的方法，不會存在這一問題。因此，本實驗主要針對本文所提出的劃分?jǐn)?shù)據(jù)庫算法(記為DPFP算法)在并行計算環(huán)境下的運行效率進行分析。實驗方法主要是將DPFP算法在Hadoop集群環(huán)境下的運行時間與傳統(tǒng)的FP-growth算法在單機環(huán)境下的運行時間進行比對。Hadoop集群環(huán)境采用主從式架構(gòu)，包括1個master主機(配置為Intel i7-9700 CPU，16GB內(nèi)存)和最多10個slave節(jié)點機(配置為Intel i5-2450 CPU，4GB內(nèi)存)。

實驗一：DPFP算法分別在由1臺master主機加5臺slave節(jié)點機和1臺master主機加10臺slave節(jié)點機組成的集群環(huán)境上運行，F(xiàn)P-growth算法在單臺節(jié)點機上運行。實驗數(shù)據(jù)集選取Frequent Itemset Mining Data Repository[16]里的T1014D100K.dat，該數(shù)據(jù)集包含10萬條記錄。其中設(shè)定的最小支持度分別為2%，4%，6%，8%和10%。實驗結(jié)果分別如圖8，9所示。

從運行結(jié)果看：

(1)DPFP算法在執(zhí)行效率上比傳統(tǒng)的FP-growth算法更高，且節(jié)點機數(shù)量越多，DPFP算法所需的時間越少，這也體現(xiàn)了并行處理的優(yōu)勢。

(2)隨著最小支持度數(shù)值的增加，兩種算法的挖掘時間都逐漸減少。這是因為最小支持度數(shù)值越大，頻繁項越少。對FP-growth算法來說，最小支持度數(shù)值越大，生成的FP樹越小，對FP樹遞歸挖掘的時間也就越少；對DPFP算法來說，最小支持度數(shù)值越大，生成的頻繁1項投影數(shù)據(jù)庫越少，分發(fā)數(shù)據(jù)的時間就越少，對投影子數(shù)據(jù)庫進行挖掘的時間也就越少。

(3)DPFP算法相比FP-growth算法的加速比并不會隨著最小支持度數(shù)值的增加而成線性增長[17]，這是因為最小支持度越大，DPFP算法中所進行的投影數(shù)據(jù)庫生成和分發(fā)所占的時間比值越大，而這些操作在FP-growth算法中是沒有的。因此，當(dāng)最小支持度逐漸增大后，F(xiàn)P-growth算法所生成的FP樹越來越小，遞歸挖掘的時間會越來越呈線性遞減的趨勢。

最小支持度圖8 實驗一5臺節(jié)點機Fig.8 Experiment 1:5-Node machines

最小支持度圖9 實驗一10臺節(jié)點機Fig.9 Experiment 1:10-Node machines

實驗二：DPFP算法在由1臺master主機加10臺slave節(jié)點機組成的集群環(huán)境上運行，F(xiàn)P-growth算法仍然在單臺節(jié)點機上運行。實驗數(shù)據(jù)由IBM QUEST Market-Basket Synthetic Data Generator產(chǎn)生，選取包含100萬條記錄的事務(wù)數(shù)據(jù)庫。設(shè)定的最小支持度同樣分別為2%，4%，6%，8%和10%。實驗結(jié)果如圖10所示。

從運行結(jié)果看，隨著事務(wù)數(shù)據(jù)庫規(guī)模的增大，DPFP算法的效率更加明顯。這是因為數(shù)據(jù)庫規(guī)模越大，F(xiàn)P-growth算法生成的FP樹就越大，遞歸挖掘龐大的FP樹將非常耗時。而對DPFP算法來說，投影數(shù)據(jù)庫生成和分發(fā)所占的時間比值變得更小，且因為DPFP算法劃分的子數(shù)據(jù)庫規(guī)模接近，分配到各節(jié)點機的負(fù)載更均衡，由多個節(jié)點機并行處理的效率更加顯現(xiàn)出來。

最小支持度圖10 實驗二10臺節(jié)點機Fig.10 Experiment 2:10-Node machines

5 總結(jié)

本文所提出的算法基于傳統(tǒng)的FP-growth算法進行改進，并通過Hadoop架構(gòu)和MapReduce編程模型實現(xiàn)。在該算法中，首先對所有頻繁1項生成投影數(shù)據(jù)庫，再對投影數(shù)據(jù)庫進行劃分。由于用戶可以靈活設(shè)置所劃分的子數(shù)據(jù)庫中事務(wù)記錄的數(shù)量，因此可以有效控制由這些子數(shù)據(jù)庫生成的FP子樹的規(guī)模，從而有效解決因FP樹在單機內(nèi)存中存儲不下導(dǎo)致算法失效的問題。同時由于采用MapReduce編程模型實現(xiàn)并行FP子樹的生成和挖掘，且分發(fā)到各節(jié)點機的用于生成FP子樹的子數(shù)據(jù)庫規(guī)模接近，使得各節(jié)點機上的負(fù)載更均衡。在大規(guī)模集群環(huán)境下使用該算法可以很好地解決對大數(shù)據(jù)的挖掘。