基于MCL與KNN的混合聚類算法

牛秦洲，陳艷(桂林理工大學(xué)信息科學(xué)與工程學(xué)院，廣西桂林　541004)

?

基于MCL與KNN的混合聚類算法

牛秦洲，陳艷
(桂林理工大學(xué)信息科學(xué)與工程學(xué)院，廣西桂林541004)

摘要:MCL是一種圖聚類算法，針對MCL計算過程會產(chǎn)生小聚類及邊緣節(jié)點從團中脫離出來的問題，提出了一種基于MCL與KNN相結(jié)合的混合聚類算法。該算法利用KNN的分類特點，以MCL聚類得到的聚類表為依據(jù)，通過KNN對小聚類中的元素進(jìn)行再分類，以提高聚類的質(zhì)量。實驗證明此方法是可行的，改進(jìn)后的算法能使聚類質(zhì)量有所提高。

關(guān)鍵詞:MCL;聚類; KNN;小聚類;再分類

聚類分析是數(shù)據(jù)挖掘領(lǐng)域中一種重要的數(shù)據(jù)處理方法，主要是對數(shù)據(jù)按某種相似性度量標(biāo)準(zhǔn)來進(jìn)行聚類。

聚類操作中比較常用的幾種算法有k-means聚類［1－2］、基于密度［3］的聚類和基于網(wǎng)格聚類［4］等，但這些算法都存在以下幾個方面的缺陷: 1)它們都是以經(jīng)典的相似性度量作為聚類的基礎(chǔ)，聚類而成的概念不能完全反映該類概念抽象的實質(zhì)，進(jìn)而導(dǎo)致求解精度下降; 2)當(dāng)樣本屬性較多時，往往很難通過簡單計算得到的相似度值來全面地反映樣本之間的相關(guān)或相似程度，從而導(dǎo)致樣本聚類概念的區(qū)分度較低。

與傳統(tǒng)的聚類算法相比，MCL ( Markov clustering，馬爾可夫聚類)能夠很好地避免以上問題的發(fā)生。MCL聚類是圖聚類的一種，其核心思想是基于模擬隨機流(使用圖的轉(zhuǎn)移概念矩陣)進(jìn)行圖聚類［5］。這種方法已被應(yīng)用到很多領(lǐng)域并取得顯著成功(如蛋白質(zhì)的Tribe-MCL聚類)［6－7］。在MCL聚類的過程中，不是簡單地求出樣本之間的關(guān)系來進(jìn)行聚類判斷，而是在這種關(guān)系的基礎(chǔ)上通過膨脹和擴展操作來獲得關(guān)于樣本之間的更深層的知識來進(jìn)行聚類。因此在聚類的過程中從全局的角度出發(fā)，對樣本間的關(guān)系分析的更全面、更徹底。但由于在MCL聚類過程中過度擬合使得容易產(chǎn)生小聚類(只有一兩個節(jié)點的聚類)從而影響聚類質(zhì)量，為了解決這個問題，筆者采用MCL結(jié)合KNN［8］的混合算法，對MCL進(jìn)行改進(jìn)以提高聚類質(zhì)量。

1　MCL聚類算法介紹

1. 1 MCL聚類算法概述

馬爾可夫聚類算法( MCL)是van Dongen［5］開發(fā)的用于圖形聚類的算法，已成功應(yīng)用于蛋白質(zhì)家族分析等領(lǐng)域。MCL算法是基于隨機流的一種方法，不需預(yù)先設(shè)定聚類數(shù)目，通過概率改變和反復(fù)修改矩陣以實現(xiàn)隨機流模擬。

MCL聚類過程主要由在隨機矩陣(馬爾可夫矩陣)上的兩個操作構(gòu)成:膨脹操作和擴展操作。膨脹操作主要是對矩陣進(jìn)行的冪操作;擴展操作是對隨機矩陣中每個元素進(jìn)行的冪操作，即Mij= ( Mij)r。

1. 2相關(guān)定義及操作介紹

圖的相關(guān)矩陣:設(shè)G為一個有n個頂點的帶有權(quán)值的圖，則G的相關(guān)矩陣被定義為M'( G)，其中M'( G)中的元素Mij'的值與圖G中相應(yīng)邊上的權(quán)值Wij相等。

