一種基于SOM劃分的FP-growth算法

郟奎奎，劉海濱

(中國航天系統(tǒng)科學(xué)與工程研究院，北京 100048)

0 引 言

數(shù)據(jù)挖掘被稱為數(shù)據(jù)集中的知識發(fā)現(xiàn)，是在大量數(shù)據(jù)集中提取對于決策過程有用的知識的過程。數(shù)據(jù)挖掘自20世紀90年代被提出后，在許多領(lǐng)域得到了很好的應(yīng)用。關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘的重要組成部分。1993年，R.Agrawal等[1]提出了關(guān)聯(lián)規(guī)則的概念及模型，該模型主要是對一個事物和其他事物相互關(guān)聯(lián)的一種描述。目前，主要的關(guān)聯(lián)規(guī)則挖掘算法有Apriori和FP-growth，二者都是串行化的算法。Apriori[2]算法需要多次掃描數(shù)據(jù)集，過程中產(chǎn)生了大量候選集，測試這些候選集需消耗大量時間。FP-growth算法是一種基于頻繁模式樹的挖掘算法。該算法可以有效挖掘頻繁模式，并且比Apriori算法快大約一個數(shù)量級。但是隨著數(shù)據(jù)量的增大和數(shù)據(jù)集中的有用信息變得越來越稀疏，在建立FP-tree時會消耗大量的內(nèi)存空間，以至于內(nèi)存不夠用，無法完成挖掘任務(wù)[3-4]。Park等[5]提出利用系統(tǒng)抽樣的方法進行數(shù)據(jù)挖掘，然而單純只依靠抽樣的數(shù)據(jù)進行數(shù)據(jù)挖掘很容易造成結(jié)果的畸形和不準確。因此，學(xué)者們開始考慮通過并行計算環(huán)境來解決上述問題。文獻[6]采用基于多線程的并行算法，雖然緩解了存儲及計算的壓力，但是內(nèi)存資源的局限制約了算法的擴展能力；文獻[7-8]中對MPI并行環(huán)境進行了詳細的敘述，然而該環(huán)境使用進程間通信的方式協(xié)調(diào)并行計算，導(dǎo)致并行效率較低、內(nèi)存開銷大并且很難解決多節(jié)點的擴展性問題。并行算法通常具有較大的進程間的調(diào)度和通信開銷，并且很難將構(gòu)建FP-tree的任務(wù)進行分割。

在前人研究成果的基礎(chǔ)上，文中提出了一種改進的FP-growth算法。眾所周知，數(shù)據(jù)集中高頻率的項集是包含在每條事務(wù)中的，那么含有頻繁項集的事務(wù)之間的歐氏距離總是較小的，所以數(shù)據(jù)集中的事務(wù)會具有聚類現(xiàn)象。利用SOM等聚類算法對其做聚類分析，再在每個類別上并行執(zhí)行數(shù)據(jù)挖掘算法就可以得到挖掘結(jié)果了。首先利用聚類算法對數(shù)據(jù)集進行分割，然后在每個數(shù)據(jù)子集上并行執(zhí)行FP-growth算法，這樣就將算法所需要的大內(nèi)存空間分割成小內(nèi)存進行運算了，并且由于子集是根據(jù)聚類結(jié)果劃分的，所以在各個子集上能夠高效地挖掘出有用的關(guān)聯(lián)規(guī)則，而非由于隨機劃分數(shù)據(jù)集導(dǎo)致挖掘出具有不確定性的規(guī)則。由于數(shù)據(jù)量較大，對大數(shù)據(jù)集做聚類分析會耗費大量的計算資源，所以文中利用系統(tǒng)抽樣方法從大數(shù)據(jù)集中抽取出具有代表性的樣本，然后利用SOM算法對樣本進行聚類分析，得到分類模型，利用該模型將整個數(shù)據(jù)集分成若干個子集，并在各個子集上采用FP-growth算法挖掘出關(guān)聯(lián)規(guī)則，最后將關(guān)聯(lián)規(guī)則合并得到總的結(jié)果，并通過實驗驗證了該算法的有效性。

1 SOM算法相關(guān)研究

