肖 文,胡 娟

0 引言

頻繁項集挖掘(Frequent Itemset Mining, FIM)是最基礎(chǔ)的數(shù)據(jù)挖掘任務(wù)之一,是關(guān)聯(lián)規(guī)則、分類、聚集、離群點分析等眾多數(shù)據(jù)挖掘任務(wù)的重要組成部分,自它被提出以來[1],受到了越來越多的關(guān)注。經(jīng)典的FIM算法可以分為三類:“產(chǎn)生-計數(shù)”類方法如Apriori[2]、DHP(Direct Hashing and Pruning)[3-4]、DIC(Dynamic Itemset Counting)[5]等;“模式增長”類方法如FP-Growth(Frequent Pattern Growth)[6]、LPTree(Linear Prefix Tree)[7]、FIUT(Frequent Items Ultrametric Trees)[8]、IFP(Improved FP-Growth)[9]、FPL/TPL(Frequent Pattern List/Transcation Pattern List)[10]等，上述兩類算法都是基于水平數(shù)據(jù)格式的。第三類算法是基于垂直數(shù)據(jù)格式的,如Eclat(Equivalence Class Transformation)以及使用位向量優(yōu)化的類Eclat算法等。

所有的FIM算法都包含兩個基本計算步驟:產(chǎn)生(候選)項集及對項集進(jìn)行計數(shù)?！爱a(chǎn)生-計數(shù)”類的方法在項枚舉樹上通過廣度優(yōu)先搜索(Breadth First Search, BFS)產(chǎn)生候選項集,并通過掃描整個數(shù)據(jù)集對每一個候選項集進(jìn)行計數(shù),從而得到頻繁項集?！澳Ｊ皆鲩L”及基于垂直數(shù)據(jù)格式的算法均通過深度優(yōu)先搜索(Depth First Search, DFS)產(chǎn)生候選項集,可以盡可能早地將非頻繁的項集進(jìn)行剪枝,效率比BFS方法更高。“模式增長”方法中項集的計數(shù)通過構(gòu)造條件數(shù)據(jù)庫來實現(xiàn),設(shè)有前綴項集p,其條件數(shù)據(jù)庫為Dp(由數(shù)據(jù)集中所有包含項集p的事務(wù)組成),找到Dp中i個頻繁項{x1,x2,…,xi},可以直接得到i個頻繁項集{p∪x1,p∪x2,…,p∪xi}?；诖怪睌?shù)據(jù)格式的FIM算法通過計算兩個項集tidset的交集來確定生成項集的支持度,設(shè)有兩個tidset:ta={1,2,3,4},tb={2,3}分別表示項a在事務(wù)號為{1,2,3,4}的事務(wù)中出現(xiàn),項b在事務(wù)號為{2,3}的事務(wù)中出現(xiàn),則tab=ta∩tb={2,3},項集{a,b}的支持度即為tab的長度?？梢詫㈨椉膖idset轉(zhuǎn)換為bitmap來進(jìn)一步提高計算交集的速度[11]。

被挖掘數(shù)據(jù)集的特征對FIM算法的效率有著顯著影響。數(shù)據(jù)集的特征主要包括事務(wù)數(shù)、項數(shù)、平均事務(wù)長度、數(shù)據(jù)尺寸等,有不少研究都關(guān)注了不同F(xiàn)IM算法針對上述特征的擴展性[12]。但上述屬性只能反映了數(shù)據(jù)集的一般特征,沒有從根本上描述數(shù)據(jù)集的本質(zhì)特征。數(shù)據(jù)集的稀疏度描述的是數(shù)據(jù)集中事務(wù)之間的差異度及信息的冗余量,是數(shù)據(jù)集的本質(zhì)特征之一,對FIM算法的效率有著顯著的影響,很少研究關(guān)注了FIM算法對于稀疏度的可擴展性問題。

