一種基于改進(jìn)粒子群算法的K-means算法

一種基于改進(jìn)粒子群算法的K-means算法

林曉雪, 趙茂先

(山東科技大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，山東 青島 266590)

摘要：針對(duì)K-means算法對(duì)初始聚類中心敏感、算法容易收斂于局部解等問題，運(yùn)用了增加飛行時(shí)間因子的粒子群算法，提高粒子群算法性能.利用改進(jìn)的粒子群算法與K-means算法相結(jié)合，提高了基于粒子群算法的K-means算法性能．?dāng)?shù)值試驗(yàn)驗(yàn)證了提出算法的收斂性，且最優(yōu)解的精度優(yōu)于K-means算法、PSO算法和PSO-K算法．

關(guān)鍵詞：K-means算法；粒子群算法；飛行時(shí)間因子； PSO-K算法

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)志碼：A

A K-means algorithm based on the improved

particle swarm optimization algorithm

LIN Xiao-xue, ZHAO Mao-xian

(College of Mathematics and Systems Science, Shandong University of Science and Technology, Qingdao 266590, China)

Abstract：Considering K-means algorithm was sensitive to the initial cluster centers and easy to converge to local solution and other issues, we increased flight time factor to improve particle swarm algorithm performance. The improved particle swarm algorithm and K-means algorithm were combined to improve the performance of K-means algorithm based on particle swarm optimization. Numerical experiments verified the proposed convergence of the algorithm, and the optimal solution accuracy was better than K-means algorithm, PSO algorithm and PSO-K algorithm.

Key words： K-means algorithm；PSO algorithm；flight time factor；PSO-K algorithm

K-means算法[1]是基于劃分的經(jīng)典聚類算法，具有容易理解、實(shí)現(xiàn)簡單、收斂速度快等優(yōu)點(diǎn)，但由于局部極值點(diǎn)的存在以及啟發(fā)算法的貪心性，使得傳統(tǒng)K-means算法有對(duì)初始聚類中心敏感、極易收斂于局部極值的缺點(diǎn)．目前，針對(duì)初始聚類中心的選取，許多研究者提出了不同改進(jìn)算法．Jim等[2]提出了一種快速找到聚類中心的算法，該算法使用聚類中心的位移拒絕不可能的候選點(diǎn)，算法縮短了計(jì)算時(shí)間．Aliasa等[3]提出了修改后的移動(dòng)K均值算法用來解決分割問題，修改后的算法是找到最近的中心為每個(gè)像素的更好聚類中心．Merwe等[4]率先提出用粒子群(Particle Swarm Optimization，PSO)算法解決聚類問題，文章介紹了粒子群算法是如何連接各個(gè)聚類中心，如何更好的實(shí)現(xiàn)K-means算法．Chen等[5]通過粒子群算法尋找聚類中心，根據(jù)聚類中心對(duì)粒子進(jìn)行位置編碼．Niknam等[6]提出了基于粒子群算法、蟻群算法和K均值聚類分析的高效混合的方法．

在分析上述研究成果和K-means算法存在缺陷的基礎(chǔ)上，本文提出一種基于自適應(yīng)飛行時(shí)間因子PSO算法的K-means算法．通過采用自適應(yīng)飛行時(shí)間因子的PSO算法，動(dòng)態(tài)調(diào)整粒子的飛行時(shí)間，避免了PSO算法中粒子出現(xiàn)早熟收斂的現(xiàn)象，消除K-means算法對(duì)初始聚類中心選取的依賴性，得到全局最優(yōu)的N個(gè)聚類中心，然后以此為初始聚類中心執(zhí)行改進(jìn)的算法獲得理想的聚類劃分．

1基本算法簡介

1.1　K-means算法

