許普樂，紀　允，張　勤

(1.蕪湖職業(yè)技術學院 教務處，安徽 蕪湖 241006；2. 中國移動通信集團安徽有限公司 銅陵分公司，安徽 銅陵 244000；3. 安徽林業(yè)職業(yè)技術學院 信息與藝術系，安徽 合肥 230031)

?

應用FP樹快速生成無關集算法

許普樂1，紀允2，張勤3

(1.蕪湖職業(yè)技術學院 教務處，安徽 蕪湖 241006；2. 中國移動通信集團安徽有限公司 銅陵分公司，安徽 銅陵 244000；3. 安徽林業(yè)職業(yè)技術學院 信息與藝術系，安徽 合肥 230031)

摘要：δ無關集的引入可解決數(shù)據(jù)挖掘領域中挖掘出來的頻繁項集數(shù)量過大以及在實際應用中獲取準確項集支持度代價過大的問題。針對傳統(tǒng)方法生成無關集生成效率過低等問題，本文提出了一種在FP樹上快速生成、結合一定的剪枝策略的快速挖掘算法FMINEX。實驗效果證明，該算法在挖掘過程中，時間和空間性能都比較好。

關鍵詞：數(shù)據(jù)挖掘；頻繁項集；δ無關集；FP樹；剪枝策略

DOI：10.13757/j.cnki.cn34-1150/n.2016.02.015

對一個數(shù)據(jù)庫而言，一個重要的數(shù)據(jù)挖掘目標就是頻繁項集的抽取。而抽取出來的頻繁項集主要用處就是提供一個項集的支持度。這在很多應用領域非常重要，例如在關聯(lián)規(guī)則的使用過程中，必須知道規(guī)則的支持度，才能計算規(guī)則的置信度。然而，在實際使用的過程中，抽取出來的頻繁項集數(shù)量非常龐大，需要耗費大量的存儲空間。同時在使用之前必須進行檢索才能得到一個任意項集的支持度，非常耗時，增加了CPU的代價[1-2]。

在實際使用過程中，很多數(shù)據(jù)挖掘問題，例如關聯(lián)規(guī)則[3-5]，就是查詢一個模式或者項集的出現(xiàn)頻率，這其實是頻繁項集頻繁度查詢問題。一個重要但很困難的問題是，頻繁項集的組合呈爆炸式增長，這樣對于海量的頻繁項集的支持度查詢計算變得很不切實際。在實際過程中，對于一個頻繁項集的支持度查詢，其實只需知道其大致支持度即可，即一個項集的支持度是用其真正的支持度在一定允許范圍內的變動結果代替。文獻[6]提出使用大致近似支持度查詢結果概念，稱之為ε適當表示。適當表示模型[6]是一些數(shù)據(jù)表現(xiàn)模式，可以替代原有精確的查詢模型，但是最終會損失一些精度，損失的精度以ε表示。

將這種ε適當表示引入到頻繁項集領域中，轉化成一種頻繁項集的有損精簡表示模型，稱之為δ無關集[7]，例如在數(shù)據(jù)庫D中，項集ABC的支持度為998，項集AB的支持度為1 000，那么規(guī)則AB?C幾乎在數(shù)據(jù)庫D中是正確的。因為規(guī)則除了兩個例外，AB出現(xiàn)的交易記錄中幾乎都出現(xiàn)了C。那么規(guī)則AB?C的支持度其實近似和項集AB的支持度是相等的，則項集ABC的支持度可以近似地由項集AB代替。項集ABC是冗余的，因為規(guī)則AB?C是成立的，除了很少的部分外。

一個項集X是無關的，X中的項不能構成一個近似精確規(guī)則。文獻[7]挖掘δ無關集使用的是廣度優(yōu)先策略，這樣的策略導致δ無關集的生成效率并不高。因此，本文提出基于FP樹上快速挖掘δ無關集中元素的算法FMINEX，該算法使用FP樹結構代替?zhèn)鹘y(tǒng)的數(shù)據(jù)庫，并且結合一定的剪枝策略，從而實現(xiàn)快速生成。

