賈 泂, 劉 群, 姜 晗

(1.浙江師范大學(xué) 數(shù)理與信息工程學(xué)院,浙江 金華 321004;2.濟(jì)寧職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)工程系,山東 濟(jì)寧 272000)

0 引 言

自Agrawal于1993年首次提出布爾型關(guān)聯(lián)規(guī)則問(wèn)題及相應(yīng)的Apriori算法[1]以來(lái),壓縮龐大的頻繁模式集及挖掘壓縮的頻繁模式集是數(shù)據(jù)挖掘領(lǐng)域研究的重要課題之一,其中最大頻繁項(xiàng)集和頻繁閉項(xiàng)集的挖掘更是最近研究的一個(gè)熱點(diǎn)問(wèn)題.現(xiàn)有的最大頻繁項(xiàng)集和頻繁閉項(xiàng)集的挖掘算法大多局限于單機(jī)環(huán)境,從單機(jī)的事務(wù)數(shù)據(jù)庫(kù)中直接挖掘,一般需要維護(hù)大量侯選項(xiàng)集并進(jìn)行超集檢測(cè),具有較高的時(shí)間和空間復(fù)雜度[2-3].挖掘分布式數(shù)據(jù)庫(kù)壓縮的頻繁模式集算法目前尚不多見(jiàn),可用的分布式系統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法主要有PDM[4],CD[5],FDM[6],FPM[7]和FMAG[8],它們的目標(biāo)是求解出存在于本地的全局大頻繁項(xiàng)集和全局頻繁項(xiàng)集.這些算法主要分為2類:一類是采用Apriori-like算法思想,如FDM和FPM算法在自底向上(Apriori-like算法的思想)的搜索過(guò)程中,對(duì)局部候選項(xiàng)集進(jìn)行有效修剪,在一定程度上提高了算法的效率;另一類是采用FP-tree(frequent pattern tree)存儲(chǔ)結(jié)構(gòu),如FMAGF通過(guò)傳送條件頻繁模式樹或條件模式基來(lái)挖掘全局頻繁項(xiàng)集,可以有效降低網(wǎng)絡(luò)的通信開銷,提高全局頻繁項(xiàng)集的挖掘效率[9].但在產(chǎn)生頻繁模式集以后,一個(gè)站點(diǎn)將保存本地存在的所有頻繁項(xiàng)集及其支持?jǐn)?shù),其數(shù)據(jù)量是非常大的.無(wú)論是采用哪一種算法,都沒(méi)有對(duì)其進(jìn)行任何有效的精簡(jiǎn)壓縮.基于此,本文提出了分布式數(shù)據(jù)庫(kù)頻繁模式集的精簡(jiǎn)表示及精簡(jiǎn)關(guān)聯(lián)規(guī)則的挖掘算法,該算法能在分布式數(shù)據(jù)庫(kù)中各局部站點(diǎn)的全局大項(xiàng)目集的基礎(chǔ)上,迅速得出各局部站點(diǎn)與整個(gè)分布式數(shù)據(jù)庫(kù)的頻繁模式集的精簡(jiǎn)表示.

1 相關(guān)概念與性質(zhì)

Pasquier等[11]首先提出了頻繁閉項(xiàng)集和最大頻繁項(xiàng)集的概念,頻繁閉項(xiàng)集的集合表示為CFIs,最大頻繁項(xiàng)集的集合表示為MFIs.從定義可知,基于頻繁閉項(xiàng)集集合CFIs可以推導(dǎo)出所有的頻繁項(xiàng)集及其準(zhǔn)確的支持度,所以頻繁閉項(xiàng)集是一個(gè)具有最小冗余的精確結(jié)果集[12].對(duì)于一個(gè)頻繁項(xiàng)集集合,其頻繁閉項(xiàng)集集合的最大頻繁項(xiàng)集集合,就是該頻繁項(xiàng)集集合的最大頻繁項(xiàng)集集合,最大頻繁項(xiàng)集保留了所有頻繁項(xiàng)集的組合.在分布式數(shù)據(jù)庫(kù)中:

定義1DBi上的局部頻繁閉項(xiàng)集是指DBi上所有滿足真超集的支持度均小于自身支持度的全局頻繁項(xiàng)集.

定義2DBi上的局部最大頻繁項(xiàng)集是指DBi上所有滿足真超集的支持度均小于最小支持度的全局頻繁項(xiàng)集.

CFIsi為在站點(diǎn)Si的頻繁閉項(xiàng)集的集合,稱之為局部頻繁閉項(xiàng)集集合;GCFIs為整個(gè)數(shù)據(jù)庫(kù)的頻繁閉項(xiàng)集的集合,稱之為全局頻繁閉項(xiàng)集集合;MFIsi為在站點(diǎn)Si的最大頻繁項(xiàng)集的集合,稱之為局部最大頻繁項(xiàng)集集合;GMFIs為整個(gè)數(shù)據(jù)庫(kù)的最大頻繁項(xiàng)集的集合,稱之為全局最大頻繁項(xiàng)集集合.由此可得以下性質(zhì):

性質(zhì)1局部頻繁閉項(xiàng)集一定是全局頻繁閉項(xiàng)集;局部最大頻繁項(xiàng)集不一定是全局最大頻繁項(xiàng)集.

證明 若某一站點(diǎn)的頻繁項(xiàng)集是局部頻繁閉項(xiàng)集而不是全局頻繁閉項(xiàng)集,那么必存在一真超集的支持?jǐn)?shù)與其支持?jǐn)?shù)相等,且必有此項(xiàng)目集與此真超集同時(shí)出現(xiàn),故與其為局部頻繁閉項(xiàng)集矛盾.由定義2容易證明局部最大頻繁項(xiàng)集不一定是全局最大頻繁項(xiàng)集.

性質(zhì)2如果一個(gè)來(lái)自站點(diǎn)Si的局部最大頻繁閉項(xiàng)集在別的站點(diǎn)不存在為其真超集的局部最大頻繁項(xiàng)集,那么該局部最大頻繁項(xiàng)集是全局最大頻繁項(xiàng)集.

性質(zhì)3MFIsi?CFIsi?FIsi.

若某站點(diǎn)的某局部最大頻繁項(xiàng)集為全局最大頻繁項(xiàng)集,則稱該最大頻繁項(xiàng)集是該站點(diǎn)全局大的,其集合為GMFIsi.在分布式數(shù)據(jù)庫(kù)得到以上所有的定義和性質(zhì)后,就可以用來(lái)精簡(jiǎn)分布式數(shù)據(jù)庫(kù)各站點(diǎn)的全局大的頻繁項(xiàng)集和整個(gè)分布式數(shù)據(jù)庫(kù)的全局頻繁項(xiàng)集,并設(shè)計(jì)在分布式數(shù)據(jù)庫(kù)中壓縮頻繁模式集的挖掘算法,包括局部頻繁閉項(xiàng)集與全局頻繁閉項(xiàng)集、局部最大頻繁項(xiàng)集、全局最大頻繁項(xiàng)集以及各站點(diǎn)的全局最大頻繁項(xiàng)集的挖掘.

2 分布式數(shù)據(jù)庫(kù)全局最大頻繁項(xiàng)集和全局頻繁閉項(xiàng)集的挖掘算法DGMCFIs

本算法分為2個(gè)步驟:

步驟1:局部頻繁閉項(xiàng)集CFIsi和局部最大頻繁項(xiàng)集MFIsi的挖掘.MFIsi和CFIsi是在站點(diǎn)Si的頻繁項(xiàng)集的2種精簡(jiǎn)表示.