K-means算法的基本原理是基于劃分的聚類算法，給定一組數(shù)據(jù)集X，數(shù)據(jù)總數(shù)n，首先隨機(jī)地選取k個(gè)初始聚類中心(聚點(diǎn))，把每個(gè)對(duì)象分配給離它最近的聚點(diǎn)，從而得到一組聚類．然后，計(jì)算每個(gè)聚類的均值作為新的聚點(diǎn)，并把每個(gè)數(shù)據(jù)重新分配到最近的聚點(diǎn)，循環(huán)執(zhí)行這一過程，直到滿足終止條件結(jié)束算法．

1.2　PSO算法

粒子群優(yōu)化算法是一種基于群體智能方法的進(jìn)化計(jì)算技術(shù)，最早由Kennedy和Eberhart[7]于1995年提出．粒子群算法就是粒子在d維空間搜索一個(gè)目標(biāo)函數(shù)的最優(yōu)解，在該空間中有N個(gè)粒子，粒子具有位置Zr和速度Vr，每個(gè)粒子的位置Zr代表了一個(gè)潛在解．將Zr代入目標(biāo)函數(shù)就可以算出其適應(yīng)度，根據(jù)適應(yīng)度的大小來衡量解的優(yōu)劣．第r個(gè)粒子目前自身搜索到的最好位置(pbest)為Pr，所有粒子目前搜索到的最優(yōu)位置(gbest)記為Pg．最早期的PSO算法通過下面的公式來更新自己的速度和位置：

(1)

(2)

其中t是迭代次數(shù)；r1和r2為[0,1]之間均勻分布的隨機(jī)數(shù)，以增加搜索隨機(jī)性和種群的多樣性；c1和c2是學(xué)習(xí)因子，也稱加速因子，代表將每個(gè)粒子推向pbest和gbest位置的統(tǒng)計(jì)加速項(xiàng)權(quán)值．

為了提高基本PSO算法的性能，Shi等[8]提出了帶有慣性權(quán)重因子w的粒子群算法，后來稱這個(gè)改進(jìn)的算法為標(biāo)準(zhǔn)粒子群算法(Stand Particle Swarm Optimization，SPSO)．SPSO算法將基本PSO算法中的速度更新公式改為下式：

(3)

位置更新公式與基本PSO算法相同．上式中w稱為慣性權(quán)重因子，是一個(gè)非負(fù)數(shù)，用來控制粒子的全局搜索能力與局部搜索能力之間的平衡．w較大時(shí)，粒子搜索全局空間的趨勢較大，有能力探索新的區(qū)域，使算法全局搜索能力加強(qiáng)；反之w較小時(shí)，粒子局部搜索能力較強(qiáng)．w適中時(shí)PSO算法找到全局最優(yōu)解的機(jī)會(huì)較大，鑒于以上分析，Shi等讓w隨迭代次數(shù)而線性遞減：

(4)

其中wmax為慣性權(quán)重初始值；wmin為慣性權(quán)重終值；tmax為最大迭代次數(shù)；t為當(dāng)前迭代次數(shù)．實(shí)驗(yàn)表明，這種改進(jìn)明顯改善了算法的性能，因此后來的改進(jìn)都在SPSO的基礎(chǔ)上進(jìn)行的改進(jìn)．

2PSO-K算法

由于K-means算法容易受初始聚類中心選取的影響，算法易收斂于局部極值．針對(duì)K-means算法的缺陷，不少學(xué)者提出了將優(yōu)化算法與K-means算法相結(jié)合的算法，基于粒子群算法的k-means算法(PSO-K算法)是一種用粒子群算法的思想來解決聚類問題的優(yōu)化算法，算法在一定程度上克服了K-means算法的缺陷．

2.1　PSO-K算法原理

對(duì)于每個(gè)聚類中心的計(jì)算公式和樣本集總的類間離散度和公式如下：

(5)

(6)

粒子的適應(yīng)度按照公式(6)計(jì)算．其中Zr為第r個(gè)粒子(1≤r≤N)，N為粒子個(gè)數(shù)，zrj為第r個(gè)粒子的第j個(gè)類的聚類中心位置，d(xi,zij)為第i個(gè)樣本數(shù)據(jù)到對(duì)應(yīng)聚類中心的距離．聚類準(zhǔn)則函數(shù)f(Zr)為各類樣本到對(duì)應(yīng)聚類中心的距離總和，也就是粒子的適應(yīng)度函數(shù)．這里d(xi,zrj)為歐式空間距離．距離公式、粒子的速度和位置更新公式如下：

