一種新型高效的無參數化聚類算法

陳靖颯，程開豐，吳懷崗

1(南京師范大學 計算機科學與技術學院，南京 210023)2(南京大學 電子科學與工程學院，南京 210023)

1 引 言

K-means算法是一種非常經典的無監督聚類算法，由于該算法具有原理簡單、易于描述、時間效率高且適于處理大規模數據等優點[1]，因此被廣泛地應用于眾多領域.但該算法也存在明顯的缺陷：聚類的準確度和計算復雜度嚴重依賴于初始聚類數k和初始簇中心參數的選擇.而在大量實際應用場景中，數據集不僅規模大，而且一直處于動態變化過程中，所以聚類數和聚類中心往往是很難提前預知和確定的.

為了解決上述問題，學者們相繼提出了一些改進方案：文獻[2]提出了利用迭代最大距離法來選取初始簇中心，它的基本假設是距離最遠的樣本點最不可能被分到同一個簇中，所以為了確定初始簇中心，迭代地選擇樣本集中距離最遠的樣本，直至樣本數達到要求，該類算法雖然能解決傳統K-means算法初始簇中心選擇的問題，但由于每次迭代時都要計算所有非簇中心集中樣本與簇中心集中樣本間距離的乘積并再比較排序，計算復雜度太高，而且最后選取出的初始簇中心會分布在樣本集的邊緣，會導致K-means的收斂速度變慢.文獻[3]提出了基于最小生成樹的MSTCluster聚類算法，該算法首先將數據集抽象成賦權完全圖WCG模型，其中的點代表向量，賦權邊代表數據間的相似關系；然后將WCG轉換成全連通的最小生成樹MST，接著統計最小生成樹中邊集權重的均值μ和方差σ，然后將μ+λ*σ作為閾值PT對最小生成樹進行剪枝.實際聚類效果證明該方法在很多場景能夠取得很不錯的聚類效果，而且計算復雜度相對經典K-means有了明顯優化，但問題是剪枝閾值中的調節因子 的取值目前還沒有統一的標準，實際使用時還是得依靠經驗設置.文獻[4，5]在最小生成樹聚類算法和層次聚類算法的基礎上，提出了一種通過控制參數來改變目標函數，進而在目標函數最小時得到最優聚類結果的算法，該類算法輸入參數少且能夠識別任意形狀任意密度的簇，但依舊是需要人為確定參數的，且目標函數的收斂性難以證明，即如果目標函數不收斂則得不到最佳聚類結果.文獻[6]提出了一種基于最小生成樹的自適應閾值自頂向下分層聚類算法，該算法先根據最近鄰關系劃分最小生成樹的邊集，再統計當前最小生成樹邊集的均值和方差，進而根據一個控制參數ρ按照一定的計算方式得出閾值，可以看出該算法也是需要人為設置參數值的，而不是完全自適應的.文獻[7]提出了一種改進的最小生成樹自適應空間點聚類算法，該算法根據最小生成樹邊長的數理統計特征定義裁剪因子，進而通過宏觀和局部兩輪剪枝逐步打斷最小生成樹中的長邊，從而得到最終聚類結果，該算法的自適應程度較高，但裁剪因子中仍含有需要人為確定的參數，也不是完全自適應的.

綜上可見，雖然已經有很多學者嘗試從不同角度去解決K-means算法對經驗參數的依賴性和計算復雜度高等問題，并取得了一定進展，但仍有改進的空間.

2 MNC算法

本文在前述工作的基礎上提出了一種基于最小生成樹的無參數化聚類算法MNC(MST based Non-parameterized Clustering)，該方法先利用最小生成樹理論[8]將待聚類的數據集轉換成最小生成樹；然后利用k=2的經典K-means算法將最小生成樹邊集的一維權重空間進行聚類，得到兩個權重集合W1和W2，再根據Everitt 在1974 年關于聚類所下的定義“一個類簇是測試空間中點的會聚，同一類簇的任意兩個點間的距離小于不同類簇的任意兩個點間的距離”[9]得到，max(W1)

2.1 符號說明

2.2 算法流程

MNC算法的基本流程如圖1.

MNC總體可分成5個階段，分別為：生成賦權完全圖、生成最小生成樹、生成剪枝閾值、剪枝分裂和離群點過濾.每個階段分別由相應的子函數GenWCG、GenMST、GenPT、Prune和Filter來實現，具體每個階段的子函數實現細節如下.