1相關概念

定義1數(shù)據(jù)庫D，R集合是項的集合，一條記錄r是R的子集，數(shù)據(jù)庫是多條r的組合。

定義2支持度，項集X的支持度是在數(shù)據(jù)庫D中出現(xiàn)X的交易記錄個數(shù)，記為Freq(X)。

定義3頻繁項集，項集X的支持度大于最小支持度σ，則成為頻繁項集，記為Freq(X，σ)。

定義4關聯(lián)規(guī)則，設R是所有項的集合，基于R的關聯(lián)規(guī)則的表現(xiàn)形式是X?Y，其中X，Y屬于R，Y≠?，X∩Y=?。

定義5δ強規(guī)則，一個δ強規(guī)則是在數(shù)據(jù)庫D中，關聯(lián)規(guī)則X?Y，其中Freq(X)-Freq(X∪Y)<=δ。說明X和X∪Y的支持度不相差δ行。

定義6δ無關集， 設項集X為δ無關集，當且僅當基于項集X沒有δ強規(guī)則，則記為Free(X，δ)。

定義7頻繁無關集， 如果δ無關集是頻繁的，大于等于最小支持度σ，則δ無關集是頻繁無關集，記為FreqFree(X，σ，δ)。

定義8頻繁無關集的負邊界， 無關集的負向邊界記為Bd-(r,σ,δ)={X|X?R,X?FreqFree(X，σ，δ)∧

[?Y?X,Y∈FreqFree(r，σ，δ)]}如果項集是頻繁的，則為頻繁無關集的負向邊界，記為FreeBd-(r,σ,δ)。

2無關集精簡表示模型和FP樹

2.1無關集精簡表示模型

無關集精簡表示模型主要有兩部分組成，δ無關集和其對應的支持度FreqFree(r，σ，δ)，以及頻繁無關集負邊界FreeBd-(r,σ,δ)所組成。

設項集X，如果?Y∈FreeBd-(r,σ,δ),Y?X，則Freq(X)=0，否則Freq(X)=min{Y|Y?X,Y∈FreqFree(r，σ，δ)}。

在文獻[7]中，BoulicautJF等人提出算法MINEX挖掘無關集所需要的元素，δ無關集以及頻繁負向邊界，其主要算法如下：

FreqFreei;={X|X∈Ci,andXisaσfrequentδfreesetindatabase}

Ci+1:={X|X?Rand?Y?X,Y∈Yj≤iFreqFreej}Yj≤iCj

i:=i+1

從這里可以看出，算法MINEX的過程主要采用類似于Apriori算法的廣度優(yōu)先策略，為了得到每個候選項集的支持度需要掃描數(shù)據(jù)庫一次，同時對于每個候選項集存在重復生成的問題。這兩個缺點導致了該算法的生成效率不高。

無關集也有類似于Apriori性質[8-11]，即無關集的所有直接子集都是無關的，非無關集的超集都非無關集。但是判斷X是否是無關集，需要遍歷X的直接子集。如果X不是無關集，則存在一個項集A∈X，Y=XA，如果Y不是無關集，或者Y是無關集并且Y?A是一個δ強規(guī)則。簡而言之，就是在第i次迭代過程中，首先計算δ強規(guī)則X?{A}，其中X是無關集，A∈RX，其中R是全部項。這樣就可以利用X∪A刪除i+1次生成的候選項集中不是δ無關集。

2.2FP樹

FP樹[12]主要為了快速生成頻繁項集。在實際數(shù)據(jù)庫中有很多交易記錄是相同的，反復掃描會增加I/O代價。FP樹的主要思想就是將數(shù)據(jù)庫中的交易記錄壓縮成一棵樹，將交易記錄盡可能的壓縮在一起，從而減少搜索時間。同時在生成的過程中使用剪枝策略，進一步加快生成速度。生成的FP樹有足夠的信息生成所有的頻繁項集。