d(xi,zrj)=‖xi-zrj‖

(7)

(8)

(9)

當(dāng)聚類中心確定時(shí)，聚類的劃分由最鄰近法則確定，即每個(gè)數(shù)據(jù)優(yōu)先劃分到離它最近的聚類．

2.2　PSO-K算法步驟

(1)種群初始化．給定樣本總數(shù)n，維數(shù)d，聚類個(gè)數(shù)k，先將每個(gè)樣本隨機(jī)指派為一類，作為最初的聚類劃分，根據(jù)公式(5)計(jì)算各類的聚類中心，作為粒子的初始位置編碼，初始化粒子速度，計(jì)算粒子的適應(yīng)度．反復(fù)進(jìn)行N次，共生成N個(gè)初始粒子；

(2)根據(jù)公式(6)、(7)計(jì)算每個(gè)粒子的適應(yīng)度值；

(3)對(duì)每個(gè)粒子的適應(yīng)度值和它所經(jīng)歷的最好位置Pr的適應(yīng)度值比較，如果更好，更新Pr；

(4)對(duì)每個(gè)粒子的適應(yīng)度值和群體所經(jīng)歷的最好位置Pg的適應(yīng)度值比較，如果更好，更新Pg；

(5)根據(jù)公式(4)、(8)和(9)更新粒子的速度和位置；

(6)根據(jù)K-means算法中的最鄰近法則，將每個(gè)樣本重新歸類，得到新的聚類劃分；

(7)判斷是否滿足終止條件，如果滿足輸出最優(yōu)解；否則返回(2)．

終止條件為粒子群的最好適應(yīng)度值在給定的迭代數(shù)內(nèi)幾乎不改變或達(dá)到給定最大迭代次數(shù)．

3改進(jìn)的PSO-K算法

3.1　自適應(yīng)飛行時(shí)間因子的PSO算法

最基本的PSO算法中粒子的位置更新公式為(2)，現(xiàn)在增加飛行時(shí)間因子T，T表示第r個(gè)粒子的飛行時(shí)間，在基本PSO算法中T=1，因此PSO算法中的位置更新公式變?yōu)橐韵鹿剑?/p>

(10)

本文采用如下改進(jìn)的飛行時(shí)間因子的計(jì)算方法：

T=F(αt,βt)=T0+αtTα-βtTβ

(11)

其中αt,βt分別表示種群多樣性和種群進(jìn)化度；T0為T的初始值，一般取0.8~1.0；Tα,Tβ用來調(diào)節(jié)αt,βt對(duì)飛行時(shí)間因子的影響程度．αt用來表示粒子的聚集程度，粒子越聚集，種群的多樣性就越差；粒子越分散，種群多樣性越好，算法就越不容易陷入局部最優(yōu)解．αt的公式表示如下：

(12)

種群進(jìn)化度指標(biāo)βt．βt用來表示種群的進(jìn)化程度，βt的公式表示如下：

(13)

由公式(13)可知βt的取值范圍，βt∈(0,1]．當(dāng)βt=1時(shí)，表明算法沒有進(jìn)化，如果在給定的次數(shù)下算法都沒有進(jìn)化，可以認(rèn)為算法找到了全局最優(yōu)解或陷入了局部最優(yōu)；當(dāng)βt越小表示種群進(jìn)化速度越快．

在進(jìn)化初期βt值較小，此時(shí)粒子的飛行時(shí)間應(yīng)該長點(diǎn)，即飛行時(shí)間因子T應(yīng)較大．隨著進(jìn)化程度的減慢，βt值逐漸增大，粒子的飛行時(shí)間應(yīng)該逐漸減?。糨^為分散，粒子群的多樣性就好，粒子群就不容易陷入局部最優(yōu)．因此T的大小應(yīng)該隨著粒子群的聚集程度增大而增大，隨著種群進(jìn)化程度的降低而減?。碩隨著αt的增大而增大，隨著βt的增大而減小，從而可以將T表示為αt和βt的函數(shù)，即公式(11)所示．由于0<αt≤1,0<βt≤1，所以T0-Tβ