由性質(zhì)3,將算法DMFI[2]和DCFI[2]作一些改進(jìn),將其推廣到分布式數(shù)據(jù)庫(kù),在各個(gè)分支數(shù)據(jù)庫(kù)的全局大頻繁項(xiàng)集上挖掘局部最大頻繁項(xiàng)集集合MFIsi和局部頻繁閉項(xiàng)集集合CFIsi.

首先,以I(全局頻繁1-項(xiàng)目集)為標(biāo)準(zhǔn)對(duì)FIsi(Si上的全局頻繁項(xiàng)目集集合)按字典順序排序[2-3];其次,從FIsi中挖掘局部頻繁閉項(xiàng)集,只需把FIsi按照支持度分成若干個(gè)支持度相等的集合;第三,從每個(gè)集合中挖掘最大頻繁項(xiàng)集,所有集合的最大頻繁項(xiàng)集的并集就組成了DBi上的局部頻繁閉項(xiàng)集集合;最后,從局部頻繁閉項(xiàng)集集合中挖掘局部最大頻繁項(xiàng)集,得出DBi的局部最大頻繁項(xiàng)集集合.這樣求局部最大頻繁項(xiàng)集比文獻(xiàn)[2]中掃描頻繁項(xiàng)集求解最大頻繁項(xiàng)集的掃描量減少許多.

每個(gè)站點(diǎn)的局部頻繁閉項(xiàng)集集合CFIsi是該分支數(shù)據(jù)庫(kù)全局大頻繁項(xiàng)集的一個(gè)無(wú)損壓縮,一個(gè)具有最小冗余的精確結(jié)果集,也是每個(gè)站點(diǎn)全局大頻繁項(xiàng)集的一個(gè)精簡(jiǎn)表示;每個(gè)站點(diǎn)的局部最大頻繁項(xiàng)集MFIsi是每個(gè)分支數(shù)據(jù)庫(kù)的全局大頻繁項(xiàng)集的一個(gè)有損壓縮,它保留了每個(gè)站點(diǎn)的全局大頻繁項(xiàng)集的組合,但損失了這些頻繁項(xiàng)集的支持?jǐn)?shù).由于最大頻繁項(xiàng)集的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于頻繁閉項(xiàng)集的數(shù)目,更遠(yuǎn)遠(yuǎn)小于頻繁項(xiàng)集的數(shù)目,所以挖掘最大頻繁項(xiàng)集可以有效壓縮問(wèn)題解的規(guī)模,對(duì)于用戶迅速發(fā)現(xiàn)和理解稠密集中的長(zhǎng)頻繁模式具有重要的意義.因此,利用其來(lái)精簡(jiǎn)分布式數(shù)據(jù)庫(kù)的頻繁模式集是一種快速簡(jiǎn)潔而有效的方法.

步驟2:全局最大頻繁項(xiàng)集GMFIs、全局頻繁閉項(xiàng)集GCFIs和各分支站點(diǎn)的全局最大頻繁項(xiàng)集GMFIsi的挖掘.GMFIs和GCFIs是整個(gè)分布式數(shù)據(jù)庫(kù)的2種精簡(jiǎn)表示,GMFIsi是Si的全局最大頻繁項(xiàng)集.

