摘  要： K-means算法是最常用的一種基于劃分的聚類算法，但該算法需要事先指定K值、隨機(jī)選擇初始聚類中心等的缺陷，從而影響了K-means聚類結(jié)果的穩(wěn)定性。針對K-means算法中的初始聚類中心是隨機(jī)選擇這一缺點進(jìn)行改進(jìn)，利用提出的新算法確定初始聚類中心，然后進(jìn)行聚類，得出最終的聚類結(jié)果。實驗證明，該改進(jìn)算法比隨機(jī)選擇初始聚類中心的算法性能得到了提高，并且具有更高的準(zhǔn)確性及穩(wěn)定性。
關(guān)鍵詞： 歐氏距離；K-means；優(yōu)化初始聚類中心

　聚類分析[1](clustering)是數(shù)據(jù)挖掘研究的重要領(lǐng)域，借助聚類分析將大量的數(shù)據(jù)對象聚成不同的類簇，使不同簇之間的相似度低，簇內(nèi)的相似度高，它是一種無監(jiān)督的學(xué)習(xí)算法。為了實現(xiàn)對數(shù)據(jù)對象的聚類，人們提出了不同的聚類算法。聚類算法主要分成基于劃分、基于密度、基于分層、基于網(wǎng)格和基于模型的五大類[2]。K-means(均值)聚類算法是典型的基于劃分的聚類算法，同時也是應(yīng)用最廣泛的一種聚類算法。K-means聚類算法[3]主要針對處理大數(shù)據(jù)集，不但處理快速簡單，而且算法具有高效性以及可伸縮性。但是K-means聚類算法存在K值需要事先指定、隨機(jī)選擇初始聚類中心等的局限性。人們針對K-means聚類算法的這些局限性提出了不同的改進(jìn)算法。劉濤等人[4]提出了基于半監(jiān)督學(xué)習(xí)的K-means聚類算法的研究，用粒子群算法以及迭代搜索的思想找到優(yōu)質(zhì)的聚類中心進(jìn)行聚類；李飛等人[5]提出了基于遺傳算法的全局搜索能力來解決初始聚類中心選擇的敏感性問題。
　K-means聚類算法由于初始聚類中心是隨機(jī)選擇的，容易造成算法會陷入局部最優(yōu)解甚至是無解的情況，而聚類結(jié)果的好壞直接取決于初始聚類中心的選擇。因此初始聚類中心的選擇十分重要。本文主要針對隨機(jī)選擇初始聚類中心這一缺點，提出了一種新的改進(jìn)的K-means聚類算法。
1 傳統(tǒng)的K-means聚類算法
　K-means聚類算法是解決聚類問題的一種經(jīng)典算法，該算法具有簡單、快速并且能夠有效處理大數(shù)據(jù)集的特點。K-means聚類算法首先從n個數(shù)據(jù)對象中任意選取k個對象作為初始聚類中心；而對于所剩下的其他對象，則根據(jù)它們與這些聚類中心的相似度(距離)，分別將它們分配給與其最相似的類簇；然后計算該類簇中所有對象的均值；不斷重復(fù)這一過程直到標(biāo)準(zhǔn)準(zhǔn)則函數(shù)開始收斂為止。具體步驟如下[6]：
輸入：k，data[n]；輸出：k個簇的集合，滿足聚類準(zhǔn)則函數(shù)收斂。

