基于距離的K－Means劃分式聚類算法及其編程實現(xiàn)

馬寶秋，連翠玲，趙 旭

（1.石家莊職業(yè)技術學院 機電工程系，河北 石家莊 050081；2.河北省科學院自動化研究所，河北 石家莊 050091）

俗話說：“物以類聚，人以群分”，在自然科學和社會科學中，存在著大量的分類問題。

類，就是指相似元素的集合。聚類就是按照事物間的相似性進行區(qū)分和分類的過程，實際就是一種分組的過程。聚類分析又稱群分析，它是研究（樣品或指標）分類問題的一種統(tǒng)計分析方法，可以作為其他分析算法的一個預處理步驟。聚類同分類不同，聚類并不關心某類是什么。聚類的目標只是把相似的東西聚到一起，因此一個聚類算法通常只需要知道如何計算相似度就可以了。

聚類分析以相似性為基礎，其由若干模式組成。這里的“模式”是指根據(jù)一個度量標準所得到的結(jié)果。在一個聚類中的模式之間比不在同一聚類中的模式之間具有更多的相似性，也就是讓在同一個聚類集合中的成員對象都有相似的一些屬性。所以，聚類分析主要依賴于對被觀測對象間的接近程度或相似程度的理解，例如對象間的距離，顏色相似度等。也正因為如此，定義不同的距離量度和相似性量度就可以產(chǎn)生不同的聚類結(jié)果。

聚類分析內(nèi)容非常豐富，有不同的聚類方法。例如劃分法（分割式）、層次法（階層式）、基于密度的方法、基于網(wǎng)格的方法、基于模型的方法等等［1］［2］。本文所論述的K－Means算法是劃分法中的一種。劃分式聚類算法在實現(xiàn)時需要首先確定聚類數(shù)量和聚類中心位置，然后根據(jù)劃分原則通過反復迭代運算，逐步降低目標函數(shù)的誤差值，使聚類中心接近實際聚類中心。當目標函數(shù)值收斂時，就會得到最終聚類結(jié)果［1］。

1 K－Means算法

給定一個由N 個元素組成的數(shù)據(jù)集，構(gòu)造K（K＜N）個聚類，每一個聚類實際就是一個分組。數(shù)據(jù)對象和分組間滿足以下要求：

（1）每一個分組至少包含一個數(shù)據(jù)對象；

（2）每一個數(shù)據(jù)對象屬于且僅屬于一個分組。

對于給定的K個聚類，按照給出的分組方法規(guī)則（算法）通過反復迭代的方式改變分組，使得每迭代一次之后的分組結(jié)果都比前一次更接近真實分組情況。我們可以把——同一分組中的數(shù)據(jù)對象按算法所得到的結(jié)果越接近越好，而不同分組中的數(shù)據(jù)對象按算法所得到的結(jié)果越遠越好，作為確定接近真實分組的標準［2］。

把N個數(shù)據(jù)聚類為K類的K－Means算法數(shù)學表達如下：

其中：Ji為第i類聚類的目標函數(shù)；

K為聚類個數(shù)；

Xj為第j個輸入向量；

Ci為第i個聚類中心（向量）；

wji為權重（Xj是否屬于聚類Ci）。

wji滿足以下關系：

因為每個數(shù)據(jù)對象都有其權重wji，這樣就由wji構(gòu)成了一個矩陣，該矩陣也稱為隸屬度矩陣。如圖1所示為有9個數(shù)據(jù)，分3個聚類的隸屬度矩陣。

圖1 隸屬度矩陣

K－means算法根據(jù)不同應用可以確定不同的算法模式，本數(shù)學表達式算法模式是基于求各個數(shù)據(jù)對象與其對應聚類中心點距離平方和的值最小，屬于劃分法，也稱為C－Means算法。

2 K－Means算法的實現(xiàn)步驟

根據(jù)上節(jié)K－means數(shù)學表達式的算法，可知，按照以下幾步即可實現(xiàn)本算法［3］。

步驟1：初步確定聚類中心。隨機選取K個數(shù)據(jù)點Ci，i＝1，…，K，并將之分別視為各聚類的初始中心。

步驟2：根據(jù)確定的聚類中心進行分組。也就是根據(jù)計算規(guī)則判斷各數(shù)據(jù)對象屬于哪一個聚類，若某個數(shù)據(jù)對象Xj被判定屬于第i個聚類，則其權重值wji＝1，否則為0。

步驟3：判斷聚類中心是否收斂。由（1）式計算目標函數(shù)J，如果J的結(jié)果保持不變或其變化達到允許的精度范圍內(nèi)，代表聚類結(jié)果已經(jīng)穩(wěn)定不變或可以接受，則可結(jié)束此迭代方法，否則進入步驟4

步驟4：更新聚類中心。以（4）式更新聚類的中心點?；氐讲襟E2

式（4）是通過對（1）式求最小值得到的，若求（1）式最小值，求下式最小值即可：

令F’＝0，則可導出（4）式。

針對二維圖像實現(xiàn)K－Means算法編程的計算機偽代碼步驟如下［4］：

