動(dòng)態(tài)分配聚類中心的改進(jìn)K均值聚類算法

程艷云，周 鵬

(南京郵電大學(xué) 自動(dòng)化學(xué)院，江蘇 南京 210023)

動(dòng)態(tài)分配聚類中心的改進(jìn)K均值聚類算法

程艷云，周 鵬

(南京郵電大學(xué) 自動(dòng)化學(xué)院，江蘇 南京 210023)

K均值算法(KMEANS)是一種應(yīng)用廣泛的經(jīng)典聚類算法，但其有兩個(gè)缺陷，即對(duì)初始聚類中心敏感及需要人工確定聚類的個(gè)數(shù)，因而聚類結(jié)果的準(zhǔn)確率較低。針對(duì)K均值聚類算法現(xiàn)存的兩個(gè)缺陷，為提高算法的精確性與穩(wěn)定性，以及改善聚類性能，提出了一種改進(jìn)的K均值算法。該算法通過定義的平均類間最大相似度指標(biāo)值來確定最佳的K值，將所有數(shù)據(jù)點(diǎn)中密度較高的點(diǎn)作為備選聚類中心，將備選點(diǎn)中密度最大的兩個(gè)點(diǎn)作為聚類中心進(jìn)行初步聚類計(jì)算并更新當(dāng)前聚類中心。當(dāng)計(jì)算得到的平均類間最大相似度現(xiàn)值小于前次計(jì)算值，則依據(jù)相對(duì)距離原則從備選點(diǎn)中動(dòng)態(tài)選擇下一個(gè)聚類中心；否則，將當(dāng)前的聚類中心作為最佳初始聚類中心進(jìn)行K均值聚類計(jì)算。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法不僅能夠有效地提高聚類計(jì)算的精確性與穩(wěn)定性，而且還能縮短聚類計(jì)算時(shí)間，具有一定的技術(shù)優(yōu)勢(shì)和應(yīng)用前景。

KMEANS算法；動(dòng)態(tài)聚類中心；相對(duì)距離；高密度點(diǎn)

0 引 言

聚類分析是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重要分支，是一種無監(jiān)督的學(xué)習(xí)方式。聚類分析的主要應(yīng)用領(lǐng)域有機(jī)器學(xué)習(xí)、模式識(shí)別、文本挖掘、圖像分割及模式分類等[1]。人們根據(jù)不同領(lǐng)域的需求研究出了不同的聚類方法。主要分為基于層次的、基于網(wǎng)格的、基于密度的、基于劃分的聚類算法[2]。其中，使用最廣泛的是基于劃分的聚類算法。基于劃分的聚類算法大多是基于數(shù)據(jù)的距離估計(jì)，通過計(jì)算數(shù)據(jù)點(diǎn)與聚類中心之間的距離將數(shù)據(jù)點(diǎn)分配到最近的聚類中心所在的類中[3]。按這個(gè)思想，發(fā)展出了不同的聚類算法，最受歡迎的是KMEANS算法。KMEANS算法收斂速度快、算法簡單、能有效處理大數(shù)據(jù)集[4]。但它有兩個(gè)主要的缺點(diǎn)：手動(dòng)確定聚類個(gè)數(shù)和初始聚類中心選擇的隨機(jī)性[5]。