基于上述分析，基本的PSO算法就改為一種自適應(yīng)改變飛行時(shí)間因子的PSO算法，相當(dāng)于提高了PSO算法性能，增強(qiáng)了算法的收斂度．

3.2　改進(jìn)的PSO-K算法步驟

本文提出的改進(jìn)PSO-K算法是采用增加飛行時(shí)間因子的PSO算法，與K-means算法相結(jié)合從而提高PSO-K算法的收斂性．

改進(jìn)的PSO-K算法具體步驟如下：

Step1 對(duì)粒子群進(jìn)行初始化操作．給定固定參數(shù)w，c1，c2，vmin，vmax，T0，Tα，Tβ．從數(shù)據(jù)集X中隨機(jī)選擇k個(gè)中心點(diǎn)，將其作為粒子位置Zr的初值．同時(shí)初始化粒子的速度Vr、個(gè)體最優(yōu)位置Pr和群體最優(yōu)位置Pg．這一過程循環(huán)N次，可生成N個(gè)初始化粒子．

Step2 根據(jù)公式(6)、(7)，計(jì)算粒子的適應(yīng)度值．

Step3 比較每個(gè)粒子的適應(yīng)度值和它所經(jīng)歷的最好位置Pr的適應(yīng)度值，如果更好，更新Pr．

Step4 比較每個(gè)粒子的適應(yīng)度值和群體所經(jīng)歷的最好位置Pg的適應(yīng)度值，如果更好，更新Pg．

Step5 根據(jù)速度公式(4)、(8)式和位置公式(10)-(13)分別更新粒子的速度和位置．

Step6 根據(jù)K-means算法中的最鄰近法則，將每個(gè)樣本重新歸類，得到新的聚類劃分．

Step7 判斷是否滿足終止條件，如果滿足輸出最優(yōu)解；否則返回(2)．

終止條件為粒子群的最好適應(yīng)度值在給定的迭代數(shù)內(nèi)幾乎不改變或達(dá)到給定最大迭代次數(shù)．

4實(shí)驗(yàn)結(jié)果及分析

本實(shí)驗(yàn)為了驗(yàn)證文中改進(jìn)的PSO-K算法的有效性，采用的數(shù)據(jù)集為UCI數(shù)據(jù)集中經(jīng)常用來測試聚類效果的數(shù)據(jù)集Iris數(shù)據(jù)集、wine數(shù)據(jù)集以及Breast Cancer數(shù)據(jù)集．

表1　測試數(shù)據(jù)集表

本文實(shí)驗(yàn)參數(shù)設(shè)置如下：粒子群的種群規(guī)模N=20，加速因子c1=c2=2，粒子群的最大迭代次數(shù)tmax=100，threp=4，threg=5，粒子群的適應(yīng)度方差閾值threσ=0.1．文中增加飛行時(shí)間因子的PSO算法中，在經(jīng)過多次試驗(yàn)之后，發(fā)現(xiàn)T0為0.8~1.0時(shí)算法效果較好，所以本文中T0=0.9．Tα和Tβ可以動(dòng)態(tài)調(diào)整，一般較大的Tα?xí)顾惴ㄈ菀滋^最優(yōu)解陷入振蕩狀態(tài)，較大的Tβ會(huì)使算法容易陷入局部最優(yōu)．經(jīng)過多次實(shí)驗(yàn)，發(fā)現(xiàn)Tα在0.05~0.1之間取值，Tβ在0.4~0.6之間取值時(shí)算法性能較好，本次試驗(yàn)Tα和Tβ分別取值0.08和0.45．實(shí)驗(yàn)中將K-means算法、PSO-K算法與文中算法進(jìn)行比較，每種算法分別執(zhí)行20次，測試結(jié)果取其平均值．算法的聚類準(zhǔn)確率以及適應(yīng)度值的比較分別見表2、表3．

