賈 泂, 劉 群, 姜 晗

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

0 引 言

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

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

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

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

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

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

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

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

性質(zhì)2如果一個來自站點Si的局部最大頻繁閉項集在別的站點不存在為其真超集的局部最大頻繁項集,那么該局部最大頻繁項集是全局最大頻繁項集.

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

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

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

本算法分為2個步驟:

步驟1:局部頻繁閉項集CFIsi和局部最大頻繁項集MFIsi的挖掘.MFIsi和CFIsi是在站點Si的頻繁項集的2種精簡表示.

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

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

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

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

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

此時,各個站點就可以得到在本站點的所有全局最大頻繁項集.對各個站點的全局最大頻繁項集求并集,也可得到所有的全局最大頻繁項集.

3 算法描述

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

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

輸出:各個站點的局部頻繁閉項集CFIsi和局部最大頻繁項集MFIsi,全局頻繁閉項集集合GCFIs,全局最大頻繁項集集合GMFIs,在各個站點的全局最大頻繁項集集合GMFIsi.

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

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

3)broadcastCFIsi;//向其他站點廣播;

5)對MFIsi按I進行字典排序;//可以利用1)排序的結果,排序后仍用MFIsi表示;

6)為MFIsi中每個元素分配一個標記位St;

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

8)Send(MFI∈MFIsi);//按hash散列的地址,把每個MFI發(fā)送到相應的站點;

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

10)GMFIs=φ;

11)for eachMFIsjdo begin

GMFIsj=DMFI(I,MFIsj);

end

12)broadcastGMFIsj;//廣播在本站點求出的全局最大頻繁項集;

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

15)For eachMFI∈MFIsiifMFI∈GMFIs

{相應位標記為MFI.St=1;}

else

{相應位標記MFI.St=0;}//超集檢測與標記全局最大頻繁項集;

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

例1設某一分布式數(shù)據(jù)庫有3個站點S1,S2,S3,其分支數(shù)據(jù)庫分別為DB1,DB2,DB3(如圖1所示),最小支持度域值為22%,經(jīng)過基于分布式系統(tǒng)關聯(lián)規(guī)則挖掘以后,按支持度降序排列的頻繁1-項集I={I2,7;I1,6;I3,6;I4,2;I5,2},頻繁項集的集合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}.

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

各個站點的頻繁項集如下:

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

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

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

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

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

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

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;//向其他站點廣播

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

6)為每一個局部最大頻繁項集分配一個標記位St;

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

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

9)接收從別的站點發(fā)來的局部最大頻繁項集;

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

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

11)broadcastGMFIsj;//廣播本站點求出的全局最大頻繁項集;

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

14)forMFI∈MFIsiifMFI∈GMFIs

{相應位標記為MFI.St=1;}

else

{相應位標記為MFI.St=0;};

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

4 算法分析

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

5 結 語

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

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

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

[3]姜晗,賈泂.基于標記域FP-Tree快速挖掘最大頻繁項集[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]楊明,孫志揮,吉根林.快速挖掘全局頻繁項目集[J].計算機研究與發(fā)展,2003,40(4):620-625.

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

[10]史忠植.知識發(fā)現(xiàn)[M].北京:清華大學出版社,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.