針對(duì)KMEANS算法主要從兩方面進(jìn)行改進(jìn)：獲得最佳聚類中心和獲得最佳聚類個(gè)數(shù)[6-7]。對(duì)于初始聚類中心的改進(jìn)，文獻(xiàn)[8]提出了最大最小距離的算法，選擇相互距離最遠(yuǎn)的K個(gè)數(shù)據(jù)對(duì)象作為初始聚類中心。文獻(xiàn)[9]提出了基于密度的改進(jìn)算法，將密度最大的K個(gè)點(diǎn)作為初始聚類中心。這些算法從不同程度上解決了初始聚類中心的隨機(jī)選擇性，一定程度上提高了聚類的精確性，但并沒有從根本上解決算法極易陷入局部最優(yōu)解的問題。對(duì)于聚類個(gè)數(shù)的改進(jìn)，目前的方法大多是人為定義一些指標(biāo)用于判斷是否達(dá)到最佳聚類個(gè)數(shù)。文獻(xiàn)[10]提出了一種確定最佳聚類個(gè)數(shù)的方法，比較K取所有可能值下的聚類結(jié)果，獲得最佳聚類個(gè)數(shù)。該方法可以確定最佳的聚類個(gè)數(shù)，但當(dāng)K值變化范圍很大時(shí)，需要花費(fèi)大量的時(shí)間和精力。文獻(xiàn)[11]提出了一種基于距離最大化的K值自動(dòng)生成算法。該方法一定程度上可以確定最佳的聚類個(gè)數(shù)，但若初始聚類中心選擇到那些異常點(diǎn)時(shí)，算法的精度將大幅下降。除此之外，還有一些改進(jìn)方法，如KMEANS算法與遺傳算法相結(jié)合[12-13]、KMEANS算法與蟻群算法相結(jié)合[14]等等。

文中在分析已有改進(jìn)算法的基礎(chǔ)上，提出一種新的改進(jìn)算法。該算法通過迭代能自動(dòng)獲得最佳的聚類個(gè)數(shù)，同時(shí)動(dòng)態(tài)分配下一個(gè)聚類中心以獲得當(dāng)前狀態(tài)下的最佳聚類中心。對(duì)于同一數(shù)據(jù)集，該算法有確定的聚類中心，所以它的聚類結(jié)果較穩(wěn)定。

1 KMEANS算法

在基于劃分式的聚類算法中，類被視為一種具有相似性質(zhì)的點(diǎn)簇。數(shù)據(jù)集中的點(diǎn)被劃分到不同的簇，是由它們到給定聚類中心的距離決定的。有幾種基于劃分式的聚類算法，如：KMEANS算法、KMEDOIDS算法、CLARANS算法。最常用的是KMEANS算法，其基本思想是，首先從數(shù)據(jù)集中隨機(jī)選擇K個(gè)數(shù)據(jù)對(duì)象作為初始聚類中心，將余下的數(shù)據(jù)對(duì)象依據(jù)它們與這些聚類中心的相似度(距離)分配到相應(yīng)的類中。然后計(jì)算每個(gè)類新的聚類中心，不斷重復(fù)這一過程，直到評(píng)價(jià)函數(shù)收斂。一般采用簇內(nèi)誤差平方和作為評(píng)價(jià)函數(shù)，其定義為：

(1)

其中，K為聚類個(gè)數(shù)；P為簇i內(nèi)的數(shù)據(jù)對(duì)象；ci為聚類中心。

聚類中心的更新依照式(2)：

(2)

KMEANS算法的執(zhí)行步驟如下[15]：

輸入：包含N個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集，聚類的個(gè)數(shù)K，算法終止條件(或迭代次數(shù))。

輸出：K個(gè)簇、評(píng)價(jià)函數(shù)值E、算法運(yùn)行時(shí)間等。

(1)隨機(jī)選擇K個(gè)數(shù)據(jù)對(duì)象作為初始聚類中心。

(2)計(jì)算余下的數(shù)據(jù)對(duì)象到這K個(gè)聚類中心之間的距離(相似度)，并將數(shù)據(jù)對(duì)象分配到距離最近的簇中。

(3)根據(jù)式(2)重新計(jì)算K個(gè)簇的聚類中心，并根據(jù)式(1)計(jì)算相應(yīng)的評(píng)價(jià)函數(shù)值E。

(4)如果達(dá)到最大的迭代次數(shù)或相鄰兩次的評(píng)價(jià)函數(shù)值之差小于ε，則算法停止。否則轉(zhuǎn)步驟(2)。

ε是一個(gè)人為定義的數(shù)值。當(dāng)相鄰兩次的評(píng)價(jià)函數(shù)值之差小于ε時(shí)，表明算法收斂。

KMEANS算法具有的優(yōu)點(diǎn)：簡單易實(shí)現(xiàn)，運(yùn)行速率快，能夠處理大型數(shù)據(jù)集。但KMEANS算法也有許多不便之處。例如：初始聚類中心的隨機(jī)選擇導(dǎo)致算法極易陷入局部最優(yōu)解。同時(shí)，算法需要首先確定聚類個(gè)數(shù)，而這一點(diǎn)是很難做到的。