2.3 生成賦權完全圖

首先將SN中的每個數據樣本看成N維歐式空間的向量，數據樣本間的相似度用向量間的歐氏距離來度量，則原數據樣本集可以轉換成賦權完全圖模型WCG=〈V,E,W〉，其中V、E和W分別代表WCG中的點集、邊集和權重集.GenWCG函數實現的偽代碼如下：

圖1 MNC算法的基本流程圖Fig.1 Flow diagram of MNC algorithm

函數GenWCG(SN)

過程：

Step 1. 點集V=SN

Step 2. 邊集E=V×V

輸出：賦權完全圖WCG=〈V,E,W〉

2.4 生成最小生成樹

采用圖論中的經典Prim算法[11]生成最小生成樹，即：構建兩個點集P和Q，分別代表已在MST和未在MST中的點集合，每次迭代時從Q中選擇距離P最近的點加入P，直至Q為空(所有點都已在MST中).生成最小生成樹的函數GenMST實現的偽代碼如下：

函數GenMST(WCG)

輸入：賦權完全圖WCG=〈V,E,W〉

過程：

Step 1.從v中隨機選擇一點

Step 2.P={v}

Step 3.Q=V-P

Step 4.whileQ≠?

do

MST=MST∪{ei,j}

endwhile

輸出：最小生成樹MST={ei,j}

2.5 生成剪枝閾值

假設SN的最優聚類函數(Optimal Clustering)為OC(SN,CN)其中CN為聚類后的簇個數.定義MST(SN)到OC(SN,M)的投影函數P，其輸出為到兩個不相交的邊集EIntra和EInter，分別為最后聚類結果簇內點間的邊集和簇間的邊集，即：

P(OC(SN,M),MST(SN))=〈EIntra,EInter〉

(1)

其中邊集EIntra和EInter滿足如下約束：

根據Everitt對聚類的定義“同一類簇的任意兩個點間的距離小于不同類簇的任意兩個點間的距離”，可得：

max(EIntra)

(2)

即從最后聚類簇的角度看MST(SN)，MST(SN)中連接簇內點最長的邊短于連接簇間最短的邊.

由于MST(SN)邊集的權重空間又可以構成一維的數據空間S1，其中每個數據樣本的坐標為MST(SN)中邊的權重值，即：

S1={di|?ei∈MST(SN),di=w(ei)}

(3)

根據式(1)，MST(SN)可以被SN的最優聚類OC(SN,M)劃分成兩個不相交的子集EIntra和EInter，而且EIntra和EInter間距離足夠遠.結合式(2)可見MST(SN)投影到OC(SN,M)的過程等價于一維數據S1的2分類過程，即：

P(OC(SN,M),MST(SN))?OC(S1，2)

(4)

根據(4)式，原復雜度較高的“不定類別數的N維空間聚類OC(SN,M)問題”被轉換成了復雜度較低的“類別數為2的一維空間聚類OC(S1，2)問題”.實現OC(S1，2)的方法有很多種，但由于OC(S1，2)具備“類別數固定為2”、“距離計算為簡單的減法”、“初始重心可選左右端點”等特點，使得經典K-means算法的缺點都可被彌補，因此本文采用經典K-means算法來實現OC(S1，2).在上述結論的基礎上，本方案的剪枝閾值生成函數GenPT實現的偽代碼如下：

函數GenPT(MST)

輸入：最小生成樹MST={ei,j}

過程：

Step 1.提取MST邊集的一維權重空間S1

Step 2.利用經典K-means對S1進行k=2的聚類，即{W1，W2}=kmeans(S1，2)，其中max(W1)

Step 3.閾值PT=min(W2)

輸出：閾值PT

2.6 剪枝分裂

利用上一步得到閾值PT，對MST進行剪枝，即MST中所有權重大于PT的邊都被斷開.經過剪枝后，原來全連通的MST會變成森林.剪枝函數Prune實現的偽代碼如下：

函數Prune(MST,PT)

輸入：

最小生成樹MST={ei,j}

剪枝閾值PT

過程：

Step 1.F=MST

Step 2.forei∈MSTdo

ifw(ei)≥PTthen

F=F-{ei}

endif

endfor

輸出：森林F

2.7 離群點過濾