2.2 改進(jìn)算法的思想及基本步驟
　影響K-means聚類算法性能的主要原因有：樣本集中孤立點以及隨機(jī)選擇初始聚類中心而造成聚類結(jié)果的不穩(wěn)定以及不準(zhǔn)確。針對K-means的這種不足，本文提出了一種新的思想：首先將樣本點中影響聚類結(jié)果的孤立點去除，然后利用坐標(biāo)平移的思想來確定初始聚類中心，利用K-means算法進(jìn)行聚類，最終得到可以滿足平方誤差準(zhǔn)則函數(shù)收斂的聚類結(jié)果。
算法具體步驟：
　首先排除樣本點中的孤立點：
　(1)輸入樣本點，利用unique函數(shù)排除樣本點中重復(fù)的數(shù)據(jù)；
　(2)計算每個樣本點與其余樣本點之間的距離存入矩陣cid中；
　(3)指定孤立點的個數(shù)acnodenum，執(zhí)行孤立點查找程序，即計算每個點與其余點的距離之和，找出距離最大的前acnodenum個點，即為孤立點；排除孤立點，將孤立點存入集合acnode中，并將這些點從原始數(shù)據(jù)集中刪除得到新的數(shù)據(jù)集datanew，即為本文算法第一次去除孤立點之后的樣本點集合。在第一次去除了孤立點之后，可以得到新的樣本點集合datanew。
其次對datanew樣本進(jìn)行處理，從中找出k個初始聚類中心：
　(4)求出樣本點集合datanew中的兩兩之間的距離存入矩陣D中；
　(5)從矩陣D中找出距離最大的兩個點A和B，其最大距離記為maxinD，根據(jù)式(2)計算其中心center和半徑(r=maxinD/2)；
　(6)第二次去除孤立點：求datanew中的每個樣本點與center的距離，將大于r的樣本點加入到集合acnode中并將其從datanew中去除得到第二次去除孤立點之后的樣本點datanewsec；
　(7)利用坐標(biāo)平移的思想求解初始聚類中心：
?、賹⒉襟E(5)中求出的A、B中的任一點加入初始聚類中心集合nc中作為第一個初始聚類中心；
?、谘h(huán)k-1次實現(xiàn)以center為參照點，將A坐標(biāo)順時針移動圓心角等于2×pi/k的度數(shù)；
?、圩罱K得到包含A在內(nèi)的k個點，將這個k個點作為初始的聚類中心存入矩陣nc中；
　(8)利用步驟(7)中求得的初始的聚類中心nc，用K-means算法進(jìn)行聚類得出滿足聚類準(zhǔn)則函數(shù)收斂的聚類結(jié)果。
　(9)計算acnode中的每個點與每個初始聚類中心的距離，將acnode中的點加入到距離初始聚類中心最近的簇中。
3 實驗結(jié)果及分析
3.1 實驗數(shù)據(jù)及實驗環(huán)境
　為了便于對比分析與計算，本實驗采用的是二維數(shù)據(jù)，并且數(shù)據(jù)類型是數(shù)值型的。實驗采用了兩組測試數(shù)據(jù)：一組是隨機(jī)數(shù)據(jù)，一組是UCI數(shù)據(jù)庫中的標(biāo)準(zhǔn)數(shù)據(jù)集Iris數(shù)據(jù)集。實驗工具采用MATLAB環(huán)境編程實現(xiàn)。
3.2 實驗方案
3.2.1 采用隨機(jī)數(shù)據(jù)
　采用傳統(tǒng)的隨機(jī)選擇初始聚類中心的K-means算法將本文的改進(jìn)算法對隨機(jī)產(chǎn)生的80個樣本進(jìn)行聚類，聚類的簇數(shù)設(shè)為k=4，比較其聚類結(jié)果圖。
　傳統(tǒng)K-means算法隨機(jī)選取4組初始聚類中心對同一樣本集進(jìn)行聚類，其聚類結(jié)果圖如圖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)。
　采用改進(jìn)算法選出的初始聚類中心為(0.231 1，  0.956 8)、(0.999 6，0.795 7)、(0.838 5，0.027 2)和(0.070 0， 0.188 3)，其聚類結(jié)果如圖2所示。

　由圖1、圖2可以看出，利用本文改進(jìn)算法選出的初始聚類中心進(jìn)行聚類，其聚類結(jié)果比較接近數(shù)據(jù)分布。
3.2.2 采用Iris數(shù)據(jù)集
Iris數(shù)據(jù)集是UCI數(shù)據(jù)庫中的一個標(biāo)準(zhǔn)數(shù)據(jù)集，包含有4個屬性，150個數(shù)據(jù)對象，可分為3類。選用Iris數(shù)據(jù)集　中間二維的數(shù)據(jù)進(jìn)行聚類，分別用原算法和改進(jìn)算法進(jìn)行實驗。對實驗結(jié)果從運(yùn)行時間以及準(zhǔn)確度上進(jìn)行分析，實驗結(jié)果匯總以及分析如表1所示。   
　從表1可以看出，改進(jìn)算法的運(yùn)行時間比傳統(tǒng)K-means算法的運(yùn)行時間要小，尤其當(dāng)數(shù)據(jù)集比較大時，其運(yùn)行時間小得多。從圖3中可以看出，采用改進(jìn)算法其準(zhǔn)確度明顯提高。

　本文提出的改進(jìn)算法雖然在查找孤立點以及計算樣本點之間的距離方面，會增加時間消耗，但是改進(jìn)算法準(zhǔn)確度較高，聚類效果較好。實驗證明該算法是切實可行的，與傳統(tǒng)的K-means算法相比較，有較好的聚類結(jié)果。
參考文獻(xiàn)
[1] Han Jiawei， KAMBER M. Data mining concepts and  techniques， second  edition[M]． Elsevier(Singapore)Pte Ltd，2006：251-263.
[2] 張建輝.K-means聚類算法的研究與應(yīng)用[D].武漢：武漢理工大學(xué)，2007：10-14.
[3] 馮超.K-means聚類算法的研究[D].大連：大連理工大學(xué)，2007：15-19.
[4] 劉濤，尹紅健.基于半監(jiān)督學(xué)習(xí)的K-均值聚類算法的研究[J].計算機(jī)應(yīng)用研究，2010，27(3)：913-917.
[5] 李飛，薛彬，黃亞樓.初始中心優(yōu)化的K-Means聚類算法[J].計算機(jī)科學(xué)，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.