圖的馬爾可夫矩陣:令M'是圖G的相關(guān)矩陣，M為圖的馬爾可夫矩陣，則M的第j列是M'的第j列的歸一化，即Mlj= Mlj'/∑iMij'。其中: l，j為常數(shù)。

令圖G的相關(guān)矩陣表示為

則圖G的馬爾可夫矩陣可表示為

擴展操作:設(shè)圖G為一個有n個頂點的圖，圖的馬爾可夫矩陣可表示為M( G)。擴展操作的作用是通過對圖的馬爾可夫矩陣進(jìn)行冪乘M = M·M，使兩個頂點間的相似度轉(zhuǎn)化為兩個頂點與共同鄰接點的相似度的乘積之和。當(dāng)擴展值e = 2時，可表示為M = M·M，Mij可表示頂點i經(jīng)過一步到達(dá)頂點j的概率;當(dāng)e = 3時，M = M3，此時Mij表示頂點i經(jīng)過兩步流向頂點j的概率;當(dāng)經(jīng)歷的步數(shù)越多，則流出所在簇而進(jìn)入另外一個簇的可能性變大。所以擴展操作數(shù)e越大，會使同一個簇之間的緊密性作用優(yōu)勢減弱。

膨脹操作:膨脹操作通過膨脹參數(shù)R來對矩陣M中的每一列元素進(jìn)行冪乘操作，然后對每一列進(jìn)行歸一化操作，這樣可以拉大同一列元素之間的差距。膨脹操作是一個非線性操作，目的是增強類內(nèi)的流，削弱類間的流。

MCL的聚類過程如圖1所示?？梢钥闯觯琈CL的聚類過程主要通過膨脹和擴展兩個操作在馬爾可夫矩陣上的交替使用來完成矩陣的修改，從而使馬爾可夫矩陣達(dá)到穩(wěn)定狀態(tài)實現(xiàn)聚類。

由于上述聚類特點，經(jīng)過一定步驟的操作后導(dǎo)致節(jié)點間關(guān)系的放大和縮小，從而使節(jié)點之間的關(guān)系出現(xiàn)偏差。由于偏差不斷擴大，致使一些邊緣節(jié)點從團中分離出來形成單個或只有兩三個節(jié)點的小聚類。

圖1　MCL聚類算法Fig. 61MCL clustering algorithm

為了減少小聚類的產(chǎn)生，提高聚類的質(zhì)量，筆者提出了一種改進(jìn)的MCL算法?？紤]到在聚類過程中由于不斷的膨脹和擴展操作導(dǎo)致節(jié)點關(guān)系的偏差放大，圖中處在同一個團中的邊緣節(jié)點容易被分離出來。然而即使被分離出來，邊緣形成的小聚類與原來一個團體形成的聚類的聯(lián)系依然是很緊密的。因此，提出了一種MCL與KNN相結(jié)合的混合聚類算法，算法的主要思想如下:在進(jìn)行聚類后，對小聚類與其他聚類的類間距離關(guān)系進(jìn)行判斷，從而決定是否需要進(jìn)一步合并。

當(dāng)小聚類與其他聚類質(zhì)心的最小距離小于某一閾值，可認(rèn)為它們之間關(guān)系比較緊密，小聚類的存在不合理，需要進(jìn)一步利用KNN對小聚類中的元素進(jìn)行重新分配;當(dāng)質(zhì)心的距離大于閾值時，則認(rèn)為小聚類與其他類存在明顯的區(qū)別，其存在是合理的。

2　混合聚類算法

2. 1算法思想

采用MCL與KNN相結(jié)合的混合算法來避免上述問題的發(fā)生。KNN算法是一種分類算法，其基本思想是:給定一個待分類的數(shù)據(jù)，通過以一個已分類的樣本空間為依據(jù)，計算離自己最近的K個樣本來判斷這個待分類數(shù)據(jù)的類別情況。因此，可以考慮利用KNN來對分離出來的小聚類進(jìn)行再次的分類，從而解決小聚類產(chǎn)生的問題。

2. 2馬爾可夫矩陣計算

在進(jìn)行MCL聚類前，需要先求出數(shù)據(jù)之間的關(guān)系，得到一個關(guān)系矩陣。定義相似度函數(shù)