圖1顯示相同數(shù)據(jù)集在不同初始聚類中心下的聚類結(jié)果。圖2顯示相同數(shù)據(jù)集在不同聚類數(shù)目下的聚類結(jié)果。圖中的數(shù)據(jù)集是人工數(shù)據(jù)集。很顯然，KMEANS算法的聚類精確度受初始聚類中心和聚類數(shù)目的影響很大。

圖1 同一數(shù)據(jù)集不同初始聚類中心下的聚類結(jié)果

2 改進(jìn)的KMEANS算法

在分析已有改進(jìn)算法的基礎(chǔ)上提出一種全新的改進(jìn)算法。該算法通過比較類間平均最大相似度可以自動(dòng)確定最佳的聚類個(gè)數(shù)，還能動(dòng)態(tài)調(diào)節(jié)當(dāng)前的聚類中心并動(dòng)態(tài)添加下一個(gè)聚類中心。該算法將密度度量和距離度量相結(jié)合，從高密度的備選點(diǎn)中選擇距離當(dāng)前更新后的聚類中心相對(duì)最遠(yuǎn)的點(diǎn)作為新的聚類中心添加到當(dāng)前聚類中心集合中。這樣做可以使不同類的聚類中心盡可能相互排斥，從而保證了類間的低相似性。同時(shí)，從高密度的備選點(diǎn)中選擇下一個(gè)聚類中心，這可以保證在同一個(gè)類中，聚類中心是一個(gè)相對(duì)密集區(qū)域的點(diǎn)，保證了類內(nèi)的高相似性。而類間低相似與類內(nèi)高相似也是對(duì)聚類結(jié)果好壞的一個(gè)評(píng)價(jià)指標(biāo)。對(duì)于一個(gè)數(shù)據(jù)集，最佳聚類個(gè)數(shù)一定，使用該算法獲得的聚類中心也是固定的，這保證了算法的穩(wěn)定性。

圖2 同一數(shù)據(jù)集在不同聚類個(gè)數(shù)下的聚類結(jié)果

一些相關(guān)的概念及公式定義如下：

點(diǎn)密度：點(diǎn)xi的r鄰域內(nèi)點(diǎn)的個(gè)數(shù)。

Density(xi)={p∈c|dist(xi,p)≤r}

(3)

其中，xi為類i的聚類中心；r為人為定義的鄰域半徑。

類內(nèi)距離：類中每個(gè)點(diǎn)到聚類中心之間的距離的均值。

(4)

類間距離：不同類的聚類中心之間的距離。

di,j=‖ci-cj‖

(5)

這里數(shù)據(jù)對(duì)象之間的距離均采用歐氏距離進(jìn)行度量。

平均類間最大相似度(AMS)：每一個(gè)類與其他類之間的最大相似度的均值。

(6)

當(dāng)AMS取得最小值時(shí)，說明聚類效果最佳，此時(shí)的K就是最佳的聚類個(gè)數(shù)。

①冰崩和冰滑坡是引起冰湖潰決的主要誘因。應(yīng)從遙感、GIS和野外調(diào)查三個(gè)層面及其組合對(duì)冰磧湖進(jìn)行系統(tǒng)監(jiān)測(cè)。冰磧湖潰決參數(shù)包括冰磧湖參數(shù)、冰磧壩參數(shù)、母冰川參數(shù)、冰湖盆參數(shù)以及它們之間的相互關(guān)系。當(dāng)前有一些經(jīng)驗(yàn)方法可以對(duì)潰決風(fēng)險(xiǎn)進(jìn)行定量評(píng)估。

改進(jìn)后算法的執(zhí)行步驟如下：

輸入：包含N個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集，用于判斷點(diǎn)密度的鄰域半徑r，作為備選初始聚類中心的高密度點(diǎn)個(gè)數(shù)M，初始的AMS值，算法的終止條件。

輸出：K個(gè)簇、評(píng)價(jià)函數(shù)值E、算法運(yùn)行時(shí)間。

