聚類集成中基聚類的優(yōu)化研究

程 凱 鐘才明 龐永明

1(寧波大學(xué)信息科學(xué)與工程學(xué)院 浙江 寧波 315210)2(寧波大學(xué)科學(xué)技術(shù)學(xué)院信息工程學(xué)院 浙江 寧波 315210)

聚類集成中基聚類的優(yōu)化研究

程 凱1鐘才明2龐永明1

1(寧波大學(xué)信息科學(xué)與工程學(xué)院 浙江 寧波 315210)2(寧波大學(xué)科學(xué)技術(shù)學(xué)院信息工程學(xué)院 浙江 寧波 315210)

聚類集成是將一個(gè)數(shù)據(jù)集的多個(gè)劃分(基聚類)合成一個(gè)新的聚類，該聚類最大程度地代表了所有輸入基聚類對數(shù)據(jù)集的聚類信息。顯而易見，初始基聚類的質(zhì)量對于最終的集成劃分至關(guān)重要。傳統(tǒng)的聚類集成中的基聚類器使用最多的是K-means，因?yàn)镵-means不僅實(shí)現(xiàn)簡單，計(jì)算復(fù)雜度不高，而且其聚類機(jī)制符合機(jī)器學(xué)習(xí)關(guān)于局部數(shù)據(jù)的類別條件概率為常數(shù)的假設(shè)。但由于K-means通常直接使用高斯距離作為距離測度，其只能發(fā)現(xiàn)球形簇的類；而對于具有結(jié)構(gòu)復(fù)雜、尤其是基于連接性且非球形分布的類結(jié)構(gòu)的數(shù)據(jù)集，不能生成高質(zhì)量(即同質(zhì)性高)的基聚類。為此提出一個(gè)基聚類的優(yōu)化方法，即：判定K-means所生成類的同質(zhì)性，對同質(zhì)性較差的類進(jìn)行再次劃分，以提高基聚類的同質(zhì)性，從而提高整個(gè)聚類集成的質(zhì)量。在8個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)數(shù)據(jù)表明所提出的方法是有效的。

聚類集成 K-means 基聚類 同質(zhì)性 偽高斯

0 引 言

采聚類分析已經(jīng)成為模式識別、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘研究領(lǐng)域的一個(gè)非常活躍的研究課題，在識別數(shù)據(jù)的內(nèi)在結(jié)構(gòu)方面具有極其重要的作用。根據(jù)數(shù)據(jù)在類中的聚集規(guī)則以及應(yīng)用這些規(guī)則的方法，有多種聚類算法[1-2]。但是沒有一種聚類算法能準(zhǔn)確揭示各種數(shù)據(jù)集內(nèi)部所呈現(xiàn)出來的多種多樣的簇結(jié)構(gòu)[3]。所以聚類集成成為了另一個(gè)重要且有效的手段，它對原始數(shù)據(jù)集的多個(gè)聚類結(jié)果進(jìn)行學(xué)習(xí)和集成，得到一個(gè)能較好地反映數(shù)據(jù)集內(nèi)在結(jié)構(gòu)的數(shù)據(jù)劃分。

聚類集成可以這樣描述：給定一個(gè)聚類結(jié)果集合, 聚類集成的目標(biāo)就是要尋找一個(gè)聚類, 使其相對于所有的輸入聚類結(jié)果來說，盡可能多地符合(或一致)[4]。聚類集成的方法有兩個(gè)步驟:對原始數(shù)據(jù)進(jìn)行不同的基聚類和合并基聚類生成最終的劃分[5](如圖1所示)。

圖1 聚類集成的一般過程

聚類集成的第一步是生成基聚類。通常在集成學(xué)習(xí)中，集群的差異度被認(rèn)為是影響集成結(jié)果的關(guān)鍵因素之一[6]，所以這一階段需要產(chǎn)生多個(gè)具有差異度的基聚類結(jié)果，差異從不同的方面反映數(shù)據(jù)集的結(jié)構(gòu)，有利于集成。這一階段是對數(shù)據(jù)集或其子集反復(fù)運(yùn)行聚類算法，有以下幾種方法：

(1) 使用一個(gè)聚類算法，每次運(yùn)行都設(shè)置不同的參數(shù)和隨機(jī)初始化[7]；

