吳滌單

摘要：針對(duì)傳統(tǒng)的k-means算法處理離散型數(shù)據(jù)的不足以及選取初始聚類中心的隨機(jī)性等缺點(diǎn)，提出了一種基于改進(jìn)的粒子群優(yōu)化k-means算法，根據(jù)文中提供的優(yōu)化算法尋找初始聚類中心后，在閥值范圍內(nèi)進(jìn)行數(shù)據(jù)樣本間的迭代更新，直至聚類中心穩(wěn)定。經(jīng)過實(shí)驗(yàn)結(jié)果驗(yàn)證分析表明，經(jīng)過改進(jìn)的粒子群優(yōu)化k-means算法與傳統(tǒng)的k-means算法相比，更具有良好的聚類收斂效果，聚類效果也相對(duì)穩(wěn)定。

關(guān)鍵詞：k-means；改進(jìn)粒子群算法；聚類

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）06-1238-04

Improved K-means Clustering Algorithm Based on Particle Swarm Optimization

WU Di-dan

（Nanjing College of Information Technology， Nanjing 210023， China）

Abstract： Random defects in the traditional K-means algorithm to process the discrete data insufficiency as well as the selection of initial clustering center， put forward an improved particle swarm optimization based on K-means algorithm， to find the initial cluster center according to the optimization algorithm is provided in this paper， are updated iteratively between data samples in the threshold range， until the clustering center. Through the experimental results verify the analysis shows that， by K-means algorithm， the improved particle swarm optimization k-means algorithm compared with the traditional clustering， has a good convergence effect， cluster effect is also relatively stable.

Key words： K-means； improved particle swarm algorithm； clustering

聚類起源于分類學(xué)，在原始的分類中，人們大都根據(jù)積累以往的知識(shí)、經(jīng)驗(yàn)把信息進(jìn)行分類。隨著信息技術(shù)的快速發(fā)展和人們對(duì)分類信息所提的要求的越來越高，根據(jù)以往的經(jīng)驗(yàn)和知識(shí)難以滿足目前日益增長(zhǎng)的各種分類需求，這就需要我們把數(shù)學(xué)工具和多元分析引入到分類學(xué)當(dāng)中來，隨之產(chǎn)生了目前的多種聚類分析方法，如模糊聚類法、系統(tǒng)聚類法、動(dòng)態(tài)聚類法、圖論聚類法、聚類預(yù)報(bào)法、序樣品聚類法等。聚類分析的算法可以分為劃分法、層次法、基于密度的方法、基于網(wǎng)格的方法、基于模型的方法[1]。目前聚類分析算法已經(jīng)廣泛的應(yīng)用于稅務(wù)、教育、商業(yè)、計(jì)算機(jī)科學(xué)、人工智能、數(shù)據(jù)挖掘、人工神經(jīng)網(wǎng)絡(luò)等多個(gè)不同的應(yīng)用領(lǐng)域[2]。

1 k-means聚類算法

隨著科學(xué)技術(shù)的日新月異的發(fā)展，人們對(duì)k-means算法的研究也日益深入，許多的學(xué)者也做不少研究、探索、改進(jìn)，如文獻(xiàn)[3]提出一種基于密度敏感相似性度量來確定聚類中心， 文獻(xiàn)[4-7]根據(jù)聚類樣本密度來初始化聚類中心，文獻(xiàn)[8]提出了K-means的譜算法，文獻(xiàn)[9]提出了一種基于影響因子的K-means算法。

k-means算法也稱為k-均值算法，是一種基于劃分法的聚類算法，同時(shí)也是一種應(yīng)用十分廣泛的聚類算法。它將聚類數(shù)據(jù)集內(nèi)的所有數(shù)據(jù)樣本的均值作為該聚類的中心點(diǎn)，該算法的主要流程是通過迭代過程把數(shù)據(jù)集劃分為不同的種類，從而使評(píng)價(jià)聚類性能的準(zhǔn)則函數(shù)達(dá)到最優(yōu)，這樣就使生成的每個(gè)聚類內(nèi)數(shù)據(jù)樣本緊湊，各個(gè)類之間相互獨(dú)立。這種劃分方法開始時(shí)將所有的對(duì)象都分配至?xí)憾ǖ腒集群，然后隨機(jī)選取數(shù)據(jù)集中心后，形成聚類中心點(diǎn)，尋找遠(yuǎn)離中心的數(shù)據(jù)點(diǎn)，把每個(gè)數(shù)據(jù)點(diǎn)都分配到與之最為接近的聚類中心點(diǎn)，把每個(gè)聚類樣本中的數(shù)據(jù)均值作為新的聚類中心，繼續(xù)選擇新的聚類中心和更新迭代直至聚類中心不再變化為止， K-means算法具體描述如下：

