一種新型高效的無參數(shù)化聚類算法

陳靖颯，程開豐，吳懷崗

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

1 引 言

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

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

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

2 MNC算法

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

2.1 符號說明

2.2 算法流程

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

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

2.3 生成賦權(quán)完全圖

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

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

函數(shù)GenWCG(SN)

過程：

Step 1. 點集V=SN

Step 2. 邊集E=V×V

輸出：賦權(quán)完全圖WCG=〈V,E,W〉

2.4 生成最小生成樹

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

函數(shù)GenMST(WCG)

輸入：賦權(quán)完全圖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 生成剪枝閾值

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

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

(1)

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

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

max(EIntra)

(2)

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

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

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

(3)

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

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

(4)

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

函數(shù)GenPT(MST)

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

過程：

Step 1.提取MST邊集的一維權(quán)重空間S1

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

Step 3.閾值PT=min(W2)

輸出：閾值PT

2.6 剪枝分裂

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

函數(shù)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 離群點過濾

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

函數(shù)Filter(F)

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

過程：

Step 1.C=ConnectedComponents(F)

Step 2.forci∈Cdo

if|ci|<3then

C=C-{ci}

endif

endfor

輸出：簇集合C

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

3 實驗與分析

3.1 實驗描述

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

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

數(shù)據(jù)集凹凸性簇形狀DS1凸凸形DS2混合半圓形+凸形DS3混合環(huán)形+凸形

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

表2 經(jīng)典UCI數(shù)據(jù)集特征
Table 2 Characteristic of UCI datasets

數(shù)據(jù)集維度樣本數(shù)類別數(shù)Iris41503Wine131783Glass102147

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

3.2 實驗結(jié)果與分析

3.2.1 二維隨機數(shù)據(jù)集

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

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

聚類算法凸形半圓形環(huán)形K-means√××MSTCluster√√√MNC√√√

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

圖2 二維數(shù)據(jù)集DS1的聚類效果Fig.2 Clustering result of DS1

圖3 二維數(shù)據(jù)集DS2的聚類效果Fig.3 Clustering result of DS2

圖4 二維數(shù)據(jù)集DS3的聚類效果Fig.4 Clustering result of DS3

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

3.2.2 經(jīng)典UCI數(shù)據(jù)集

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

表4 UCI數(shù)據(jù)集聚類后的RAND系數(shù)
Table 4 RAND coefficients for UCI datasets clustering

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

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

迭代實驗中傳統(tǒng)K-means的輸入?yún)?shù)(簇數(shù)k初始取值為2、迭代步長為1)和MSTCluster的輸入?yún)?shù)(調(diào)節(jié)因子初始取值為1、迭代步長為0.2)的最終取值總結(jié)如表5.

表5 輸入?yún)?shù)的迭代統(tǒng)計
Table 5 Statistics of iterative input parameters

聚類算法輸入?yún)?shù)最終取值DS1DS1DS2IrisWineGlassK-means簇數(shù)k 665337MSTCluster調(diào)節(jié)因子λ1.61.62.02.21.82.0

從上述結(jié)果可見針對不同形狀數(shù)據(jù)集，傳統(tǒng)K-means和MSTCluster的輸入?yún)?shù)在迭代停止時各不相同.由于不同形狀數(shù)據(jù)集的最優(yōu)化參數(shù)無法提前預知，所以本文MNC算法的非參數(shù)化特點具有很大優(yōu)勢.

3.2.3 運行時間統(tǒng)計

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

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

表6 運行時間統(tǒng)計
Table 6 Statistics of runtime

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

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

4 總 結(jié)

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