基于半靜態(tài)分層抽樣的模糊聚類分析方法的改進(jìn)

謝笑盈

（浙江工商大學(xué) 統(tǒng)計(jì)學(xué)院，杭州 310018）

0 引言

聚類分析是根據(jù)某種相似性度量將數(shù)據(jù)劃分成有意義或有用的組，對聚類的研究源于對相似度的研究。隨著研究的深入，聚類從最初的簡單的數(shù)值型（包括離散的和連續(xù)的）數(shù)據(jù)以及邏輯型數(shù)據(jù)的聚類發(fā)展到對復(fù)雜的事務(wù)數(shù)據(jù)庫的聚類，這其中對相似性的定義也發(fā)生了巨大的變化。在對數(shù)據(jù)對象分組過程中，其目標(biāo)是組內(nèi)的對象相互之間是相似的（相關(guān)的），而不同組中的對象是不同的（不相關(guān)的）。通常，組內(nèi)的相似性越大，組間的差別越大，聚類效果越好。經(jīng)常地，我們把組也稱為簇。主要的聚類分析方法有劃分方法、層次方法、基于密度的方法、基于模糊的方法等。本文將要討論的是基于模糊的方法。

1 基于模糊的聚類方法

當(dāng)數(shù)據(jù)集中的數(shù)據(jù)分布在明顯分離的組中時(shí)，利用聚類算法，可以將數(shù)據(jù)對象明確地分到不相交的簇中，即，一個(gè)對象的所屬的簇是非此即彼的。但在很多情況下，數(shù)據(jù)集中的對象不能劃分成明顯分離的簇，一個(gè)對象即可以劃分到A簇，也可以劃分到B簇，但可能離A簇稍微近一些，此時(shí)最好的解決辦法是為該對象劃分到A簇或B簇設(shè)置一個(gè)權(quán)值，指明該對象屬于該簇的程度，即對象Xi以Wij的可能性屬于Cj類。設(shè)置權(quán)值的方法可以用概率統(tǒng)計(jì)的方法，也可用模糊集理論的方法。基于統(tǒng)計(jì)模型的模糊聚類[1]就是利用概率統(tǒng)計(jì)為對象設(shè)置權(quán)值的一種方法。該方法假定數(shù)據(jù)是由一個(gè)統(tǒng)計(jì)過程產(chǎn)生的，并且通過找出擬合數(shù)據(jù)最佳的統(tǒng)計(jì)模型來描述數(shù)據(jù)，其中，統(tǒng)計(jì)模型用分布和該分布的一組參數(shù)來描述。更具體地說，就是可以把每個(gè)簇用一個(gè)合適的分布來表示，那么不同分布的對象自然要在聚類后被分開來，比較成熟的基于統(tǒng)計(jì)模型的模糊聚類方法是期望最大化（EM，expectation maximization)算法，它對參數(shù)做初始的猜測，然后通過迭代改進(jìn)這些估計(jì)，直到參數(shù)不再改變?yōu)橹埂Ｒ蛊谕畲蠡尚校仨氈栏鱾€(gè)簇是滿足什么分布，理論上應(yīng)該首先考察各個(gè)對象所在簇的分布。但根據(jù)大量的統(tǒng)計(jì)事實(shí)，我們通常假定連續(xù)型數(shù)據(jù)對象是符合多元正態(tài)分布的，而離散型數(shù)據(jù)對象則多假定其滿足泊松分布或二項(xiàng)分布。下面是對EM算法進(jìn)行一定改進(jìn)后的簡要步驟：

(1)用DBSCAN[2]基于中心的聚類掃描一遍數(shù)據(jù)庫，快速剔除離群點(diǎn)；

(2)為模糊聚類選擇合適的統(tǒng)計(jì)分布組(比如一系列均值不相同的多元正態(tài)分布)；

(3)選擇模型參數(shù)的初始集合（比如多元正態(tài)分布中均值和方差）;

(4)對于每個(gè)數(shù)據(jù)對象，計(jì)算該對象屬于每個(gè)分布的概率（貝葉斯公式）;

(5)得到（3）中所有數(shù)據(jù)對象的聯(lián)合概率密度函數(shù)，并對其用最大似然法求出新的參數(shù)估計(jì)，更新（2）中的模型參數(shù)集;

(6)重復(fù)（3）、（4）、（5），直到參數(shù)不再改變?yōu)橹埂?/p>