(2) 使用不同的聚類算法，如K-means、SL(Single-Linkage)、CL(Complete-Linkage)，AL(Average-Linkage)等產(chǎn)生多個(gè)不同的聚類[7]；

(3) 將數(shù)據(jù)集的特征空間投影到數(shù)據(jù)子空間，有隨機(jī)投影和一維投影等手段[7，9]；

(4) 對數(shù)據(jù)集的子集進(jìn)行聚類，子集可通過采樣如Sub-sampling，Bagging，Bootstrap和隨機(jī)采樣等方法獲得[7，10-12]。

聚類集成的第二步是合并基聚類，得到一個(gè)統(tǒng)一的聚類結(jié)果。目前存在許多合并基聚類的方法，如投票法[7]、超圖劃分[6]、基于有效性指標(biāo)的集成方法[8]。

本文主要是針對聚類集成第一步中基聚類的質(zhì)量提出了一種優(yōu)化方法，即判定基聚類中每個(gè)類的同質(zhì)性，對同質(zhì)性較低的類進(jìn)行二次處理，以提高基聚類的同質(zhì)性，生成高質(zhì)量的基聚類。

目前大多數(shù)聚類集成中基聚類采用的方法是K-means，因?yàn)榧芍行枰^多的基聚類，而K-means實(shí)現(xiàn)簡單，計(jì)算復(fù)雜度不高，執(zhí)行速度快[13]。但K-means適宜發(fā)現(xiàn)球形簇的數(shù)據(jù)集，對于結(jié)構(gòu)復(fù)雜的數(shù)據(jù)集，尤其是邊界不易區(qū)分、非球形分布以及高維數(shù)據(jù)，不能產(chǎn)生較好的聚類結(jié)果，所以它生成基聚類還是有缺陷[14]。

(a) 存在偽高斯的基聚類 (b) 理想的基聚類圖2 同一數(shù)據(jù)集不同的基聚類結(jié)果

本文提出的基聚類算法大致流程如圖3所示。為了生成多個(gè)具有差異度的基聚類，采用聚類集成中常用的基聚類方法K-means進(jìn)行多次聚類。每一個(gè)基聚類結(jié)果都是由K-means劃分成的多個(gè)小高斯簇組成，其中有一些高斯簇并不是一個(gè)真實(shí)的高斯，而是由若干個(gè)更小的高斯簇組成。對于基聚類中的每個(gè)高斯簇，分別計(jì)算它的覆蓋率。覆蓋率是反映高斯簇同質(zhì)性高低的一個(gè)重要指標(biāo)，通過它可以找出同質(zhì)性較低的高斯簇，即偽高斯。對于找出的偽高斯，并不知道它是何種結(jié)構(gòu)，所以分別采用K-means和SL對其進(jìn)行二分，選擇其中較好的一種處理結(jié)果作為優(yōu)化后的基聚類結(jié)果。對基聚類中的每一個(gè)偽高斯都作如上處理，生成最終高質(zhì)量的基聚類。

圖3 本文方法實(shí)現(xiàn)的示意圖

1 偽高斯的判別

對于每一個(gè)高斯簇，可以利用它的均值Mu和協(xié)方差矩陣Sigma生成一個(gè)標(biāo)準(zhǔn)的高斯分布。將生成的高斯覆蓋在原來的高斯上，觀察覆蓋情況，會發(fā)現(xiàn)對于偽高斯，它的結(jié)構(gòu)、形狀和生成的標(biāo)準(zhǔn)高斯差異太大，所以重合的部分較少，即覆蓋率低(如圖4(a)所示)；而對于真實(shí)高斯，通過它生成的也是一個(gè)標(biāo)準(zhǔn)的高斯，他們的形狀、結(jié)構(gòu)差異不大，重合的部分較多，即覆蓋率高(如圖4(b)所示)。

(a) 偽高斯 (b) 真實(shí)高斯圖4 不同高斯簇的覆蓋情況