步驟2是在步驟1的基礎(chǔ)上進(jìn)行的.由性質(zhì)1及性質(zhì)2可得:從各分支數(shù)據(jù)庫(kù)的局部頻繁閉項(xiàng)集挖掘全局頻繁閉項(xiàng)集,只需對(duì)各分支數(shù)據(jù)庫(kù)的局部頻繁閉項(xiàng)集求并集.挖掘全局最大頻繁項(xiàng)集時(shí),為每一個(gè)局部的最大頻繁項(xiàng)集設(shè)置一個(gè)標(biāo)記位,并采用分組計(jì)數(shù)技術(shù).在此算法中,筆者采用一個(gè)hash函數(shù),每個(gè)站點(diǎn)都存有此函數(shù),以字典排序后將第1個(gè)項(xiàng)目相同的局部最大頻繁項(xiàng)集散列到同一站點(diǎn),組成一組并用MFIsj表示.該站點(diǎn)作為這些局部最大頻繁項(xiàng)集的計(jì)數(shù)站點(diǎn).例如,可以采用某一hash函數(shù),假設(shè)有n個(gè)站點(diǎn),字典排序后以Im∈I開頭的所有局部最大頻繁項(xiàng)集都散列到站點(diǎn)Sm mod n并設(shè)為Si,此時(shí)在Si聚集了所有以Im開頭的、來(lái)自不同站點(diǎn)的局部最大頻繁項(xiàng)集的一個(gè)集合MFIsj,將散列到同一站點(diǎn)的不同的組分開計(jì)算,再求每組MFIsj中的最大頻繁項(xiàng)集,即可得到以Im開頭的這一組局部最大頻繁項(xiàng)集組中的最大頻繁項(xiàng)集GMFIsj,同時(shí)站點(diǎn)Si把在本地的最大頻繁項(xiàng)集中的元素按hash函數(shù)計(jì)算后得到的地址發(fā)送到相應(yīng)的站點(diǎn).假設(shè)I共有q個(gè)元素,則MFIsj={MFI|MFI∈MFIsi,MFI以Im開頭}表示來(lái)自不同站點(diǎn)的字典排序后以某一特定項(xiàng)目Im開頭的局部最大頻繁項(xiàng)集的集合,j(=1,2,3,…,q)表示Im在I中的次序,GMFIsj={MFI|MFI∈MFIsj,MFI在MFIsj是最大頻繁項(xiàng)集}.

此時(shí),各個(gè)站點(diǎn)就可以得到在本站點(diǎn)的所有全局最大頻繁項(xiàng)集.對(duì)各個(gè)站點(diǎn)的全局最大頻繁項(xiàng)集求并集,也可得到所有的全局最大頻繁項(xiàng)集.

3 算法描述

基于頻繁項(xiàng)集的分布式數(shù)據(jù)庫(kù)精簡(jiǎn)關(guān)聯(lián)規(guī)則挖掘算法(設(shè)本地為Si,每個(gè)站點(diǎn)同時(shí)執(zhí)行)如下:

輸入:全局頻繁1-項(xiàng)集的集合I,DBi中的全局大頻繁項(xiàng)集的集合FIsi(i=1,2,3,…,n);

輸出:各個(gè)站點(diǎn)的局部頻繁閉項(xiàng)集CFIsi和局部最大頻繁項(xiàng)集MFIsi,全局頻繁閉項(xiàng)集集合GCFIs,全局最大頻繁項(xiàng)集集合GMFIs,在各個(gè)站點(diǎn)的全局最大頻繁項(xiàng)集集合GMFIsi.

1)DCFI(I,FIsi);//returnCFIsi;

2)DMFI(I,CFIsi);//returnMFIsi;

3)broadcastCFIsi;//向其他站點(diǎn)廣播;

5)對(duì)MFIsi按I進(jìn)行字典排序;//可以利用1)排序的結(jié)果,排序后仍用MFIsi表示;

6)為MFIsi中每個(gè)元素分配一個(gè)標(biāo)記位St;

7)Sm mod n=hash(Im);//把MFIsi中的元素按項(xiàng)目集的第1項(xiàng)散列到某一站點(diǎn);

8)Send(MFI∈MFIsi);//按hash散列的地址,把每個(gè)MFI發(fā)送到相應(yīng)的站點(diǎn);

9)receive(MFI∈MFIsj),j=1,2,3,…,q;//每個(gè)站點(diǎn)可能有多個(gè)組,按j編組;

10)GMFIs=φ;

11)for eachMFIsjdo begin

GMFIsj=DMFI(I,MFIsj);

end

