基于元學(xué)習(xí)的分布式挖掘頻繁閉合模式算法研究
2009-01-01 00:00:00琚春華倪棟君
計(jì)算機(jī)應(yīng)用研究 2009年1期
(浙江工商大學(xué) 計(jì)算機(jī)與信息工程學(xué)院， 杭州 310018)
摘 要：利用元學(xué)習(xí)技術(shù)提出了一種分布式挖掘頻繁閉合模式算法；為適應(yīng)不同的分布式環(huán)境，還給出了該算法的一個(gè)變種；最后通過實(shí)驗(yàn)討論了不同分布式下選取算法的策略。算法具有挖掘效率高、通信量少、可靠性高的特點(diǎn)，適合分布式挖掘。
關(guān)鍵詞：數(shù)據(jù)挖掘； 頻繁閉合模式； 分布式挖掘； 元學(xué)習(xí)
中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)志碼：A
文章編號(hào)：10013695(2009)01004103
Study of algorithm for distributed mining frequent closed
patterns based on metalearn technology
JU Chunhua， NI Dongjun
(College of Computer Information Engineering， Zhejiang Gongshang University， Hangzhou 310018， China）
Abstract:This paper presented a distributed algorithm for mining frequent closed patterns using metalearning. In order to accommodate the different distributed environment， also presented another similar algorithm. In the end， discussed the strategy for choosing the right distributed algorithm by experiment. This algorithm is more efficient and has less communicated and high reliability， applicable to distributed mining well.
Key words：data mining; frequent closed patterns; distributed mining; metalearning
頻繁模式挖掘在數(shù)據(jù)挖掘領(lǐng)域有著廣泛的應(yīng)用。雖然頻繁模式的挖掘在近些年來被深入研究，也提出了一些比最初的Aprior算法[1]性能更好的算法，但是一旦支持度降低或數(shù)據(jù)傾斜，頻繁模式的數(shù)量就會(huì)急劇增加，這些算法的性能也將急劇下降。用頻繁閉合模式挖掘代替頻繁模式挖掘是近年來提出的新策略。頻繁閉合模式集合包含了頻繁模式集合的全部信息，但數(shù)量前者通常比后者要小很多。此外，由頻繁閉合模式集合可直接產(chǎn)生無冗余的關(guān)聯(lián)規(guī)則。近年來隨著分布式環(huán)境的日益普遍，而現(xiàn)有的挖掘頻繁閉合模式算法如AClose[2]、CLOSET+[3]、CHARM[4]等都是針對(duì)單處理器、單一數(shù)據(jù)集，不適用分布式環(huán)境。所以研究分布式下的挖掘頻繁閉合模式算法具有重要意義。本文在已有挖掘閉合模式算法的基礎(chǔ)上，針對(duì)頻繁閉合模式和分布式環(huán)境的特點(diǎn)，提出利用元學(xué)習(xí)技術(shù)并行地在各個(gè)站點(diǎn)挖掘局部頻繁閉合模式；然后根據(jù)不同的分布式環(huán)境采用不同的學(xué)習(xí)策略，最終挖掘出全局頻繁閉合模式。
1 問題描述
1.1 頻繁閉合模式
給定一個(gè)事務(wù)數(shù)據(jù)庫DB，I(xiàn)={I1，I2，…，Im}為DB中m個(gè)不同項(xiàng)目的集合。DB中每一個(gè)事務(wù)T就是I中的一組不同項(xiàng)目集，即TI。
定義1 模式X在DB中的支持度定義為sup(X)=DB中包含X的事務(wù)個(gè)數(shù)/DB中的總事務(wù)個(gè)數(shù)。
定義2 模式X如果滿足sup(X)≥min_sup，則稱X是頻繁模式，min_sup是設(shè)定的最小支持度閾值。
定義3 對(duì)于模式X，如果不存在任何真超集Y，使得sup(X)=sup(Y)，則稱X是閉合的；如果X既是頻繁的又是閉合的，則稱X是頻繁閉合模式。
引理1 在DB中，包含頻繁模式X且與X有相同支持度的頻繁閉合模式有且僅有一個(gè)[5]。
引理2 設(shè)X、Y都是頻繁模式，假如XY且sup(X)=sup(Y)，則X不是頻繁閉合模式。
1.2 分布式頻繁閉合模式挖掘
假設(shè)分布式數(shù)據(jù)庫DB{DB1，DB2，…，DBn}在分布式系統(tǒng)S(S1，S2，…，Sn， n是站點(diǎn)數(shù))上存放，對(duì)于任一個(gè)閉合模式X、X.sup和X.supi分別表示閉合模式X在DB和DBi上的支持?jǐn)?shù)。
定義4 在S(S1，S2，…，Sn)中，如果X.sup≥min_sup×DB，則稱X是全局頻繁閉合模式;如果X.supi≥min_sup×DBi，則稱X在站點(diǎn)Si上是頻繁閉合模式。
引理3 若X為全局頻繁閉合模式，則必存在一個(gè)站點(diǎn)Si (1≤i≤n)，使得X在站點(diǎn)Si上為局部頻繁閉合模式。
證明 若不存在站點(diǎn)Si(1≤i≤n)使得X在站點(diǎn)Si上為局部頻繁閉合模式，則X在任一個(gè)站點(diǎn)的支持?jǐn)?shù)X.supi＜min_sup×DBi，可得：
∑ni=1X.supi＜∑ni=1min_sup×DBi
∑ni=1X.supi=X.sup
∑ni=1 min_sup×DBi=min_sup×DB
即X.sup＜min_sup×DB與X為全局頻繁閉合模式相矛盾，因此必存在一個(gè)站點(diǎn)Si（1≤i≤n），使得X在站點(diǎn)Si上為局部頻繁閉合模式。
引理4 n個(gè)站點(diǎn)S1，S2，S3，…，Sn，Li（1≤i≤n）為站點(diǎn)Si（1≤i≤n）的局部頻繁閉合模式，L′=∪ni=1Li ，則L′必為全局頻繁閉合模式L的超集。
證明 要證L′是全局頻繁閉合L的超集，只要證明對(duì)X∈L，則 X∈L′。
因?yàn)閄∈L， 所以X.sup≥min_sup×DB；假設(shè)XL′，則有X.sup=∑ni=1X.supi＜∑ni=1 min_sup×DBi=min_sup×DB。這與X∈L相矛盾，故假設(shè)不成立，定理得證。
由上所述，分布式挖掘頻繁閉合模式的主要任務(wù)是并行地在多個(gè)站點(diǎn)上挖掘局部頻繁閉合模式集，在此基礎(chǔ)上協(xié)助產(chǎn)生全局頻繁閉合模式集。
2 有關(guān)技術(shù)
2.1 子集檢查
頻繁閉合模式挖掘不僅要判斷模式的頻繁性，還要判斷模式的閉合性。子集檢查技術(shù)能用來判斷模式的閉合性，其步驟為：首先對(duì)候選的閉合模式集按模式長(zhǎng)度從小到大排列，然后從最短模式如X開始與它后面的模式相比較。如果發(fā)現(xiàn)模式Y(jié)滿足XY且X.sup=Y.sup的條件，由引理2可得X不是閉合模式則被裁剪，繼續(xù)從Y開始與它后面的模式相比較，重復(fù)X的檢查。這樣掃描一遍候選閉合模式集可產(chǎn)生一個(gè)閉合模式。反復(fù)掃描候選閉合模式集，直到全為閉合模式為止。
2.2 元學(xué)習(xí)
元學(xué)習(xí)是關(guān)于學(xué)習(xí)的學(xué)習(xí)，在學(xué)習(xí)結(jié)果的基礎(chǔ)上再進(jìn)行學(xué)習(xí)或多次學(xué)習(xí)而得到最終結(jié)果[6]。在各站點(diǎn)中，根據(jù)給定的最小支持度，所挖掘出的局部頻繁閉合模式集L(i)(i=1，2，…，n)可看做第一次學(xué)習(xí)的結(jié)果。為挖掘出全局頻繁閉合模式集，需要對(duì)L(i)不斷學(xué)習(xí)。針對(duì)不同的分布式環(huán)境，其學(xué)習(xí)策略應(yīng)有所不同。下面給出常見的兩種分布式環(huán)境下挖掘頻繁閉合模式的方法。
方法1 先分站點(diǎn)全局頻繁裁剪再對(duì)元學(xué)習(xí)站點(diǎn)閉合檢查。
各個(gè)站點(diǎn)將本地的頻繁閉合模式發(fā)往其他各站點(diǎn)，收集其在其他站點(diǎn)的支持?jǐn)?shù)，等求出其在所有站點(diǎn)上的實(shí)際支持?jǐn)?shù)后與全局最小支持?jǐn)?shù)進(jìn)行比較，裁剪非全局頻繁的模式。之后，任選一個(gè)站點(diǎn)作為元學(xué)習(xí)站點(diǎn)，元學(xué)習(xí)站點(diǎn)收集各站點(diǎn)的模式及其支持?jǐn)?shù)并進(jìn)行子集檢查，求得全局頻繁閉合模式集。這種方法在各分站點(diǎn)能挖掘出具有全局意義的頻繁閉合模式且每次通信量較少，但各站點(diǎn)通信較頻繁，適合于站點(diǎn)數(shù)較少、通信帶寬小的分布式環(huán)境。
方法2 元學(xué)習(xí)站點(diǎn)先進(jìn)行全局頻繁裁剪后作閉合性檢查。
任選一個(gè)站點(diǎn)作為元學(xué)習(xí)站點(diǎn)，各個(gè)站點(diǎn)將本地的頻繁閉合模式發(fā)往元學(xué)習(xí)站點(diǎn)。元學(xué)習(xí)站點(diǎn)將相同模式進(jìn)行簡(jiǎn)單歸并，形成全局候選頻繁閉合模式。然后，全局候選頻繁閉合模式依次掃描各站點(diǎn)數(shù)據(jù)庫，求得其在所有站點(diǎn)上的實(shí)際支持?jǐn)?shù)；裁剪非全局頻繁的模式，再進(jìn)行子集檢查，求得全局頻繁閉合模式集。這種方法，元站點(diǎn)與其他各站點(diǎn)通信量較大，但通信次數(shù)并不頻繁，適合于站點(diǎn)數(shù)較多、通信帶寬大的分布式環(huán)境。
3 利用元學(xué)習(xí)技術(shù)分布式閉合模式挖掘算法
利用元學(xué)習(xí)分布式挖掘頻繁閉合模式算法大致可以分為三個(gè)階段：a)局部挖掘，并行地在各個(gè)站點(diǎn)上挖掘頻繁閉合模式；b)全局頻繁裁剪，利用元學(xué)習(xí)策略進(jìn)行全局頻繁裁剪，生成候選的全局頻繁閉合模式；c)閉合性裁剪，采用子集檢查法對(duì)候選的全局頻繁閉合模式進(jìn)行閉包性檢測(cè)，生成全局頻繁閉合模式。利用上述技術(shù)，本章給出分布式挖掘頻繁閉合模式的算法DMCP(distributed mining closed patterns)及其變種。
3.1 算法DMCP
算法DMCP:采用先分站點(diǎn)全局頻繁裁剪后元學(xué)習(xí)站點(diǎn)閉合檢查方法
輸入：分布式數(shù)據(jù)庫DBi(i=1，2，…，n)，最小支持度min_sup；
輸出：全局頻繁閉合模式集L。
①for i=1，2，…，n do{
②L(i)=local-mining(DBi，min_sup); /* 根據(jù)每一站點(diǎn)上的數(shù)據(jù)集DBi和min_sup 生成局部頻繁閉合模式集L(i) */
③send L(i) to DBj; /*發(fā)送L(i)到其他各站點(diǎn)*/
④for j=1，2，…，n andj≠i do{
⑤if L(j) has been mine from DBj{ /* DBj 上L(j)已經(jīng)被挖掘出來的情形 */
/*在L(j)上掃描檢查有否與L(i)相同的模式，如有則記下其支持?jǐn)?shù)*/
⑥X∈ L(i) if X∈L(j) write down X.supj
/*如L(i)還有剩下的模式，掃描一遍DBj 檢查有否與L(i)相同的模式，如有則記下其支持?jǐn)?shù)*/
⑦scan DBj and check L(i)
⑧}else{ scan DBj and check L(i) /* DBj 上L(j)沒有被挖掘出來則掃描一遍DBj 檢查有否與L(i)相同的模式，如有則記下支持?jǐn)?shù)*/
} }
⑨receive(X.supi) (X∈L(i))
/* 收集L(i)在其他站點(diǎn)的支持?jǐn)?shù)*/
⑩if X.supi＜min_sup×DB delete X /*在站點(diǎn)Si上進(jìn)行全局頻繁裁剪*/
}
B11L=receive(X， X.supi) /*在元站點(diǎn)上，收集各站點(diǎn)的模式及支持?jǐn)?shù) */
B12L=check_close(L) /* 用子集檢查技術(shù)進(jìn)行閉包性檢測(cè) */
B13return L
算法說明:
a)①~⑩各站點(diǎn)形成具有全局意義的頻繁閉合模式；B12集成各站點(diǎn)的模式時(shí)可能會(huì)產(chǎn)生重復(fù)閉合頻繁模式，用子集檢查技術(shù)進(jìn)行修正。
b)②并行地挖掘各站點(diǎn)局部頻繁閉合模式。
c)⑤~⑨先挖掘完的站點(diǎn)立即發(fā)送其本地的頻繁閉合模式到其他站點(diǎn)；其他站點(diǎn)收到后，先掃描容量較小的局部頻繁閉合模式(如果已挖掘完成)，再掃描其數(shù)據(jù)庫，不必等到全部分站點(diǎn)挖掘出局部頻繁閉合模式才進(jìn)行通信。這樣，最大限度地增大了并行度，提高了挖掘效率。
d)③ ⑨ B11表明各站點(diǎn)的通信量。
3.2 算法DMCP的變種算法DMCPML
算法DMCP為了在各個(gè)站點(diǎn)進(jìn)行全局頻繁裁剪，需要把某一站點(diǎn)的所有局部頻繁閉合模式發(fā)往其他各個(gè)站點(diǎn)以收集支持?jǐn)?shù)，這樣增大了站點(diǎn)之間的通信次數(shù)。為了減少通信次數(shù)，采用元站點(diǎn)先進(jìn)行頻繁裁剪后閉合裁剪的方法。此算法稱為DMCPML，如下所示:
將算法DMCP③~B11修改為
③L=receive(i，L(i)) /*在元站點(diǎn)上，收集各站點(diǎn)的模式 */
④L=process(L) /* L中刪除重復(fù)的模式*/
}
⑤for j=1，2，…，n do{
⑥掃描j站點(diǎn)上數(shù)據(jù)集DBj一遍，生成L在DBj中所有模式的支持個(gè)數(shù);
⑦receive(j，L);/* 收集L在各站點(diǎn)上的實(shí)際支持?jǐn)?shù)*/
}
⑧if X.sup＜min_sup×DB delete X(X∈L) /*元學(xué)習(xí)站點(diǎn)上對(duì)L進(jìn)行模式的頻繁性裁剪*/
4 DMCP算法與其他相關(guān)算法比較
DMCP算法與分布式算法DMAR[7]、SMDM[8]比較。現(xiàn)有分布式算法很多，如典型的FDM、DMAR、SMDM算法等。文獻(xiàn)[7]提到DMAR算法性能已超過FDM，故本文選用DMAR代替FDM。
1)產(chǎn)生關(guān)聯(lián)規(guī)則效率 DMCP算法能挖掘出完備的頻繁閉合模式集，DMAR算法只能挖掘出完備的頻繁模式集，而SMDM僅能挖掘近似的頻繁模式集。頻繁閉合模式能立即得到無冗余關(guān)聯(lián)規(guī)則，而從頻繁模式推導(dǎo)出無冗余關(guān)聯(lián)規(guī)則系統(tǒng)開銷較大。
2)通信量 DMCP算法與DMAR算法通信次數(shù)相同，但由于頻繁閉合模式集一般比頻繁模式集規(guī)模要小得多，每次通信量也要小得多。
3)可靠性 采用DMAR算法挖掘，如果分站點(diǎn)支持度設(shè)置很低或數(shù)據(jù)傾斜時(shí)會(huì)產(chǎn)生海量的頻繁模式，最終某些站點(diǎn) 因內(nèi)存不足導(dǎo)致挖掘任務(wù)失敗。DMCP算法可以在支持度更低的情況下正常運(yùn)行。
4)挖掘效率 DMAR要等到各站點(diǎn)挖掘出局部頻繁模式集后才進(jìn)行站點(diǎn)間通信；此外，在元學(xué)習(xí)站點(diǎn)上集成并處理大量的候選頻繁模式系統(tǒng)開銷也很大。而DMCP算法在每個(gè)站點(diǎn)挖掘出本地頻繁閉合模式后就立即與其他站點(diǎn)通信，增大了并發(fā)度。在元學(xué)習(xí)站點(diǎn)上雖然有子集檢查的額外開銷，但相比DMAR算法，各站點(diǎn)通信量少很多，元學(xué)習(xí)站點(diǎn)集成和處理的候選模式規(guī)模也小很多。總體而言，DMCP比DMAR算法挖掘效率要高。
5 實(shí)驗(yàn)結(jié)果與分析
實(shí)驗(yàn)的硬件平臺(tái)是PentiumⅢ 1 000 MHz CPU，256 MB Memory，20 GB HD的PC機(jī)；操作系統(tǒng)是Windows 2000 Server。數(shù)據(jù)集由IBM Almaden生成器[9]生成，各站點(diǎn)配置相同，存放10 000條事務(wù)數(shù)據(jù)。下面在局域網(wǎng)和非局域網(wǎng)兩種不同的分布式環(huán)境下對(duì)DMCP及其變種算法DMCPML進(jìn)行了對(duì)比實(shí)驗(yàn)。其局部挖掘算法都為AClose算法。
圖1 表明局域網(wǎng)內(nèi)最小支持度為min_sup=1%的情況下，DMCP算法與DMCPML算法在不同站點(diǎn)數(shù)下挖掘時(shí)間的比值，即加速比。在實(shí)驗(yàn)過程中發(fā)現(xiàn)，同一局域網(wǎng)帶寬很大，影響加速比的因素主要是站點(diǎn)間的通信次數(shù)，而不是通信量大小。DMCP算法通信次數(shù)復(fù)雜度為O(n2)，而DMCPML算法通信次數(shù)復(fù)雜度僅為O(n)，隨著站點(diǎn)數(shù)增加，加速比越來越大。
圖2表明在局域網(wǎng)內(nèi)站點(diǎn)數(shù)n=4的情況下，DMCP算法與DMCPML算法在不同支持度下挖掘時(shí)間的比值。從實(shí)驗(yàn)結(jié)果中可以發(fā)現(xiàn)，隨著支持度的降低，加速比略有下降，但不明顯。下降的原因是隨著支持度降低，各站點(diǎn)挖掘出的頻繁閉合模式集就會(huì)增大，使得 DMCPML算法和DMCP算法每次通信量的絕對(duì)差值變大（DMCPML每次通信量為所有站點(diǎn)的候選集，而DMCP僅為各站點(diǎn)的候選集）。不明顯主要也是因?yàn)樵谕粋€(gè)局域網(wǎng)內(nèi)。
圖3 表明分站點(diǎn)在不同的網(wǎng)段上最小支持度 min_sup=1%的情況下， DMCP算法與DMCPML算法在不同站點(diǎn)數(shù)下挖掘時(shí)間的比值。從實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，隨著站點(diǎn)數(shù)的增加，加速比有下降的趨勢(shì)。其原因主要是不同網(wǎng)段通信開銷較大，對(duì)通信量大小較敏感，通信量也成為影響加速比的因素。由前面分析可得，DMCP算法的通信量比DMCPML算法要小得多。
圖4 表明分站點(diǎn)在不同的網(wǎng)段上站點(diǎn)數(shù)n=4的情況下，DMCP算法與DMCPML算法挖掘時(shí)間的比值。從實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，隨著支持度的降低，加速比下降較圖3明顯。下降明顯的原因是站點(diǎn)數(shù)相同，兩個(gè)算法通信次數(shù)的絕對(duì)差值保持不變，而在圖3中兩者的通信次數(shù)絕對(duì)差值在增加。下降原因與圖3的原因一樣。
由上述實(shí)驗(yàn)結(jié)果和分析可得出分布式環(huán)境下選取DMCP算法及其變種的一般規(guī)律：當(dāng)網(wǎng)絡(luò)帶寬較大，或者估計(jì)挖掘出的閉合模式集規(guī)模不大（小于10 000條），或者分站點(diǎn)數(shù)較多（大于10個(gè)），則選用DMCPML算法；反之選用DMCP算法。
6 結(jié)束語
本文充分利用元學(xué)習(xí)技術(shù)，針對(duì)不同的分布式環(huán)境，采取不同元學(xué)習(xí)策略，提出了一種分布式頻繁閉合模式的挖掘算法DMCP及其變種。與其他相關(guān)算法相比，其具有效率高、可靠和通信量少等特點(diǎn)。生成的閉合頻繁模式易于無冗余規(guī)則的發(fā)現(xiàn)，對(duì)各局部站點(diǎn)和全局輔助決策具有重要意義。但分布式下挖掘局部閉合模式仍是時(shí)間和存儲(chǔ)開銷很大的任務(wù)，為發(fā)現(xiàn)全局頻繁閉合模式，需要多次掃描數(shù)據(jù)庫。下一步的工作在于提高局部站點(diǎn)挖掘頻繁閉合模式的效率和減少數(shù)據(jù)庫掃描次數(shù)。
參考文獻(xiàn)：
［1］AGRAWAL R，SRIKANT R. Fast algorithms for mining association rules[C]//Proc ofthe 20th International Conference on very Large Databases. Santiago:Morgan Kaufmann Publishers， 1994:487499.
[2]PASQUIER N， BASTIDE Y， TAOUIL R， et al. Discovering frequent closed itemsets for association rules[C]//Proc ofthe 7th International Conference on Database Theory. London: SpringerVerlag， 1999: 398416.
[3]WANG Jianyong， HAN Jiawei， PEI Jian. CLOSET+: searching for the best strategies for mining frequent closed itemsets[C]//Proc of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press， 2003:236245.
[4]ZAKI M J， HSIAO C J. CHARM: an efficient algorithm for closed itemset mining[C]//Proc of the 2nd SIAM International Conference on Data Mining.Arlington:SIAM，2002:1228.
[5]繆裕青. 頻繁閉合項(xiàng)目集的并行挖掘算法研究[J]. 計(jì)算機(jī)科學(xué)，2004，31(5):166168.
[6]CHAN P. An extensible metalearning approach for scalable and accurate inductive learning[D]. New York: Columbia University， 1996.
[7]張繼福，鄭鏈 ，史虹，等. 基于元學(xué)習(xí)技術(shù)的分布式挖掘關(guān)聯(lián)規(guī)則研究[J]. 系統(tǒng)仿真學(xué)報(bào)，2004，16（4）:696699.
[8]王春花，黃厚寬.利用抽樣技術(shù)分布式開采可變精度的關(guān)聯(lián)規(guī)則[J]. 計(jì)算機(jī)研究與發(fā)展，2000，38(9):11011106.
[9]SRIKANT R. Quest synthetic data generation code[R]. San Jose: IBM Almaden Research Center， 1994.
