面向大數據的數據庫劃分FP-Growth改進算法

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

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

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

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

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

1 傳統的FP-growth算法

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

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

表1 事務數據庫DTable 1 Transaction database D

其算法的主要步驟如下：

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

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

(2)FP樹構造：首先創建樹的根節點，用“null”標記。第二次掃描數據庫D，在FP樹中為每個事務創建一個分枝，分枝中的每個節點對應該事務的每一個項(刪除非頻繁項)，且按表L中的順序鏈接，同時分枝中的每個項計數加1。最后，建立頻繁1項頭表與FP樹的關聯，得到如下圖1所示的FP樹。

圖1 FP樹Fig.1 FP Tree

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

Procedure FP-growth(tree,α)

IF tree含單個路徑P THEN

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

產生模式β∪α，其支持度等于β中節點的

最小支持度計數；

ELSE

FOR tree的頭表中的每個αi

{產生模式β=αi∪α，其支持度等于αi；

構造β的條件模式基，然后構造β的條件FP樹treeβ；

IF treeβ≠Φ THEN

調用FP-growth(treeβ,β)；

}

2 FP-growth算法的改進

FP-growth算法在事務數據庫規模不是很大，FP樹能夠在單機內存中存儲下的情況下是有效的。但在大數據環境下，面對海量數據庫，所構建的FP樹根本無法在單機內存中存儲，這種方法也就失效了。為此，我們對傳統的FP-growth算法進行改進。我們仍然以前面的事務數據庫D為例，說明具體的改進方法。本算法的運行環境是一個由一臺mater主機和多臺slave節點機組成的并行計算環境。在這種運行環境下，改進后的算法的實現過程如下：

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

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

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

表3 a對應的投影數據庫DaTable 3 The corresponding projection database Da with a

表4 c對應的投影數據庫DcTable 4 The corresponding projection database Dc with c

表5 d對應的投影數據庫DdTable 5 The corresponding projection database Dd with d

表6 e對應的投影數據庫DeTable 6 The corresponding projection database De with e

表7 a對應的投影子數據庫Da:1Table 7 The corresponding projection sub-database Da:1 with a

這些投影子數據庫被分發在一個個節點機上。

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

① 創建FP子樹的根節點，以“null”標記。

② 遍歷數據庫Dm:i，對Dm:i中的每個事務執行：

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

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

表8 a對應的投影子數據庫Da:2Table 8 The corresponding projection sub-database Da:2 with a

表9 c對應的投影數據庫Dc:1Table 9 The corresponding projection sub-database Dc:1 with c

表10 c對應的投影數據庫Dc:2Table 10 The corresponding projection sub-database Dc:1 with c

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

(5)每個節點機對所構建的FP子樹進行挖掘，產生局部頻繁項集。設某節點機處理生成的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根節點null開始的每一條路徑R

FOR路徑R中的每個節點p

產生模式C=p∪m，其支持度計數等于C中各節點支持度計數的最小值

FOR路徑R中的每個節點組合P

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

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

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

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

3 并行頻繁項集挖掘實現

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

第一階段實現過程如下：

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

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

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

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

第二階段實現過程如下：

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

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

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

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

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

4 算法實驗分析

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

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

從運行結果看：

(1)DPFP算法在執行效率上比傳統的FP-growth算法更高，且節點機數量越多，DPFP算法所需的時間越少，這也體現了并行處理的優勢。

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

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

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

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

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

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

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

5 總結

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