12)broadcastGMFIsj;//廣播在本站點(diǎn)求出的全局最大頻繁項(xiàng)集;

13)receiveGMFIsj;//接受發(fā)自其他站點(diǎn)的全局最大頻繁項(xiàng)集

15)For eachMFI∈MFIsiifMFI∈GMFIs

{相應(yīng)位標(biāo)記為MFI.St=1;}

else

{相應(yīng)位標(biāo)記MFI.St=0;}//超集檢測(cè)與標(biāo)記全局最大頻繁項(xiàng)集;

16)GMFIsi={MFI|MFI∈MFIsi,i=1,2,…,n,MFI.St=1};//存在于站點(diǎn)Si的全局最大頻繁項(xiàng)集;

例1設(shè)某一分布式數(shù)據(jù)庫(kù)有3個(gè)站點(diǎn)S1,S2,S3,其分支數(shù)據(jù)庫(kù)分別為DB1,DB2,DB3(如圖1所示),最小支持度域值為22%,經(jīng)過(guò)基于分布式系統(tǒng)關(guān)聯(lián)規(guī)則挖掘以后,按支持度降序排列的頻繁1-項(xiàng)集I={I2,7;I1,6;I3,6;I4,2;I5,2},頻繁項(xiàng)集的集合FIs={I1,6;I2,7;I3,6;I4,2;I5,2;I1I2,4;I1I3,4;I1I5,2;I2I3,4;I2I4,2;I2I5,2;I1I2I3,2;I1I2I5,2}.

站點(diǎn)S1,分支數(shù)據(jù)庫(kù)DB1 站點(diǎn)S2,分支數(shù)據(jù)庫(kù)DB2 站點(diǎn)S3,分支數(shù)據(jù)庫(kù)DB3

各個(gè)站點(diǎn)的頻繁項(xiàng)集如下:

S1站點(diǎn)分支數(shù)據(jù)庫(kù)DB1頻繁項(xiàng)集為{I1,6;I2,7;I3,6;I4,2;I5,2;I1I2,4;I1I5,2;I2I3,4;I2I4,2;I2I5,2;I1I2I5,2};

S2站點(diǎn)分支數(shù)據(jù)庫(kù)DB2頻繁項(xiàng)集為{I1,6;I2,7;I3,6;I4,2;I1I2,4;I1I3,4;I2I3,4;I2I4,2};

S3站點(diǎn)分支數(shù)據(jù)庫(kù)DB3頻繁項(xiàng)集為{I1,6;I2,7;I3,6;I5,2;I1I2,4;I1I3,4;I1I5,2;I2I3,4;I2I5,2;I1I2I3,2;I1I2I5,2}.

算法的執(zhí)行過(guò)程如下:

1)調(diào)用DCFI,得到站點(diǎn)的局部頻繁閉項(xiàng)集集合CFIsi,如S1有CFIs1={I2I4,2;I2I1I5,2;I2I1,4;I2I3,4;I1,6;I3,6;I2,7};

2)調(diào)用DMFI(I,CFIs1),得到局部最大頻繁項(xiàng)集集合MFIsi,故有MFIs1={I2I4;I2I1I5;I2I3},同理S2,S3站點(diǎn)的頻繁閉項(xiàng)集和局部最大頻繁項(xiàng)集分別為:

CFIs2={I2I4,2;I1I2,4;I1I3,4;I2I3,4;I1,6;I3,6;I2,7},

CFIs3={I2I1I3,2;I2I1I5,2;I2I1,4;I2I3,4;I1I3,4;I1,6;I3,6;I2,7},

MFIs2={I2I4;I1I2;I1I3;I2I3},MFIs3={I2I1I3;I2I1I5};

3)broadcastCFIsi;//向其他站點(diǎn)廣播

5)對(duì)本站點(diǎn)的局部最大頻繁項(xiàng)集集合進(jìn)行字典排序,排序后仍記為MFIsi,故MFIs1={I2I1I5;I2I3;I2I4},同理MFIs2={I2I1;I2I3;I2I4;I1I3},MFIs3={I2I1I3;I2I1I5};