第一步：從數(shù)據(jù)集S中，隨機(jī)選取k個(gè)初始聚類中心（M1， M2， M3，… MI，…， MK）

第二步：計(jì)算各個(gè)數(shù)據(jù)點(diǎn)到初始聚類中心（Mi）的距離，根據(jù)兩者之間距離把各個(gè)數(shù)據(jù)點(diǎn)劃分到相應(yīng)的數(shù)據(jù)簇

第三步：通過計(jì)算更新后的數(shù)據(jù)簇平均值，找出更加合適的聚類中心Mi

第四步：調(diào)整每個(gè)數(shù)據(jù)簇的中心點(diǎn)Mi，判斷數(shù)據(jù)簇的中心點(diǎn)是否變化，若變化跳轉(zhuǎn)到步驟2；否則，結(jié)束迭代

2 基于改進(jìn)的粒子群優(yōu)化的k-means聚類算法

聚類通常可以定義為對(duì)分組的數(shù)據(jù)集進(jìn)行分類的方法，通過聚類使同一組中的數(shù)據(jù)樣本具有高度相似性，不同組中的數(shù)據(jù)樣本具有高度的相異性。K-means聚類的主要缺點(diǎn)在于初始聚類中心的選擇是完全隨機(jī)的。正因?yàn)檫@種隨機(jī)選取初始聚類中心的方式，由此產(chǎn)生的聚類收斂質(zhì)量難以確定?？梢圆扇〉奈ㄒ淮胧┦菍⒈M量選擇集群中心點(diǎn)作為初始聚類中心。但這只是一種預(yù)防措施，從根本上解決不了的問題。正因?yàn)閭鹘y(tǒng)的k-means算法的這些缺陷，該文在k-means聚類算法的基礎(chǔ)上引入改進(jìn)的粒子群算法，對(duì)k-means算法進(jìn)行優(yōu)化，使之能達(dá)到較好的聚類效果。

2.1 相關(guān)定義

定義1 歐氏距離，數(shù)據(jù)集中空間數(shù)據(jù)點(diǎn)X和數(shù)據(jù)點(diǎn)Y之間的距離

D[X，Y]=[i=1n（xi-yi）2] （1）

定義2 切比雪夫距離，兩個(gè)二維向量之間的最大距離

D[X，Y]max=max[xi-yi] （2）

定義3 數(shù)據(jù)點(diǎn)與數(shù)據(jù)集合之間的平均距離

D[X，N]avg= Average（D[X，n]），n∈N （3）

2.2 粒子群算法

粒子群優(yōu)化算法（PSO）是由美國(guó)的Kennedy和Eberhart博士受到鳥群覓食行為的啟發(fā)于1995年提出的。它屬于一種進(jìn)化算法，與遺傳算法有一定的相似性，都是通過隨機(jī)選定初始解，通過迭代更新，來尋找最優(yōu)解。但它與遺傳算法相比操作實(shí)現(xiàn)簡(jiǎn)單，收斂速度也較快，故在應(yīng)用領(lǐng)域上也比遺傳算法較為廣泛，在現(xiàn)實(shí)世界中解決問題也具有較大的優(yōu)越性。

PSO初始化每個(gè)問題的解都可以看成一個(gè)粒子，然后通過迭代更新來查找問題的答案（最優(yōu)解）。所有的粒子都有一個(gè)經(jīng)過規(guī)則優(yōu)化的適應(yīng)值，單個(gè)的粒子都有一個(gè)決定方向和距離的速度。在尋找最優(yōu)解的過程其實(shí)就是一個(gè)粒子迭代更新的過程，在每次迭代過程當(dāng)中，粒子通過兩個(gè)極值來更新自我，第一個(gè)就是粒子自己所檢索到的最優(yōu)解（個(gè)體極值pBest），第二個(gè)就是目前整個(gè)種群所找到的最優(yōu)解（種群極值gBest），在粒子群優(yōu)化算法當(dāng)中，粒子的位置用W[tij] （W[ti1]， W[ti2]， W[ti3]， ……， W[tix]），在尋找問題最優(yōu)解的過程當(dāng)中取決于合適的優(yōu)化規(guī)則和粒子的飛行速度。