式中: simG( X，Y)表示實例X，Y之間的相似度; k表示樣本的屬性個數(shù); dn( Xi，Yi)為兩個實例的屬性i的距離; wi為屬性i的權(quán)值; Di表示屬性i的取值范圍; range( Di)為Di中的最大差值。利用上面的相似度計算模型來計算樣本之間的關(guān)系，得到關(guān)系矩陣即馬爾可夫矩陣。

2. 3質(zhì)心判斷

在對聚類進(jìn)行質(zhì)量評價時，類間距離常會被作為一個重要因素考慮。采用同樣的思想，對于產(chǎn)生的小聚類，利用類間的距離來衡量兩個類是否聚類合理。

由于同一個聚類中的樣本相似程度高，因此可以利用質(zhì)心來簡化整個類。

質(zhì)心代表的是聚類中各實例的平均化，通過質(zhì)心間的距離從整體上判斷聚類之間分布的合理性，這里引入閾值Td進(jìn)行判斷，若兩個質(zhì)心的距離小于Td，則認(rèn)為它們屬于同一個聚類，利用KNN對小聚類中的元素進(jìn)行精確再分配;若兩個質(zhì)心的距離大于Td，則認(rèn)為它們不屬于同一個聚類，不需要對小聚類作任何處理。

2. 4改進(jìn)算法描述

通過將MCL算法結(jié)合KNN算法的思想控制小聚類的生成，首先對MCL產(chǎn)生的聚類進(jìn)行檢測，若產(chǎn)生小聚類，判斷是否需要對小聚類進(jìn)行處理，若需要，則對小聚類中的對象采用KNN算法，利用原始的馬爾可夫關(guān)系矩陣，找出小聚類中每個對象的K個最相似的對象，并計算所屬類的權(quán)值，通過KNN將小聚類中的對象合并到權(quán)值最大的一類中去，這樣可以有效地控制小聚類的形成，滿足用戶的需求，同時也提高了聚類的質(zhì)量。K的取值涉及到再分類的精確性:當(dāng)K取值過大，考慮的周圍點多，影響因素多，分類的精度在一定程度上降低; K取值過小，則由于考慮的周圍點太少，使得分類過于片面，如何選擇一個合適的K值，需要根據(jù)具體情況而定，如聚類數(shù)量、規(guī)模、分類精度要求等。

定義K的取值其中: Ki表示小聚類i對應(yīng)的K值; vsi表示小聚類i的元素個數(shù); m是一個常數(shù)，主要用于調(diào)節(jié)分類精度，m = max( vsi，Nc) ; Nc為MCL聚類后得到的聚類數(shù)，m取vsi與Nc之間的最大值，這樣的取值，既避免了小聚類本身元素的干擾，又充分考慮到了訓(xùn)練樣本的分類信息，使待分類元素能夠在一個合適的K值下更加合理、可靠地進(jìn)行再分類。

算法具體過程如下。

需要建立一張輔助表Tbad，用于存放經(jīng)過驗證可以單獨存在的小聚類。

輸入R值、距離閾值Td。

①對所有訓(xùn)練樣本求關(guān)系矩陣其中: G為關(guān)系矩陣，Gij是關(guān)系矩陣的第i行第j列的值，表示第i個樣本與第j個樣本的關(guān)系值。

②對數(shù)據(jù)進(jìn)行MCL聚類，聚類結(jié)束，形成一張聚類信息表Tbinf。

③查看Tbinf中是否有小聚類產(chǎn)生，若Tbinf中有小聚類，則查看Tbad中是否有此聚類的信息:若Tbad中有此聚類的信息，則在Tbinf中繼續(xù)往下尋找;若Tbad中沒有此聚類的信息，則進(jìn)入④;若Tbinf中沒有小聚類存在，則輸出。

④計算各聚類的質(zhì)心，利用質(zhì)心關(guān)系來判斷小聚類的分布是否合理，即小聚類的質(zhì)心與其他聚類的質(zhì)心距離是否小于給定值Td:若小于Td則說明兩個聚類很相似，小聚類產(chǎn)生不合理，需要進(jìn)行再分配，進(jìn)入⑤;若大于Td則說明小聚類與其他聚類區(qū)別比較明顯，可以單獨存在，將小聚類的信息寫入Tbad表中，返回③。

