摘 要： K-means算法是最常用的一種基于劃分的聚類算法，但該算法需要事先指定K值、隨機選擇初始聚類中心等的缺陷，從而影響了K-means聚類結果的穩定性。針對K-means算法中的初始聚類中心是隨機選擇這一缺點進行改進，利用提出的新算法確定初始聚類中心，然后進行聚類，得出最終的聚類結果。實驗證明，該改進算法比隨機選擇初始聚類中心的算法性能得到了提高，并且具有更高的準確性及穩定性。
關鍵詞： 歐氏距離；K-means；優化初始聚類中心
聚類分析[1](clustering)是數據挖掘研究的重要領域，借助聚類分析將大量的數據對象聚成不同的類簇，使不同簇之間的相似度低，簇內的相似度高，它是一種無監督的學習算法。為了實現對數據對象的聚類，人們提出了不同的聚類算法。聚類算法主要分成基于劃分、基于密度、基于分層、基于網格和基于模型的五大類[2]。K-means(均值)聚類算法是典型的基于劃分的聚類算法，同時也是應用最廣泛的一種聚類算法。K-means聚類算法[3]主要針對處理大數據集，不但處理快速簡單，而且算法具有高效性以及可伸縮性。但是K-means聚類算法存在K值需要事先指定、隨機選擇初始聚類中心等的局限性。人們針對K-means聚類算法的這些局限性提出了不同的改進算法。劉濤等人[4]提出了基于半監督學習的K-means聚類算法的研究，用粒子群算法以及迭代搜索的思想找到優質的聚類中心進行聚類；李飛等人[5]提出了基于遺傳算法的全局搜索能力來解決初始聚類中心選擇的敏感性問題。
K-means聚類算法由于初始聚類中心是隨機選擇的，容易造成算法會陷入局部最優解甚至是無解的情況，而聚類結果的好壞直接取決于初始聚類中心的選擇。因此初始聚類中心的選擇十分重要。本文主要針對隨機選擇初始聚類中心這一缺點，提出了一種新的改進的K-means聚類算法。
1 傳統的K-means聚類算法
K-means聚類算法是解決聚類問題的一種經典算法，該算法具有簡單、快速并且能夠有效處理大數據集的特點。K-means聚類算法首先從n個數據對象中任意選取k個對象作為初始聚類中心；而對于所剩下的其他對象，則根據它們與這些聚類中心的相似度(距離)，分別將它們分配給與其最相似的類簇；然后計算該類簇中所有對象的均值；不斷重復這一過程直到標準準則函數開始收斂為止。具體步驟如下[6]：
輸入：k，data[n]；輸出：k個簇的集合，滿足聚類準則函數收斂。
2.2 改進算法的思想及基本步驟
影響K-means聚類算法性能的主要原因有：樣本集中孤立點以及隨機選擇初始聚類中心而造成聚類結果的不穩定以及不準確。針對K-means的這種不足，本文提出了一種新的思想：首先將樣本點中影響聚類結果的孤立點去除，然后利用坐標平移的思想來確定初始聚類中心，利用K-means算法進行聚類，最終得到可以滿足平方誤差準則函數收斂的聚類結果。
算法具體步驟：
首先排除樣本點中的孤立點：
(1)輸入樣本點，利用unique函數排除樣本點中重復的數據；
(2)計算每個樣本點與其余樣本點之間的距離存入矩陣cid中；
(3)指定孤立點的個數acnodenum，執行孤立點查找程序，即計算每個點與其余點的距離之和，找出距離最大的前acnodenum個點，即為孤立點；排除孤立點，將孤立點存入集合acnode中，并將這些點從原始數據集中刪除得到新的數據集datanew，即為本文算法第一次去除孤立點之后的樣本點集合。在第一次去除了孤立點之后，可以得到新的樣本點集合datanew。
其次對datanew樣本進行處理，從中找出k個初始聚類中心：
(4)求出樣本點集合datanew中的兩兩之間的距離存入矩陣D中；
(5)從矩陣D中找出距離最大的兩個點A和B，其最大距離記為maxinD，根據式(2)計算其中心center和半徑(r=maxinD/2)；
(6)第二次去除孤立點：求datanew中的每個樣本點與center的距離，將大于r的樣本點加入到集合acnode中并將其從datanew中去除得到第二次去除孤立點之后的樣本點datanewsec；
(7)利用坐標平移的思想求解初始聚類中心：
?、賹⒉襟E(5)中求出的A、B中的任一點加入初始聚類中心集合nc中作為第一個初始聚類中心；
?、谘hk-1次實現以center為參照點，將A坐標順時針移動圓心角等于2×pi/k的度數；
③最終得到包含A在內的k個點，將這個k個點作為初始的聚類中心存入矩陣nc中；
(8)利用步驟(7)中求得的初始的聚類中心nc，用K-means算法進行聚類得出滿足聚類準則函數收斂的聚類結果。
(9)計算acnode中的每個點與每個初始聚類中心的距離，將acnode中的點加入到距離初始聚類中心最近的簇中。
3 實驗結果及分析
3.1 實驗數據及實驗環境
為了便于對比分析與計算，本實驗采用的是二維數據，并且數據類型是數值型的。實驗采用了兩組測試數據：一組是隨機數據，一組是UCI數據庫中的標準數據集Iris數據集。實驗工具采用MATLAB環境編程實現。
3.2 實驗方案
3.2.1 采用隨機數據
采用傳統的隨機選擇初始聚類中心的K-means算法將本文的改進算法對隨機產生的80個樣本進行聚類，聚類的簇數設為k=4，比較其聚類結果圖。
傳統K-means算法隨機選取4組初始聚類中心對同一樣本集進行聚類，其聚類結果圖如圖1所示。
第1組：(0.660 2，0.207 1)、(0.342 0，0.607 2)、(0.289 7， 0.629 9)、(0.341 2，0.370 5)。
第2組：(0.767 6，0.274 6)、(0.261 0，0.193 1)、(0.719 7，0.827 6)、(0.315 8，0.620 6)。
第3組：(0.580 8，0.104 6)、(0.815 8，0.400 6)、(0.211 4，0.445 7)、(0.623 2，0.807 5)。
第4組：(0.568 1，0.846 9)、(0.781 2，0.575 2)、(0.211 4，0.445 7)、(0.628 6，0.122 5)。
采用改進算法選出的初始聚類中心為(0.231 1， 0.956 8)、(0.999 6，0.795 7)、(0.838 5，0.027 2)和(0.070 0， 0.188 3)，其聚類結果如圖2所示。
由圖1、圖2可以看出，利用本文改進算法選出的初始聚類中心進行聚類，其聚類結果比較接近數據分布。
3.2.2 采用Iris數據集
Iris數據集是UCI數據庫中的一個標準數據集，包含有4個屬性，150個數據對象，可分為3類。選用Iris數據集 中間二維的數據進行聚類，分別用原算法和改進算法進行實驗。對實驗結果從運行時間以及準確度上進行分析，實驗結果匯總以及分析如表1所示。
從表1可以看出，改進算法的運行時間比傳統K-means算法的運行時間要小，尤其當數據集比較大時，其運行時間小得多。從圖3中可以看出，采用改進算法其準確度明顯提高。
本文提出的改進算法雖然在查找孤立點以及計算樣本點之間的距離方面，會增加時間消耗，但是改進算法準確度較高，聚類效果較好。實驗證明該算法是切實可行的，與傳統的K-means算法相比較，有較好的聚類結果。
參考文獻
[1] Han Jiawei， KAMBER M. Data mining concepts and techniques， second edition[M]． Elsevier(Singapore)Pte Ltd，2006：251-263.
[2] 張建輝.K-means聚類算法的研究與應用[D].武漢：武漢理工大學，2007：10-14.
[3] 馮超.K-means聚類算法的研究[D].大連：大連理工大學，2007：15-19.
[4] 劉濤，尹紅健.基于半監督學習的K-均值聚類算法的研究[J].計算機應用研究，2010，27(3)：913-917.
[5] 李飛，薛彬，黃亞樓.初始中心優化的K-Means聚類算法[J].計算機科學，2002，29(7)：94-96.
[6] Shi Na， Liu Xumin， Guan Yong. Research on k-means clustering algorithm[C]. Third International Symposium on Intelligent Information Technology and Security Informatics， 2010：63-67.