V[i+1ij]= w*V[tij]+c1*r*（pBest[tij]- W[tij]）+c2*r*（gBest[tij]- W[tij]） （4）

W[t+1ij] = W[tij] + V[i+1ij] （5）

V[i+1ij] 是粒子的速度， w是慣性權(quán)重， W[tij]是當(dāng)前粒子的位置r 是介于（0， 1）之間的隨機(jī)數(shù)，c1，c2 是學(xué)習(xí)因子。

2.3改進(jìn)的粒子群算法

因?yàn)榱Ｗ拥倪\(yùn)行速度決定了粒子運(yùn)行的方向和距離，在公式（4）中，存在w、r、c1、c2等隨機(jī)數(shù)，每次循環(huán)更新搜索最優(yōu)解時(shí)也存在一定的隨機(jī)性。粒子具有可記憶性，為了提高粒子的可遺傳性，提高集群的收斂效率，對(duì)公式（4）進(jìn)行一些必要的改進(jìn)[10]。

c1*r=w1=[pBesttijWtij]，c2*r=w2=[gBesttijWtij]

V[i+1ij]= w*V[tij]+w1*（pBest[tij]- W[tij]）+w2（gBest[tij]- W[tij]） （6）

通過對(duì)粒子運(yùn)行速度計(jì)算的改進(jìn)，增強(qiáng)了粒子局部的搜索能力，提高了聚類的效果。

2.4基于改進(jìn)粒子群優(yōu)化的k-means算法

假定我們要把一個(gè)含有n個(gè)數(shù)據(jù)樣本空間的數(shù)據(jù)集（S）聚類為k個(gè)數(shù)據(jù)簇（M1 ， M2，… ，Mk）。首先對(duì)數(shù)據(jù)集內(nèi)的數(shù)據(jù)樣本根據(jù)公式（1）進(jìn)行預(yù)先處理，根據(jù)公式（1）計(jì)算出來的歐式距離來分析各個(gè)樣本的歸屬性，降低聚類的復(fù)雜性。在粒子群優(yōu)化算法當(dāng)中，粒子具有可記憶性，粒子能記住自己搜索到的最優(yōu)解。粒子的當(dāng)前位置根據(jù)公式（5）由粒子的速度和粒子前一次位置所決定。使用改進(jìn)了的粒子群優(yōu)化算法在初始聚類中心時(shí)，我們通過計(jì)算粒子間的歐式距離選出k個(gè)最小平方差的數(shù)據(jù)點(diǎn)作為聚類的初始中心。然后通過粒子的迭代更新，直至滿足聚類的終止條件為止，找到最優(yōu)的聚類中心。改進(jìn)的粒子群算法優(yōu)化k-means聚類算法的具體步驟如下：

輸入：給定的數(shù)據(jù)集S（含有n個(gè)數(shù)據(jù)樣本，n1，n2，…nd）

輸出：k個(gè)聚類

第一步：結(jié)合公式（6）計(jì)算數(shù)據(jù)集S中所有樣本之間的距離，根據(jù)公式（1），選定k個(gè)初始聚類中心

第二步：根據(jù)公式（2），計(jì)算出一個(gè)最大閥值f

第三步：根據(jù)公式（3）提供的數(shù)據(jù)點(diǎn)到集合之間的平均距離，把各個(gè)數(shù)據(jù)樣本歸到k個(gè)初始聚類中心，形成k個(gè)初始數(shù)據(jù)簇（V[0i]={V[0i1]， V[0i2]，……， V[0in]}）

第四步：利用改進(jìn)了粒子群位置計(jì)算公式，重新計(jì)算各個(gè)數(shù)據(jù)點(diǎn)之間的距離（距離均應(yīng)小于最大閥值f），根據(jù)公式（6），更新聚類中心 V[ti]={V[ti1]，V[ti2]，……V[tik]}