聚類分析是目前數(shù)據(jù)挖掘的研究熱點之一，聚類分析能夠?qū)?shù)據(jù)聚類成為多個類或簇，從而使得在同一個類中的數(shù)據(jù)具有比較高的相似度，而不同類的數(shù)據(jù)之間有比較大的差別[9]。聚類分析過程是無監(jiān)督的分析過程，在對數(shù)據(jù)進行分類之前，對類別數(shù)據(jù)是未知的。經(jīng)典的聚類分析算法有K-means、CURE等，這些算法需要提前設(shè)定聚類的類別數(shù)。這種事前設(shè)定類別數(shù)的做法大多基于程序設(shè)計經(jīng)驗，并且需要經(jīng)過不斷試驗才能得到比較正確的分類，這種做法具有一定的不確定性，在一定程度上降低了聚類分析結(jié)果的可信度。自組織映射(self-organizing map)是由芬蘭學(xué)者Kohonen提出的一種只有兩層神經(jīng)網(wǎng)絡(luò)的算法。SOM的權(quán)值調(diào)整方法與其他神經(jīng)網(wǎng)絡(luò)相似，都是采用梯度下降法不斷地調(diào)整權(quán)值。它比較特有的地方就是將高維數(shù)據(jù)點按照原有的順序拓撲關(guān)聯(lián)到二維平面網(wǎng)格節(jié)點上，這樣就實現(xiàn)了高維數(shù)據(jù)的二維結(jié)構(gòu)可視化。此外，由于SOM的高維數(shù)據(jù)的低維表達能力，SOM在數(shù)據(jù)分類、聚類等應(yīng)用領(lǐng)域有很多成功的應(yīng)用案例。文中利用SOM聚類算法實現(xiàn)對海量數(shù)據(jù)的聚類分析，進而利用聚類模型對數(shù)據(jù)庫進行分割，并在各個子集上進行FP-growth數(shù)據(jù)挖掘。

1.1 SOM算法描述

SOM神經(jīng)網(wǎng)絡(luò)算法是一種特殊的神經(jīng)網(wǎng)絡(luò)，由輸入層和輸出層構(gòu)成。在輸入層上只存在一個神經(jīng)元節(jié)點，該神經(jīng)元節(jié)點對應(yīng)于輸入向量x=[x1,x2,…,xd]，其中d是輸入數(shù)據(jù)維數(shù)；在輸出層上有一系列的組織在二維平面網(wǎng)格上的神經(jīng)元節(jié)點。每個神經(jīng)元節(jié)點都相應(yīng)地有一個權(quán)矢量m=[m1,m2,…,md]。SOM神經(jīng)網(wǎng)絡(luò)權(quán)值的訓(xùn)練步驟如下：

(1)設(shè)定輸出層每個節(jié)點的初始權(quán)重值。通過預(yù)先定義一個訓(xùn)練長度或者設(shè)定程序終止的誤差閾值，來判斷訓(xùn)練的終止條件。

(2)在數(shù)據(jù)集中選取一個樣本x，計算樣本與每個輸出層神經(jīng)元節(jié)點之間的歐氏距離,然后選取與樣本x距離最近的神經(jīng)元節(jié)點,該神經(jīng)元節(jié)點稱為該樣本的最佳匹配節(jié)點(best-match unit,BMU),記為mc。

‖x-mc‖=min{‖x-mi‖}

(1)

(3)依據(jù)預(yù)先設(shè)定的鄰域函數(shù)來確定BMU鄰域的范圍,進而利用調(diào)節(jié)函數(shù)調(diào)整BMU及其鄰域內(nèi)神經(jīng)元節(jié)點的權(quán)重值:

mi(t+1)=mi(t)+a(t)hci(t)[x(t)-mi(t)]

(2)

其中，mi(t)為第t步節(jié)點i的權(quán)值；a(t)為第t步的學(xué)習(xí)率；hci(t)為鄰域函數(shù)。

學(xué)習(xí)率一般伴隨著訓(xùn)練的推進而逐漸變小,這里一般選擇按線性減小、指數(shù)減小的方式。這里的鄰域函數(shù)通常使用高斯函數(shù)或者氣泡函數(shù)。

(4)如果還沒有達到訓(xùn)練結(jié)束的條件,則返回步驟(2)繼續(xù)訓(xùn)練。

1.2 聚簇分布特征圖

