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

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

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

　本文提出的改進(jìn)算法雖然在查找孤立點(diǎn)以及計(jì)算樣本點(diǎn)之間的距離方面，會(huì)增加時(shí)間消耗，但是改進(jìn)算法準(zhǔn)確度較高，聚類效果較好。實(shí)驗(yàn)證明該算法是切實(shí)可行的，與傳統(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ì)算機(jī)應(yīng)用研究，2010，27(3)：913-917.
[5] 李飛，薛彬，黃亞樓.初始中心優(yōu)化的K-Means聚類算法[J].計(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.