郟奎奎，劉海濱

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

0 引 言

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

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

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

聚類分析是目前數(shù)據(jù)挖掘的研究熱點(diǎn)之一，聚類分析能夠?qū)?shù)據(jù)聚類成為多個(gè)類或簇，從而使得在同一個(gè)類中的數(shù)據(jù)具有比較高的相似度，而不同類的數(shù)據(jù)之間有比較大的差別[9]。聚類分析過程是無監(jiān)督的分析過程，在對數(shù)據(jù)進(jìn)行分類之前，對類別數(shù)據(jù)是未知的。經(jīng)典的聚類分析算法有K-means、CURE等，這些算法需要提前設(shè)定聚類的類別數(shù)。這種事前設(shè)定類別數(shù)的做法大多基于程序設(shè)計(jì)經(jīng)驗(yàn)，并且需要經(jīng)過不斷試驗(yàn)才能得到比較正確的分類，這種做法具有一定的不確定性，在一定程度上降低了聚類分析結(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ù)點(diǎn)按照原有的順序拓?fù)潢P(guān)聯(lián)到二維平面網(wǎng)格節(jié)點(diǎn)上，這樣就實(shí)現(xiàn)了高維數(shù)據(jù)的二維結(jié)構(gòu)可視化。此外，由于SOM的高維數(shù)據(jù)的低維表達(dá)能力，SOM在數(shù)據(jù)分類、聚類等應(yīng)用領(lǐng)域有很多成功的應(yīng)用案例。文中利用SOM聚類算法實(shí)現(xiàn)對海量數(shù)據(jù)的聚類分析，進(jìn)而利用聚類模型對數(shù)據(jù)庫進(jìn)行分割，并在各個(gè)子集上進(jìn)行FP-growth數(shù)據(jù)挖掘。

1.1 SOM算法描述

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

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

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

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

(1)

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

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

(2)

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

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

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

1.2 聚簇分布特征圖

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

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

(3)

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

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

(4)

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

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

2 FP-growth算法研究

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

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

定義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ī)則挖掘首先要找出所有滿足最小支持度的項(xiàng)集，再計(jì)算出置信度大于閾值的所有關(guān)聯(lián)規(guī)則。

2.2 FP-growth算法

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

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

(1)Insert模塊。

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

輸出：FP(子)樹Rr

IfLi!=null then

取出Li的第一項(xiàng)i

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

++N.count

Else

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

N.count=l

將N加入項(xiàng)頭表中

Insert(Li-1,N)

(2)Search模塊。

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

輸出：頻繁項(xiàng)集合L_S

IfT中只有一個(gè)分支Pthen

ForP上節(jié)點(diǎn)的每個(gè)組合β

β=α∪β

L_S=L_S∪{β}

Else

ForT中的每個(gè)頻繁項(xiàng)i

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

IfRβ≠? then

Search(Rβ,β)

(3)FP-growth模塊。

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

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

掃描T找出頻繁1-項(xiàng)集L

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

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

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

找出t中的頻繁1-項(xiàng)集合Li

Li中的項(xiàng)按L中的順序排序

Insert(Li,NULL)

L_S=Search(FP,NULL)

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

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

表1 事務(wù)集合T

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

圖1 FP樹與項(xiàng)頭表

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

3.1 算法過程

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

(1)數(shù)據(jù)標(biāo)準(zhǔn)化。

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

圖2 算法流程

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

(2)抽取樣本。

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

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

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

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

(3)聚類分析。

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

C={c1,c2,…,cn}

(7)

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

C中任何一個(gè)元素ck表示如下：

ck={ck1,ck2,…,ckm}

(8)

其中，m為中心坐標(biāo)點(diǎn)的維數(shù)。

(4)FP-growth挖掘。

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

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

(9)

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

圖3 聚類效果

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

4.2 基于SOM劃分的FP-growth算法性能實(shí)驗(yàn)

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

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

將改進(jìn)算法與Apriori算法和FP-growth算法進(jìn)行速度上的比較，在支持度為5%的情況下，各個(gè)算法的運(yùn)算時(shí)間如圖5所示。

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

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

5 結(jié)束語

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

參考文獻(xiàn):

[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é)報(bào):自然科學(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ī)的閉頻繁項(xiàng)集挖掘算法[J].計(jì)算機(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é)報(bào),2005,16(7):1262-1269.

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

[10] 王 樂,馮 林,王 水.不產(chǎn)生候選項(xiàng)集的TOP-K高效用模式挖掘算法[J].計(jì)算機(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] 楊中華.平面點(diǎn)列最小覆蓋圓的計(jì)算方法[J].北京工業(yè)大學(xué)學(xué)報(bào),2000,26(2):96-97.

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

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

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