K-means聚類算法性能分析與優化研究

楊 柳

(西安電子工程研究所 西安 710100)

0 引言

隨著信息技術的高速發展，數據對社會生產與生活中諸多領域的影響越來越突出，大量的數據應用于軍事及民用領域中，數據與生產生活的關系愈發緊密。如何從海量數據中提煉出有用的信息使其更好地服務生活，成為當前面臨的難題。因此，數據挖掘技術在各行各業得到迅速地發展。數據挖掘技術是指從大量、無規則、有噪聲數據中挖掘出有價值的信息。聚類算法是數據挖掘的重要組成部分，是將數據以無監督方法，根據數據的特征劃分成多個簇，數據聚類分析是對數據進一步處理的基礎。常見的聚類的方法包括層次方法、劃分方法、網格方法、密度方法、模型方法[1]。

K-means聚類算法屬于劃分方法，是一種經典的聚類算法，具有簡潔易懂、快速有效等優勢，近年來受到廣泛關注。本文介紹了K-means算法的原理和實現過程，分析了K-means聚類算法的性能以及不同因子對K-means聚類算法的影響機理，為無監督聚類過程的設計與應用提供了理論指導。

1 數據聚類問題概述

聚類是指將數據集分成若干個不同的簇，同一簇內的數據相似度盡可能大，不同簇的相似度盡可能小。假設數據集A，A={a1,a2…aN}，其中N代表數據集中數據對象個數。聚類是把A中N個數據對象劃分成k個簇{C1,C2…Ci…Ck}，Ci表示第i個簇。聚類后的結果集表示為X[2]：

(1)

聚類問題的基本流程是，首先提取對象特征，判斷特征之間的相似程度。然后選取合適的聚類算法進行聚類，最后進行結果驗證。聚類分析是在無先驗知識的前提下進行聚類，在沒有訓練集條件下以數據之間的相似度差異將數據劃分成若干簇。數據差異性一般取決于數據之間的某種距離，依據數據的性質可以采用不同的距離，常用的歐式距離表示如下：

d(ai,aj)=

(2)

其中d(ai,aj)表示數據ai和aj之間的歐式距離，p表示數據ai的維度。

準則函數通常用來評價聚類質量，恰當的準則函數能夠有效促使相似度大的數據分配到同一個簇中，相似度低的數據分配到不同的簇。聚類算法中常見的準則函數包括誤差平方和準則、加權平均平方距離和及類間距離和準則等，其中誤差平方和準則Jc表示為：

(3)

式中nj是類Cj中對象的個數，mj類Cj的平均值，定義為

(4)

Jc可以用來描述N個數據對象需要劃分成k個類時，所產生的總的誤差平方和。Jc越大說明總的誤差平方和越大，表示聚類效果不好，所以應讓其值盡可能小。當各類樣本比較密集且樣本數目懸殊不大時使用誤差平方和準則較合適。

2 K-means聚類算法

基于劃分方法的聚類算法是將數據點的中心作為簇的質心，根據數據之間的相似性度為標準，使同一個簇內數據盡可能相似。劃分方法首先任意分配初始聚類，然后不斷地迭代改變每一次聚類分結果，但是要求每一迭代的聚類效果要優于上一次。劃分方法運行速度快，原理簡單，容易實現。K-means聚類算法是基于劃分方法的一種典型代表[2-4]。

K-means是一種動態迭代聚類算法，其中K表示類別(簇個數)，Means表示均值。K-Means利用數據點均值進行聚類。K-means算法開始執行之前需要給定參數K，確定數據集中簇的個數。然后確定K個類的質心，一般隨機選取K個數據作為簇的初始質心。接著執行數據聚類進程，計算剩余數據點到初始簇質點的相似程度，該相似程度可以使用距離或其他數據屬性特征，根據相似程度分配數據點到距離最近的簇中，接著重新計算當前簇中的所有數據點的均值，并依此均值作為簇的新質心，重復計算每個數據點到當前簇質心的距離，直到聚類中元素不再改變或是準則函數收斂到某一個值，算法結束迭代。

3 K-means算法的具體流程

1)在所有數據樣本中隨機選取K個數據對象作為初始聚類中心，c1,c2…ck；

2)遍歷所有數據，計算每個數據點相對各個聚類中心的歐氏距離d(ai,cj)(1≤i≤N,1≤j≤K)；

3)根據距離d(ai,cj)，將每個數據劃分到距離最近的中心點所屬類中；