⑤在基礎(chǔ)關(guān)系表中找出與小聚類元素最接近的k個元素，以MCL聚類信息表Tbinf為基礎(chǔ)，計算k個元素的類別信息，從而確定小聚類元素的最終類別信息，并更新Tbinf表，返回③。

計算公式如下:

C( x) = { Ci| max( W( x，Ci) ) }。( 9)其中: W( x，Ci)表示x屬于類別i的權(quán)值; xj為x的K個最相似樣本的第j個樣本; C( x)表示待分類樣本的類別信息，待分類樣本的類別為W( x，Ci)最大時的類別。

輸出:聚類得到的各個簇信息。

其中，Tbad結(jié)構(gòu)如下:

3　算法檢驗

3. 1檢驗標(biāo)準(zhǔn)

3. 1. 1模塊度指標(biāo)模塊度［9］指標(biāo)是由Newman等提出來的一種聚類評價標(biāo)準(zhǔn)，也是最廣泛被使用的度量聚類質(zhì)量好壞的指標(biāo)之一。

公式定義如下:

其中: E為一個k·k的矩陣; eij表示第i行第j列的一個值，也表示聚類i與聚類j的所有邊占整個圖中所有邊的比例，表示矩陣的跡; ai為，即矩陣E中的第i行的所有值相加，表示聚類i與其他聚類相連的邊之和占整個圖中的邊的比例。

3. 1. 2 DB Index指標(biāo)DB Index［10］準(zhǔn)則作為一種評判準(zhǔn)則，同時使用了類間距離和類內(nèi)離散度，基本內(nèi)容如下。

類內(nèi)平均離散度

其中: Zi是Ci類的類中心; | Ci|表示Ci類樣本數(shù)。類間距離

即用兩個類中心的距離表示類間距離。DB Index定義為其中:是分類數(shù)目。DB Index準(zhǔn)則是DB的值越小，說明分類的效果越好。

3. 2實驗分析

通過采用UCI機器學(xué)習(xí)數(shù)據(jù)庫［11］中的Seeds數(shù)據(jù)集和Iris數(shù)據(jù)集對本文提出的算法與MCL算法、K均值算法、K調(diào)和均值( KHM)算法和模糊C均值算法分別進(jìn)行聚類質(zhì)量的比較。Seeds數(shù)據(jù)集和Iris數(shù)據(jù)集都是用于檢驗分類算法的標(biāo)準(zhǔn)數(shù)據(jù)，因此選用這些標(biāo)準(zhǔn)數(shù)據(jù)，對算法的驗證具有一定的說服力。

首先以模塊度指標(biāo)對MCL聚類與本文提出的混合聚類算法進(jìn)行比較。在Matlab下進(jìn)行仿真，結(jié)果如圖2所示。表1給出了仿真得到的具體數(shù)據(jù)。

當(dāng)膨脹參數(shù)R值為4～6時，MCL和混合算法聚類效果是一樣的，這是由于R的取值比較小沒有產(chǎn)生小聚類所致。隨著R值的增大，MCL算法產(chǎn)生的小聚類個數(shù)增多，由于這些小聚類與其他聚類間的聯(lián)系比較密切，因此使類之間的區(qū)分度比改進(jìn)后算法的聚類區(qū)分度低，由表1可以看出，在相同R值下改進(jìn)后的算法能得到質(zhì)量更好的聚類。

圖2　Seeds數(shù)據(jù)集聚類的模塊度仿真比較Fig. 62Module simulations comparison of Seeds data aggregation

R值的取值:當(dāng)R取值太小，聚類粒度過大，整個數(shù)據(jù)集都被聚為一類，起不到區(qū)分的作用; 當(dāng)R取值過大時，聚類粒度過細(xì)，可能導(dǎo)致整個數(shù)據(jù)集中的每個實例被單獨作為一類。膨脹參數(shù)R值的選取標(biāo)準(zhǔn)，主要根據(jù)聚類評價標(biāo)準(zhǔn)及用戶對數(shù)據(jù)的聚類規(guī)模的要求來選擇R值。