FP樹的生成主要分為兩步：先掃描數(shù)據(jù)庫，得到所有項的出現(xiàn)次數(shù)，并且進行降序排序；然后將數(shù)據(jù)庫中的每條記錄嚴格按照降序的次序進行排序，同時將其插入到FP樹中，最終生成FP樹。在交易記錄排序和插入過程中，如果某一項的支持度小于最小支持度，則將其刪除。

FP樹的主要組成為FP樹上的節(jié)點和頭表節(jié)點。樹上的節(jié)點主要由項和項在該處出現(xiàn)的次數(shù)組成。頭表節(jié)點只要包括項和項在數(shù)據(jù)庫中出現(xiàn)的次數(shù)以及指向樹中第一個項的節(jié)點。

3FMINEX算法

針對無關集需要反復掃描數(shù)據(jù)庫和存儲重復生成的兩個問題，F(xiàn)MINEX算法提出在FP樹上解決。該算法主要在FP樹上反復迭代的過程中得到項集，對于每一個項集進行判斷，同時在生成新的FP樹的時候根據(jù)無關集的反單調性質對FP樹進行剪枝，使得生成的新FP樹更小。

3.1理論基礎

由數(shù)據(jù)庫生成的FP樹，可以有完整的信息生成所有的頻繁項集。因為頻繁項集具有反單調性質，所以如果一個項集不是頻繁的，則其超集必定不是頻繁的。在FP樹中的表現(xiàn)就是如果一個項集不是頻繁的，則不需生成其條件數(shù)據(jù)庫。FP樹是不斷的迭代生成頻繁項集的條件數(shù)據(jù)庫，從而挖掘出所有的頻繁項集。

在FP樹上，也可以使用類似的方法快速生成δ無關集。在本文中，提出基于FP樹快速生成δ無關集頻繁項集精簡表示模型。在文獻[7]中，δ無關集具有反單調性質，如果一個項集不是無關集，則其超集不是無關集。這種性質非常適合使用深度優(yōu)先策略生成。FMINEX算法對于每一個δ無關集都生成一個條件數(shù)據(jù)庫，如果該項集不是無關集，則無需生成其條件數(shù)據(jù)庫。

3.2具體算法

在FP樹上挖掘項集X的時候，可以采用反單調思想。設項集X的條件數(shù)據(jù)庫為Dx，其中Dx是所有頻繁項為F，設a∈F，則a是頻繁項，如果X∪{a}是頻繁無關集，則a保留；否則如果項集X∪{a}不是無關集但是頻繁的，則加入帶頻繁負向邊界中，否則將a從F中除去。如果F中的元素超過1個，則繼續(xù)這個過程，生成新的FP樹。

在挖掘過程中，對于一個候選項集X是否頻繁的判斷是非常迅速的。由于對一個項集的判斷需要使用其子集，所以一個項集生成之前，其子集必須首先生成。

算法FMINEX

輸入：數(shù)據(jù)庫D，最小支持度σ，最大無關值δ。

輸出：頻繁無關集FreqFree和邊界BD-

1) S是一個頻繁無關集

2) Ds是S的條件數(shù)據(jù)庫

3) 掃描數(shù)據(jù)庫Ds，得到所有的頻繁項F，并且將這些頻繁項進行降序排序F={F1，F(xiàn)2，…,Fn}

4)forallitema∈Fdo

5)ifFreq(S∪{a})>= σand?X?S∪{a},X∈FreqFree,Y=RX,Freq(X)-Freq(X∪Y)<=δand?X?S∪{a},X∈FreqFree

6)FreqFree=FreqFree∪(S∪{a})

7)elseifFreq(S∪{a}) >= σand

?X?S∪{a},X∈FreqFree,Y=RX,

Freq(X)-Freq(X∪Y)>δand?X?S∪{a},X∈FreqFree

8)BD-=BD-∪(S∪{a})

9)F=F-a

10)else

11)F=F-a

12)endfor

13)if|F| <=1

14)return

15)foralltransactiont ∈Ds

16)t=t∩F

17)將t中的項按照F中的排序進行排序

18)將所有的t重新生成一顆FP樹

19)Endfor

20)forallitema∈Fdo

21)FMINEX(S∪{a},Ds∪{a},σ,δ)

22)Endfor