EM算法利用各種類型的分布，可以發(fā)現(xiàn)不同大小和不同形狀的簇，而且使聚類結(jié)果有很好的統(tǒng)計(jì)性質(zhì)，這對于描述和理解數(shù)據(jù)都是非常有利的。但另一方面，因?yàn)镋M涉及到復(fù)雜的運(yùn)算，所有當(dāng)對象的屬性個(gè)數(shù)很多時(shí)，計(jì)算一個(gè)如此復(fù)雜的密度函數(shù)的最大似然值是不切實(shí)際的；另外，當(dāng)簇只包含少量數(shù)據(jù)點(diǎn)，或者數(shù)據(jù)點(diǎn)之間有線性關(guān)系時(shí)，用該方法也不適合。最后，對于離群點(diǎn)和噪聲，該方法也存在問題，上述部分改進(jìn)后的EM算法克服了最后一個(gè)缺點(diǎn)，剔除了離群點(diǎn)和噪聲，對另外兩個(gè)缺點(diǎn)的改進(jìn)將在后文中提出。

2 數(shù)據(jù)挖掘中的抽樣技術(shù)

數(shù)據(jù)挖掘中應(yīng)用的抽樣技術(shù)主要來源于統(tǒng)計(jì)學(xué)中的抽樣技術(shù)，但因使用目的和使用方式的區(qū)別，通常將數(shù)據(jù)挖掘中的抽樣技術(shù)分為兩類[3],即：靜態(tài)抽樣和動態(tài)抽樣。靜態(tài)抽樣也稱一階段抽樣或一次性抽樣,是根據(jù)預(yù)先估計(jì)的誤差范圍、可靠性等計(jì)算一個(gè)固定的樣本量,所有的后續(xù)分析只依據(jù)這一次性抽取的樣本。該抽樣方式一般在數(shù)據(jù)挖掘算法執(zhí)行之前進(jìn)行,適合各類挖掘任務(wù)的運(yùn)用。數(shù)據(jù)挖掘的靜態(tài)抽樣方式都來自于統(tǒng)計(jì)抽樣調(diào)查領(lǐng)域,主要有簡單隨機(jī)抽樣、分層抽樣、整群抽樣。其中，簡單抽樣應(yīng)用最廣，分層抽樣在分類問題中運(yùn)用普遍，整群抽樣在聚類時(shí)運(yùn)用較多。比如,Heikki Mannila 等(1994)、Hannu Toivonen(1996)、M.Zakiand S.Parthasarathy(1997)、Einoshin Suzuki(2005), 都 運(yùn) 用 一 次 性抽樣方式挖掘了關(guān)聯(lián)規(guī)則。靜態(tài)抽樣是從統(tǒng)計(jì)學(xué)的角度靜態(tài)地判斷樣本與總體的近似程度。優(yōu)點(diǎn)是實(shí)施比較方便。缺陷在于沒有與挖掘工具結(jié)合起來,不能明智地回答樣本是否足夠好。

動態(tài)抽樣指需要經(jīng)過兩次或更多次抽樣才能達(dá)到最終要求的抽樣方法,抽樣過程與算法的執(zhí)行過程和推斷是交互進(jìn)行的。它直接利用挖掘工具,能及時(shí)提供樣本與總體接近程度的信息,而不是間接地考慮樣本的統(tǒng)計(jì)特性。在該抽樣方式下,決策者能夠在算法效率和模型正確性之間及時(shí)做出抉擇。數(shù)據(jù)挖掘中常用的動態(tài)抽樣技術(shù)有累進(jìn)抽樣和序貫抽樣，它們都可以稱為適應(yīng)性(adaptive)抽樣。序貫抽樣是數(shù)據(jù)挖掘中最早使用的適應(yīng)性抽樣方法,主要用于關(guān)聯(lián)規(guī)則挖掘[4]和聚類分析。

Baohua Gu等在[5]介紹了一種獨(dú)立于具體算法得最優(yōu)樣本容量的確定方法法，這個(gè)方法可歸類于上文所提的靜態(tài)抽樣：用S.Kullback[6]的信息理論來描述抽樣樣本與總體數(shù)據(jù)集之間的信息差異Di，給Di和樣本容量n做回歸分析，當(dāng)回歸曲線的斜率接近于1時(shí)，說明樣本容量n已達(dá)到了最優(yōu)（OSS），此時(shí)的n即為最優(yōu)樣本容量OSS。結(jié)合該方法，本文使用下列算法來計(jì)算最優(yōu)樣本容量OSS：

(1)輸入數(shù)據(jù)集D,其中包含N個(gè)實(shí)例；

(2)隨機(jī)產(chǎn)生n個(gè)樣本容量跨度在[1,N]區(qū)域中的樣本Si,(i=1..n)，[Si]表示樣本 Si的樣本容量并且滿足/Si+1/=10*/Si/（i=1…n）；