為了了解不同F(xiàn)IM算法對于稀疏度的可擴展性,首先要對數(shù)據(jù)集稀疏度進(jìn)行定量的分析。不少研究以數(shù)據(jù)集的一般特征為基礎(chǔ),文獻(xiàn)[13-17]中提出了一些數(shù)據(jù)集稀疏度的度量方法;閆珍等[18]提出一種將事務(wù)數(shù)據(jù)庫轉(zhuǎn)換為二進(jìn)制矩陣,借用工程數(shù)學(xué)中”稀疏矩陣”的概念來描述數(shù)據(jù)集的稀疏度;還有一些方法首先將數(shù)據(jù)集轉(zhuǎn)換為特殊的數(shù)據(jù)格式(一般為類似FP-Tree的樹結(jié)構(gòu)),通過對特定數(shù)據(jù)結(jié)構(gòu)的分析來得出數(shù)據(jù)集的稀疏度[19-20];Shepard[21]在2013年給出了一種基于等價類及等價類內(nèi)部冗余度的數(shù)據(jù)稀疏度度量方法。雖然上述稀疏度度量方法一定程度上解決了數(shù)據(jù)集稀疏度度量問題,但沒有兼顧到FIM任務(wù)背景下決定稀疏度的所有要素,且沒有研究關(guān)注數(shù)據(jù)稀疏度對不同類型FIM算法的效率影響。

本文主要工作為:

1)對已有的數(shù)據(jù)集稀疏度量化度量方法進(jìn)行了綜述,討論了每種類型方法的優(yōu)缺點并進(jìn)行了比較。

2)提出了一種基于事務(wù)頻繁項集之間差異度的數(shù)據(jù)集稀疏度度量方法,這種度量方法有如下三個特點:考慮了最小支持度對數(shù)據(jù)稀疏度的影響(不同的支持度會導(dǎo)致頻繁項在數(shù)據(jù)集中的不同分布),考慮了事務(wù)之間的差異(關(guān)聯(lián))度,數(shù)據(jù)集的整體稀疏度由各個局部稀疏度組成。

3)提出了一種基于FP-Tree(Frequent Pattern Tree)的稀疏度的近似度量方法,這種方法同樣考慮了最小支持度以及事務(wù)之間部分的差異(關(guān)聯(lián))度,雖然是一種近似的稀疏度度量方法,但計算效率比第一種方法更高。

4)通過實驗研究了數(shù)據(jù)稀疏度對于不同類型FIM算法的性能影響,比較了不同類型FIM算法對數(shù)據(jù)稀疏度的可擴展性。

1 符號及相關(guān)定義

設(shè)I={i1,i2,…,in}是項的集合,X是一個項集,X?I,包含k個項的項集稱為k-項集;一個事務(wù)T=(tid,X),其中tid為事務(wù)標(biāo)識,X為一個項集;事務(wù)數(shù)據(jù)庫D={t1,t2,…,tn}是T的集合。項集X在事務(wù)數(shù)據(jù)庫D中的支持度Sup(X)為D中包含X事務(wù)的數(shù)量。最小支持度minsup是用戶給定的一個閾值,如果Sup(x)≥minsup,則稱項集x是頻繁的。

定義1 頻繁項的集合I′。一個事務(wù)數(shù)據(jù)庫D頻繁項的集合由所有頻繁的項組成。

I′={i|i∈I&&Sup(i)≥minsup}

定義2 事務(wù)的頻繁項集T′。一個事務(wù)T=(tid,X)的頻繁項集T′由事務(wù)中所有頻繁的項組成。

T′={i|i∈X&&i∈I′}

定義3 項集的長度|X|。一個項集的長度定義為項集中包含的項的個數(shù)。

定義4 設(shè)有兩個項集X、Y,其中長度較大的一個項集表示為max(X,Y)。

2 已有度量方法

為了量化度量數(shù)據(jù)集的稀疏度,已提出的方法可以大致分為三類:第一類是使用數(shù)據(jù)集的基本特征作為參數(shù)來計算數(shù)據(jù)集的稀疏度;第二類是將數(shù)據(jù)集轉(zhuǎn)換為特定的數(shù)據(jù)結(jié)構(gòu)(大多是類似于FP-Tree的樹結(jié)構(gòu)),通過對特定數(shù)據(jù)結(jié)構(gòu)特征的分析來體現(xiàn)數(shù)據(jù)集的稀疏度;第三類是利用等價類(閉項集)的概念,將事務(wù)的頻繁項集劃分為若干個等價類,通過計算每一個等價類的稀疏度來得到整個數(shù)據(jù)集的稀疏度度量。