對于覆蓋率的概念，也可以使用密度的概念來描述。對一個(gè)數(shù)據(jù)集，數(shù)據(jù)點(diǎn)分布密集的區(qū)域，密度較高，數(shù)據(jù)點(diǎn)分布稀疏的區(qū)域，密度較低。對圖4中的兩個(gè)數(shù)據(jù)集，生成相應(yīng)的密度估計(jì)圖(如圖5所示)。圖5(a)中，偽高斯的密度曲線有兩個(gè)波峰，而生成的標(biāo)準(zhǔn)高斯只有一個(gè)波峰，且與偽高斯的波峰所在位置完全不一樣。根據(jù)生成的標(biāo)準(zhǔn)高斯中每個(gè)點(diǎn)在兩個(gè)密度曲線中的密度計(jì)算差值，找出覆蓋的點(diǎn)，可以得到同樣的結(jié)論：重合部分較少，覆蓋率低。相反，對于圖5(b)，原本的高斯與生成的標(biāo)準(zhǔn)高斯所描繪的密度曲線都有一個(gè)波峰且位置幾乎相同，根據(jù)密度差值計(jì)算出大部分點(diǎn)都是覆蓋的點(diǎn)，重合的部分較多，覆蓋率高。

(a) 偽高斯 (b) 真實(shí)高斯圖5 不同高斯簇的密度分布情況

判別偽高斯的具體方法是，對于每一個(gè)高斯簇，定義這個(gè)集合為X_Old={xi,xi+1,…,xj}，集合中點(diǎn)的個(gè)數(shù)為Num，利用集合X_Old的均值Mu和協(xié)方差矩陣Sigma生成標(biāo)準(zhǔn)的高斯分布數(shù)據(jù)集X_New={xm,xm+1,…,xn}。

對于X_New中的每一個(gè)點(diǎn)xm，采用最近鄰算法，找到X_Old中距離xm最近的一個(gè)點(diǎn)xi，并計(jì)算出它們的歐式距離Dism，即

Dism=min{dis(xm,xi)xm∈X_New,xi∈X_Old}

(1)

這里會設(shè)定一個(gè)距離閾值delta，對X_New中每一個(gè)點(diǎn)，當(dāng)Dism小于delta，便認(rèn)為該點(diǎn)是覆蓋在原來高斯上的點(diǎn)，加入到集合X_Cover中:

X_Cover={xkxk∈X_New,Disk

(2)

delta的計(jì)算如下：顯而易見，對于偽高斯(如圖4(a)所示)，Dism的波動(dòng)幅度較大，而對于非偽高斯(如圖4(b)所示)，Dism的波動(dòng)幅度較小，因此可以對基聚類的每一個(gè)集合求方差Var={Var1,Var2,…,VarK}，并作歸一化處理：

Vari=(Vari-Varmin)/(Varmax-Varmin)

(3)

Vari作為參數(shù)delta的影響因子，這里delta定義如下:

(4)

其中Dis_ave=Dism/Num，即最小距離Dism的均值。

經(jīng)過上面的處理會得到集合X_Cover，集合中點(diǎn)的個(gè)數(shù)為Num_Cover，集合中所有的點(diǎn)都覆蓋在原來高斯上。這樣便可以計(jì)算出每個(gè)高斯的覆蓋率:

ratio=Num_Cover/Num

(5)

其中，這里需要設(shè)定一個(gè)覆蓋率閾值beta=0.75，具體beta的大小將在實(shí)驗(yàn)階段進(jìn)行討論。當(dāng)ratio小于閾值時(shí)，便可以判斷該高斯為偽高斯。這樣就通過基于距離計(jì)算覆蓋率的方法，找出了偽高斯。具體算法流程見算法1。

算法1

步驟1使用K-means基聚類得到K個(gè)類；

步驟2根據(jù)每一個(gè)類X_Old的均值Mu和協(xié)方差矩陣Sigma生成標(biāo)準(zhǔn)高斯X_New；

步驟3對X_New中每一個(gè)點(diǎn)，計(jì)算X_Old中距離它最近點(diǎn)的歐式距離Dism；

步驟4通過距離閾值delta篩選出X_New中覆蓋在原來集合X_Old上的點(diǎn)，加入到集合X_Cover中；

步驟5利用X_Cover中點(diǎn)的個(gè)數(shù)Num_Cover和X_New中點(diǎn)的個(gè)數(shù)Num_Cover，計(jì)算每個(gè)類的覆蓋率ratio，并與閾值beta作比較，判斷該類是否為偽高斯。

2 偽高斯的精化

由于基聚類是由K-means劃分成的多個(gè)小高斯簇組成，高斯簇的個(gè)數(shù)較多，每個(gè)高斯簇的點(diǎn)較少，高斯簇的結(jié)構(gòu)比較簡單，所以偽高斯的結(jié)構(gòu)也比較簡單。一般具有兩種結(jié)構(gòu)：高斯球形簇結(jié)構(gòu)和基于連接的結(jié)構(gòu)，直接采用二分就可以將其劃分開。這里有提供兩種方法對它進(jìn)行處理：第一種方法，利用K-means對偽高斯進(jìn)行二分，K-means對高斯結(jié)構(gòu)的數(shù)據(jù)集能夠較好的進(jìn)行處理；第二種方法，利用SL對偽高斯進(jìn)行二分，SL對基于連接的數(shù)據(jù)集有較好的處理能力。

定義集合X_Found={xa,xa+1,…,xb}為偽高斯，利用K-means對其二分，得到兩個(gè)類X_Found11、X_Found12和二分后的分類標(biāo)簽C1；同時(shí)，利用SL對X_Found二分，得到兩個(gè)類X_Found21、X_Found22和二分后的分類標(biāo)簽C2。

對于X_Found，如果二分的效果很好，則利用算法1分別對劃分開的兩個(gè)類計(jì)算覆蓋率，得到的兩個(gè)覆蓋率結(jié)果應(yīng)該是較高的。反之，如果二分的效果不好，計(jì)算出的覆蓋率應(yīng)該很低。這可以作為選擇何種二分方法的依據(jù)。

基于以上考慮，對K-means二分結(jié)果X_Found11和X_Found12利用算法1計(jì)算兩個(gè)類的覆蓋率得到ratio11、ratio12。同時(shí)對SL二分結(jié)果X_Found21、X_Found22也作相同計(jì)算得到覆蓋率ratio21和ratio22。這樣便可計(jì)算出K-means劃分的綜合覆蓋率ratio1和SL劃分的綜合覆蓋率ratio2：

ratio1=ratio11+ratio12

(6)

ratio2=ratio21+ratio22

(7)

選擇其中覆蓋率較大的一種二分結(jié)果作為最終偽高斯的劃分結(jié)果，用公式表示：

(8)

這樣便得到偽高斯處理之后的類標(biāo)簽Ci。具體算法流程見算法2。

算法2

步驟1K-means對偽高斯X_Found二分，得到兩個(gè)類X_Found11、X_Found12和二分后的分類標(biāo)簽C1；

步驟2SL對偽高斯X_Found二分，得到兩個(gè)類X_Found21、X_Found22和二分后的分類標(biāo)簽C2；

步驟3對X_Found11、X_Found12、X_Found21和X_Found22利用算法1，計(jì)算覆蓋率ratio11、ratio12、ratio21和ratio22；

步驟4計(jì)算K-means二分方法的綜合覆蓋率ratio1和SL二分方法的綜合覆蓋率ratio2；

步驟5選擇覆蓋率大的一種二分結(jié)果作為偽高斯的分類標(biāo)簽Ci。

對于每一個(gè)基聚類中出現(xiàn)的偽高斯都作如上處理，便可得到優(yōu)化之后的基聚類結(jié)果E={C1,C2,…,CK}。

有了高質(zhì)量的基聚類，無疑將提高最終集成的質(zhì)量，本文在優(yōu)化基聚類之后，采用了Strehl提出的方法[7]進(jìn)行集成，具體的實(shí)驗(yàn)結(jié)果在下一節(jié)中說明。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 集成結(jié)果比較

實(shí)驗(yàn)采用8個(gè)不同的數(shù)據(jù)集分別進(jìn)行聚類集成，其中Path-based、Spiral、Jain和S1四個(gè)數(shù)據(jù)集來自http://cs.uef.fi/sipu/datasets；Data1、Data2、Data3和Data4為四個(gè)人工描繪的數(shù)據(jù)集。集成部分采用Strehl提出的方法[7]。圖6是直接K-means基聚類對8個(gè)不同形狀的數(shù)據(jù)集集成的結(jié)果，圖7是本文方法對8個(gè)數(shù)據(jù)集集成的結(jié)果。

圖6 基于K-means基聚類的集成結(jié)果

圖7 基于改進(jìn)基聚類方法的集成結(jié)果

表1中的數(shù)據(jù)為50次集成準(zhǔn)確率的均值。所選的8種數(shù)據(jù)集內(nèi)部較為復(fù)雜，具有很好的代表性，Path-based、Jain、S1和Data4四個(gè)數(shù)據(jù)集內(nèi)部結(jié)構(gòu)復(fù)雜，既有球形分布也有非球形分布，且有邊界不易區(qū)分的部分。K-means基聚類對這些地方?jīng)]有很好的處理，不能產(chǎn)生質(zhì)量較高的基聚類結(jié)果。改進(jìn)的基聚類算法對這些易產(chǎn)生同質(zhì)性較低劃分的地方作了處理，一定程度上提高了集成的效果。Spiral、Data1、Data2和Data3四個(gè)數(shù)據(jù)集屬于基于連接性且非球形分布的類結(jié)構(gòu)的數(shù)據(jù)集，K-means不能生成高質(zhì)量的基聚類，所以集成的效果也一般，改進(jìn)的基聚類算法對這類數(shù)據(jù)能較好的處理，大大提高了聚類集成的效果。