時間復(fù)雜度:由于改進(jìn)算法是在MCL基礎(chǔ)上結(jié)合KNN的算法，因此，改進(jìn)算法在時間復(fù)雜度上比MCL時間復(fù)雜度多出了KNN部分，即O( N)。其中N為聚類數(shù)據(jù)的規(guī)模，當(dāng)N的數(shù)量只有幾百個案例時，改進(jìn)算法與原算法在時間消耗上沒有太大差別;隨著N的增大，改進(jìn)算法與原算法在時間消耗上差距逐漸拉大。

利用DB Index準(zhǔn)則對K均值聚類、K調(diào)和均值( KHM)算法、模糊C均值聚類算法和本文提出的MCL混合聚類算法進(jìn)行聚類質(zhì)量比較，DB Index準(zhǔn)則利用對聚類后各聚類之間的距離和聚類內(nèi)部的離散度來評定聚類的質(zhì)量，在Matlab下的仿真結(jié)果如圖3所示，表2為仿真得到的具體數(shù)據(jù)。

從表2可以看出，當(dāng)聚類數(shù)為2、3時，本文算法與FCM算法比較接近，可能是由于聚類數(shù)過少所致。隨著聚類數(shù)的加大，F(xiàn)CM算法與本文算法得到的聚類質(zhì)量差距開始變大;隨著聚類個數(shù)的增加，K均值算法、KHM算法、FCM算法和本文算法的DB Index值都呈上升趨勢，即聚類質(zhì)量都在下降，但其他算法與本文算法相比聚類質(zhì)量下降速度快，聚類質(zhì)量比本文算法的聚類質(zhì)量差。這說明了本文提出的改進(jìn)算法效果更好，可以得到質(zhì)量更好的聚類結(jié)果。

表1　Seeds數(shù)據(jù)集聚類的模塊度仿真數(shù)據(jù)Table 1　Module comparison of Seeds data aggregation

圖3　4種聚類算法對Iris數(shù)據(jù)集的DB Index指標(biāo)仿真Fig. 63Simulations of DB Index of Iris data aggregation with 4 clustering algorithms

表2　Iris數(shù)據(jù)集聚類的DB Index指標(biāo)仿真結(jié)果Table 2　DB Index of Iris data aggregation

從以上實驗看，基于MCL與KNN相結(jié)合的混合聚類算法，能夠增強聚類的效果，提高類與類之間的區(qū)分度。與幾種經(jīng)典的聚類算法進(jìn)行實驗比較，通過對數(shù)據(jù)的聚類粒度的不斷調(diào)整分析幾種聚類算法在此過程中的聚類性能。對于同一數(shù)據(jù)樣本集，隨著聚類粒度的不斷細(xì)化，聚類得到的數(shù)目變大，由于基于MCL與KNN的聚類算法，結(jié)合了MCL的全局判斷性，即在進(jìn)行聚類時，是在對全局?jǐn)?shù)據(jù)之間的距離關(guān)系進(jìn)行分析的基礎(chǔ)上獲得的知識為依據(jù)進(jìn)行聚類的，避免了聚類過程中只考慮部分?jǐn)?shù)據(jù)的距離關(guān)系而導(dǎo)致的片面性，通過膨脹因子拉大差距，從而使實例之間的區(qū)分度得到提高，另外通過結(jié)合KNN的分類特性，克服了因膨脹因子而導(dǎo)致的過度分離現(xiàn)象(小聚類)，在整個聚類過程中，基于MCL的聚類算法既保證了聚類結(jié)果的區(qū)分度，又防止了過度分離的現(xiàn)象，使聚類結(jié)果在保持實例的區(qū)分度和相似度上得到了較好的平衡。與其他算法在整個實驗中進(jìn)行比較，得到了較好的聚類結(jié)果，具有一定的典型性。

4　結(jié)束語