人們通常難以從高維數(shù)據(jù)中區(qū)分出數(shù)據(jù)的分布特征，然而SOM算法能夠?qū)⒏呔S數(shù)據(jù)拓撲保序地映射到二維平面網(wǎng)格上，映射后的數(shù)據(jù)結(jié)構(gòu)具有顯著的聚類特征，從而能夠高效地識別出聚類數(shù)據(jù)。文中利用SOM算法的這一特征來實現(xiàn)大數(shù)據(jù)集的聚類分析。眾所周知，很多算法在進行聚類分析之前往往需要盲目地確定聚類的簇數(shù)，尤其隨著數(shù)據(jù)的增大，這種方法往往效果很差。針對這種情況,設(shè)計了一種聚類分布特征圖,這個特征用來在聚類前先對數(shù)據(jù)進行預(yù)處理,這樣就能快速獲得數(shù)據(jù)分布的特點,從而確定數(shù)據(jù)聚類的類別數(shù)目。

通常訓(xùn)練好的SOM神經(jīng)網(wǎng)絡(luò)的輸出層往往組織成一個網(wǎng)絡(luò)結(jié)構(gòu),然后對每個神經(jīng)元節(jié)點按列優(yōu)先進行編號。假定SOM輸出層共有m*n個神經(jīng)元節(jié)點，則定義下面的距離矩陣(distance-matrix)，簡稱D-matrix：

(3)

其中，dij表示第i個神經(jīng)元節(jié)點與第j個神經(jīng)元節(jié)點之間的歐氏距離。

接著將距離與一個顏色范圍建立一一對應(yīng)的關(guān)系，一般在灰度模式下，距離自小到大，距離所對應(yīng)的顏色由淺至深，所以就可以得到一個與距離矩陣相對應(yīng)的顏色矩陣(color-matrix)，簡稱C-matrix。

(4)

其中，cij表示與dij相對應(yīng)的顏色取值。

對每個輸出層節(jié)點根據(jù)顏色矩陣進行灰度值的著色，那么就得到了一張聚類分布特征圖，根據(jù)聚類分布特征圖就可以確定聚類個數(shù)。

2 FP-growth算法研究

2.1 關(guān)聯(lián)規(guī)則挖掘的定義

關(guān)聯(lián)規(guī)則是對一個事物和其他事物相互關(guān)聯(lián)的一種描述。關(guān)聯(lián)規(guī)則的挖掘就是從大量的數(shù)據(jù)集中找出這些數(shù)據(jù)之間的相互聯(lián)系。衡量規(guī)則的2個度量是支持度和置信度。

定義1：規(guī)則A?B在事務(wù)集D中成立，具有支持度S(support)，S是D中包含A∪B的事務(wù)數(shù)與所有事務(wù)數(shù)之比，記為support(A?B)，它等于事務(wù)包含集合A和B的并的概率P(A∪B)。即

support(A?B)=P(A∪B)=D(X)/|D|

(5)

其中，D(X)是數(shù)據(jù)集D包含X的事務(wù)數(shù)。

定義2：規(guī)則A?B在事務(wù)集D中的置信度C(confidence)是指包含A和B的事務(wù)數(shù)與包含A的事務(wù)數(shù)之比,它是條件概率P(A|B)。即

confidence(A?B)=P(A|B)=support(A∪

B)/support(A)

(6)

關(guān)聯(lián)規(guī)則挖掘首先要找出所有滿足最小支持度的項集，再計算出置信度大于閾值的所有關(guān)聯(lián)規(guī)則。

2.2 FP-growth算法

FP-growth算法主要是利用一個樹型結(jié)構(gòu)來存儲數(shù)據(jù)項之間的順序關(guān)系，它通常需要掃描兩次數(shù)據(jù)庫來構(gòu)建FP-tree，第一次掃描獲得頻繁1-項集，并篩選出滿足支持度大小的頻繁項，根據(jù)頻繁項的支持度計數(shù)進行從高到低的排序。第二次掃描數(shù)據(jù)庫就是按照第一次的頻繁項排序?qū)υ际聞?wù)中的數(shù)據(jù)項重新排序，并將其添加到以“NULL”為根節(jié)點的FP-tree中。在構(gòu)建FP-tree的過程中，通常會建立一個項頭表T，表中包括三部分信息，分別是頻繁項、對應(yīng)的支持度計數(shù)和指向FP-tree節(jié)點的指針。根據(jù)FP-tree提取出條件模式基，滿足置信度閾值的條件模式基和后綴就是挖掘出的關(guān)聯(lián)規(guī)則。