(3)計(jì)算每個(gè)樣本Si在數(shù)據(jù)集D中的樣本質(zhì)量Qi；

(4)根據(jù)點(diǎn)(Si,Qi)的坐標(biāo)擬合出一條樣本容量和質(zhì)量的曲線；

(5)輸出 SOSS。

其中樣本質(zhì)量Qi的計(jì)算公式為為每個(gè)樣本表示該數(shù)據(jù)集的屬性個(gè)數(shù)，的每個(gè)樣本的第i個(gè)屬性有c種不同的取值，t表示總體，s表示樣本，ptj表示總體中第i個(gè)屬性的第j個(gè)取值的概率，psj表示樣本中第i個(gè)屬性的第j個(gè)取值的概率。

3 引入抽樣技術(shù)后的改進(jìn)的模糊聚類分析方法

在模糊聚類中運(yùn)用抽樣技術(shù)，通常的做法，是設(shè)計(jì)合適的抽樣方案，提取一個(gè)樣本，對樣本中的點(diǎn)進(jìn)行聚類；然后將其余的點(diǎn)指派到已有的離其最近的簇中。在抽樣中，最可能犯的錯(cuò)誤是因?yàn)槌闃佣鴣G失比較小的簇。當(dāng)然，如果丟失的是噪聲，就無所謂了。

在設(shè)計(jì)抽樣方案時(shí)，為了使抽取的樣本最大可能地反映總體的信息，本文結(jié)合靜態(tài)抽樣和動態(tài)抽樣的優(yōu)點(diǎn)，在參考最優(yōu)樣本統(tǒng)計(jì)量的基礎(chǔ)上設(shè)計(jì)一種半靜態(tài)抽樣方法，具體算法如下：

(1)通過主成分分析或信息增益計(jì)算找到與挖掘任務(wù)關(guān)系最緊密的屬性A，若用主成分計(jì)算時(shí)，A是第一主成分中系數(shù)最大的那個(gè)屬性；若用信息增益計(jì)算時(shí)，A是使信息增益最大的屬性（在數(shù)據(jù)量極大時(shí)，可用原數(shù)據(jù)集的一個(gè)隨機(jī)樣本來計(jì)算屬性A，實(shí)驗(yàn)證明代表性較好）；

(2)按 A 的值（a1,a2,…，an）對原數(shù)據(jù)集進(jìn)行分組，各組的樣本個(gè)數(shù)分別為N1,N2,…，Nn;

(3)計(jì)算最優(yōu)樣本容量OSS（前文已提）；

(4)給每個(gè)組分配樣本個(gè)數(shù)Si=OSSNi/N，得到最終的抽樣樣本

(5)在S上進(jìn)行挖掘算法的挖掘。

該算法通過計(jì)算最具代表性的屬性A，達(dá)到對數(shù)據(jù)集分層的目的，若選取主成分法尋找屬性A時(shí)，可以克服屬性間的線性相關(guān)問題。另外在選擇了最優(yōu)樣本容量的基礎(chǔ)上，通過對數(shù)據(jù)集的分層抽樣增加了樣本的代表性，使得抽樣樣本的特性最大可能地接近總體特性。

為了提高聚類的效率，我們還引進(jìn)維歸約的思想來加快聚類的速度。在高維數(shù)據(jù)集中（現(xiàn)實(shí)中的數(shù)據(jù)集大多是有十幾個(gè)，幾十個(gè)甚至上百個(gè)屬性的高維數(shù)據(jù)集），考察對象鄰近度的傳統(tǒng)的歐幾里得距離等概念變得不再適合。因?yàn)殡S著維數(shù)的增加，數(shù)據(jù)集構(gòu)成的體積迅速增加（半徑為r，維數(shù)為d的超球的體積正比于rd。），若數(shù)據(jù)集中點(diǎn)的個(gè)數(shù)很少，則其密度將趨向于0，那么各個(gè)數(shù)據(jù)子集的基于密度的鄰近度度量將趨于一致，此時(shí)基于密度的聚類算法將不再適用。如果一個(gè)數(shù)據(jù)集的某一個(gè)子集擁有與之相同的簇的話，那么對該數(shù)據(jù)集維規(guī)約后的子集進(jìn)行聚類就可以得到簇，當(dāng)然這里的前提條件是重要的：數(shù)據(jù)集的聚類信息集中在少量幾個(gè)屬性上，其余屬性是隨機(jī)分布的。而要判斷一個(gè)數(shù)據(jù)集是否滿足這一條件并不是太困難的事情，只需對各個(gè)屬性進(jìn)行統(tǒng)計(jì)分析和信息分析就可以得出結(jié)果。將上述思想結(jié)合后得到引入抽樣后的基于統(tǒng)計(jì)模型的模糊聚類的一個(gè)改進(jìn)如下：