表1 K-means基聚類算法和改進(jìn)基聚類算法的集成準(zhǔn)確率

3.2 基聚類中類數(shù)目K的討論

圖8 基聚類算法不同K取值時(shí)的集成準(zhǔn)確率

3.3 覆蓋率閾值beta的討論

算法1中基聚類的每個(gè)類計(jì)算出的覆蓋率與beta進(jìn)行比較，當(dāng)覆蓋率小于beta時(shí)，則判斷該類為偽高斯，并作進(jìn)一步處理，反之則不作處理。所以beta的大小非常關(guān)鍵，直接影響判斷偽高斯的正確與否，需要進(jìn)行大量的實(shí)驗(yàn)來確定beta的取值。

圖9表示兩個(gè)高斯簇逐漸靠近變化為一個(gè)高斯簇的過程中覆蓋率的變化情況，可以發(fā)現(xiàn)兩個(gè)高斯簇越靠近，覆蓋率越高，當(dāng)兩個(gè)高斯簇合并為一個(gè)高斯簇時(shí)覆蓋率達(dá)到最高。經(jīng)過大量數(shù)據(jù)集的實(shí)驗(yàn)與分析，表明beta=0.75是一個(gè)較合理的取值，可以作為覆蓋率閾值準(zhǔn)確判斷一個(gè)類是否為偽高斯。

圖9 兩個(gè)高斯簇逐漸靠近變化為一個(gè)高斯過程中覆蓋率變化情況

4 結(jié) 語

本文對聚類集成中傳統(tǒng)的基聚類方法進(jìn)行優(yōu)化，建立一個(gè)能產(chǎn)生更好基聚類的算法，對提高聚類集成的質(zhì)量有顯著的效果。改進(jìn)的方法重點(diǎn)解決如何通過類與類之間的覆蓋率在無類標(biāo)簽的情況下判斷類的同質(zhì)性，找到同質(zhì)性低的類，并對其作精化處理，得到更好的基聚類，以完成更好的聚類集成。

但是這種算法依然存在一些局限性，對一些高維的數(shù)據(jù)集聚類效果不是很好。分析可知，覆蓋率計(jì)算中使用歐氏距離作為距離測度，這種方法不能很好地表現(xiàn)出一些高維數(shù)據(jù)集中點(diǎn)與點(diǎn)之間的距離。其次，對于基聚類中出現(xiàn)同質(zhì)性較低的偽高斯情況較少的數(shù)據(jù)集，它的集成結(jié)果提高有限。因?yàn)橥|(zhì)性較低的偽高斯是影響集成效果的關(guān)鍵，本算法針對的是基聚類中出現(xiàn)偽高斯情況較多的數(shù)據(jù)集，對這樣的數(shù)據(jù)集有較大的改進(jìn)。本方法存在一些不足，也是未來一段時(shí)間需要做的工作。