FP-growth算法主要由三個模塊構(gòu)成：FP-growth模塊主要是FP-growth算法執(zhí)行的流程；Insert模塊主要完成FP樹的構(gòu)建過程；Search模塊用來獲取條件模式基集合，該條件模式基集合可以用來確定最后的關(guān)聯(lián)規(guī)則。

(1)Insert模塊。

輸入：已排序的頻繁項集Li，F(xiàn)P(子)樹根節(jié)點Rr

輸出：FP(子)樹Rr

IfLi!=null then

取出Li的第一項i

IfRr存在某子節(jié)點N=ithen

++N.count

Else

創(chuàng)建Rr的子節(jié)點N,節(jié)點內(nèi)容為i

N.count=l

將N加入項頭表中

Insert(Li-1,N)

(2)Search模塊。

輸入：FP樹T,后綴模式α

輸出：頻繁項集合L_S

IfT中只有一個分支Pthen

ForP上節(jié)點的每個組合β

β=α∪β

L_S=L_S∪{β}

Else

ForT中的每個頻繁項i

構(gòu)造β的條件模式及條件FP樹Rβ

IfRβ≠? then

Search(Rβ,β)

(3)FP-growth模塊。

輸入：事務(wù)集合T，最小支持度min_sup，最小置信度min_conf

輸出：強關(guān)聯(lián)規(guī)則集合R_S

掃描T找出頻繁1-項集L

按支持度計數(shù)降序排序L

創(chuàng)建FP樹的根節(jié)點NULL

ForT中的每個事務(wù)t

找出t中的頻繁1-項集合Li

Li中的項按L中的順序排序

Insert(Li,NULL)

L_S=Search(FP,NULL)

在L_S中產(chǎn)生強關(guān)聯(lián)規(guī)則集合R_S

接下來用一個簡單的例子解釋如何構(gòu)建FP樹。假設(shè)存在事務(wù)集合T，如表1所示。假定min_sup=20%，那么事務(wù)集支持度計數(shù)=20%×10=2次。首先掃描一遍事務(wù)集，統(tǒng)計各類項的支持度計數(shù)，去掉支持度計數(shù)小于2的項。然后將頻繁1-項按照支持度計數(shù)從高到低排序，生成排序的頻繁1-項集L1=[B:8,A:7,C:5,D:2,E:2]。

表1 事務(wù)集合T

根據(jù)排好序的頻繁1-項集集合創(chuàng)建項頭表，然后再遍歷一遍數(shù)據(jù)庫，構(gòu)建FP樹。構(gòu)建過程按照L1中項的順序創(chuàng)建，將頻繁項按照順序插入到以NULL為根節(jié)點的樹中，隨著事務(wù)中數(shù)據(jù)項的插入更新各個樹節(jié)點的支持度計數(shù)。根據(jù)Insert算法，遍歷所有事務(wù)之后得出圖1所示的FP-tree。故FP-growth算法是將事務(wù)中所有符合要求的項、項的計數(shù)以及項之間的相互關(guān)系都壓縮到一棵樹中。

圖1 FP樹與項頭表

3 基于SOM劃分的FP-growth算法

3.1 算法過程

FP-growth通過構(gòu)造FP-tree來尋找頻繁模式，然而當(dāng)數(shù)據(jù)集達到一定規(guī)模時，構(gòu)造基于內(nèi)存的FP-tree仍然是不現(xiàn)實的。文中提出的基于SOM劃分的FP-growth算法能解決上述問題。該算法利用SOM聚類方法得到信息較為聚集的數(shù)據(jù)子集，在各個子集上并行實施FP-growth算法，從而在大型數(shù)據(jù)集上挖掘出關(guān)聯(lián)規(guī)則。該算法總體分成5步:數(shù)據(jù)標準化；按照系統(tǒng)抽樣的方法從數(shù)據(jù)集中抽取樣本數(shù)據(jù)；利用SOM算法對樣本數(shù)據(jù)聚類，得到數(shù)據(jù)集事務(wù)的分類模型；將整個數(shù)據(jù)集中的事務(wù)按照分類模型分成若干個數(shù)據(jù)子集，在數(shù)據(jù)子集上并行執(zhí)行FP-growth挖掘；匯總結(jié)果。算法流程如圖2所示。

(1)數(shù)據(jù)標準化。

數(shù)據(jù)集中的每條事務(wù)中包含的項都是離散的，為了便于求解事務(wù)之間的歐氏距離，需要把事務(wù)中的項改為用數(shù)字表示，含有對應(yīng)的項記為1，不含的記為0。具體過程如下：