(1)計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的點(diǎn)密度，并將點(diǎn)密度最大的M個(gè)點(diǎn)加入到備選點(diǎn)集D中。

(2)從集合D中選出密度最大的兩個(gè)點(diǎn)作為初步聚類中心，并將其從D中刪除。

(3)從集合D中選擇距離前兩個(gè)聚類中心最遠(yuǎn)的點(diǎn)，作為下一個(gè)聚類中心，并將其從D中刪除。

(4)將N個(gè)數(shù)據(jù)點(diǎn)根據(jù)以上聚類中心進(jìn)行一次迭代劃分，并計(jì)算AMS值。

(5)如果新獲得的AMS值小于上一次的AMS值，算法繼續(xù)，轉(zhuǎn)步驟(6)。否則，以AMS最小時(shí)所對(duì)應(yīng)的聚類中心作為KMEANS算法的初始聚類中心，轉(zhuǎn)步驟(7)。

(7)進(jìn)行KMEANS聚類。

這里進(jìn)行最后一步聚類的聚類中心是經(jīng)過K-1次動(dòng)態(tài)分配而獲得的最佳K個(gè)聚類中心。它是嚴(yán)格按照數(shù)據(jù)的特點(diǎn)產(chǎn)生的，而不是隨機(jī)選擇的，因此可以有效避免聚類結(jié)果的波動(dòng)性。同時(shí)，由這種機(jī)制產(chǎn)生的最佳聚類中心可以很好地避開離群點(diǎn)(那些誤差很大的點(diǎn))，因此可以在較大程度上提高聚類的準(zhǔn)確性。

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)描述

為驗(yàn)證文中改進(jìn)算法的聚類準(zhǔn)確性和穩(wěn)定性，選用UCI數(shù)據(jù)庫上的Iris、Wine、Seeds、Breast共4組數(shù)據(jù)作為測(cè)試數(shù)據(jù)。由于傳統(tǒng)的KMEANS聚類算法和改進(jìn)的最大最小距離聚類算法對(duì)初始聚類中心的選擇具有隨機(jī)性，故對(duì)上述兩種算法取20次實(shí)驗(yàn)結(jié)果的均值作為最終的聚類結(jié)果。UCI數(shù)據(jù)庫是一個(gè)專門用于測(cè)試機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘算法的數(shù)據(jù)庫。庫中的數(shù)據(jù)都有明確的分類，因此可用UCI數(shù)據(jù)來檢測(cè)聚類算法的準(zhǔn)確率。表1是用于測(cè)試的4組數(shù)據(jù)的屬性。

3.2 實(shí)驗(yàn)結(jié)果

用隨機(jī)選擇初始聚類中心的KMEANS算法和改進(jìn)的最大最小距離KMEANS算法以及文中改進(jìn)算法對(duì)以上4組測(cè)試數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。表2是這4組數(shù)據(jù)集在不同聚類算法下的聚類準(zhǔn)確率。

表1 測(cè)試數(shù)據(jù)集屬性

表2 傳統(tǒng)KMEANS算法與改進(jìn)算法的準(zhǔn)確率 %

由表1及表2可以看出，傳統(tǒng)算法在相同聚類數(shù)目下，數(shù)據(jù)維度越大，聚類結(jié)果精確率越低。數(shù)據(jù)總量對(duì)聚類結(jié)果的精確率也有影響，但影響程度低于數(shù)據(jù)維度的影響。此外，聚類數(shù)目對(duì)聚類精確度的影響也很大。文中提出的動(dòng)態(tài)聚類算法相比傳統(tǒng)的聚類算法和改進(jìn)的最大最小距離算法而言，能夠不同程度地提高聚類精確度。

表3是4組數(shù)據(jù)集在這三種聚類算法下的評(píng)價(jià)函數(shù)值(總的誤差)。評(píng)價(jià)函數(shù)是用于判斷一個(gè)聚類效果好壞的重要指標(biāo)。評(píng)價(jià)函數(shù)值越小，聚類效果越好。

表3 傳統(tǒng)KMEANS算法與改進(jìn)算法的評(píng)價(jià)函數(shù)值