23)returnFreqFree∪BD-

FMINEX主要的輸入?yún)?shù)是數(shù)據(jù)庫D、最小支持度σ以及最大無關值δ，輸出是頻繁無關集和其對應的支持度，以及負向邊界。由于FP樹的生成是反復迭代的過程，在第1到第3步，是針對一個項集S，和其對應的條件數(shù)據(jù)庫Ds。首先掃描數(shù)據(jù)庫得到所有項的支持度集合F，并且按照降序進行排序。在第4步到第12步都是對S和F中的每一個項a組合而生成的項集(S∪{a})進行判斷，在第5和第6步中，判斷項集(S∪{a})是否是無關集，如果是，則加入到無關集中。在第7步到第9步，如果項集(S∪{a})是頻繁的，并且所有的直接子集是無關集，而本身不是無關集，則將其加入到負向邊界中，同時將a從F中刪除。這就使用到了剪枝策略，因為不是無關集的超集肯定不是無關集。對于不滿足第5步要求的項a都從F中刪除，也使用到了剪枝策略。第13步和第14步判斷集合F中的元素，如果個數(shù)小于等于1，則停止建立新的FP樹。在第15到第19步是根據(jù)集合F中的結果建立新的FP樹，第20步到22步，是對新建立起來的FP樹遞歸調用本算法。最終返回無關集所有元素。

4實驗結果對比以及分析

為了研究FMINEX算法的性能，實驗對比了原算法MINEX和最新利用FP樹結構的算法FPASCAL[1]。這3種算法都使用C++分別進行實現(xiàn)，運行的平臺是WIN7，I5處理器，4G內存。實驗對比內容包括時間、空間消耗情況。由于FMINEX算法和FPASCAL算法使用的是FP樹，因此其占用的內存大小存在變化，而MINEX算法使用的是數(shù)據(jù)庫，占用的內存一直不變。在對比實驗中，所使用的數(shù)據(jù)集分別為chess、connect、pumsb、pumbs_star、T10I4D100K、T40I10D100K，這些數(shù)據(jù)集都可以從http://fimi.cs.helsinki.fi/data/中下載。

在實驗中，代表精度誤差的δ是一個很重要的參數(shù)，它代表了在實際使用過程中可以最大容忍的項集和其超集支持度誤差的值。本文考察了當δ分別等于10、20、30的情況下，F(xiàn)MINEX和MINEX的運行效果。挖掘出來的δ無關集和文獻[7]中一樣，具體結果可參看文獻[7]實驗部分，而算法效率結果如下所示。而需要注意的是FPASCAL算法是無損壓縮，δ對其生成的結果沒有任何影響。MINEX算法在運行過程中將數(shù)據(jù)集全部存儲在內存中，因此占用的空間不會隨著支持度或δ的變化而改變, 一直保持不變。

當δ=10時，算法FMINEX和MINEX以及FPASCAL在chess數(shù)據(jù)集上運行的結果如圖1所示。在圖1(a)中可以很明顯地發(fā)現(xiàn)FMINEX比MINEX至少快3倍，并且隨著支持度的降低，性能優(yōu)勢更加明顯。這是因為隨著支持度降低，MINEX需要掃描數(shù)據(jù)庫的次數(shù)加多，而FMINEX生成的FP樹規(guī)模雖有變大，但是壓縮效果明顯，所以算法整體效率很高。而FPASCAL算法雖然是無損壓縮，由于使用FP樹結構，所以算法整體效率依然高于MINEX算法。

在圖1(b)中，在剛開始的時候，F(xiàn)MINEX所占的空間比MINEX要大，這是因為當支持度較低的情況下，F(xiàn)P樹需要存儲的頭表節(jié)點和樹中的節(jié)點的數(shù)量較多，因此占用了很多的空間，但是隨著支持度的增加，F(xiàn)P樹的規(guī)模逐漸減少，比MINEX占用的空間少。而FPASCAL是無損壓縮，需要占用的存儲空間比FMINEX要大。

圖1當δ=10時3種算法在chess數(shù)據(jù)集上運行比較結果