圖2 算法流程

(a)掃描一遍數(shù)據(jù)集，求出數(shù)據(jù)集中大于支持度的頻繁1-項集L1；

(2)抽取樣本。

(a)將數(shù)據(jù)庫D中事務(wù)編號，每條事務(wù)對應(yīng)一個唯一的編號；

(b)將編號按某個間隔分成k段,當(dāng)N/n(N表示數(shù)據(jù)集中的總的事務(wù)數(shù),n表示樣本容量大小)是整數(shù)時，k=N/n；當(dāng)N/n為小數(shù)時,從總的事務(wù)中去除一些事務(wù),使剩下的事務(wù)數(shù)目能被n整除,這時k=N'/n(N'為剩下的事務(wù)數(shù))；

(c)在第一段中隨機確定一個編號l;

(d)從整體中按照編號l,l+k,…,l+(n-1)k抽取出來作為樣本。

(3)聚類分析。

利用SOM算法對樣本數(shù)據(jù)進行聚類分析，經(jīng)過若干次迭代運算，得到自組織神經(jīng)元間的距離數(shù)據(jù)，神經(jīng)元之間距離小的為同一類，距離大的為不同類。神經(jīng)元在二維平面上的分布情況很容易通過肉眼大概分辨出數(shù)據(jù)集中存在幾類數(shù)據(jù)。類別個數(shù)可以根據(jù)需要而定，一般情況下分得精細度越高，數(shù)據(jù)集中的類別數(shù)越多。文中在實驗驗證階段，依次提高數(shù)據(jù)劃分的精確度來驗證算法的加速程度。確定分類個數(shù)后，利用點集最小圓覆蓋法[12]確定每個類別的中心位置，得到中心位置集合：

C={c1,c2,…,cn}

(7)

其中，n為分類的類別數(shù)。

C中任何一個元素ck表示如下：

ck={ck1,ck2,…,ckm}

(8)

其中，m為中心坐標點的維數(shù)。

(4)FP-growth挖掘。

將數(shù)據(jù)集中的每條數(shù)據(jù)與C中的中心點進行比較，距離最小的中心點所屬的類別就是該條數(shù)據(jù)所屬的類別，即：

‖ti-cmin‖=min{‖ti-ck‖}

(9)

其中，ti表示任意一條事務(wù)數(shù)據(jù)；cmin表示與ti最近的中心點；ck表示C中任意一個中心點。

根據(jù)事務(wù)ti所屬的類別將其分配到對應(yīng)的計算節(jié)點上，這個分配過程在分布式計算Spark框架內(nèi)完成，在Spark平臺上編寫的數(shù)據(jù)分配程序依據(jù)事務(wù)數(shù)據(jù)與中心點的歐氏距離來分配數(shù)據(jù)所屬計算節(jié)點，詳細的Spark平臺的搭建和配置過程可參考文獻[13]。經(jīng)過數(shù)據(jù)分割后,數(shù)據(jù)集D被分割成s個子集，表示為D=D1∪D2∪…∪Ds。

在每個計算節(jié)點上構(gòu)建FP-tree，構(gòu)建過程按照2.2節(jié)的算法。由于這個階段之前已經(jīng)得到頻繁1-項集，并且該項集已按照支持度從大到小排序，所以只需將每條事務(wù)中的項添加到FP-tree上即可。

(5)結(jié)果匯總。

(a)在每個計算節(jié)點上，根據(jù)2.2節(jié)的Search()算法求出所有條件模式基；

(c)將(b)中得到的關(guān)聯(lián)規(guī)則合并就得到了整個數(shù)據(jù)集中蘊含的關(guān)聯(lián)規(guī)則。由于之前做了SOM聚類分析，所以每個數(shù)據(jù)子集上包含有相應(yīng)類別的高密度頻繁項，那么也就包含了對應(yīng)的關(guān)聯(lián)規(guī)則。假設(shè)數(shù)據(jù)集D中包含的關(guān)聯(lián)規(guī)則集R={r1,r2,…,rn}(n表示數(shù)據(jù)集中包含的關(guān)聯(lián)規(guī)則個數(shù)，ri表示任意一條關(guān)聯(lián)規(guī)則)，任意一個數(shù)據(jù)子集所包含的關(guān)聯(lián)規(guī)則集RDi={rDi1,rDi2,…,rDim}(i=1,2,…,n，m表示子集中包含的關(guān)聯(lián)規(guī)則的個數(shù)，rDij表示子集中任意一條關(guān)聯(lián)規(guī)則)，則有：RD1∪RD2∪…∪RDs=R={r1,r2,…,rn}。