由表3可以看出，最大最小距離算法雖然可以提高聚類算法的精確率，減小誤差值，但該算法具有一定的適用范圍。在Breast數(shù)據(jù)集上，最大最小距離算法提高了聚類精確率，但誤差值卻比傳統(tǒng)算法要大。相比于前兩種算法，文中算法可以較好地降低誤差值。這也一定程度上說明了文中算法具有一定的優(yōu)勢(shì)。

圖3是4組測(cè)試數(shù)據(jù)集在這三種聚類算法下的聚類時(shí)間曲線(單位：s)。

可以看出，最大最小距離算法在Breast數(shù)據(jù)集上的運(yùn)行時(shí)間要比傳統(tǒng)K均值算法長，說明了最大最小距離算法具有一定適用范圍。文中提出的動(dòng)態(tài)聚類算法相比以上兩種算法，能夠很好地縮短運(yùn)行時(shí)間，提高算法效率。

圖3 三種聚類算法的聚類時(shí)間曲線

3.3 實(shí)驗(yàn)分析

綜合以上實(shí)驗(yàn)結(jié)果可知，傳統(tǒng)的K均值算法在數(shù)據(jù)對(duì)象增加或數(shù)據(jù)維度加大的情況下，聚類準(zhǔn)確率有所下降。當(dāng)聚類個(gè)數(shù)增加時(shí)，聚類結(jié)果的準(zhǔn)確率下降最明顯。改進(jìn)的最大最小距離算法一定程度上提高了算法的聚類精度，但對(duì)于某些數(shù)據(jù)集，它的運(yùn)行時(shí)間以及評(píng)價(jià)函數(shù)值甚至要超過傳統(tǒng)的K均值聚類算法。這說明改進(jìn)的最大最小距離聚類算法只適用于某些特定的數(shù)據(jù)集。文中提出的改進(jìn)算法在聚類準(zhǔn)確率方面具有很大的提高。同時(shí)，與前兩種算法相比，很好地降低了聚類時(shí)間開銷。從評(píng)價(jià)函數(shù)值指標(biāo)也可以看出這種算法具有一定的優(yōu)越性。

4 結(jié)束語

文中提出的動(dòng)態(tài)分配聚類中心的聚類算法對(duì)聚類結(jié)果的準(zhǔn)確率有很大的提高。相比于傳統(tǒng)的K均值聚類算法和改進(jìn)的最大最小距離算法，由于每種數(shù)據(jù)集的數(shù)據(jù)對(duì)象一定，經(jīng)過動(dòng)態(tài)分配的初始聚類中心一定，故該算法的聚類結(jié)果較穩(wěn)定。但這種算法需要計(jì)算每個(gè)數(shù)據(jù)對(duì)象對(duì)于給定鄰域內(nèi)的密度，故隨著數(shù)據(jù)集中數(shù)據(jù)對(duì)象的增大，其時(shí)間復(fù)雜度也會(huì)隨之增加。當(dāng)數(shù)據(jù)對(duì)象十分龐大時(shí)，如何降低該算法的時(shí)間復(fù)雜度，將是下一步需要解決的問題之一。