(a) 時間效率對比圖；(b) 空間使用對比圖

當δ=10的時候，算法FMINEX和MINEX以及FPASCAL在connect數(shù)據(jù)集上運行的結果如圖2所示。在圖2中可以很清晰地看出，無論是時間效率還是空間效率，F(xiàn)MINEX算法的性能均比MINEX算法要好。在圖2(a) 中FMINEX比MINEX快至少30倍，并且隨著支持度的降低，性能優(yōu)勢進一步明顯。原因和在chess數(shù)據(jù)集上運行結果是一樣的。在圖2(b)中FMINEX比MINEX的空間使用量少5倍以上，并且隨著支持度的增加，占用的空間進一步減少。這是因為connect數(shù)據(jù)集中的數(shù)據(jù)比較密集，壓縮效果比較明顯。FPASCAL算法是無損壓縮，挖掘出的項集數(shù)量比無關集多，但是由于使用FP樹結構，所以FPASCAL的時間和空間效率在這兩種算法之間。

圖2當δ=10時3種算法在connect數(shù)據(jù)集上運行比較結果

(a) 時間效率對比圖；(b) 空間使用對比圖

當δ=20時候，算法FMINEX和MINEX以及FPASCAL在pumsb數(shù)據(jù)集上運行結果如圖3所示。在圖3中可以很清晰地看出，F(xiàn)MINEX算法的時間和空間性能均比MINEX算法要好。在圖3(a)中可以發(fā)現(xiàn)，算法FMINEX比算法MINEX的運行速度快3-6倍。在圖3(b)中，可以看出FMINEX所占的空間比MINEX要少2-20倍。算法時間和空間效率優(yōu)勢的原因是pumsb是數(shù)據(jù)密集型數(shù)據(jù)集，F(xiàn)P樹的壓縮效果比較好。FPASCAL算法的性能表現(xiàn)在兩種算法之間。

圖3當δ=20時3種算法在pumsb數(shù)據(jù)集上運行比較結果

(a) 時間效率對比圖； (b) 空間使用對比圖

當δ=30的時候，算法FMINEX和MINEX以及FPASCAL在T10I4D100K和T40I10D100K數(shù)據(jù)集上運行結果如圖4和圖5所示。

在圖4(a)和圖5(a)中，算法FMINEX的運行速度比MINEX快2-3倍，PASCAL算法的速度介于兩者之間。由于T10I4D100K和T40I10D100K是典型的數(shù)據(jù)稀疏型數(shù)據(jù)集，生成的FP樹壓縮效果不夠好，和掃描數(shù)據(jù)庫而得到支持度相比，F(xiàn)MINEX在FP樹上優(yōu)勢并不明顯。

在圖4(b)和圖5(b)中，算法FMINEX和FPASCAL在支持度比較低的時候，占用的空間均比MINEX大。這是因為T10I4D100K和T40I10D100K是典型的稀疏型數(shù)據(jù)集，在支持度比較低的情況下，壓縮效果并不好。然而隨著支持度的增加，在FP樹中需要存儲的頭表節(jié)點和樹中的節(jié)點的數(shù)量會減少，所以FMINEX和PASCAL所占的空間會小于MINEX。由于FPASCAL是無損壓縮，因此所需要的存儲空間比FMINEX多。

圖4當δ=30時3種算法在T10I4D100K數(shù)據(jù)集上運行比較結果

(a) 時間效率對比圖；(b) 空間使用對比圖

5結束語

頻繁項集數(shù)量過于龐大而導致的查詢項集支持度的代價大的問題是頻繁項集研究領域中的一個重要研究課題，無關集實現(xiàn)了在查詢結果準確率和查詢效率之間的折中，達到了以較小的支持度誤差實現(xiàn)查詢效率大幅提高的效果。針對無關集生成的效率不高的問題，本文提出在FP樹快速挖掘無關集精簡表示中所需要元素的算法FMINEX，實驗結果證明，算法FMINEX的性能不僅比原有算法MINEX要好，而且比最新利用FP樹結構的算法FPASCAL還要好。探討如何在分布式環(huán)境下快速生成無關集精簡表示成為以后研究的重點和方向。