3.2 算法復(fù)雜度分析

假設(shè)某挖掘任務(wù)中有s個關(guān)聯(lián)規(guī)則、m個符合最小支持度的項，事務(wù)有n個、平均每個事務(wù)中包含a個符合最小支持度的項。那么經(jīng)典算法獲取s個關(guān)聯(lián)規(guī)則，忽略連接數(shù)據(jù)庫等開銷，算法需要計算的次數(shù)為m×n×a+m×s，由于n和m占主導(dǎo)作用，所以時間復(fù)雜度為O(mn)。假設(shè)抽取樣本的個數(shù)為b，聚類個數(shù)為c，改進算法的時間復(fù)雜度為m×n×a+m×s+c×b，由于b和c相較于其他項很小，可以忽略不計，所以時間復(fù)雜度也為O(mn)[14-15]。雖然改進算法與原算法的時間復(fù)雜度相同，但是由于改進算法將數(shù)據(jù)庫分割成小的子集，大大降低了算法的空間復(fù)雜度，減小了計算過程中的內(nèi)存空間占用量，增大了對海量數(shù)據(jù)挖掘的可能性。而且在改進算法中各個子集并行進行數(shù)據(jù)挖掘，也大大縮減了運算時間。

4 實驗及結(jié)果分析

通過實驗對提出的基于SOM劃分的FP-tree算法進行驗證。實驗中的數(shù)據(jù)集均來自Frequent Itemset Mining Dataset Repository。

4.1 SOM聚類分析結(jié)果

實驗中使用的是connect.data數(shù)據(jù)集。對該數(shù)據(jù)集進行抽樣，對抽樣樣本進行SOM聚類分析，經(jīng)過100次迭代后，二維平面上的神經(jīng)元出現(xiàn)了聚簇，相似的神經(jīng)元相互靠近，不同類的神經(jīng)元相互遠離。每個神經(jīng)元都與某些輸入點有著強連接，并且神經(jīng)元之間也存在著連接權(quán)值，將距離較近的神經(jīng)元歸為一類，它們對應(yīng)的樣本點也屬于同一類。

為了凸顯聚類效果，在每一個類別上加入一個收縮因子，在收縮因子的作用下樣本點向各自的數(shù)據(jù)中心靠攏。為了更直觀地看到分類效果，在每個類別上分別標記不同的圖形：三角形、方形、菱形和圓形。經(jīng)過多次調(diào)整參數(shù)，得到的聚類效果如圖3所示。由于這個過程需要比較復(fù)雜的編程，所以利用Java程序編程實現(xiàn)聚類的效果顯示。

圖3 聚類效果

從圖中可以看出，經(jīng)過SOM聚類分析，樣本數(shù)據(jù)分成了4類，雖然每個類別有一些數(shù)據(jù)相互重疊，但是總體上并不影響最后的聚類效果。

4.2 基于SOM劃分的FP-growth算法性能實驗

根據(jù)4.1中的聚類結(jié)果，將原數(shù)據(jù)集分割成4個子集，在每個子集上并行執(zhí)行FP-growth算法。算法執(zhí)行過程中單個計算節(jié)點的內(nèi)存占用情況如圖4(a)所示。圖4(b)顯示的是未改進的FP-growth算法執(zhí)行過程中的內(nèi)存占用量。圖4中顯示的是加上計算機操作系統(tǒng)和其他進程所占的內(nèi)存空間后的內(nèi)存使用情況，并且是以60 s為一個時間片段顯示的。通過比較發(fā)現(xiàn)，改進算法內(nèi)存占用量遠遠低于未改進算法，可以用來對大型數(shù)據(jù)集進行數(shù)據(jù)挖掘，而未改進的FP-growth在對大型數(shù)據(jù)集進行挖掘時，很快就會占用大量內(nèi)存，以至于計算機物理內(nèi)存空間不夠造成數(shù)據(jù)挖掘任務(wù)無法繼續(xù)進行。

圖4 內(nèi)存占用量

將改進算法與Apriori算法和FP-growth算法進行速度上的比較，在支持度為5%的情況下，各個算法的運算時間如圖5所示。

