多數據庫中例外模式挖掘方法研究

摘要:首先比較了現有的兩種挖掘方法，提出了一種改進技術。綜合考慮例外的局部和全局興趣度，剔除非真正有趣的局部例外;增加兩種客觀度量并按模式重要度排序。實驗表明該方法不僅可以有效挖掘多數據庫中例外模式，而且還大大減少了用戶負擔。

關鍵詞:多數據庫挖掘;例外模式;低選票例外;興趣度度量

中圖分類號:TP391文獻標志碼:A

文章編號:1001－3695(2008)02－0382－04

0引言

多數據庫挖掘就是對多個數據庫中的數據進行分析，從中找出多個數據庫共有的或個別數據庫特有的新穎有趣的模式。隨著分布式數據庫技術及計算機網絡技術的不斷發展和應用，多數據庫挖掘技術研究已經成為近年來數據挖掘和知識發現領域研究的熱點[1~6]。相對于傳統的從選擇數據到綜合數據最后集中挖掘的多數據庫挖掘技術[7~11]，新的多數據庫挖掘方法保持了數據的分布式存儲方式，采用先挖掘單個數據庫得到局部模式，再綜合局部模式進行全局分析的兩級挖掘過程[1]，不僅避免了集成數據造成的海量數據挖掘，同時還保持了局部數據庫的獨立性和完整性，對局部私有數據的安全性也起到了保護作用，因此成為近年來多數據庫挖掘的重點研究課題。在文獻[1]中，將多數據庫挖掘的模式分為局部模式(local pattern)#65380;高選票模式(high－vote pattern)#65380;例外模式#65380;推薦模式(suggested pattern)四類。本文研究的是例外模式。所謂多數據庫例外模式，就是那些僅被少數幾個子公司或個別子公司高度支持的模式[1]。通過參考這些例外的模式，總公司可以因地制宜地為少數幾個公司制定適合它們特點的策略。這對于日益激烈的商業競爭來說，是必不可少的舉措。因此多數據庫例外模式也成為一項有重要意義和應用價值的研究工作。到目前為止，文獻[4，5]分別提出了多數據庫中例外模式挖掘的方法，它們為多數據庫模式挖掘提供技術支持。現有的技術方法中存在如下兩個問題:存在冗余的例外模式，降低了模式挖掘的質量;對于挖掘出來的模式，用戶無法辨別它們的例外程度，造成用戶負擔過重。本文為此提出了一種改進的例外模式挖掘方法。

1現有的挖掘技術

多數據庫例外模式是多數據庫模式挖掘中的一種，它首次在文獻[1]中提出并定義。這類模式在個別數據庫里具有較高的支持度而在其他數據庫中具有較低支持度或零支持度(即不被其他數據庫支持)。從該定義中可以知道，局部模式中那些被越少的數據庫支持而在局部數據庫中支持度越高的就有可能成為例外模式。由于本文中的例外模式是從全局的角度考慮(如總公司決策層)，因此也稱為全局例外模式。如不特別說明，本文中的模式指的是頻繁項集。

文獻[4]介紹了一種多數據庫例外模式的挖掘方法和過程。該方法采用了兩極挖掘過程:首先對各個局部數據庫進行挖掘，得到局部模式; 然后將每個子數據庫中局部模式綜合之后再進行分析，從而得到例外模式。 局部模式綜合之后，先統計每個模式的選票數num(P)(即支持該模式的數據庫個數)與所有模式的平均選票率。將每個模式的選票數與平均選票率進行比較，若小于平均選票率，則為候選例外模式并保存。通過計算所有候選例外模式的全局支持度，將所有候選例外模式按照全局支持度的大小排序，最后輸出所有滿足用戶要求的例外模式及來自數據庫的名稱。文獻[5]中，使用了兩個度量即例外模式的全局例外偏離度EPI和局部相對重要度RI，同時滿足專家給定的這兩個最小閾值的為例外模式。其中選票偏離度EPI考慮了模式的選票率與平均選票率的偏離度;局部相對重要度RI考慮了模式在局部數據庫的相對支持率(EPI和RI的計算公式見第2章)。EPI越高，說明越少的數據庫支持，例外可能性越大; RI越大，在支持的數據庫中，模式支持度越高，例外的可能性越大。這兩個度量剛好符合了多數據庫例外模式的定義。文獻[4]中，全局支持度計算用的是模式在各個數據庫中支持度的均值，也就意味著若一個模式被確定為例外模式，則在所有支持它的數據庫中都是例外模式。實際上，挖掘例外模式正是要找出某些數據中真正有趣的對總公司發展起重要作用的少量模式，并不意味著凡是支持它的數據庫都要特別考慮，即造成了模式冗余。而且，兩種模式挖掘方法都沒有考慮到一個問題，即挖掘出來的模式得到的例外模式會出現一個數據庫中有多個例外#65380;一個例外同時在多個數據庫中的情況。對用戶而言，如何看待這種例外模式在全局的地位呢?這并不是無足輕重的問題。 例如，新的子公司經營的是新的領域#65380;新的產品，那么，挖掘該子數據庫中很可能出現多個例外。這種情況下若一視同仁，把大量的資源投資在這個新的部門，勢必會造成決策失誤。因此，需要從總公司的全局角度考慮，對采用上述方法挖掘出來的例外進行進一步的分析，確定例外模式的優先次序。目的就在于將有限的資源用在最有價值的例外模式上，這對于商業競爭來說是很必要也是很重要的。