由表2可知，無論是對(duì)低維Iris數(shù)據(jù)集，還是高維wine數(shù)據(jù)集和Breast Cancer數(shù)據(jù)集， K-means算法的聚類準(zhǔn)確率最低，PSO-K算法比K-means算

表2　K-means、PSO-K算法與文中算法聚類準(zhǔn)確率比較

表3　K-means、PSO-K算法與文中算法適應(yīng)度值比較

法聚類效果好一些，相比之下文中算法聚類效果最好．由表3可知，無論是對(duì)低維Iris數(shù)據(jù)集，還是高維wine數(shù)據(jù)集和Breast Cancer數(shù)據(jù)集， K-means算法的適應(yīng)度值最大，PSO-K算法比K-means算法的適應(yīng)度值小一些，相比之下文中算法的適應(yīng)度值最?。m應(yīng)度值越小則表明聚類劃分得到的類內(nèi)數(shù)據(jù)對(duì)象之間緊密程度越好，由此可知文中改進(jìn)算法的聚類效果最好．

為了驗(yàn)證算法的收斂性能，對(duì)Iris數(shù)據(jù)集進(jìn)行測試得到三種算法的收斂曲線圖(圖1)．

圖1　三種算法的收斂曲線圖

從圖1中可以看出 K-means算法前期收斂速度最快，但算法容易收斂于局部解，PSO-K算法由于粒子群早熟收斂問題，收斂速度沒有K-means算法收斂速度快．文中改進(jìn)算法由于增加了自適應(yīng)飛行時(shí)間因子，提高了PSO算法性能，同時(shí)又對(duì)早熟收斂的粒子執(zhí)行變異操作，這樣就增加了算法的收斂速度．所以文中算法的收斂性較理想．

5結(jié)束語

本文研究的基于粒子群算法的K-means算法是聚類分析研究的新的主流方向，通過采用自適應(yīng)飛行時(shí)間因子的PSO算法與K-means算法相結(jié)合，提出了的改進(jìn)的PSO-K算法．通過數(shù)值實(shí)驗(yàn)，文中算法比K-means算法、PSO-K算法具有更優(yōu)的全局收斂性，進(jìn)而驗(yàn)證了本文算法的可行性和有效性．然而與傳統(tǒng)K-means算法相比，文中算法的運(yùn)算時(shí)間有所增加，如何提高K-means算法精確度并同時(shí)保持較快的計(jì)算速度，是進(jìn)一步需要研究的課題．

參考文獻(xiàn)：

[1] Hartigan J A. Clustering Algorithms[M]. New York: John Wiley & Sons Inc, 1975.

[2] Jim Z C, Huang T J, Liaw Y C. A fast k-means clustering algorithm using cluster center displacement[J]. Pattern Recognition, 2009(42):2551-2556.

[3] Aliasa M F, Isa A M, Suaiman S A,etal. Modified moving k-means clustering algorithm[J]. International Journal of Knowledge-based and Intelligent Engineering Systems, 2012(16): 79-86.

[4] Merwe D W, Engelbrecht A P. Data Clustering using Particle Swarm Optimization[C]// Evolutionary Computation, 2003: 215-220.

[5] Chen C Y, Fun Y. Particle Swarm Optimization Algorithm and Its Application to Clustering Analysis[J].International Conference on Networks, 2004, 3(21): 789-794.

[6] Niknam T, Amiri B. An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis[J]. Applied Soft Computing, 2010(10): 183-197.

[7] Kennedy J, Eberhart R. Particle Swarm Optimization[J]. International conference on neural network, 1995, 4(2): 1942-1948.

[8] Shi Y, Eberhart R. A Modified Particle Swarm Optimizer[C]// International conference on Evolutionary Computation Anchorage, 1998: 69-73.

(編輯：姚佳良)