從FIM挖掘的背景來看,數(shù)據(jù)集的稀疏度度量方法應(yīng)考慮三個方面的要素:一是要考慮最小支持度的影響，根據(jù)先驗性質(zhì)[1],FIM挖掘只關(guān)注數(shù)據(jù)集中所有頻繁的項,不同的支持度會導(dǎo)致事務(wù)中包含不同的頻繁項;二是要考慮事務(wù)頻繁項集之間的差異度,全面地反映一個數(shù)據(jù)集內(nèi)事務(wù)之間的關(guān)聯(lián)程度;三是可以將整個數(shù)據(jù)集劃分為若干部分,整個數(shù)據(jù)集的稀疏度由所有局部稀疏度構(gòu)成。

2.1 數(shù)據(jù)集基本特征的度量方法

Bayardo等[13]提出了一種數(shù)據(jù)集稀疏度度量的粗略描述,將稀疏數(shù)據(jù)集描述為“數(shù)據(jù)集中有大量的項,但每條事務(wù)中項的數(shù)量(平均事務(wù)長度)是很小的。”稀疏度的計算方法如下所示:

數(shù)據(jù)稀疏度使用事務(wù)平均長度和數(shù)據(jù)集中項總數(shù)的比值體現(xiàn),這種計算方法沒有涵蓋上述三個要素的任何一個,只能說是一種十分粗略的稀疏度定量描述,其優(yōu)點是計算十分方便。

Gouda等[14]中提出一種利用頻繁項集長度大致估計數(shù)據(jù)集稀疏度的方法。如果頻繁項集的平均長度很長,則數(shù)據(jù)是密集的;反之是稀疏的。這種方法只能給出一個粗略的定性描述,且沒有明確頻繁項集的平均長度的閾值是多少。

有不少研究利用頻繁項的平均支持度與最小支持度的比值作為量化估計數(shù)據(jù)集的方法,其計算公式為:

數(shù)據(jù)越密集,則密集度越大;數(shù)據(jù)越稀疏,則密集度越小,稀疏度越大。這種方法雖然考慮了最小支持度對數(shù)據(jù)稀疏度的影響,計算也十分簡便,但只考慮了數(shù)據(jù)集中頻繁的項,而沒有考慮事務(wù)頻繁項集之間的關(guān)聯(lián)關(guān)系,不能全面反映一個數(shù)據(jù)集的特征。

文獻(xiàn)[15-17]中提出的度量方法考慮了項在整個數(shù)據(jù)集中的分布情況,使用分布比例來衡量數(shù)據(jù)集的稀疏度。設(shè)數(shù)據(jù)集中所有項的集合I={i1,i2,…,in},數(shù)據(jù)集稀疏度計算方法如下所示:

分布比例越高,則數(shù)據(jù)集越密集;分布比例越低,則數(shù)據(jù)集越稀疏。這種方法計算也十分簡單,但存在著明顯的缺點:沒有體現(xiàn)最小支持度對數(shù)據(jù)集稀疏度的影響;沒有反映事務(wù)頻繁項集之間的關(guān)聯(lián)程度;在某些情況下,兩個數(shù)據(jù)集可能擁有相同的項分布比例,但兩個數(shù)據(jù)集實際上存在著重大的差異。

閆珍等[18]提出的方法與分布比例的思想類似,首先將事務(wù)數(shù)據(jù)庫轉(zhuǎn)換為二進(jìn)制矩陣,通過矩陣中非零元素的占比來得到數(shù)據(jù)集的稀疏度,其計算公式如下:

稀疏度=t/(m×n)

其中:t為矩陣中非零元素的個數(shù);m×n為矩陣的尺寸。一般而言,稀疏度小于等于0.05為稀疏數(shù)據(jù)集[22]。

2.2 基于特殊數(shù)據(jù)結(jié)構(gòu)的度量方法

Grahne等[19]中提出一種基于FP-Tree的稀疏度粗略的估計方法,首先將數(shù)據(jù)集構(gòu)造成一棵FP-Tree,然后以樹層次的方法對該FP-Tree進(jìn)行檢查:若FP-Tree上1/4部分包含的節(jié)點少于15%的總結(jié)點,則數(shù)據(jù)集是密集的；否則數(shù)據(jù)集是稀疏的。這種方法考慮了最小支持度的影響,也考慮了事務(wù)頻繁項集之間的關(guān)聯(lián)程度,但只能得出定性的稀疏度度量結(jié)論(密集或稀疏),無法量化一個數(shù)據(jù)集的稀疏程度。在文獻(xiàn)[23]中說明,這種度量方法有時會產(chǎn)生錯誤的結(jié)論。