2改進的多數據庫例外模式挖掘方法

2.1挖掘過程

假設有n個數據庫D1，D2，…，Dn;LP1，LP2，…，LPn為相應的數據庫挖掘出來的局部模式集合;minsup pi為用戶給定的第i個數據庫的最小支持度(i=1，2，…，n);對于任一個模式Pj，它在第i個數據庫中的支持度為sup pi(Pj)。

改進的挖掘方法采用的是文獻[1]提出的新的兩極挖掘思想。首先在各個子數據庫進行局部模式的挖掘，過程如下:

a)各個局部數據庫中滿足用戶或專家設定的最小支持度的頻繁模式首先被挖掘出來，成為局部模式集合。統計各個局部模式的個數NLocal以及所有局部模式個數m。

b)保持各個局部模式集合的獨立性，計算不同局部模式的選票率VR(Pi)以及模式的平均選票數(average voting number，AVN)。其中:選票率VR(Pi)為支持該模式的數據庫個數與所有局部數據庫個數的比值;AVN為所有模式的支持數之和與模式個數的比值，即

d)對各個候選模式使用局部和全局興趣度兩個度量，找出真正的例外。

兩個度量分別是全局例外興趣度EPI和相對興趣度RI。其中，EPI也稱為模式的例外偏離度，是指模式Pi的選票率偏離平均選票率的程度。這是從全局的角度考慮的，所以也稱全局例外興趣度。

EPI(Pi)=[VN(Pi)-AVN]/(-AVN)(3)

因為-AVN

RI指的是模式在支持其數據庫中的興趣程度。因為考慮是在局部數據庫中，也稱為局部例外興趣度。它也是用一個比值表示:

RI(Pj)=[sup pi(Pj)-minsup pi]/(maxsup pi-minsup pi)(4)

其中:sup pi(Pj)表示模式Pj在第i個數據庫中的實際支持度;minsup pi表示第i個數據庫的最小支持度;maxsup pi表示第i個數據庫的最大支持度。注意:若Pj在某個數據庫中不出現，則sup pi(Pj)=0。

式(4)利用了區間值計算，即利用某個模式的支持度與最小支持度的差距作為度量的一個尺度。不同的數據庫有不同的數據信息，當兩個數據庫的最小支持度分別是0.49和0.11時，不能簡單地說一個數據庫中支持度為0.5的模式比另一個數據庫中支持度為0.22的模式的支持度大。因為這兩個數據庫的最小支持度不同，需要將每個模式的支持度與相應的最小支持度比較后再綜合計算。根據這個公式可以獲知某個模式P在某個數據庫dbi的重要性。若RI值越大，則該模式在第i個數據庫中的重要程度越大，這樣的例外也就越有趣。

EPI與RI可以有效地度量從局部到全局兩極模式的興趣度。與僅考慮全局興趣度方法[4]相比，更合理且更有說服力。

e)根據用戶設定的最小閾值minEPI 和minRI， 從各局部數據庫中篩選出滿足這兩個閾值的模式為例外模式，歸并入待定模式集合;同時統計各個局部模式集合中滿足這兩個閾值的例外模式個數m。其次，對由上述過程得到的例外模式集合進行合并，并最后進行匯總分析。在模式匯總后，增加兩個客觀度量EPS和RS。EPS和RS的計算是基于模式本身的統計數據，因此從度量的分類來說，屬于客觀度量[12]。客觀度量的使用對模式的興趣度和重要度評估起到了重要的作用[13]。具體由下面的步驟f)#65380;g)所示。

f)對于匯總后的不同例外模式P1，P2，…，Pm， 計算它們的重要度EPS以確定不同例外的地位。例外模式全局重要度為

EPS(EPi)={EPI(EPi)+[∑kj=1RI(EPi)]/k}/2(5)