6)為每一個(gè)局部最大頻繁項(xiàng)集分配一個(gè)標(biāo)記位St;

7)用hash函數(shù)對(duì)本站點(diǎn)的局部最大頻繁項(xiàng)集按項(xiàng)目集的第1個(gè)項(xiàng)目散列到相應(yīng)站點(diǎn),第1項(xiàng)相同的局部最大頻繁項(xiàng)集就被散列到同一個(gè)站點(diǎn)的同一組中,并用MFIsj表示,如在S1站點(diǎn)上MFIs1中的元素的第1項(xiàng)都是I2,故把它們?nèi)及l(fā)送到S2 mod 3=S2中,并被放在同一組MFIsj;

8)發(fā)送完后接受從別的站點(diǎn)發(fā)送過(guò)來(lái)的局部最大頻繁項(xiàng)集,故站點(diǎn)S1有MFIs2={I1I3},同理在站點(diǎn)S2有MFIs1={I2I1I5;I2I3;I2I4;I2I1;I2I1I3},在站點(diǎn)S3上MFIsj=φ;

9)接收從別的站點(diǎn)發(fā)來(lái)的局部最大頻繁項(xiàng)集;

10)對(duì)每個(gè)MFIsj調(diào)用GMFIsj=DMFI(I,MFIsj),故有

GMFIs1={I2I1I3;I2I1I5;I2I4},GMFIs2={I1I3},GMFIs3=φ;

11)broadcastGMFIsj;//廣播本站點(diǎn)求出的全局最大頻繁項(xiàng)集;

12)receiveGMFIsj;//接受發(fā)自其他站點(diǎn)的全局最大頻繁項(xiàng)集;

14)forMFI∈MFIsiifMFI∈GMFIs

{相應(yīng)位標(biāo)記為MFI.St=1;}

else

{相應(yīng)位標(biāo)記為MFI.St=0;};

15)GMFIsi={MFI|MFI∈MFIsi,i=1,2,…,n,MFI.St=1};//生成存在于站點(diǎn)Si的全局最大頻繁項(xiàng)集

4 算法分析

在算法DGMCFIs中,首先，基于各個(gè)站點(diǎn)的全局大頻繁項(xiàng)集求出了局部頻繁閉項(xiàng)集和局部最大頻繁項(xiàng)集,其中先求局部頻繁閉項(xiàng)集,再在局部閉項(xiàng)集中求局部最大頻繁項(xiàng)集.顯然，這樣求局部最大頻繁項(xiàng)集比文獻(xiàn)[2]中掃描頻繁項(xiàng)集求解最大頻繁項(xiàng)集的掃描量大大減少.其次,在求全局最大頻繁項(xiàng)集和存在于局部的全局最大頻繁項(xiàng)集時(shí),繼續(xù)利用前面字典排序的結(jié)果,采用分組計(jì)數(shù)技術(shù),將局部最大頻繁項(xiàng)集發(fā)送到特定的站點(diǎn).在此，只需將局部最大頻繁項(xiàng)集發(fā)送到特定的站點(diǎn)，而不是在各個(gè)站點(diǎn)上求局部最大頻繁項(xiàng)集的并集.這是因?yàn)?如果此時(shí)簡(jiǎn)單地求并集,超集檢測(cè)會(huì)將每個(gè)站點(diǎn)的局部最大頻繁項(xiàng)集發(fā)送到其他的每個(gè)站點(diǎn),其通信量將會(huì)是巨大的,為nN(N為MFI∈MFIsi的總數(shù)).分組后先求出每組中的最大頻繁項(xiàng)集,再求每組中最大頻繁項(xiàng)集的并集,將大大減少網(wǎng)絡(luò)間的通信量.第三,在得到全局最大頻繁項(xiàng)集后,各個(gè)站點(diǎn)自己進(jìn)行超集檢測(cè),這樣就可以獲得全局最大頻繁項(xiàng)集,其通信量為(N+nM)(M為MFI∈GMFIsj的總數(shù)).采用堆排序方法的復(fù)雜度為O(nlog2n),整個(gè)算法在各個(gè)站點(diǎn)都能并行執(zhí)行.實(shí)際上,整個(gè)算法只進(jìn)行了1次字典排序,存在于各站點(diǎn)的全局頻繁項(xiàng)集、局部頻繁閉項(xiàng)集、發(fā)送到本地的局部最大頻繁項(xiàng)集、局部最大頻繁項(xiàng)集與最大頻繁項(xiàng)集各掃描了1次.