為了克服稀疏度不能準(zhǔn)確量化度量的缺點,Salleb-Aouissi等[20]提出一種精確的度量方法,首先將數(shù)據(jù)集構(gòu)成一個類似FP-Tree的數(shù)據(jù)結(jié)構(gòu)二元決策圖(Binary Decision Diagram, BDD),通過檢查BDD的特征來得出數(shù)據(jù)集量化的稀疏度,具體計算公式如下:

若SPBDD的比值很小,說明BDD中的節(jié)點很少,數(shù)據(jù)集是密集的;反之?dāng)?shù)據(jù)集為稀疏的。這種方法可以得到一個精確量化的稀疏度度量,但沒有考慮最小支持度的因素。

上述兩種基于樹的度量方法實際上主要關(guān)注點是事務(wù)之間的差異(關(guān)聯(lián))程度。如果事務(wù)之間的差異度低,則在FP-Tree或BDD中一個節(jié)點可以代表多個事務(wù)共同項,整個數(shù)據(jù)結(jié)構(gòu)中的節(jié)點就相應(yīng)減少;反之則BDD中的節(jié)點數(shù)量更多。

2.3 基于等價類劃分的度量方法

Shepard[21]中提出一種基于等價類的數(shù)據(jù)集稀疏度度量方法,主要借助了閉項集及等價類中的最小項集(Mininal Generators, MG)的概念[24]。其計算方法主要描述為:首先將數(shù)據(jù)集的所有事務(wù)劃分為n個等價類{Y1,Y2,…,Yn},同一等價類中的事務(wù)具有相同的閉項集,整個數(shù)據(jù)集的稀疏度是所有等價類稀疏度的平均數(shù):

每一個等價類稀疏度的計算方法為:

Sp(Yi)=y/x2

其中:y為等價類中無冗余的mg的個數(shù);x為等價類中所有的項集數(shù)。

這種度量方法雖然可以給出一個量化精確的稀疏度度量,也考慮了部分事務(wù)之間的關(guān)聯(lián)(同一個等價類內(nèi)部的事務(wù)),但很明顯,它沒有考慮最小支持度對數(shù)據(jù)集稀疏度的影響,且沒有考慮不同等價類之間的關(guān)聯(lián)關(guān)系。

可以將上述度量方法從三個維度對比如表1所示。

表1 六類稀疏度度量方法的比較

3 稀疏度度量方法

本文首先提出一種定量的稀疏度度量方法,考慮最小支持度對數(shù)據(jù)集稀疏度的影響,全面關(guān)注事務(wù)之間的差異度(關(guān)聯(lián)程度),整個數(shù)據(jù)集的稀疏度由局部稀疏度組成。

3.1 基于事務(wù)差異度的稀疏度度量方法

由于不同最小支持度下事務(wù)的頻繁項集是完全不同的,因此在FIM任務(wù)背景下,數(shù)據(jù)集的稀疏度是一個與最小支持度緊密關(guān)聯(lián)的指標(biāo)。設(shè)數(shù)據(jù)集D={T1,T2,…,Tn},則所有事務(wù)之間的關(guān)系可用R來表示:

R={r|r=(Ti,Tj)}; 1≤i≤n, 1≤j≤n,i≠j

在FIM任務(wù)背景下,只需要考慮事務(wù)頻繁項集之間的關(guān)系,可以得到R′:

R′={r′|r′= (Ti′,Tj′)}; 1≤i≤n, 1≤j≤n,i≠j

其中：Ti′為Ti的頻繁項集。

整個數(shù)據(jù)集的稀疏度可由任意兩個事務(wù)之間的差異度定義而來。可以對任意事務(wù)之間的差異度求平均數(shù)得到數(shù)據(jù)集的稀疏度,即如下定義:

定義5 設(shè)數(shù)據(jù)集D中共有n條事務(wù),其關(guān)系集合R′={r1,r2,…,rn},數(shù)據(jù)集D的稀疏度定義為SP(D),計算公式為:

下面討論任意兩個事務(wù)頻繁項集之間差異度的計算問題。本文引入數(shù)據(jù)挖掘領(lǐng)域中“標(biāo)稱屬性”的概念[25],將一個事務(wù)看成是由若干個標(biāo)稱屬性刻畫的對象,其頻繁項集中的每一個項可以看成是一個標(biāo)稱屬性。如有兩個事務(wù)的頻繁項集X′={a,b,c}和Y′={b,c,d,e},則事務(wù)X′有3個標(biāo)稱屬性,Y′有4個標(biāo)稱屬性。計算兩個使用標(biāo)稱屬性刻畫的實體i、j之間差異度dif(i,j)可使用如下計算公式[25]:

dif(i,j)= (p-m)/p

其中:m為i、j中相同的屬性數(shù);p為刻畫實體屬性的總數(shù)。如將X′和Y′均看成使用標(biāo)稱屬性刻畫的實體,它們具有共同的標(biāo)稱屬性{b,c},刻畫實體所有的屬性數(shù)為4,則兩者的差異度為(4-2)/4=0.5。

因此,可以正式將兩個事務(wù)的頻繁項集之間的差異度定義如下:

定義6 兩個事務(wù)的頻繁項集Ti′和Tj′之間的差異度定義為dif(Ti′,Tj′),其計算方法為:

dif(Ti′,Tj′)=

下面討論數(shù)據(jù)集稀疏度的最大值和最小值。根據(jù)定義5,Sp(D)由任意兩條事務(wù)的頻繁項集之間的差異度求平均值所得。對于dif(Ti′,Tj′),若Ti′和Tj′的長度相等且每一個項均相等,則dif(Ti′,Tj′)=0;若Ti′和Tj′的長度相等且每一個項均不相等,則dif(Ti′,Tj′)=1;除了上述兩種極端情況之外,dif(Ti′,Tj′)是一個在范圍(0,1)內(nèi)的小數(shù)。因此對于SP(D)而言,其取值必然在區(qū)間[0,1]內(nèi)。為了便于查看和書寫,可以將SP(D)×100%得到的一個百分比作為數(shù)據(jù)集稀疏度的表現(xiàn)方式。

3.2 基于FP-Tree的稀疏度度量方法

3.1節(jié)提出的稀疏度度量方法支持最小支持度考慮了所有事務(wù)之間的差異度,具有較好的代表性;但有一個明顯的缺陷,即計算成本很高。設(shè)數(shù)據(jù)集D中有n個事務(wù),則R′中有[n(n-1)]/2個元素,計算一個關(guān)系差異度的時間復(fù)雜度為O(1),則計算SP(D)的時間復(fù)雜度為O(n2),當(dāng)數(shù)據(jù)集中包含海量事務(wù)時,計算成本很高。為了降低計算成本,可以將基于FP-Tree的方法和計算SPBDD的方法進(jìn)行結(jié)合,提出一種新的基于FP-Tree的稀疏度計算方法。其主要思想是將數(shù)據(jù)集轉(zhuǎn)換為對應(yīng)的FP-Tree后,對FP-Tree中的節(jié)點進(jìn)行檢查來代表數(shù)據(jù)集的稀疏度。設(shè)數(shù)據(jù)集D的I′={i1,i2,…,in},基于FP-Tree的稀疏度計算方式如下:

這種計算方法在構(gòu)造FP-Tree時支持最小支持度,通過FP-Tree的節(jié)點共享體現(xiàn)事務(wù)之間的差異度。設(shè)數(shù)據(jù)集中有n個事務(wù),若任意兩個事務(wù)的頻繁項集Ti′和Tj′的長度相等且每一個項均相等,則數(shù)據(jù)集最密集,FPSP(D)=1/n;若任意兩個事務(wù)的頻繁項集Ti′和Tj′的長度相等且每一個項均不相等,則數(shù)據(jù)集最稀疏,FPSP(D)=1;因此對于任何數(shù)據(jù)集D,FPSP(D)的取值范圍為[1/n, 1]。

4 實驗結(jié)果分析