其中:EPI(Pi)為模式Pi的選票偏離度;k為支持該模式的數據庫個數，也為模式的選票數;[∑kj=1RI(EPi)]/k為例外模式的全局支持度。為了能進一步度量例外模式的興趣程度，在定義EPS時，同時考慮了模式的選票偏離度以及全局支持度，能更充分地體現例外模式的重要程度。所以，EPS可以有效度量不同例外的重要程度，特別是可以有效解決同一個數據庫中有多個例外時的情形。當用戶得到的是按照EPS值進行降序排列的例外模式序列時，就可以有的放矢地進行分析和決策。

g)對于同一個例外模式在不同數據庫中的重要度，也定義了一個例外模式相對重要度RS。例外模式相對重要度為

其中:numEPdbi為第i個數據庫中例外的個數;numCEPdbi為第i個數據庫中候選例外的個數。兩者的比值為第i個數據庫的權值，用來表示該數據庫在所有數據庫中的例外權重。為了衡量同一個例外模式在不同數據庫中的例外程度，RS同時考慮了模式的相對支持度RI#65380;數據庫中例外的個數以及數據庫的權重因子。同樣對RS值按降序排序，將排序結果輸出給用戶，用戶可以有效地決定哪些例外才是真正有趣的例外。

改進的挖掘方法與已有的方法區別之處在于:

a)不是直接將局部模式綜合起來馬上進行全局挖掘，而是全局分析時依然保持各個局部數據庫的局部模式的完整性，在得到了例外模式集合后才將所有例外模式集合合并。同時考慮了局部數據庫的權重，依據例外模式的比重決定各個數據庫的不同權值，而不是一視同仁。這樣更符合實際情況。

b)從局部和全局兩個角度考慮模式的興趣度和重要度，既剔除了非真正有趣的例外，也解決了同一個數據庫中不同例外以及不同例外處于同一個數據庫中的例外重要度計算。

c)輸出給用戶的不是一堆無區別的模式集合，而是經過了重要度排序的模式序列，給出了例外模式的優劣之分，解決了用戶無法輕易識別出哪些才是真正有趣的例外難題。

為何D的重要度最大呢? 可以從上述數據中看出，由于D只有一個數據庫支持，并且在支持的數據庫中相對支持度較高，而其他例外具有兩個或兩個以上數據庫支持，并且相對支持度也沒有明顯優勢。G的重要度為何比H高呢?G和H都是只有兩個數據庫支持，但是G在支持的數據庫中支持度均相對比H的高，如G在db4中為最大支持度0.5。這也可以很好地解釋G的重要度要高于H;而且對于同一個DB中的G和E， 由于G的支持度要大于E，G 的重要度也大于E。 同理，也可以解釋序列中其他模式的重要度排序。

對于同一個模式在不同DB中的重要度，模式G 在db2#65380;db4中均為例外，那么在哪一個中更重要呢?計算它們的例外模式相對重要度:

即RSdb4(G)> RSdb2(G)。說明首先考慮db4中的G例外。上面的數據表明，由于db2中例外有三個，候選例外有四個，并且G在db2中的支持度相對并不突出，而在db4中只有兩個例外并且G的支持度為最高支持度，db4中的G相對重要。這也與計算的結果相呼應。

上述例子說明本文方法是準確有效的，是直接服務于用戶的，是多數據庫例外模式挖掘過程中重要的一步。增加的兩個度量看似后挖掘的模式評價，但在本文中特地將模式的進一步分析和評價融入數據挖掘階段。因為這樣做可以提高模式挖掘的質量，縮短知識發現的過程[14，15]。

3實驗和結果分析

MDBExcePMining算法用VC++ 6.0實現，在內存為2 GB#65380;CPU主頻為2.6 GHz#65380;操作系統為Windows 2000的Dell Workstation PWS650計算機上進行實驗。實驗的目的不是要評價算法的運行速度，而是與現有的挖掘算法相比，改進的算法能否更有效地發現例外以及能否有效度量例外。對真實數據集zoo database[16]進行了實驗，該數據集共有101個實例，7個大類，18個屬性域。為了獲得多個相關的數據庫，將該數據庫按照類別屬性垂直劃分成7類數據集。由于zoo database是一個小型數據集，選擇了其中3個最大的類來進行試驗，每類數據集平均分成若干個子數據集。預處理時，使用不同的數字代表不同的屬性值使之易于用程序實現。預處理后，挖掘每類數據集得到相應的頻繁集。數據集中共有101個實例，具體劃分后，表1顯示了3個類數據集的相關信息。由于數據集的真實特性，為提高算法的效率#65380;減少不必要的時間損耗，選取了11個存在差異的屬性作為屬性集合，而且頻繁集取屬性域中那些與其他同類中非一致的屬性。模式取不同的屬性特征，屬性特征的相異個數為支持度。這個實驗中低選票模式的平均選票數C1: AVN=2.25， C2:ANV=3.3。

