Ｋ－ｍｅａｎｓ算法的初始點優化研究

摘要：為了克服經典K-means算法對初始聚類中心過分依賴的缺點，該文提出采用競爭神經網絡和密度思想對經典k-means算法進行預處理，從而改變經典K-means算法對初始聚類中心的隨機選擇。實驗結果表明，這兩種方法是有效的。

關鍵詞：聚類；k-means；算法；實驗

中圖分類號：TP311文獻標識碼：A 文章編號：1009-3044(2008)32-1176-02

Study on the Initial Centrists of K-means Algorithm

MOU Ying1， QUAN Tai-feng2

(1.College of Physics and Information Technology， Chongqing Normal University， Chongqing 400047，China;2.Chongqing Communication Institute， Chongqing 400035， China)

Abstract: In order to conquer the problem that k-means algorithm depends on initial cluster centrists， so this paper discusses use competition neural network and the mind of density to improve the classic k-means algorithm. The two methods are able to improve the random choice of the initial centrists in the classic k-means algorithm. Experimental results show that the two algorithms are effective.

Key words: clustering; K-means; algorithm; experiment

1 引言

聚類是將數據對象分組成為多個類或簇，在同一個簇中對象之間具有較高的相似度，而不同簇中的對象之間差別較大[1]。在聚類算法中，K-means算法是其中一種最常用最知名的劃分方法[2]，它根據事先確定的K值，把樣本分為K類，使所有樣本到聚類中心的距離平方和最小。現在K-means算法已經應用到各種領域，包括圖像和語音數據壓縮，用徑向基函數網絡進行系統建模的數據處理等[3]，但經典K-means算法在運行初期隨機產生聚類初始點；如果初始聚類點離數據本身中心較近，則算法運行效率較高否則反之。

本文將競爭神經網絡和經典K-means算法相結合，提出一種基于競爭神經網絡的K-means算法。另外還采用基于密度的思想進行尋找初始聚類中心，從而改變經典K-means算法對初始聚類中心的隨機選擇。實驗結果表明，這兩種方法有效的克服了K-means對初始聚類中心的依賴性。

2 經典K-means算法

經典K-means算法的基本思想是：給定一個包含n個數據對象的數據庫，以及要生成的簇的數目k，隨機選取k個對象作為初始的聚類中心，然后計算剩余各個樣本到每一個聚類中心的距離，把該樣本歸到離它最近的那個聚類中心所在的類，直到調整結束且聚類平均誤差準則函數E已經收斂。

K-means算法的具體描述如下：

1）任選k個對象特征矢量作為初始聚類中心：z1(0)，z2(0)…zk(0)，令t=0

2）將待分類的對象特征矢量集{xi}中的對象逐個按最小距離原則分配給k類中的某一類，即

如果

i=1，2，…N(1)

則判xi∈wi(t+1)。

其中dij(t)表示xi和wj(t)的中心zj(t)的距離，上角標表示迭代次數。于是產生新的聚類wj(t+1)(j=1，2，…，k)。

3）計算重新分類后的各類心

式中nj(t+1)為wj(t+1)類中所含對象的個數。

因為這一步采取平均的方法計算調整后各類的中心，且定為k類，故稱K－均值法。

4）如果Zj(t+1)=Zj(t)(j=1，2，…，k)，則結束；否則，t=t+1，轉至（2）

經典K－means算法的計算復雜度為O(nkt)，其中，n為對象個數，k為聚類個數，t為循環次數。由于它要求用戶輸入希望產生聚類的數目，而實際中的k值也很難被精確的確定，往往表現為一個模糊的取值區間[4]。并且在經典K-means算法中，首先需要根據初始聚類中心來確定一個初始劃分，然后對初始劃分進行優化。這個初始聚類中心的選擇對聚類結果有較大的影響，一旦初始值選擇得不好，可能無法得到有效的聚類結果，所以這個算法的聚類結果對初值的依賴是很強的，這也成為K-means算法的一個主要問題。然而其方法簡單，結果尚令人滿意，故應用較多。

3 兩種改進算法介紹

3.1 基于競爭神經網絡的K-means算法

競爭神經網絡是基于生物神經系統中的“側抑制”現象形成的。競爭神經網絡的顯著特點是它的輸出神經元相互競爭以確定勝者，勝者指出哪一種原型模式最能代表輸入模式。競爭神經網絡是一種“自發”分類器，一種基于感知機的無監督的神經網絡[5]。因此利用競爭神經網絡來對經典K-means算法的初始聚類點進行改進，使改進后的K-means算法的初始聚類中心穩定的靠近于數據本身的類中心，從而減少經典K-means的循環次數。

考慮到競爭神經網絡的建網速度，在訓練競爭神經網絡的時候，將原始數據按照10%進行采樣，用采樣后的數據建立競爭神經網絡。按照競爭神經網絡的聚類結果，將簇中數據的均值作為初始聚類中心輸入經典的K-means算法，從而起到優化初始聚類中心的作用。具體的采樣方法是，以α為半徑畫圓，在這個圓內隨機選取數據點的10%作為采樣數據，α越小，其采樣頻率越高，采樣到的數據越多；α越大，其采樣頻率越低，采樣到的數據越少。當α取一個較適中的值的時候，采樣到的數據可以反映原始數據的分布，也能夠有效的減少數據量。

圖1為基于競爭神經網絡的K-means算法的流程圖。

算法描述如下：

1）從文件中讀出數據。

2）利用最小－最大規范化操作將數據的每個屬性映射到 空間。

3）采用歐式距離，計算各個數據之間的相異度矩陣。