實驗選取FIM挖掘標(biāo)準(zhǔn)數(shù)據(jù)集[26]中的四個數(shù)據(jù)集用于測試本文提出的兩種稀疏度計算方法及三種典型FIM算法對于稀疏度的可擴展性。其中：mushroom和chess為兩個傳統(tǒng)的密集數(shù)據(jù)集,retail和T10I4D100K為兩個傳統(tǒng)的稀疏數(shù)據(jù)集。數(shù)據(jù)集的基本屬性如表2所示。

表2 四個測試數(shù)據(jù)集的基本屬性

4.1 稀疏度度量結(jié)果對比

使用本文第3章中提出的兩種稀疏度量化度量方法,對四個標(biāo)準(zhǔn)數(shù)據(jù)集分別計算其量化稀疏度,第一種方法度量值記為SP,第二種方法度量值記為FPSP。具體結(jié)果見圖1。

圖1 本文提出的兩種方法對四個標(biāo)準(zhǔn)數(shù)據(jù)集的度量結(jié)果

從圖1可以看出:

1)在FIM任務(wù)背景下,數(shù)據(jù)集稀疏度(SP)是一個與最小支持度(minsup)相關(guān)聯(lián)的一個數(shù)值,且與最小支持度成反比。

2)本文提出的兩種稀疏度度量方法都具有良好的區(qū)分度,即對于一個數(shù)據(jù)集而言,不存在支持度不同而稀疏度相同的情況。從文獻(xiàn)[21]中可以看出,基于等價類的稀疏度度量方法在T40I0D100K數(shù)據(jù)集上,當(dāng)最小支持度分別為1%、1.5%、2%、2.5%、5%、10%時,其稀疏度值均為100%,基于等價類的稀疏度度量方法在某些數(shù)據(jù)集上區(qū)分度較差。

3)對于相對密集的數(shù)據(jù)集來說,如mushroom和chess,SP的數(shù)值與minsup成近似線性關(guān)系,而FPSP增長得比較慢(主要原因是事務(wù)的頻繁項集之間差別較小,可以共享很多前綴);而對于較為稀疏的數(shù)據(jù)集來說,如retail和T10I4D100K,SP的增長率較小,而FPSP的增長率較大,這也說明對于稀疏度很高的數(shù)據(jù)集,不適合使用基于FP-Tree的FIM算法(如FP-Growth),會構(gòu)造大量的條件數(shù)據(jù)庫，影響算法效率。

將文獻(xiàn)[17,21]中提出的稀疏度計算方法分別記為SPmg和CD,選擇標(biāo)準(zhǔn)數(shù)據(jù)集中較為密集的數(shù)據(jù)集mushroom和稀疏數(shù)據(jù)集T10I4D100K,分別計算四種稀疏度如表3所示。

表3 不同度量方法在兩個數(shù)據(jù)集上的比較 %

從表3可以看到,本文提出的度量方法與已有方法在度量值上具有一定的一致性。但本文提出的兩種度量方法均以事務(wù)之間的差異性為基礎(chǔ),度量值與最小支持度之間成明顯的反比關(guān)系,而SPmg以等價類中的冗余度為基礎(chǔ),CD主要考慮的是項在數(shù)據(jù)集中的分布情況,相對來說其度量值和最小支持度之間的關(guān)聯(lián)性不明顯。

圖2 三種算法在密集據(jù)集上的執(zhí)行時間

圖3 兩種算法在稀疏數(shù)據(jù)集上的執(zhí)行時間

4.2 三種類型算法效率對比

從三類FIM算法中各選取一種經(jīng)典的算法,研究其對于數(shù)據(jù)稀疏度的擴展性?！爱a(chǎn)生-測試”類選擇經(jīng)典的Apriori算法;“模式增長”類選擇經(jīng)典的FP-Growth算法;基于垂直數(shù)據(jù)格式的算法選擇基于bitmap優(yōu)化的Eclat算法(Eclat-bitmap算法)。

三種算法在兩個較密集的數(shù)據(jù)集上執(zhí)行時間如圖2所示,從中可以看出:

1)Apriori算法的性能隨著數(shù)據(jù)集稀疏度的增長降低得十分明顯。其主要原因是隨著稀疏度的增長,數(shù)據(jù)集中頻繁項的數(shù)量急劇增長,基于BFS的候選項集產(chǎn)生策略會導(dǎo)致候選項集數(shù)量相對于頻繁項的數(shù)量呈指數(shù)級別增長,極大地影響Apriori算法的性能。