表2給出了挖掘出的部分典型例外模式及它們的rank情況。

從表2中可以看到:先是屬性特征例外挖掘，當屬性特征例外集合起來，就是例外動物樣本挖掘了，即得到的例外是那些在數據集中不同于眾的動物。例如哺乳類別數據集中的dolphin，就由于其屬性特征的不同于眾，無毛發#65380;水里生活#65380;無腳以及有翅這四個不同于其他哺乳類動物的特征，是La1中特有的，因而成為一個例外。同樣，C2類數據集Lb1中的ostrich#65380;Lb2中的penguin#65380;C3類數據集Lc1中的carp等都是由于其特征例外而成為特殊動物。限于篇幅，結果中沒有列出所有的例外模式以及那些在局部例外而全局非例外的模式。從該結果可以看出，本文的方法是合理而有效的。

4 結束語

本文針對現有多數據庫例外挖掘中存在的不足，提出了進一步的改進，同時采用局部和全局興趣度#65380;重要度對例外模式進行有效的度量，既剔除了冗余例外，又提高了模式質量，還減少了用戶負擔。實驗證明，改進的挖掘方法是現有例外模式挖掘方法的改進和完善。

參考文獻:

[1]ZHANG Shi－chao，WU Xin－dong， ZHANG Cheng－qi.Multi－database mining [J].IEEE Computational Intelligence Bulletin，2003，2(1):5－13.

[2]ZHANG Shi－chao，ZHANG Cheng－qi，WU Xin－dong.Knowledge discovery in multiple databases[M]. London: Springer Press，2004.

[3]WU Xin－dong， ZHANG Shi－chao. Synthesizing high－frequency rules from different data sources[J].IEEE Trans on Knowledge and Data Engineering，2003，15(2):353－367.

[4]ZHANG Shi－chao，ZHANG Cheng－qi，YU J X.An efficient strategy for mining exceptions in multi－databases[J].Information System，2004，165(1－2):1－20.

[5]ZHANG Cheng－qi， LIU Mei－ling， NIE Wen－long， et al.Identifying global exceptional patterns in multi－database mining[J].IEEE Computational Intelligence Bulletin，2004，3(1):19－24.

[6]ZHANG Cheng－qi，ZHANG Shi－chao.Database clustering for mining multi－databases[C]//Proc of the 11th IEEE International Conference on Fuzzy Systems. 2002:974－979.

[7]WROBEL S.An algorithm for multi－relational discovery of subgroups[C]//Proc of the 1st European Symposium on Principles of Data Mining and Knowledge Discovery. London: Springer－Verlag， 1997:367－375.

[8]LIU Huan，LU Hong－jun，YAO Jun.Identifying relevant databases for multi－database mining[C]//Proc of Pacific－Asia Conference on Knowledge Discovery and Data.1998:210－221.

[9]YAO Jun， LIU Huan.Searching multiple databases for interesting complexes[C]//Proc of Pacific－Asia Conference on Knowledge Discovery and Data Mining. 1997:198－210.

[10]ZHONG Ning，YAO Yi－yu，OHSUGA S.Peculiarity oriented multi－database mining[C]//Proc of Pacific－Asia Conference on Knowledge Discovery and Data Mining. 1999:136－146.

[11]ARONIS J， KOLLURI V， PROVOST F， et al.The WoRLD: know－ledge discovery from multiple distributed databases[C]//Proc of the 10th International Florida AI Research Symposium. 1997:337－341.

[12]BHATNAGAR V， HEGMI A S，KUMAR N. Novelty as a measure of interestingness in knowledge discovery[J].International Journal of Information Technology，2005，2(1):36－41.

[13]HUSSAIN F，LIU H，SUZUKI E，et al.Exception rule mining with a relative interestingness measure[C]//Proc of Pacific－Asia Conference on Knowledge Discovery and Data Mining. 2000:86－97.

[14]ZHANG Shi－chao， ZHANG Cheng－qi，YAN Xiao－wei.Post－mining: maintenance of association rules by weighting [J].Information Systems，2003，28(7):691－707.

[15]FAYYAD U M， PIATESKY－SHAPIRO G，SMYTH P，et al.Advances in knowledge discovery and data mining [M]. Cambridge: AAAI/MIT Press，1996.

[16]Collections of datasets UCI[EB/OL].http://www.cs.waikato.ac.nz/ml/weka.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”