經過剪枝得到的森林F中的連通分量可以作為初步的聚類結果，但由于實際數據集中往往包含很多無用的噪聲數據，如果不進行過濾，就會降低聚類結果的精度.噪聲數據反映在聚類結果中，就是空間密度低且距離正常數據比較遠的離群點[12].為了在中檢測這些離群點，只需對F的連通分量進行點數判斷，本算法視包含的點數少于3的連通分量為離群點.離群點過濾函數Filter實現的偽代碼如下：

函數Filter(F)

輸入：森林F={ei,j}

過程：

Step 1.C=ConnectedComponents(F)

Step 2.forci∈Cdo

if|ci|<3then

C=C-{ci}

endif

endfor

輸出：簇集合C

其中的ConnectedComponeents()函數為連通分量提取函數，實現時可以采用圖論算法中經典的Hopcroft算法[13].經過濾后的連通分量即為MNC算法的最終聚類結果.

3 實驗與分析

3.1 實驗描述

由于好的聚類算法應該能夠處理不同凹凸形狀的數據集，所以為了驗證本算法的有效性和最后聚類效果的直觀可視性，實驗首先選擇了經典機器學習庫scikit-learn[14]中的3組具有不同形狀的二維隨機數據集DS1、DS2和DS3，三者中包含的簇形狀總結如表1.

表1 二維數據集中的數據簇形狀
Table 1 Data cluster shape of 2D datasets

數據集凹凸性簇形狀DS1凸凸形DS2混合半圓形+凸形DS3混合環形+凸形

為了進一步證明MNC算法的有效性，本文又選取了三個經典的UCI多維數據集Iris、Wine和Glass.三者的屬性數(維度)、樣本數、類別數總結如表2.

表2 經典UCI數據集特征
Table 2 Characteristic of UCI datasets

數據集維度樣本數類別數Iris41503Wine131783Glass102147

由于傳統K-means和MSTCluster都是參數化算法，即輸入除了待聚類的數據集外，還需要額外的參數：傳統K-means的簇數k和MSTCluster的調節因子λ.而對于不同形狀數據集，相應的最優化參數無法提前預知，所以本實驗對傳統K-means和MSTCluster采取了迭代實驗的方式：以兩者參數可能取值的最小值為初始值，每次以小步長進行遞增，對每個可能的參數都進行聚類實驗，并對得到的聚類結果進行評價函數計算，最后當評價函數值達到極小時，我們認為達到最優聚類.

3.2 實驗結果與分析

3.2.1 二維隨機數據集

對于二維隨機數據集，不同聚類算法(經典K-means、基于最小生成樹的傳統MSTCluster算法和本文MNC算法)的最優聚類效果如圖2～圖4所示(其中X表示離群點)，從中可以得出不同算法對不同形狀數據簇的識別能力，總結如表3.

表3 對不同二維形狀數據簇的識別能力
Table 3 Cluster identification ability of different 2D shapes

聚類算法凸形半圓形環形K-means√××MSTCluster√√√MNC√√√

可見傳統K-means只能識別凸形數據簇，而基于最小生成樹的MSTCluster和本文的MNC算法不僅能識別常規凸形數據簇，而且還能夠識別半圓、環等非凸的數據簇.分析其原因是與傳統K-means直接進行聚類不同，MNC和MSTCluster都采用了先凝聚再分類的間接方式，即先將整個數據集按照最小生成樹的方式凝聚成一個大的類，然后分析數據集的整體性質，并在此指導下自頂向下地進行分類.由于充分利用到了數據集的整體性質，所以最后分類的結果相比傳統K-means會更加準確.

圖2 二維數據集DS1的聚類效果Fig.2 Clustering result of DS1

圖3 二維數據集DS2的聚類效果Fig.3 Clustering result of DS2

圖4 二維數據集DS3的聚類效果Fig.4 Clustering result of DS3

而對比MNC和MSTCluster之間的聚類結果，可以發現MNC比MSTCluster更優：DS2中的兩個半圓形簇和DS3中的兩個環形簇，MSTCluster都沒有進行區分，而MNC成功進行了區分.上述結果說明MSTCluster迭代實驗停止時還并未到達真正的最優，而不同形狀數據集的最優化λ參數是無法提前預知的.

3.2.2 經典UCI數據集

