許普樂，紀(jì)　允，張　勤

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

?

應(yīng)用FP樹快速生成無關(guān)集算法

許普樂1，紀(jì)允2，張勤3

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

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

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

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

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

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

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

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

1相關(guān)概念

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

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

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

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

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

定義6δ無關(guān)集， 設(shè)項(xiàng)集X為δ無關(guān)集，當(dāng)且僅當(dāng)基于項(xiàng)集X沒有δ強(qiáng)規(guī)則，則記為Free(X，δ)。

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

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

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

2無關(guān)集精簡表示模型和FP樹

2.1無關(guān)集精簡表示模型

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

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

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

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)先策略，為了得到每個(gè)候選項(xiàng)集的支持度需要掃描數(shù)據(jù)庫一次，同時(shí)對(duì)于每個(gè)候選項(xiàng)集存在重復(fù)生成的問題。這兩個(gè)缺點(diǎn)導(dǎo)致了該算法的生成效率不高。

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

2.2FP樹

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

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

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

3FMINEX算法

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

3.1理論基礎(chǔ)

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

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

3.2具體算法

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

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

算法FMINEX

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

輸出：頻繁無關(guān)集FreqFree和邊界BD-

1) S是一個(gè)頻繁無關(guān)集

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

3) 掃描數(shù)據(jù)庫Ds，得到所有的頻繁項(xiàng)F，并且將這些頻繁項(xiàng)進(jìn)行降序排序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中的項(xiàng)按照F中的排序進(jìn)行排序

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

4實(shí)驗(yàn)結(jié)果對(duì)比以及分析

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

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

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

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

圖1當(dāng)δ=10時(shí)3種算法在chess數(shù)據(jù)集上運(yùn)行比較結(jié)果

(a) 時(shí)間效率對(duì)比圖；(b) 空間使用對(duì)比圖

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

圖2當(dāng)δ=10時(shí)3種算法在connect數(shù)據(jù)集上運(yùn)行比較結(jié)果

(a) 時(shí)間效率對(duì)比圖；(b) 空間使用對(duì)比圖

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

圖3當(dāng)δ=20時(shí)3種算法在pumsb數(shù)據(jù)集上運(yùn)行比較結(jié)果

(a) 時(shí)間效率對(duì)比圖； (b) 空間使用對(duì)比圖

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

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

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

圖4當(dāng)δ=30時(shí)3種算法在T10I4D100K數(shù)據(jù)集上運(yùn)行比較結(jié)果

(a) 時(shí)間效率對(duì)比圖；(b) 空間使用對(duì)比圖

5結(jié)束語

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

參考文獻(xiàn):

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

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

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

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

[5] 王創(chuàng)新. 關(guān)聯(lián)規(guī)則提取中對(duì)Apriori算法的一種改進(jìn)[J]. 計(jì)算機(jī)工程與應(yīng)用, 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ìn)的頻繁項(xiàng)集挖掘算法研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012, 48(19): 119-121.

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

[11] 王艷, 薛海燕, 李玲玲, 等. 一種改進(jìn)的加權(quán)頻繁項(xiàng)集挖掘算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 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

基金項(xiàng)目：安徽省高等學(xué)校省級(jí)一般教學(xué)研究項(xiàng)目(20101264)。

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

中圖分類號(hào)：TP311

文獻(xiàn)標(biāo)識(shí)碼：A

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

E-mial: jiyun1988@126.com

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