[1] Duda R O, Hart P E, Stork D G. Pattern classification[M]// Pattern classification. Wiley, 2001:119-131.

[2] Jain A K, Dubes R C. Algorithms for clustering data[J]. Technometrics, 1988, 32(2):227-229.

[3] 孫吉貴, 劉杰, 趙連宇. 聚類算法研究[J]. 軟件學(xué)報(bào), 2008, 19(1): 48-61.

[4] Gionis A, Mannila H, Tsaparas P. Clustering aggregation[J]. ACM Transactions on Knowledge Discovery from Data, 2007, 1(1): 1-30.

[5] Sandro Vega-pons, Jose Ruiz-shulcloper. A Survey of Clustering Ensemble Algorithms[J]. International Journal of Pattern Recognition and Articial Intelligence, 2011, 25(3): 337-372.

[6] 羅會蘭, 孔繁勝, 李一嘯. 聚類集成中的差異性度量研究[J]. 計(jì)算機(jī)學(xué)報(bào), 2007, 30(8): 1315-1324.

[7] Strehl A, Ghosh J, Cardie C. Cluster ensembles: A knowledge reuse framework for combining multiple partitions[J]. Journal of Machine Learning Research, 2002, 3(3): 583-617.

[8] 王海波, 徐濤. 基于有效性指標(biāo)的聚類集成學(xué)習(xí)方法[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2012, 29(9): 45-49.

[9] Topchy A, Jain AK, Punch W. Combining multiple weak clusterings[J]. IEEE international conference on data mining, 2003, 1(1): 331-338.

[10] Dudoit S, Fridlyand J. Bagging to improve the accuracy of a clustering procedure[J]. Bioinformatics, 2003, 19(9): 1090-1099.

[11] Fraley C, Raftery AE. How many clusters? Which clustering method? Answers via model based cluster analysis[J]. The Computer Journal, 1998, 41(8): 578-588.

[12] Minaei-Bidgoli B, Topchy A, Punch W. Ensembles of partitions via data resampling[J]. Proceedings of international conference on information technology, 2004, 2(2): 188-192.

[13] Iam-On N, Boongoen T, Garrett S, et al. A Link-Based Approach to the Cluster Ensemble Problem[J]. IEEE Transactions on Software Engineering, 2011, 33(12):2396-2409.

[14] 韓最蛟. 基于數(shù)據(jù)密集性的自適應(yīng)K均值初始化方法[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2014, 31(2): 182-187.

REFINEMENTOFBASECLUSTERSFORCLUSTERINGINTEGRATION

Cheng Kai1Zhong Caiming2Pang Yongming11

(CollegeofInformationScienceandEngineering,NingboUniversity,Ningbo315210,Zhejiang,China)2(CollegeofScienceandTechnology,NingboUniversity,Ningbo315210,Zhejiang,China)

Cluster ensemble integrates the multiple partitions of a dataset into a new clustering, which discloses the cluster structure information of all the base clusters to the greatest extent. The qualities of base clusters are obviously crucial to the final ensemble result. K-means is one of the most used algorithms to produce base partitions, as it can be implemented easily and the corresponding computational cost is low, and furthermore, its clustering mechanism conforms to the assumption in machines learning that the class conditional probability of local data is a constant. But K-means usually adopts Gaussian distance as the distance measure, thus it can only find the clusters of spherical shape. It is also unable to generate high-quality base clusters when applied to datasets with complex structures, especially those whose class structures are not distributed spherically but based on connectivity. Therefore, this paper presents an optimization method for base clusters, namely, to judge the homogeneity of the clusters generated by K-means and partition those with poor homogeneity once again to improve the homogeneity. As a result, the quality of the entire cluster ensemble is improved. The experiments on 8 datasets demonstrate the effectiveness of the proposed method.

Clustering integration K-means Base clusters Homogeneity Spurious Gaussian

TP18

A

10.3969/j.issn.1000-386x.2017.09.052

2016-08-27。國家自然科學(xué)基金項(xiàng)目(61175054)。程凱，碩士生，主研領(lǐng)域：模式識別,機(jī)器學(xué)習(xí)。鐘才明，教授。龐永明，碩士生。