第五步：如果達(dá)到規(guī)定的收斂效果或者最大的迭代次數(shù)就終止更新聚類中心，結(jié)束優(yōu)化，輸出k個(gè)數(shù)據(jù)簇。

3 實(shí)驗(yàn)驗(yàn)證

為了驗(yàn)證本文經(jīng)過改進(jìn)的粒子群優(yōu)化k-means算法的聚類效果，選用操作系統(tǒng)為 Windows7專業(yè)版，內(nèi)存4G ，處理器為Intel（R） Xeon（R）CPU e31225 @3.10G Hz，在常用的標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集uci中使用Iris、Balance-scal兩種數(shù)據(jù)集，采用傳統(tǒng)的k-means算法、粒子群優(yōu)化k-means算法、改進(jìn)的粒子群優(yōu)化k-means算法，分別測(cè)試8次并對(duì)其聚類效果進(jìn)行分析。如下所示。

表1 傳統(tǒng)的k-means在Iris、Balance-scal兩種數(shù)據(jù)集上的測(cè)試

根據(jù)三種不同算法（傳統(tǒng)的k-means算法、粒子群優(yōu)化k-means算法、經(jīng)過改進(jìn)的粒子群優(yōu)化k-means算法）在兩個(gè)不同的通用數(shù)據(jù)集（Iris、Balance-scal）上的測(cè)試結(jié)果可以看出，在Iris數(shù)據(jù)集上使用三種不同的算法得到的平均準(zhǔn)確率依次分別為63.98%，64.83%，77.61%，在Balance-scal數(shù)據(jù)集上使用三種不同的算法得到的平均準(zhǔn)確率依次分別為63.64%，64.19%，77.33%，算法迭代次數(shù)都是8次，實(shí)驗(yàn)結(jié)果表明基于改進(jìn)的粒子群優(yōu)化k-means聚類算法，收斂程度高，取得了較好的聚類效果。

4 結(jié)束語

k-means算法是一種基于劃分的應(yīng)用十分廣泛的進(jìn)化聚類算法，該文提出根據(jù)改進(jìn)了的粒子群算法來優(yōu)化k-means，彌補(bǔ)了傳統(tǒng)k-means算法隨機(jī)選取初始聚類中心的不足，經(jīng)過實(shí)驗(yàn)驗(yàn)證取得了良好的收斂效果，聚類質(zhì)量穩(wěn)定。

參考文獻(xiàn)：

[1] Xu Song，He Yan，Sun Xiuxia，et a1.New visual localization algorithm for targets with different heights[J].Chinese Journal of Scientific Instrument，2010，31（3）：546-551.

[2] Rui Xu，Wunsch D.Survey of clustering algorithms[J].IEEE Trans on Neural Network，2005，16（3）：645-678.

[3] 王玲，薄列峰，焦李成.密度敏感的普聚類[J].電子學(xué)報(bào)，2007，35（8）：1577-1578.

[4] LAI Yuxia，LIU Jianping.Optimization study on initial center of K-means algorithm[J].Computer Engineering and Applications，2008，44（10）：147-149.

[5] HAN Lingbo，WANG Qiang，JIANG Zhengfeng.Improved K-means initial clustering center selection algorithm[J].Computer Engineering and Applications，2010，46（17）：150-152.

[6] YUAN Fang，ZHOU Zhiyong，SONG Xin.K-means clustering algorithm with meliorated initial center[J].Computer Engineering，2007，33（3）：65-66.

[7] 汪中，劉貴全，陳恩紅.一種優(yōu)化初始中心點(diǎn)的K-means算法[J].模式識(shí)別與人工智能，2009，22（2）：299-304.

[8] 錢線，黃萱菁，吳立德.初始化K-means譜算法[J].自動(dòng)化學(xué)報(bào)，2007，33（4）：342-346.

[9] Leng Mingwei，Tang Haitao，Chen Xiaoyun.An efficient K-means clustering algorithm based on influence factors[C].Eighth ACIS International Conference on Software Engineering，Artificial Intelligence，Networking，and Parallel/Distributed Computing，2007：815-820.

[10] 陳東輝，劉志鏡，王縱虎.一種基于粒子群優(yōu)化的可能性C均值聚類改進(jìn)方法[J].計(jì)算機(jī)科學(xué)，2012，39（11）：123-124.