5 結(jié) 語(yǔ)

將頻繁閉項(xiàng)集與最大頻繁項(xiàng)集的概念推廣到分布式數(shù)據(jù)庫(kù)系統(tǒng)中,在所需的空間與通信量盡可能少的前提下,提出了在分布式環(huán)境中全局范圍內(nèi)精簡(jiǎn)的頻繁模式集挖掘算法,算法有效地壓縮了頻繁模式集.面對(duì)分布式數(shù)據(jù)庫(kù)系統(tǒng)海量的局部與全局的頻繁模式集,此種關(guān)聯(lián)規(guī)則的精簡(jiǎn)表示與求解算法具有一定的現(xiàn)實(shí)意義.

[1]Han Jiawei,Micheline K.數(shù)據(jù)挖掘概念與技術(shù)[M].范明,孟小峰,譯.北京:機(jī)械工業(yè)出版社,2001:149-175.

[2]姜晗,賈泂.基于頻繁項(xiàng)集挖掘最大頻繁項(xiàng)集和頻繁閉項(xiàng)集[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(28):146-148.

[3]姜晗,賈泂.基于標(biāo)記域FP-Tree快速挖掘最大頻繁項(xiàng)集[J].計(jì)算機(jī)研究與發(fā)展,2007,44(增):334-338.

[4]Park J S,Chen M S,Yu P S.Efficient parallel data mining for association rules[M]//PIssinou N K,Park E K.Proceedings of 4th International Conference on Information and Knowledge Management.New York:ACM Press,1995:31-36.

[5]Agrawal R,Shafer J.Parallel mining of association rules[J].IEEE Trans on Knowledge and Data Engineering,1996,8(6):962-969.

[6]Cheung D W,Han Jiawei,Fu A W,et al.A fast distributed algorithm for mining association rules[M]// Ng V T.Proceedings of 4th International Conference on Parallel and Distributed Information Systems.Florida:Harlequin Books Press,1996:31-44.

[7]Cheung D W,Lee S D,Xiao Yongqiao.Effect of data skewness and workload balance in parallel data mining[J].IEEE Trans on Knowledge and Data Engineering,2002,14(3):498-514.

[8]楊明,孫志揮,吉根林.快速挖掘全局頻繁項(xiàng)目集[J].計(jì)算機(jī)研究與發(fā)展,2003,40(4):620-625.

[9]楊明,孫志揮,宋余慶.快速更新全局頻繁項(xiàng)目集[J].軟件學(xué)報(bào),2004,15(8):1189-1197.

[10]史忠植.知識(shí)發(fā)現(xiàn)[M].北京:清華大學(xué)出版社,2005:69-78.

[11]Pasquier N,Bastide Y,Taouil R,et al.Pruning closed itemset lattices for association rules[M]//Lakhal Proceedings of BDA ’98 Conference.Tunisie:BDA Press,1998:177-196.

[12]Pasquier N,Basride Y,Taouil R,et al.Discovering frequent closed itemsets for association rules[M]//Beer C,Buneman P.Database Theory-ICDT ’99.Berlin:Springer,1999:398-416.