(1)對數(shù)據(jù)集進(jìn)行統(tǒng)計(jì)或信息分析，剔除不必要的屬性；

(2)對該數(shù)據(jù)集進(jìn)行異常點(diǎn)的剔除；

(3)運(yùn)用半靜態(tài)抽樣算法計(jì)算出樣本集合S；

(4)對樣本集S進(jìn)行基于改進(jìn)的統(tǒng)計(jì)模型的模糊聚類EM進(jìn)行分析；

(5)對聚類結(jié)果進(jìn)行評估。

4 實(shí)證分析

結(jié)合上述分析，選用UCI數(shù)據(jù)庫中人口調(diào)查數(shù)據(jù)集為例，該數(shù)據(jù)集有32561條記錄，將抽樣方法引入EM模糊聚類，做出分析見表1。

表1

從表1中可以清楚地看出EM算法因?yàn)橐?jì)算涉及所有屬性的似然函數(shù)，并由此計(jì)算各個(gè)參數(shù)的值，所以運(yùn)行速度非常慢，這也從事實(shí)上印證了前文對EM算法缺點(diǎn)的討論：當(dāng)涉及的屬性個(gè)數(shù)較多，或數(shù)據(jù)集的記錄條數(shù)很多時(shí)，EM的計(jì)算是不可行的。通過對屬性的刪減，可以減少部分運(yùn)行時(shí)間，但聚類的結(jié)果有較大的不同，這說明在原數(shù)據(jù)集和它的子集上發(fā)現(xiàn)的感興趣的簇可能是不一樣的，這可能是因?yàn)樘蕹膶傩灾杏杏绊懘貍€(gè)數(shù)的因子存在。另外，刪減屬性使得聚類結(jié)果在似然值上也發(fā)生了較大的改變，涉及的屬性個(gè)數(shù)越少，似然值越大。

從抽樣的結(jié)果看，無論在原數(shù)據(jù)集上的抽樣還是在刪除屬性后子集上的抽樣，都大大減少了聚類的時(shí)間，而且抽樣并不影響結(jié)果中簇的個(gè)數(shù)，似然值也變化甚微。這說明抽樣技術(shù)的應(yīng)用在提高聚類效率的同時(shí)，還能保證聚類結(jié)果的一致性，是解決高數(shù)量級的數(shù)據(jù)集運(yùn)算不可行的好辦法。

5 結(jié)束語

雖然有學(xué)者提出在超大型的數(shù)據(jù)集上應(yīng)用增量算法或分塊處理來提高數(shù)據(jù)挖掘的效率可能比用抽樣技術(shù)更有效，但在本文的實(shí)踐過程中發(fā)現(xiàn)，對于中等數(shù)量級（幾萬到幾十萬數(shù)量級）的數(shù)據(jù)集，抽樣技術(shù)有著其他技術(shù)不可比擬的優(yōu)勢——速度快，準(zhǔn)確性高，易實(shí)現(xiàn)，特別是對于總體數(shù)據(jù)集有較好的統(tǒng)計(jì)特性時(shí)。今后，筆者將繼續(xù)致力于研究統(tǒng)計(jì)方法與挖掘技術(shù)的結(jié)合。

[1]F.Hoppner,F.Klawonn,et al.Fuzzy Cluster Analysis:Methods for Classification,Data Analysis and Image Recognition[M].New York:John Wiley,1999.

[2]M.Ester.,H.P.Kriegel.,J.Sander.A Density Based Algorithm for Discovrerying Clusters in Large Spatial Databases with Noise[C].In Proc of the 2nd.Knowledge Discovery and Data Mining,1996.

[3]朱梅紅.數(shù)據(jù)挖掘中抽樣技術(shù)的應(yīng)用[J].統(tǒng)計(jì)與決策，2007，(8).

[4]Tobias Scheffer,Stefan Wrobel.Finding the Most Interesting Patterns in a Database Quickly by Using Sequential Sampling[J].The Journal of Machine Learning，2000,8.

[5]Baohua Gu,Bing Liu,Feifang Hu,Huan Liu.Efficiently Determine the Starting Sample Size for Progressive Sampling[J].Lecture Notes in Computer Scierce,2001,2167.

[6]S.Kullback.Information Theory and Statistics[M].Chichester:John Wiley and Sons,1987.