[1]KanungoT,MountDM,NetanyahuNS,etal.AnefficientK-meansclusteringalgorithm:analysisandimplementation[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,2002,24(7):881-892.

[2] 倪志偉,倪麗萍,劉慧婷,等.動(dòng)態(tài)數(shù)據(jù)挖掘[M].北京:科學(xué)出版社,2010.

[3]ChaventM,LechevallierY,BriantO.Monotheticdivisivehierarchicalclusteringmethod[J].ComputationalStatistics&DataAnalysis,2007,52(2):687-701.

[4]SudiptoG,RajeevR,KyuseokS.Cure:anefficientclusteringalgorithmforlargedatabases[J].InformationSystems,1998,26(1):35-58.

[5]XuJinhua,LiuHong.Webusersclusteringanalysisbasedonk-meansalgorithm[C]//IEEE2010internationalconferenceoninformation,networkingandautomation.Kunming,China:IEEE,2010.

[6]LouhichiS,GzaraM,AbdallahHB.Adensitybasedalgorithmfordiscoveringclusterswithvarieddensity[C]//IEEE2014worldcongressoncomputerapplicationandinformationsystems.Hammamet,Tunisia,American:IEEE,2014:1-6.

[7]YedlaM,PathakotaSR,SrinivasaTM.Enhancingk-meansclusteringalgorithmwithimprovedinitialcenter[J].InternationalJournalofComputerScienceandInformationTechnologies,2010,1(2):121-125.

[8] 周 涓,熊忠陽,張玉芳,等.基于最大最小距離法的多中心聚類算法[J].計(jì)算機(jī)應(yīng)用,2006,26(6):1425-1427.

[9] 韓凌波,王 強(qiáng),蔣正鋒,等.一種改進(jìn)的K-means初始聚類中心選取算法[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(17):150-152.

[10] 周世兵,徐振源,唐旭清.K-means算法最佳聚類數(shù)確定方法[J].計(jì)算機(jī)應(yīng)用,2010,30(8):1995-1998.

[11] 劉鳳芹.K-means聚類算法改進(jìn)研究[D].濟(jì)南:山東師范大學(xué),2013.

[12]GriraN,CrucianuM,BoujemaaN.Activesemisupervisedfuzzyclustering[J].PatternRecognition,2008,41(5):1834-1844.

[13]CristoforD,SimoviciDA.Aninformationtheoreticalapproachtoclusteringcategoricaldatabasesusinggeneticalgorithms[C]//ProcofSIAMICDM.Arlington,American:[s.n.],2002.

[14] 鞏敦衛(wèi),蔣余慶,張 勇,等.基于微粒群優(yōu)化聚類數(shù)目的K-均值算法[J].控制理論與應(yīng)用,2009,26(10):1175-1179.

[15]ZhangZhe,ZhangJunxi,XueHuifeng.ImprovedK-Meansclusteringalgorithm[C]//Congressandsignalprocessing.[s.l.]:[s.n.],2008:169-172.

ImprovedK-means Clustering Algorithm for Dynamic Allocation Cluster Center

CHENG Yan-yun，ZHOU Peng

(School of Automation，Nanjing University of Posts and Telecommunications，Nanjing 210023，China)

KMEANS algorithm is a classical clustering algorithm with popular application.However,there are two defects of it known as sensitivity to initial cluster centers and clustering number needs to determine.Thus,the accuracy of clustering results is rather low.In order to improve its accuracy and stability and ameliorate its clustering performance,an improvedK-meansclusteringalgorithmhasbeenpresentedandacquired.OptimumKvalueisdeterminedfortheimprovedalgorithmbydefiningaveragemaximumsimilarityindexbetweenclasses,andthentwopointswithhighestdensityareselectedasclustercentersforinitialKMEANSclusteringandupdatingthecurrentclustercenteraftertheoneswithhigherdensityhavebeentakenascandidateclusteringcenters.Ifthecurrentvalueofaveragemaximumsimilarityindexbetweenclassesislessthantheformer,thennextclustercenterisdynamicallychosenfromcandidateclustercentersbyprincipleofrelativedistance.Otherwise,thecurrentcenteristakenasoptimumclustercenterforKMEANSclustering.Resultsofexperimentsshowthattheimprovedalgorithmcaneffectivelyboostclusteringaccuracyandstabilityandshortentheclusteringtime.Italsoimpliesbothdefinitetechnicaladvantagesandperspectiveforapplicationoftheimprovedalgorithm.

KMEANS algorithm;dynamic clustering center;relative distance;high density point

2016-04-06

2016-08-17

時(shí)間：2017-01-10

江蘇省自然科學(xué)基金(BK20140877,BK2014803)

程艷云(1979-)，女，副教授，碩士生導(dǎo)師，從事自動(dòng)控制原理、網(wǎng)絡(luò)優(yōu)化的教學(xué)科研工作；周 鵬(1991-)，男，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘與智能計(jì)算。

http://www.cnki.net/kcms/detail/61.1450.TP.20170110.1029.078.html

TP

A

1673-629X(2017)02-0033-04

10.3969/j.issn.1673-629X.2017.02.008