2)FP-Growth算法的性能在數(shù)據(jù)集稀疏度較小的情況下具有較好的性能,但隨著數(shù)據(jù)集稀疏度的增加會產(chǎn)生明顯的惡化。其主要原因是隨著稀疏度的增長,事務(wù)頻繁項集之間的差異度越來越大,導(dǎo)致構(gòu)造的FP-Tree中事務(wù)間共享的節(jié)點數(shù)量減少,在挖掘過程中構(gòu)造的條件數(shù)據(jù)庫數(shù)量急劇增加,影響了FP-Growth算法的性能。

3)Eclat-bitmap算法在數(shù)據(jù)集稀疏度較低的情況下具備十分良好的性能,在候選項集產(chǎn)生及計數(shù)兩個階段都優(yōu)于上述兩種算法。

由于Apriori算法在數(shù)據(jù)集稀疏度高時性能惡化十分劇烈,因此對于兩個較為稀疏的算法已不再將Apriori算法作為參照對象,只考慮FP-Growth和Eclat-bitmap兩種類型的算法。

FP-Growth算法和Eclat-bitmap算法在兩個較稀疏的數(shù)據(jù)集上執(zhí)行時間如圖3所示，從中可以看出:

1)相比較而言,Eclat-bitmap算法在稀疏度較低的情況下,性能比FP-Grwoth算法要出色。但當(dāng)稀疏度上升到一定高度時,性能與FP-Growth相當(dāng)。

2)在稀疏度極高時,已有的三種典型算法的性能都不能令人十分滿意,不能很好地解決極度稀疏數(shù)據(jù)集中的FIM問題。

5 結(jié)語

數(shù)據(jù)集的特征對FIM算法的性能有著顯著的影響,除了事務(wù)數(shù)、項數(shù)及平均事務(wù)長度等數(shù)據(jù)集的一般特征外,稀疏度是描述數(shù)據(jù)集本質(zhì)特征最重要的屬性之一。本文提出了兩種量化度量數(shù)據(jù)集稀疏度的方法,考慮了最小支持度對數(shù)據(jù)集稀疏度的影響和事務(wù)之間的差異性:基于事務(wù)差異度的度量方法全面反映了所有事務(wù)之間的差異性(關(guān)聯(lián)性);而基于FP-Tree的度量方法具有更好的計算性能。從實驗結(jié)果來看,三種類型算法中“產(chǎn)生-測試”類的方法(如Apriori)對稀疏度擴展性最差,基于數(shù)據(jù)垂直格式的方法(如Eclat-bitmap)對稀疏度的擴展性最好,但當(dāng)數(shù)據(jù)稀疏度增大到一定程度時,性能仍然出現(xiàn)了極度的惡化。因此,對于極度稀疏的數(shù)據(jù)集,可以數(shù)據(jù)垂直格式方法的設(shè)計思路,優(yōu)化設(shè)計新的FIM算法,來提高挖掘的效率。

參考文獻(xiàn)(References)

[1] AGRAWAL R, IMIELINSKI T, SWAMI A N. 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: ACM,1993: 207-216.

[2] AGRAWAL R, SRIKANT R. Fast algorithms for mining association rules in large databases[EB/OL]. [2017- 05- 10]. http://www.cs.uu.nl/docs/vakken/adm/agrawalfast.pdf.

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

[4] OZEL S A, GUVENIR H A. An algorithm for mining association rules using perfect hashing and database pruning[C]// Proceedings of the 10th Turkish Symposium on Artificial Intelligence and Neural Networks. Berlin: Springer, 2001: 257-264.

[5] BRIN S, MOTWANI R, ULLMAN J D, et al. Dynamic itemset counting and implication rules for market basket data[J]. ACM Sigmod Record, 2001, 26(2): 255-264.

[6] HAN J, PEI J, YIN Y, et al. Mining frequent patterns without candidate generation: a frequent-pattern tree approach[J]. Data Mining & Knowledge Discovery, 2015, 8(1): 53-87.

[7] PYUN G, YUN U, RYU K H. Efficient frequent pattern mining based on linear prefix tree[J]. Knowledge-Based Systems, 2014, 55: 125-139.