4）計算Davg=AVG(Dij)，α=Davg/2即α取數據平均相異度的一半。以α為半徑，按10％的采樣頻率進行數據采樣。

5）將采樣后的數據輸入競爭神經網絡進行初始聚類。

6）將初始聚類產生的各個簇的對象的均值作為經典K-means算法的初始聚類中心。

7）運行經典K-means算法。

3.2 一種基于密度的K-means算法

由于經典的K-means算法對聚類個數和初始聚類中心存在依賴性的問題，所以其結果可能是局部最優的。如果隨機選擇的聚類初始點靠近于數據本身的中心，則算法運行的循環次數少，而且數據分類也比較合乎實際；當隨機選擇的初始聚類點不是很好的時候，算法運行的循環次數會增加，而數據分類也在一定程度上趨向于局部最優。這個改進思路就想利用數據的分布，尋找能夠代表不同簇的數據，并利用他們周圍的數據來對這些數據進行修正，試圖尋找比較靠近于數據本身中心的初始聚類點。具體來說，首先尋找相距最遠的兩個點A和B，認為他們代表數據的兩個簇。然后選取一個點C，使AC和BC的距離都大于某一個值，如此重復，直到找到k個代表點。接著在每個代表點附近尋找α·n/k個點，其中α表示采樣頻率，n表示數據個數，k表示簇數目。這些點和該代表點屬于同一簇，然后對這些認為屬于各簇的數據求平均，將得到的k個初始聚類點輸入經典K－means算法。圖2為一種基于密度的K-means算法的流程圖。

算法描述如下：

1）從文件中讀出數據。

2）輸入k，表示數據需要聚成幾類。

3）利用最小－最大規范化操作將數據的每個屬性映射到[0，1]空間。

4）采用歐式距離，計算各個數據之間的相異度矩陣。

5）尋找兩個相距最遠的點，設為A和B，將它們作為簇中心，置h=2。

6）如果k>h，尋找一個點C，使C到已有簇中心的聚類大于ymax-β，其中ymax=(Davg+MAX(Dij))/2，Davg=AVG(Dij) (0<β<1)，置h=h+1，重復這一步直到h=k，其中的β典型值是0.05。

7）在這k個點的周圍，尋找與其最近的α·n/k個點，其中α=0.1。

8）將這些認為屬于某個簇的點做平均，將他們的均值作為經典K-means算法的初始聚類中心。

9）運行經典K-means算法。

4 實驗

4.1 測試數據

本文的算法均使用matlab進行仿真實驗，并與經典K-means算法進行比較。為了便于更加直觀的觀察聚類結果，采用了主元分析（PCA）進行降維處理，將數據投影到3維空間上進行顯示。實驗測試數據采用來自UCI測試庫的專門用于測試分類、聚類算法的Iris數據庫，以及一組客觀的個人信用數據。表1列出了各測試數據集的記錄數、屬性數和類別數。

4.2 實驗結果對比

首先實驗同時使用兩種改進算法和K-means算法對Iris數據進行聚類，表2是三種算法的實驗結果對比，其中可以看出，兩種改進方法的循環次數遠遠小于經典K-means算法。

然后實驗同時使用兩種改進算法和K-means算法對Credit數據進行聚類，表3是三種算法的實驗結果對比，其中可以看出兩種改進方法的循環次數小于經典K-means算法。

4.3 實驗結果分析

通過實驗結果對比可以看出：經典的K-means算法與聚類數目和初始聚類中心的選擇有很大關系，多次運行算法，從不同的初始聚類中心出發會得到不同的聚類結果和準確性，具有一定的主觀性和隨機性，算法穩定性不好。基于競爭神經網絡的K-means算法在運行經典的K-means算法之前用競爭神網做了一個預處理，而基于密度的K-means算法在運行經典的K-means算法之前做了一個預處理。這兩種算法都改變了初始聚類中心的隨機選擇，使輸入經典K-means算法的初始聚類中心離數據本身的類中心較近，改變其對聚類初始中心的依賴問題；而在競爭神網建立網絡的時候，利用采樣數據進行訓練，有效降低了數據量，減少了競爭神網的建立速度；并且多次運行算法，結果較穩定。從實驗結果也可以看出，它在兩組測試數據上運行得較好。

5 結論

本文針對經典K-means算法的主要不足，采用優化聚類中心的方法提出了基于競爭神經網絡的K-means算法和基于密度的K-means算法，從而使K-means算法能夠自適應的確定聚類中心，避免初始聚類中心的隨機性，在一定程度上彌補了經典算法的不足。

從實驗的結果來看，采用隨機選取初始聚類點的方法，初始聚類中心靠近數據本身的類中心時近時遠，非常不穩定，用于實際的數據聚類，效果不太好。而采用了一系列的改進算法后，其初始聚類點離數據本身類中心較近，并且較穩定，用于實際的數據聚類，效果較好。

參考文獻：

[1] HAN Jia-wei， Kamber M.數據挖掘:概念與技術[M].范明，孟小峰，譯.北京：機械工業出版社，2001:223-230.

[2] Belouchrani A，Abed-meraim K，Cardoso J F，et al.A Bjind Source Separation Technique Using Second-order Statistics[J].IEEE Trans.Signal Processing，1997，45(2):434-444.

[3] Charalampidis D，Kasparis T.Wavelet-Based Rotational Invariant Roughness Features for Texture Classification and Segmentation[J].IEEE Transactions on Image Processing，2002，11(8):825-837.

[4] 李永森，楊善林，馬溪駿，等.空間聚類算法中的K值優化問題研究[J].系統仿真學報，2006，18(3):576-576.

[5] Martin T H.神經網絡設計[M].戴葵，譯.北京:機械工業出版社，2002:285-310.