本文針對MCL自身存在的不足，考慮到KNN算法的分類特性，提出了一種MCL與KNN相結(jié)合的混合聚類算法。該混合聚類算法結(jié)合了MCL聚類和KNN算法自身的特點，以MCL聚類信息為指導(dǎo)，利用KNN對小聚類進(jìn)行再分配，從而優(yōu)化聚類結(jié)果，混合聚類算法很好地彌補了MCL聚類過程中容易產(chǎn)生小聚類的不足。與MCL算法相比，在產(chǎn)生小聚類時，混合算法能很好地將小聚類進(jìn)行再分配，從而提高了聚類的質(zhì)量。利用傳統(tǒng)聚類算法與改進(jìn)算法進(jìn)行比較實驗，結(jié)果證明此方法是有效的、可行的，具有較好的實際應(yīng)用價值。由于本算法是在MCL基礎(chǔ)上結(jié)合了KNN分類算法，改進(jìn)算法的時間復(fù)雜度比MCL的時間復(fù)雜度多出O( N)，即KNN的時間復(fù)雜度。隨著數(shù)據(jù)規(guī)模的增大或者小聚類數(shù)量的增多，改進(jìn)算法所消耗的時間將逐漸增大。此算法比較適合數(shù)量中等的數(shù)據(jù)進(jìn)行聚類，既能保持比MCL算法更好的聚類性能，又能避免消耗過多的時間。

參考文獻(xiàn):

［1］喬麗，姜慧霖，賈世杰．基于改進(jìn)k-means聚類的案例檢索策略［J］．計算機工程，2011，37 ( 5) : 193－195．

［2］喬麗，姜慧霖．一種k-means聚類的案例檢索算法［J］．計算機工程與應(yīng)用，2011，47 ( 4) : 185－187．

［3］Chen Y X，Tu L．Density-based clustering for real-time stream data［C］/ /Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，ACM，2007: 133－142．

［4］趙慧，劉希玉，崔海青．網(wǎng)格聚類算法［J］．計算機技術(shù)與發(fā)展，2010，20 ( 9) : 83－85．

［5］van Dongen S．Performance criteria for graph clustering and Markov cluster experiments［R］．Amsterdam: National Research Institute for Mathematics and Computer Science in the Netherlands，2000．

［6］溫菊屏，鐘勇．圖聚類的算法及其在社會關(guān)系網(wǎng)絡(luò)中的應(yīng)用［J］．計算機應(yīng)用與軟件，2012，29( 2) :161－163．

［7］Akama H，Miyake M，Jung J．How to take advantage of the limitations with Markov clustering—the foundations of branching Markov clustering ( BMCL)［C］/ /The Third International Joint Conference on Natural Language Processing．Hyderabad: the Asian Federation of Natural Language Processing，2008: 901－906．

［8］孫榮宗，苗奪謙，衛(wèi)志華，等．基于粗糙集的快速KNN文本分類算法［J］．計算機工程，2010，36( 24) :175－177．

［9］Newman M E J，Girvan M．Finding and evaluating community structure in networks［J］．Physical Review E，2004，69 ( 2) : 026113．

［10］羅蘭，曾斌．基于時序向量聚類的周期關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法［J］．計算機工程，2010，36 ( 19) : 110－112．

［11］Frank A，Asunclon A．UCI machine learning repository ［EB/OL］．［2011－11－02］．http: / /archive．ics．uci．edu/ml．

Hybrid clustering algorithm based on KNN and MCL

NIU Qin-zhou，CHEN Yan
( College of Information Science and Engineering，Guilin University of Technology，Guilin 541004，China)

Abstract:MCL is a graph clustering algorithm．With the characteristics of MCL computational process，MCL is prone to producing small clustering and separating edge nodes from the groups．A hybrid clustering based on MCL combined with KNN algorithm is proposed．Hybrid algorithm improves the quality of clustering by reclassification of elements in small clustering by KNN classification characteristics and clustering tables required by MCL clustering．Experiments prove that this method is feasible and the improved algorithm can enhance the quality of clustering．

Key words:MCL; clustering; KNN; small clustering; reclassification

作者簡介:牛秦洲( 1956—)，男，教授，研究方向:制造業(yè)信息化、人工智能。

基金項目:國家自然科學(xué)基金項目( 51365010) ;廣西科學(xué)研究與技術(shù)開發(fā)計劃項目(桂科合1346011－10)

收稿日期:2014－03－24

doi:10. 3969/j．issn. 1674－9057. 2015. 01. 029

文章編號:1674－9057( 2015) 01－0181－06

文獻(xiàn)標(biāo)志碼:A

中圖分類號:TP301. 6

引文格式:牛秦洲，陳艷．基于MCL與KNN的混合聚類算法［J］．桂林理工大學(xué)學(xué)報，2015，35 ( 1) : 181－186．