參考文獻:

[1] 許普樂, 張勤, 紀允. 基于FP樹的一種快速挖掘生成器算法[J]. 安慶師范學院學報 (自然科學版), 2013，19 (1):48-53.

[2]HanJiawei，MichelineKamber．數(shù)據(jù)挖掘概念與技術[M]．范明，孟小峰，譯．北京：機械工業(yè)出版社，2004：1-261.

[3] 田衛(wèi)東，紀允. 一種頻繁核心項集的快速挖掘算法[J]. 計算機工程, 2014, 40(6): 120-124.

[4] 紀允. 析取閉合項集的快速生成和恢復算法研究[D]. 合肥：合肥工業(yè)大學, 2013.

[5] 王創(chuàng)新. 關聯(lián)規(guī)則提取中對Apriori算法的一種改進[J]. 計算機工程與應用, 2004, 40(34): 183-185.

[6]MannilaH,ToivonenH.Multipleusesoffrequentsetsandcondensedrepresentations:extendedabstract[C].Procofthe2ndInternationalConferenceonKnowledgeDiscoveryandDataMining(KDD’96), 1996: 189-194.

[7]BoulicautJF,BykowskiA,RigottiC.Free-sets:Acondensedrepresentationofbooleandatafortheapproximationoffrequencyqueries[J].DataMiningandKnowledgeDiscovery, 2003, 7(1): 5-22.

[8]AgrawalR,ImielińskiT,SwamiA.Miningassociationrulesbetweensetsofitemsinlargedatabases[C].ACMSIGMODRecord, 1993, 22(2): 207-216.

[9] 王艷, 李玲玲, 邵曉艷. 改進的頻繁項集挖掘算法研究[J]. 計算機工程與應用, 2012, 48(19): 119-121.

[10] 張云濤, 于治樓, 張化祥. 關聯(lián)規(guī)則中頻繁項集高效挖掘的研究[J]. 計算機工程與應用, 2011, 47(3): 139-141.

[11] 王艷, 薛海燕, 李玲玲, 等. 一種改進的加權頻繁項集挖掘算法[J]. 計算機工程與應用, 2010, 46(23): 135-137.

[12]HanJiawei,PeiJian,YinYiwen.Miningfrequentpatternswithoutcandidategeneration[C].ProcofACM-SIGMODInternationalConferenceonManagementofData,Dallas,USA:ACMPress, 2000:1-12.

AFastAlgorithmforMiningFreeSetsBasedonFPTree

XUPu-le1,JIYun2,ZHANGqin3

(1.Dean'sOffice,WuhuInstituteofTechnology,Wuhu,Anhui241006,China;2.TonglingBranch,ChinaMobileGroupAnhuiCompanyLimited，Tongling,Anhui244000,China;3SchoolofInformationandArt,AnhuiVocationalandTechnicalCollegeofForestry,Hefei,Anhui230031,China)

Abstract:Byintroducingfreesets,wesolvetheoverlargenumberofminedfrequentitemsetsindataminingandhighcostofgetexactlysupportofitemsetinspecificusingareaproblems.AnewalgorithmFMINEXisproposed,miningfreesetsfromFPtreewithapruningstrategywhichaimstosolvetheinefficientoftraditionalminingfreesetsmethod.ExperimentalresultstestifyFMINEXandshowabetterperformancebothintimeandspaceconsuminginminingprocess.

Keywords:datamining;frequentitemsets;freesets;FPtree;pruningstrategy

* 收稿日期：2014-07-09

基金項目：安徽省高等學校省級一般教學研究項目(20101264)。

作者簡介：許普樂，男，安徽蕪湖人，碩士，蕪湖職業(yè)技術學院副教授，研究方向為數(shù)據(jù)挖掘、智能計算等。

中圖分類號：TP311

文獻標識碼：A

文章編號：1007-4260(2016)02-0060-06

E-mial: jiyun1988@126.com

網(wǎng)絡出版時間：2016-06-08 12:57網(wǎng)絡出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160608.1257.015.html