4)計算每個簇的平均值，并作為新的中心點，參考公式(4)；

5)重復步驟2)～ 4)，直至準則函數收斂，或執行了足夠多的迭代。

4 聚類初始質心對聚類的影響

在K-means算法中，動態迭代依賴于隨機選取的K個初始聚類質心，算法每一次聚類結果都不相同。當K個質心分布在數據點集的各個簇中時，聚類效果良好。當某個簇中包含兩個聚類質心，且簇間離較遠時，就會導致簇的分裂以及另外兩個簇的錯誤合并，聚類效果較差。

針對K-means聚類算法中隨機選取初始質心的導致聚類質量不穩定的問題， K-means++算法對初始聚類中心進行了修正。K-means++算法與K-means算法都采用動態迭代的思想，主要改進是如何初始選取K個初始聚類質心。K-means++算法選取初始聚類中心時，假設當前已選取了n個初始聚類中心(0

K-means聚類算法的選擇初始質心的流程如下：

1)從數據點集中選取一個數據點作為初始聚類中心；

2)計算每個數據與當前已有聚類中心之間的最短距離D(i)；

3)選擇新的聚類中心，D(i)較大者成為聚類中心的概率越大；

4)重復2)和3)，直到選擇出K個聚類中心。

其中，步驟3)的具體實施方法是：

①累加每個數據點與距離最近的聚類中心點距離，累加和表示為sum(D(i))；

②在0到sum(D(i))之間取一個隨機值R，然后循環計算R=R-D(i)(i=i+1)，直到R≤0。此時的數據集A中的第i個數據點即為下一個聚類中心。

為了說明初始聚類質心對聚類結果的影響，本文隨機產生了一組數據點集，分別采用K-means算法和K-means++算法進行聚類。以數據點之間的歐式距離為標準，采用誤差平方和為準則函數。數據點集個數N=800，聚類個數K=6。

圖1 K-means算法聚類結果-隨機初始質心(a)

圖2 K-means算法聚類結果-隨機初始質心(b)

圖1和圖2給出了采用隨機初始質心時聚類結果，其中(a)和(b)代表不同的隨機值。對比圖1和圖2可以明顯地看出，當給定不同的初始聚類質心時，得到的聚類結果也不盡相同，且聚類效果并不理想，尤其是圖1的聚類結果。 圖3給出了K-means++算法聚類結果，對比原始數據點的分布可以看出，K-means++算法聚類結果更為合理。

圖3 K-means++算法聚類結果

5 聚類個數對聚類性能的影響

K-means聚類算法要求算法開始之前必須確定聚類個數 K值，該設置會對聚類結果產生一定的影響，同時也限制了其無監督聚類算法的應用。

一般化的聚類方法歸納為：

3)計算不同K值下的準則函數輸出；

4)搜尋準則函數的最大(最小值)對應的K值及聚類結果，或者尋找準則函數輸出轉折點對應的K值及聚類結果。

圖4 K-means++算法聚類結果-K=4

有效性值根據實際應用的不同可以采用不同的有效性值，常見的有效性函數可參考[6]。為了說明K值對聚類結果的影響，本文隨機產生了一組數據點集，采用K-means++算法進行聚類。以數據點之間的歐式距離為標準，采用誤差平方和為準則函數。數據點集個數N=800。

圖5 誤差平方和隨K值變化

從圖5給出的誤差平方和隨K值變化的趨勢可以看出，隨著聚類個數的不斷增加，整個聚類結果的誤差平方和不斷的減小。此時誤差平方和并不能完全反應聚類的效果。同時，大范圍的搜索也會導致資源的浪費，一種可行的方法是觀察誤差平方和的變化趨勢，當誤差平方和逐漸收斂時即可停止搜索過程。圖5中，當K≥4時，誤差平方和逐漸收斂，故K=4是一個相對合理的聚類個數，對應的聚類結果如圖4所示，與原始數據集分布可以看出，聚類結果基本有效的反映了原始數據集的分布特征。

6 結束語

本文首先回顧了聚類問題的相關理論基礎，然后針對基于劃分的聚類思想展開了討論，重點介紹了K-means和K-means++兩種聚類算法方法，并且討論了影響聚類性能的兩個重要問題，聚類初始質心和聚類個數對聚類性能的影響，通過仿真研究驗證了本文的觀點，下一步工作將深入開展無監督聚類算法在實際應用中的優化問題，包括算法收斂速度、相似度量函數選擇等。