（1）設定聚類數(shù)目K，允許的最大執(zhí)行步驟tmax和一個很小的容忍誤差ε＞0；

（2）隨機或人為決定聚類中心起始位置Cj（x，y）0，0＜j≤K；

（3）fort＝1，…，tmax

（A）forj＝1，…，N

（i）計算圖像中各點到聚類中心的距離；

（ii）計算各圖像點屬于哪一聚類（建立隸屬度矩陣）；

（B）更新聚類中心；

（C）根據(jù)收斂準則計算，若E（t）＝‖J（t）－J（t－1）‖＜ε成立則退出循環(huán)，否則進行下一輪迭代。

Nextt

（4）若t循環(huán)正常結(jié)束，則所得到的Ci（xi，yi），i＝1，…，K，即為每個聚類的中心點。

若t循環(huán)是因為達到tmax而結(jié)束，則表示所聚類的數(shù)據(jù)是發(fā)散的，沒有聚類中心；或者在限定的次數(shù)內(nèi)聚類中心還不穩(wěn)定，可以采用增大循環(huán)次數(shù)tmax的方式解決。

筆者通過以上方法實現(xiàn)了基于距離劃分的K－Means聚類算法。對于筆者分類應用中的一個結(jié)果如圖2所示。

圖2 K－Means算法驗證

3 算法實現(xiàn)中的注意事項

（1）需先設計數(shù)據(jù)輸入對話框，用來輸入聚類的數(shù)目K以及容忍誤差ε。

（2）通常情況下采用計算機隨機函數(shù)來產(chǎn)生聚類K個中心，但是針對具體的問題可以有一些啟發(fā)式的選取方法或者直接人工選取。

（3）計算圖像中各點到聚類中心的距離時，使用歐式幾何計算2點間距離即可。

（4）隸屬度矩陣保存于一個2維數(shù)組中。內(nèi)層j循環(huán)每循環(huán)一次，根據(jù)結(jié)果對矩陣中的數(shù)值進行相應的修改。

（6）所得到的計算結(jié)果是各個聚類分組的幾何中心。

4 算法總結(jié)

K－Means算法在運算過程中沒有任何先驗的知識可以應用，因此是一種無監(jiān)督的分類［1］［5］。每個聚類結(jié)果都屬于高斯分布。大多數(shù)情況下能夠給出令人滿意的結(jié)果，算是一種簡單高效應用廣泛的聚類方法。

K－Means聚類算法也有其局限的方面。首先，初值的選取對是否能收斂到全局最優(yōu)解有很大的關系。因為初始聚類中心位置可能是隨機函數(shù)產(chǎn)生的，即不是理想的位置，使得目標函數(shù)J很容易落入局部解，不能保證全局最優(yōu)，導致分類出來的結(jié)果不理想［6］。所以應該多次選取初值運行K－Means，并取其中最好的一次結(jié)果。

其次，運算量大，因為每迭代一次就需要遍歷所有數(shù)據(jù)一遍，其運算復雜度為O（tKmn），其中，t為迭代次數(shù)，K為聚類數(shù)，m為特征屬性數(shù)，n為待分類的對象數(shù)［1］。因此該算法的數(shù)值運算量較大，對于大的數(shù)據(jù)量一般不能進行實時運算。

第三，所產(chǎn)生每個聚類的大小相差不會很大，而且對于噪聲數(shù)據(jù)很敏感。

第四，該算法聚類結(jié)果以近圓形為主，對于圖3所示的圖形就不適合分類了；對于這種情況可以采用基于密度的方法進行分類。這樣就能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點。

最后，該算法是一種硬劃分，它把每個待辨識的對象嚴格地劃分到某個類中，具有非此即彼的性質(zhì)，對于一些特殊的場合就不合適了。

5 結(jié)束語

論述了基于歐式距離的劃分式K－Means算法，筆者使用C＋＋編程實現(xiàn)本文算法，并應用于“基于實時超聲影像的軟組織形變跟蹤技術”課題軟件中，實現(xiàn)了對感興趣區(qū)域（ROI）的前期分類，為后續(xù)的圖像處理打下了堅實的基礎。但由于其固有的缺點，還不能夠滿足實時性的需要，后續(xù)工作中將對其進行進一步的改進以提高系統(tǒng)實時性。

圖3 不規(guī)則分布數(shù)據(jù)的分類

［1］孫吉貴，劉杰，趙連宇.聚類算法研究［J］.軟件學報，2008，19（1）：48－61.

［2］蔡元萃，陳立潮.聚類算法研究綜述［J］.科技情報開發(fā)與經(jīng)濟，2007，17（1）：145－146.

［3］步媛媛，關忠仁.基于K－means聚類算法的研究［J］.西南民族大學學報·自然科學版，2009，35（1）：198－200.

［4］陳壽文，李明東.基于面向?qū)ο笏枷隟－Means算法實現(xiàn)［J］.滁州學院學報，2008，10（3）：42－44.

［5］楊燕，靳蕃，KAMEL Mohamed.聚類有效性評價綜述［J］.計算機應用研究，2008，25（6）.

［6］韓曉紅，胡彧.K－means聚類算法的研究［J］.太原理工大學學報，2009，40（3）：236－239.