從圖中可以看出，隨著數(shù)據(jù)量的增加，三種算法所消耗的時間都在增加，然而FP-growth算法的時間消耗明顯低于Apriori算法，主要因為隨著數(shù)據(jù)量的增大，Apriori算法會產(chǎn)生大量的候選項，這些候選項的處理耗費了大量時間。改進的FP-growth算法相較于沒有改進的FP-growth算法明顯降低了算法的運算時間。從圖中可以看出,未改進的FP-growth算法隨著數(shù)據(jù)量的增加所消耗的時間也在快速增長，而改進的FP-growth算法呈現(xiàn)平緩的增長趨勢，由此可見改進算法在性能上有明顯的提升。

圖5 執(zhí)行時間對比

5 結(jié)束語

主要闡述了對FP-growth算法改進的過程。該算法利用SOM聚類算法對從大數(shù)據(jù)集中抽樣的樣本進行聚類分析，根據(jù)聚類結(jié)果將大數(shù)據(jù)集分解成若干個子集，這些子集具有較高密度的關(guān)聯(lián)規(guī)則，在各個子集上并行執(zhí)行FP-growth算法就得到了數(shù)據(jù)集中所包含的關(guān)聯(lián)規(guī)則。實驗結(jié)果表明，改進算法降低了內(nèi)存的占用率，縮短了數(shù)據(jù)挖掘時間。

參考文獻:

[1] AGRAWAL R,IMIELINSKI T，SWAMI A.Mining association rules between sets of items in large databases[C]//Proceedings of the 1993 ACM-SIGMOD international conference on management of data.New York,NY,USA:ACM,1993:207-216．

[2] AGRAWAL R,SRIKANT R.Fast algorithms for mining association rules[C]//Proceedings of the 1994 international conference on very large data bases.[s.l.]:[s.n.],1994:487-499.

[3] HAN J,PEI J,YIN Y.Mining frequent patterns without candidate generation[C]//Proceedings of 2000 ACM SIGMOD international conference on management of data.New York,NY,USA:ACM,2000:1-12.

[4] 楊 勇,王 偉.一種基于MapReduce的并行FP-growth算法[J].重慶郵電大學(xué)學(xué)報:自然科學(xué)版,2013,25(5):651-657.

[5] PARK J S,CHEN M,YU P S.Using a hash-based method with transaction trimming and database scan reduction for mining association rules[J].IEEE Transactions on Knowledge and Data Engineering,1997,9(5):813-825.

[6] 吳建章,韓立新,曾曉勤.一種基于多核微機的閉頻繁項集挖掘算法[J].計算機應(yīng)用與軟件,2013,30(3):44-46.

[7] AOUADL M,LE-KHAC N A,KECHADI T M.Distributed

frequent itemsets mining in heterogeneous platforms[J].Journal of Engineering,Computing and Architecture,2007,1(2):1-12.

[8] 鄒 翔,張 巍,劉 洋,等.分布式序列模式發(fā)現(xiàn)算法的研究[J].軟件學(xué)報,2005,16(7):1262-1269.

[9] 李文棟.基于Spark的大數(shù)據(jù)挖掘技術(shù)的研究與實現(xiàn)[D].濟南:山東大學(xué),2015.

[10] 王 樂,馮 林,王 水.不產(chǎn)生候選項集的TOP-K高效用模式挖掘算法[J].計算機研究與發(fā)展,2015,52(2):445-455.

[11] GOETHALS B,MOHAMMED J Z.Advances in frequent itemset mining implementations:report on FIMI'03[J].ACM SIGKDD Explorations Newsletter,2004,6(1):109-117.

[12] 楊中華.平面點列最小覆蓋圓的計算方法[J].北京工業(yè)大學(xué)學(xué)報,2000,26(2):96-97.

[13] 毛宇星,施伯樂.基于擴展自然序樹的概化關(guān)聯(lián)規(guī)則增量挖掘方法[J].計算機研究與發(fā)展,2012,49(3):598-606.

[14] HAN J W，MICHELINE K．?dāng)?shù)據(jù)挖掘:概念與技術(shù)[M].范明，孟小峰，譯.北京:機械工業(yè)出版社，2012.

[15] 易 彤,徐寶文,吳方君.一種基于FP樹的挖掘關(guān)聯(lián)規(guī)則的增量更新算法[J].計算機學(xué)報,2004,27(5):703-710.