[8] TSAY Y J, HSU T J, YU J R. FIUT: a new method for mining frequent itemsets[J]. Information Sciences, 2009, 179(11): 1724-1737.

[9] LIN K C, LIAO I E, CHEN Z S. An improved frequent pattern growth method for mining association rules[J]. Expert Systems with Applications, 2011, 38(5): 5154-5161.

[10] TSENG F C. An adaptive approach to mining frequent itemsets efficiently[J]. Expert Systems with Applications, 2012, 39(18): 13166-13172.

[11] BURDICK D, CALIMLIM M, FLANNICK J, et al. MAFIA: a maximal frequent itemset algorithm[J]. IEEE Transactions on Knowledge & Data Engineering, 2005, 17(11): 1490-1504.

[12] GOETHALS B, ZAKI M J. Advances in frequent itemset mining implementations: report on FIMI’03[J]. ACM Sigkdd Explorations Newsletter, 2003, 6(1): 109-117.

[13] BAYARDO R J J, AGRAWAL R, GUNOPULOS D. Constraint-based rule mining in large, dense databases[J]. Data Mining & Knowledge Discovery, 2000, 4(2/3): 217-240.

[14] GOUDA K, ZAKI M J. Efficiently mining maximal frequent itemsets[C]// ICDM 2001: Proceedings of the 2001 IEEE International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2001: 163-170.

[15] PALMERINI P, ORLANDO S, PEREGO R. Statistical properties of transactional databases[C]// SAC 2004: Proceedings of the 2004 ACM Symposium on Applied Computing. New York: ACM, 515-519.

[16] STEINBACH M, TAN P N, KUMAR V. Support envelopes: a technique for exploring the structure of association patterns[C]// Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2004: 296-305.

[17] YAN H, CHEN K, LIU L, et al. SCALE: a scalable framework for efficiently clustering transactional data[J]. Data Mining & Knowledge Discovery, 2010, 20(1): 1-27.

[18] 閆珍, 皮德常, 吳文昊. 高維稀疏數(shù)據(jù)頻繁項集挖掘算法的研究[J]. 計算機科學(xué), 2011, 38(6): 183-186.(YAN Z, PI D C, WU W H. Research on frequent itemsets mining algorithm for high-dimensional sparse data[J]. Computer Science, 2011, 38(6): 183-186.)

[19] GRAHNE G, ZHU J F. Efficiently using prefix-trees in mining frequent itemsets[EB/OL]. [2017- 05- 10]. http://ceur-ws.org/Vol-90/grahne.pdf.

[20] SALLEB-AOUISSI A, VRAIN C. A Contribution to the Use of Decision Diagrams for Loading and Mining Transaction Databases[M]. Amsterdam: IOS Press, 2007:220-242.

[21] SHEPARD T H. Looking for a structural characterization of the sparseness measure of(frequent closed) itemset contexts[J]. Information Sciences, 2013, 222(3): 343-361.

[22] 嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu)(C語言版) [M]. 北京:清華大學(xué)出版社, 2007: 96-96.(YAN W M, WU W M. Data Structure(C Language Edition) [M]. Beijing: Tsinghua University Press, 2007: 96-96.)

[23] YAHIA S B, HAMROUNI T, NGUIFO E M. Frequent closed itemset based algorithms[J]. ACM SIGKDD Explorations Newsletter, 2006, 8(1): 93-104.

[24] PASQUIER N, BASTIDE Y, TAOUIL R, et al. Discovering frequent closed itemsets for association rules[C]// ICDT 1999: Proceedings of the 7th International Conference on Database Theory, LNCS 1540. Berlin: Springer, 1999: 398-416.

[25] 韓家煒, 范明.數(shù)據(jù)挖掘: 概念與技術(shù)[M]. 北京:機械工業(yè)出版社, 2012: 27-46.(HAN J W, FAN M. Data Mining: Concepts and Techniques[M]. Beijing: China Machine Press, 2012: 27-46.)

[26] IEEE computer society. Frequent itemset mining dataset repository[DB/OL].[2017- 11- 01].http://fimi.ua.ac.be/data/.

This work is partially supported by the Natural Science Foundation of the Colleges and Universities in Anhui Province (KJ2016A623).