對于經典UCI數據集，由于其高維特性，無法直觀展示聚類效果，故采用經典聚類評價指標中的RAND系數來進行評估.RAND系數反映的是對于有參考標簽(比如Iris數據集中花的類別)的數據集，實際聚類結果與參考結果間的相似度[15]，其取值范圍在[0，1]之間，值越大表示聚類結果的準確度越高.本文選取Iris、Wine、Glass三種UCI數據集進行聚類實驗，不同聚類算法的RAND系數統計如表4.

表4 UCI數據集聚類后的RAND系數
Table 4 RAND coefficients for UCI datasets clustering

聚類算法IrisWineGlassK-means0.430.160.31MSTCluster0.520.270.41MNC0.660.330.56

由上述結果可見，針對三種實際的數據集，三種不同聚類算法中，MNC算法的RAND系數都是最大的，傳統K-means算法的RAND系數最小.此結果說明不僅針對前述隨機數據集，對于Iris等實際數據集，本文的MNC算法相對傳統K-means等算法仍然能提供更高的聚類準確率.

迭代實驗中傳統K-means的輸入參數(簇數k初始取值為2、迭代步長為1)和MSTCluster的輸入參數(調節因子初始取值為1、迭代步長為0.2)的最終取值總結如表5.

表5 輸入參數的迭代統計
Table 5 Statistics of iterative input parameters

聚類算法輸入參數最終取值DS1DS1DS2IrisWineGlassK-means簇數k 665337MSTCluster調節因子λ1.61.62.02.21.82.0

從上述結果可見針對不同形狀數據集，傳統K-means和MSTCluster的輸入參數在迭代停止時各不相同.由于不同形狀數據集的最優化參數無法提前預知，所以本文MNC算法的非參數化特點具有很大優勢.

3.2.3 運行時間統計

不同數據集下各聚類算法的運行時間統計如表6，時間單位為秒.(由于K-means和MSTCluster采用了多次迭代實驗的方式，因此這兩者的運行時間采用的是多次迭代的均值)

由表6的結果可見，對所有數據集，K-means時間最長，MSTCluster次之，MNC最短.具體6個數據集下MNC相對傳統K-means的優化比例分別為37%、47%、50%、50%、45%和46%，相對MSTCluster的優化比例分別為17%、26%、30%、25%、29%和28%.分析其原因是K-means算法每次迭代時都要重算所有數據對象與各簇新中心間的歐式距離，而每次歐式距離的計算除了加、減等簡單運算，還有復雜的平方和開方運算，在MSTCluster和MNC中，數據對象間歐式距離的計算只會在算法的第一階段進行一次，后續兩個階段中都只有簡單的加、減和比較操作，所以相比傳統K-means，MSTCluster和MNC的計算復雜度更低.而MSTCluster和MNC之間相比，雖然兩者前期都基于最小生成樹，但不同的是MSTCluster中剪枝閾值的產生需要依賴經驗參數(調節因子)，而MNC的剪枝閾值則是根據最小生成樹自動產生，避免了對參數空間的最優搜索過程，所以MNC的計算復雜度相比MSTCluster更低.

表6 運行時間統計
Table 6 Statistics of runtime

數據集K-means/sMSTCluster/sMNC/sDS10.0140.0110.009DS20.0470.0300.025DS30.0750.0500.037Iris0.1200.0800.060wine0.1380.1060.075glass0.1590.1190.086

綜上所述，本文的MNC算法不僅對不同形狀的二維隨機數據集和經典高維數據集能夠有效聚類，而且無參數化的特點使得算法的計算復雜度相比傳統算法能夠進一步優化.

4 總 結

為了解決K-means算法對初始聚類數k和初始簇中心經驗參數的依賴問題，本文提出了一種只依賴數據集本身而無需經驗參數的新型無參數化聚類MNC算法.該算法首先依據最小生成樹理論將整個數據集凝聚成一個大類，然后利用傳統聚類算法對最小生成樹邊集的一維權重空間二次聚類得到簇內邊集和簇間邊集，最后以此為依據對最小生成樹進行剪枝而得到連通分量，該連通分量即為聚類的簇.為了驗證該算法的有效性和實用性，本研究還通過實驗分析對比了不同聚類算法的準確度和復雜度.實驗結果表明，MNC算法不僅能夠準確識別不同形狀的數據簇，還可以消除傳統算法對參數空間的迭代搜索過程，從而降低計算復雜度，提高聚類效率.