改進(jìn)粒子群算法在數(shù)據(jù)聚類中的應(yīng)用

王金永， 董玉民

（1.青島理工大學(xué) 計(jì)算機(jī)工程學(xué)院，山東 青島 266033；2.青島理工大學(xué) 網(wǎng)絡(luò)中心，山東 青島 266033）

1 粒子群算法和聚類分析的研究背景

1995年，Eberhart和Kennedy在長期觀察鳥群、魚群覓食行為規(guī)律的啟發(fā)下，提出了粒子群算法（Particle Swarm Optimization，PSO），該算法是一種基于群智能（Swarm Intelligence）的優(yōu)化算法［1］。鳥群在覓食行為遇到危險(xiǎn)信號(hào)時(shí)，每一只鳥通過合作與競爭產(chǎn)生強(qiáng)大的力量來盡快地取得食物、避開危險(xiǎn)。該算法可以根據(jù)當(dāng)前的搜索情況，動(dòng)態(tài)調(diào)整其搜索策略。由于算法收斂速度快，全局搜索能力強(qiáng)，需要設(shè)置參數(shù)少，近年來提出了許多改進(jìn)算法來增強(qiáng)跳出局部極值的能力，受到學(xué)術(shù)界的廣泛重視［2］。

由于粒子群算法的優(yōu)良特性，在很多相關(guān)領(lǐng)域引起了對(duì)這一新生事物的迅速關(guān)注。首先是在1997年，由Eberhart R C［3］等提出了二進(jìn)制粒子群算 法。隨 后，Shi Y［4－5］和Eberhart R C［6］在1998年對(duì)速度項(xiàng)引入了慣性權(quán)重參數(shù)，提高了算法的收斂性，并在程序運(yùn)行過程中不斷動(dòng)態(tài)地調(diào)整慣性權(quán)重來調(diào)節(jié)算法的收斂速度，該方程被稱之為標(biāo)準(zhǔn)的PSO算法［7］。為了改善算法的收斂性，1999年，Clerc等引入了收縮因子，提出了帶收縮因子的CF－PSO算法［8－9］。

聚類分析（cluster analysis）簡稱聚類（clustering），是將數(shù)據(jù)觀測對(duì)象逐步劃分成子集的過程，每個(gè)子集是一個(gè)簇（cluster），通過聚類，結(jié)果是每一個(gè)簇中的對(duì)象彼此相似，并且與其他簇中的對(duì)象不相似。由于簇是數(shù)據(jù)對(duì)象的集合，因此數(shù)據(jù)對(duì)象的簇可以看作隱含的類。在這種意義下，聚類有時(shí)又稱為自動(dòng)分類。聚類可以自動(dòng)地發(fā)現(xiàn)大量數(shù)據(jù)的分組，這是聚類分析的突出優(yōu)點(diǎn)。對(duì)聚類分析的算法研究也就成為研究的熱點(diǎn)。為了很好地處理分類屬性數(shù)據(jù)，文獻(xiàn)［10］提出一種加權(quán)粗糙聚類算法，該算法聚類結(jié)果不受數(shù)據(jù)樣本輸入順序的影響，根據(jù)粗糙集理論中的信息增益概念自適應(yīng)地更新聚類過程，來獲取全局最優(yōu)的聚類權(quán)重和聚類劃分。近幾年對(duì)數(shù)據(jù)聚類的研究越來越多，出現(xiàn)了一些新型聚類算法，如張莉［11］等提出了基于樣本預(yù)處理的核聚類算法，王順久［12］等提出了基于樣本的投影尋蹤聚類算法，王娜［13］等提出了基于流行距離的迭代優(yōu)化聚類算法等。

2 粒子群算法的原理與數(shù)學(xué)描述

粒子群算法的基本思想來源于自然界中的鳥群覓食行為，在算法中，每一個(gè)優(yōu)化問題的解看作搜索空間中的一只鳥，即“粒子”。算法開始時(shí)，首先在可行解空間中隨機(jī)初始化一群粒子，即隨機(jī)生成初始種群，并且根據(jù)目標(biāo)函數(shù)計(jì)算出每一個(gè)粒子的適應(yīng)度值。每個(gè)粒子在空間中飛行的方向和距離由運(yùn)動(dòng)的速度決定，一般情況下，就像鳥兒追隨離食物最近的鳥群一樣，粒子也會(huì)追隨離最優(yōu)粒子距離最近的粒子群周圍搜索。在每一次的迭代中，粒子將根據(jù)兩個(gè)極值來不斷更新迭代，一個(gè)是粒子自身經(jīng)歷過的最優(yōu)位置，也就是自身最優(yōu)解，另外一個(gè)是整個(gè)種群經(jīng)歷過的最優(yōu)位置，也就是全局極值。

為了將粒子群算法實(shí)現(xiàn)，需先將算法用數(shù)學(xué)形式描述：假設(shè)由n個(gè)粒子組成的種群Z＝｛Z1，Z2，…，Zn｝，其中問題的一個(gè)解用每一個(gè)粒子的位置Zi＝｛zi1，zi2，…，ziD｝來表示，D表示粒子的空間搜索維數(shù)。種群中的每一個(gè)粒子通過不斷調(diào)整自己的位置Zi來搜索更新解。在搜索過程中，每一個(gè)粒子都能記住自己經(jīng)歷過的最好位置，即搜索到的自身最好解，記做pid，以及整個(gè)粒子群經(jīng)歷過的最好的位置，即目前搜索到的群體最優(yōu)解，記做pgd。除了用位置表示粒子信息外，用速度來表示粒子的運(yùn)動(dòng)方向，記做Vi＝｛vi1，vi2，…，viD｝，當(dāng)pid和pgd都找到后，粒子的速度更新情況見式（1），位置更新情況見式（2）［14］。

式中：vid（t＋1）——第i個(gè)粒子在第t＋1次迭代中第d維上的速度；

ω——粒子運(yùn)動(dòng)的慣性權(quán)重；

η1，η2——加速常數(shù)；

rand（）——0～1之間的隨機(jī)數(shù)。

搜索運(yùn)動(dòng)過程中，為了防止粒子的運(yùn)動(dòng)速度過大，即算法收斂速度過快，可以設(shè)速度上限vmax，當(dāng)vid（t＋1）≥vmax時(shí)，vid（t＋1）＝vmax；當(dāng)vid（t＋1）≤－vmax時(shí)，vid（t＋1）＝－vmax。

從粒子速度更新式（1）和位置更新式（2）可以看出，粒子的運(yùn)動(dòng)方向由3部分影響因素決定：自己原有的速度vid（t）、粒子當(dāng)前位置與自身最佳位置的距離pid－zid（t）、粒子當(dāng)前位置與群體最佳位置的距離pgd－zid（t），并分別設(shè)置每一部分的權(quán)重來表示相對(duì)重要性，分別由權(quán)重系數(shù)ω，η1，η2表示，當(dāng)找到足夠好的最優(yōu)解或達(dá)到最大迭代次數(shù)時(shí)，算法結(jié)束。影響粒子運(yùn)動(dòng)方向的3部分影響因素的加權(quán)求和示意圖如圖1所示。

圖1 3種移動(dòng)方向的加權(quán)求和示意圖

3 粒子群算法的流程描述

經(jīng)過了解粒子群算法的概念、基本原理和數(shù)學(xué)描述，下面介紹粒子群算法的基本流程，如圖2所示。

圖2 算法流程圖

從粒子群算法流程圖可以看出，粒子群算法參數(shù)相對(duì)較少，數(shù)學(xué)原理簡單，迭代循環(huán)簡單易懂，算法易于實(shí)現(xiàn)。為了描述算法流程，需要先定義幾個(gè)參數(shù)和函數(shù)，先假定粒子群種群規(guī)模為n。

設(shè)Zi＝｛zi1，zi2，…，ziD｝表示第i個(gè)粒子的位置；

fitness（Zi）表示求第i個(gè)粒子的解，也就是適應(yīng)度函數(shù)；

Vi＝｛vi1，vi2，…，viD｝表示第i個(gè)粒子的速度向量；

pid表示自身搜索到的最優(yōu)解，即第i個(gè)粒子經(jīng)歷到的最優(yōu)位置；

pgd表示全局搜索到的最優(yōu)解，即種群中適應(yīng)度最高的最優(yōu)位置。

下面對(duì)算法流程圖2做詳細(xì)說明：

第1步：初始化粒子群。

1）：隨機(jī)初始化種群，隨機(jī)初始化粒子位置Zi＝｛zi1，zi2，…，ziD｝；

2）隨機(jī)初始化粒子速度Vi＝｛vi1，vi2，…，viD｝；

3）計(jì)算適應(yīng)度函數(shù)fitness（Zi），并令pid＝zid，i＝1，2，…，n；d＝1，2，…，D；

4）初始化全局最優(yōu)解pgd，選擇種群中的適應(yīng)度函數(shù)值最高的粒子的位置向量初始化pgd，i＝1，2，…，n。

第2步：按照下面步驟算法循環(huán)迭代，直到滿足算法結(jié)束的條件為止。

1）選擇恰當(dāng)?shù)乃俣葢T性因子ω；

2）計(jì)算群體中所有粒子的適應(yīng)度函數(shù)值fitness（Zi），當(dāng)出現(xiàn)個(gè)體適應(yīng)度函數(shù)值大于當(dāng)前個(gè)體最優(yōu)適應(yīng)度函數(shù)值時(shí)，即fitness（zid）＞fitness（pid），令pid＝zid；

3）當(dāng)種群中個(gè)體最優(yōu)值pid大于當(dāng)前群體最優(yōu)值 時(shí)，則 更 新pgd的 值，即fitness（pid）＞fitness（pgd），令pgd＝pid；

4）依據(jù)式（1）和式（2）不斷更新每一個(gè)粒子的速度和位置，即更新vid和zid的值。

4 粒子群算法的參數(shù)分析

在基本粒子群算法的數(shù)學(xué)描述中（見式（1）和式（2）），主要有3個(gè)影響決定粒子速度和位置的參數(shù)，分別是速度慣性權(quán)重ω、速度調(diào)節(jié)參數(shù)η1，η2，參數(shù)的選擇對(duì)粒子群算法的性能和效率有很大的影響，ω表示粒子從當(dāng)前時(shí)刻到下一時(shí)刻保持的運(yùn)動(dòng)慣性，η1，η2表示粒子向自身當(dāng)前最優(yōu)位置pid和群體當(dāng)前最優(yōu)位置pgd運(yùn)動(dòng)的加速權(quán)重。下面分析3個(gè)系數(shù)表示的意義：如果慣性權(quán)重ω＝0，那么說明粒子的運(yùn)動(dòng)速度沒有慣性，不受當(dāng)前運(yùn)動(dòng)速度的影響，粒子群將收斂到當(dāng)前的全局最優(yōu)位置，不會(huì)再去搜索更優(yōu)解。如果參數(shù)η1＝0，那么說明不會(huì)追隨自身最優(yōu)位置，粒子失去“自我認(rèn)知”能力，只具有“社會(huì)認(rèn)知”能力，此時(shí)粒子群收斂速度很快，同時(shí)容易陷入局部極值。如果參數(shù)η2＝0，那么說明粒子失去“社會(huì)認(rèn)知”能力，只具有“自我認(rèn)知”能力，這時(shí)候相當(dāng)于多個(gè)粒子各自獨(dú)立搜索，很難搜索收斂到全局最優(yōu)解。通過分析得知，3個(gè)參數(shù)都會(huì)影響算法的搜索效率，針對(duì)不同的問題，選擇適合的參數(shù)才能取得更好的收斂速度和穩(wěn)定性，根據(jù)大量實(shí)踐經(jīng)驗(yàn)，令ω取0～1之間的隨機(jī)數(shù)，η1，η2分別取2，可以取得較好的效果。

5 粒子群算法在數(shù)據(jù)聚類中的應(yīng)用

設(shè)N個(gè)樣品構(gòu)成的樣品集X＝｛Xi，i＝1，2，…，N｝，其中Xi為n維特征向量，用表示第j個(gè)聚類的中心，用表示樣品Xi到對(duì)應(yīng)的聚類中心的歐氏距離，聚類問題就是要找到一個(gè)劃分ω＝｛ω1，ω2，…，ωM｝，使得總的類內(nèi)離散度和J達(dá)到最?。?5］：

聚類準(zhǔn)則函數(shù)J即為各類樣品到對(duì)應(yīng)聚類中心的距離的總和。

當(dāng)聚類中心確定時(shí)，可以由最近鄰法則決定聚類的劃分。即對(duì)樣品Xi，若第j類的聚類中心滿足，就是樣品Xi與聚類中心之間的距離是所有樣品與聚類中心距離的最小值，見式（4），則樣品Xi屬于聚類ωj。

在用粒子群優(yōu)化算法求解聚類問題時(shí)，每一個(gè)粒子就是問題的一個(gè)可行解，所有的粒子組成粒子群（也就是解集）。根據(jù)對(duì)聚類結(jié)果理解的不同，對(duì)解集的描述可以有兩種形式：第1種是類ω1，ω2，…ωM為解集，也就是聚類結(jié)果；第2種是以中心集合（j＝1，2，…，M）為解集，即聚類結(jié)果。論文中采用第2種形式，用基于聚類中心集合作為聚類問題的對(duì)應(yīng)解，也就是說解集是由M個(gè)聚類中心組成的，M是已知的聚類數(shù)目。

根據(jù)粒子群算法的數(shù)學(xué)描述式（1）和式（2），可以得到粒子i的速度和位置更新公式：

根據(jù)已經(jīng)定義好的粒子群結(jié)構(gòu)，采用粒子群聚類算法便可以求得聚類問題的最優(yōu)解。通過剛才介紹粒子群聚類算法的原理、算法描述和算法實(shí)現(xiàn)步驟，通過編寫程序，并且在MATLABR2013a編程環(huán)境寫運(yùn)行，可以觀察分析粒子群算法的具體應(yīng)用。首先給出粒子群聚類算法的核心代碼，第一大模塊是根據(jù)式（5）和式（6）更新粒子的位置和速度代碼［16］：

第二大模塊是利用距離的平方和的平方根來度量粒子之間的距離，具體代碼如下：

第三大模塊是求粒子的適應(yīng)度，根據(jù)粒子群聚類算法的粒子適應(yīng)度更新條件，適應(yīng)度取歐式聚類的倒數(shù)，程序代碼如下：

下面對(duì)某地區(qū)的煤層地質(zhì)條件數(shù)據(jù)，應(yīng)用粒子群優(yōu)化算法進(jìn)行聚類分析，根據(jù)不同煤層塊段的特征：平均厚度、煤層傾角、離差系數(shù)、煤層合格標(biāo)準(zhǔn)、含矸系數(shù)等進(jìn)行分類，聚類后的數(shù)據(jù)可以用于指導(dǎo)煤礦的開采，提高煤礦開采的安全性和效率。

各煤層塊段的特性指標(biāo)值見表1。

表1 各煤層塊段的特性指標(biāo)值

程序中設(shè)定樣本數(shù)據(jù)的聚類數(shù)目為K＝3，維數(shù)D＝5，通過運(yùn)行程序，pso聚類的全局最優(yōu)位置、函數(shù)適應(yīng)度如下，并且繪制了函數(shù)適應(yīng)度曲線。

實(shí)驗(yàn)?zāi)康模簩?duì)上述實(shí)驗(yàn)數(shù)據(jù)應(yīng)用粒子群聚類算法，在MATLABR2013a編程環(huán)境下運(yùn)行聚類算法程序，觀察聚類效果。

實(shí)驗(yàn)的適應(yīng)度函數(shù)是：result＝dis；%適應(yīng)度函數(shù)。

粒子群聚類算法中“函數(shù)適應(yīng)度－迭代次數(shù)”曲線如圖3所示。

圖3 粒子群聚類算法中“函數(shù)適應(yīng)度－迭代次數(shù)”曲線

1）當(dāng)?shù)螖?shù)MaxDT＝100時(shí)，迭代次數(shù)－適應(yīng)度值曲線見圖3（a）。

最后結(jié)果是：ans＝3.240801487577032e－04。

2）當(dāng)?shù)螖?shù)MaxDT＝200時(shí)，迭代次數(shù)－適應(yīng)度值曲線見圖3（b）。

最后結(jié)果是：ans＝1.617915530278782e－04。

3）當(dāng)?shù)螖?shù)MaxDT＝500時(shí)，迭代次數(shù)－適應(yīng)度值曲線見圖3（c）。

最后結(jié)果是：ans＝6.465458242701003e－05。

實(shí)驗(yàn)結(jié)果分析：由于“w＝1－t／MaxDT”，即慣性因子與迭代次數(shù)有關(guān)，進(jìn)而影響粒子速度更新公式“v（i，：）＝w＊v（i，：）＋c1＊rand＊（y（i，：）－x（i，：））＋c2＊rand＊（pg－x（i，：））；”，也就影響了粒子的位置“pos（i，：）＝x（i，：）＋v（i，：）”，最終也會(huì)影響粒子之間的歐氏距離，也就是實(shí)驗(yàn)的適應(yīng)度函數(shù)是：“result＝dis；%適應(yīng)度函數(shù)”，所以圖3中的3幅圖像的初始適應(yīng)度有差別，但是隨著迭代次數(shù)的增加，都在不斷的減小。從3次（迭代次數(shù)分別是100、200、500）程序運(yùn)行情況可以得出：適應(yīng)度ans即result代表樣品和聚類中心的歐氏距離，隨著迭代次數(shù)越大，函數(shù)的適應(yīng)度ans越小，最終趨于零。說明樣品與聚類中心的距離不斷減小，當(dāng)?shù)螖?shù)大約為500時(shí)，適應(yīng)度測量函數(shù)歐式距離趨于零，數(shù)據(jù)的聚類效果越好。

6 K－均值聚類算法思想

粒子群優(yōu)化算法的缺點(diǎn)是易陷入局部極值點(diǎn)；全局搜索能力強(qiáng)，但是搜索精度不高；PSO算法同時(shí)記憶位置和速度信息，高效的信息共享機(jī)制可能導(dǎo)致粒子尋優(yōu)時(shí)都移向某個(gè)全局最優(yōu)點(diǎn)。粒子群算法的優(yōu)點(diǎn)是收斂速度較快；全局搜索能力強(qiáng)，能夠有效避免早熟；粒子群中多個(gè)粒子同時(shí)搜索，具有并行性；需要設(shè)置的參數(shù)較少，因此算法簡單，易于實(shí)現(xiàn)。

K－均值算法思想簡單易行，是一種傳統(tǒng)的聚類分析方法，但是當(dāng)數(shù)據(jù)中存在離群點(diǎn)時(shí)，K－均值聚類效果會(huì)更不理想，K－均值的聚類結(jié)果受初始聚類中心的選擇影響較大，如果初始聚類中心選擇不當(dāng)，算法可能收斂于一般結(jié)果。認(rèn)識(shí)到粒子群算法和K－均值聚類算法各自的優(yōu)缺點(diǎn)之后，可以設(shè)想將兩種算法都進(jìn)行改進(jìn)結(jié)合，充分利用各自的優(yōu)點(diǎn)，避開兩種算法的缺點(diǎn)，融合并利用全局搜索能力較強(qiáng)的粒子群優(yōu)化算法和局部尋優(yōu)能力較強(qiáng)的K－均值聚類算法，提出了一種基于K－均值的粒子群優(yōu)化聚類算法，該算法充分優(yōu)化了K－均值聚類算法，提高了局部搜索和全局搜索的能力，加快了算法的收斂速度［17］。

K－均值聚類基本思想是：首先初始化數(shù)據(jù)，隨機(jī)選擇K個(gè)聚類中心，然后按照歐氏距離緊鄰原則，根據(jù)每一個(gè)樣品與初始聚類中心的相似程度重新劃分聚類；計(jì)算該類所有元素的平均值，重新確定新的聚類中心；逐步依次迭代，直到聚類中心不再變化。假設(shè)模式樣本集為X＝｛Xi，i＝1，2，…，n｝，其中Xi為D維模式向量，聚類問題就是要找到一個(gè)劃分ω＝｛ω1，ω2，…，ωm｝，滿足下式

并且使得總的類間離散度和式（8）達(dá)到最?。?/p>

J——各類樣本到對(duì)應(yīng)聚類中心的歐氏距離的總和。

7 基于K－均值的粒子群聚類算法流程及其應(yīng)用

算法首先需要根據(jù)近鄰法則，確定粒子的位置編碼和各類的聚類中心；然后根據(jù)聚類劃分，按照式（8）計(jì)算類內(nèi)離散度和J；最后計(jì)算粒子的適應(yīng)度函數(shù)之和fitness，當(dāng)適應(yīng)度越大，說明聚類效果越好。所以基于K－均值的粒子群聚類算法描述如下：

1）初始化種群。在初始化粒子群時(shí)，現(xiàn)將每一個(gè)樣品隨機(jī)對(duì)應(yīng)于某一類，并作為初始劃分，計(jì)算初始粒子的位置編碼，即計(jì)算各類的聚類中心；初始化粒子的速度；計(jì)算粒子的適應(yīng)度；反復(fù)進(jìn)行N次，生成N個(gè)初始化的粒子群。

2）將粒子現(xiàn)在的適應(yīng)度值和經(jīng)歷過的最好位置pid的適應(yīng)度值進(jìn)行比較，及時(shí)更新pid的信息。

3）將粒子現(xiàn)在的適應(yīng)度值和種群經(jīng)歷過的最好位置pgd的適應(yīng)度值進(jìn)行比較，及時(shí)更新pgd的信息。

4）根據(jù)式（1）和式（2）不斷調(diào)整粒子的速度和位置。

5）對(duì)新個(gè)體進(jìn)行K－均值聚類優(yōu)化，按照下面兩步進(jìn)行K－均值優(yōu)化：

①根據(jù)最近鄰法則，按照粒子的聚類中心編碼，確定對(duì)應(yīng)粒子的聚類劃分；

②更新粒子的適應(yīng)度值，計(jì)算新的聚類中心，更新原來的粒子編碼。由于K－均值聚類具有較強(qiáng)的局部搜素能力，此時(shí)引入K－均值優(yōu)化后的粒子群聚類算法可以得到很好的改善，提高了算法的收斂速度和搜索效率。

6）不斷迭代，如果達(dá)到最大迭代次數(shù)或者聚類中心不再發(fā)生變化，則算法結(jié)束，否則轉(zhuǎn)到步驟2）繼續(xù)迭代。

基于K－均值粒子群優(yōu)化算法的核心代碼如下［16］：

%更新粒子的速度和位置

對(duì)表1中的數(shù)據(jù)，輸出的適應(yīng)度－迭代次數(shù)可以形象的表示隨著迭代次數(shù)的增加，聚類效果的變化過程如圖4所示。

圖4 基于K－均值粒子群優(yōu)化算法運(yùn)行圖

實(shí)驗(yàn)結(jié)果：

1）當(dāng)?shù)螖?shù)為50次時(shí)（見圖4（a）），實(shí)驗(yàn)結(jié)果如下：

fpclu＝3 2 1 3 3 1 1 1 1 3 1 3 1 3 1 3 1 3 1 1

說明在s20×5數(shù)據(jù)中，第1、4、5、10、12、14、16、18行數(shù)據(jù)歸為一類；第2行數(shù)據(jù)歸為一類；第3、6、7、8、9、11、13、15、17、19、20行數(shù)據(jù)歸為一類。輸出的適應(yīng)度值為：

kfitness＝2.158006918671278e－04。

2）當(dāng)?shù)螖?shù)為200次時(shí)（見圖4（b）），實(shí)驗(yàn)結(jié)果如下：

fpclu＝2 2 3 2 2 3 3 3 3 2 3 2 3 2 3 2 1 2 1 3

說明在s20×5數(shù)據(jù)中，第1、2、4、5、10、12、14、16、18行數(shù)據(jù)歸為一類；第3、6、7、8、9、11、13、15、20行數(shù)據(jù)歸為一類；第17、19行數(shù)據(jù)歸為一類。輸出的適應(yīng)度值為：

kfitness＝1.412634231439157e－04。

3）迭代次數(shù)為300次時(shí)（見圖4（c）），結(jié)果如下：

kpclu＝1 1 2 1 1 2 3 3 3 1 2 3 2 1 2 1 2 1 2 3

說明在s20×5數(shù)據(jù)中，第1、2、4、5、10、14、16、18行數(shù)據(jù)歸為一類；第3、6、11、13、15、17、19行數(shù)據(jù)歸為一類；第7、8、9、12、20行數(shù)據(jù)歸為一類。輸出的適應(yīng)度值為：

kfitness＝5.077943793714523e－05。

從圖4可以看出，輸出的適應(yīng)度－迭代次數(shù)的增加，聚類結(jié)果不斷得到優(yōu)化，但是相對(duì)于粒子群聚類，改進(jìn)后的聚類算法能夠在較少的迭代次數(shù)內(nèi)完成聚類，說明基于K－均值的粒子群聚類算法更加優(yōu)秀。在前面介紹的粒子群聚類算法中（見圖3），需要經(jīng)過大約500次的迭代，聚類結(jié)果相對(duì)穩(wěn)定，才滿足程序結(jié)束條件；而在基于K－均值的粒子群聚類算法中，在較少的迭代次數(shù)內(nèi)（大約300次）就達(dá)到聚類結(jié)果的穩(wěn)定，程序結(jié)束，較好地完成了數(shù)據(jù)聚類。

8 結(jié) 語

闡述了粒子群算法的原理，以及在數(shù)據(jù)聚類中的應(yīng)用。通過分析和論述，可以看到雖然粒子群算法出現(xiàn)的相對(duì)較晚，在短短的20年發(fā)展歷程中，展現(xiàn)出強(qiáng)大的生命力和研究潛力，但是算法自身存在一些缺點(diǎn)，比如容易陷入局部極值、對(duì)離散的問題處理不佳等原因，后期出現(xiàn)了很多對(duì)基本粒子群算法的改進(jìn)。粒子群算法是一種仿生算法，自身具備的一些優(yōu)秀的進(jìn)化特點(diǎn)使其成為智能優(yōu)化領(lǐng)域的一個(gè)研究熱點(diǎn)。但是由于粒子群算法的數(shù)學(xué)基礎(chǔ)相對(duì)薄弱，對(duì)這個(gè)新興的智能優(yōu)化算法的研究需要長期的不斷完善的過程。

［1］ 趙志剛，常成.簡化的自適應(yīng)粒子群優(yōu)化算法［J］.廣西大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，5（5）：793－798.

［2］ 段曉東，王存睿，劉向東.粒子群算法及其應(yīng)用［M］.沈陽：遼寧大學(xué)出版社，2007.

［3］ Eberhart R C，Kennedy J.A discrete binary version of particle swarm algorithm［C］／／Proceedings of the IEEE International Conference on System，Man，and Cybernetics，1997：4104－4108.

［4］ Shi Y，Eberhart R C.A modified particle swarm optimizaerf［C］／／Proceedings of the IEEE International Conference on Evolutionary Computation，1998：69－73.

［5］ Shi Y，Eberhart R C.Fuzzy adaptive particle swarm optimization［C］／／Proceedings of the Congress on Evolutionary Computation，2001：101－106.

［6］ Eberhart R C，Kennedy J.Swarm intelligence［M］.［S.l.］：Morgan Kaufmanns，2001.

［7］ Shi Y，Eberhart R C.Parameter Selection in Particle Swarm Optirnization［C］／／Proceedings of Annual Conference on Evolutionary Programming，1998：591－600.

［8］ Clerc M，Kennedy J.The particle swarm optimization：Explosion，stability，and convergence in multi－dimensional complex space［J］.IEEE Transaction on Evolutionary Computation，2002，6（1）：58－73.

［9］ Shi Y，Eberhart R C.A modified particle swarm optimization［C］／／Proceedings of IEEE International Conference on Evolutionary Computation，1998：69－73.

［10］ Jian Fu，Jian Yin.Weighted Rough Clustering on Categorical Data［C］／／International Conference on Computer Science and Service System（CSSS），Nanjing，2011：939－944.

［11］ 張莉，周偉達(dá)，焦李成.核聚類算法［J］.計(jì)算機(jī)學(xué)報(bào)，2002，25（6）：587－590.

［12］ 王順久，倪長健.投影尋蹤動(dòng)態(tài)聚類模型及其應(yīng)用［J］.哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2009，41（1）：178－181.

［13］ 王娜，杜海峰，王孫安.一種基于流形距離的迭代優(yōu)化聚類算法［J］.西安交通大學(xué)學(xué)報(bào)，2009，43（5）：76－79.

［14］ 黃太安，生佳根，徐紅洋，等.一種改進(jìn)的簡化粒子群算法［J］.計(jì)算機(jī)仿真，2013，2（2）：327－330.

［15］ 楊淑瑩.模式識(shí)別與智能計(jì)算［M］.北京：電子工業(yè)出版社，2008：337－346.

［16］ 程序員聯(lián)合開發(fā)網(wǎng)（programmers united develop net）［EB／OL］.［2015－08－15］.http：／／www.pudn.com.

［17］ 陳小全，張繼紅.基于改進(jìn)粒子群算法的聚類算法［C］／／.2011年第17屆全國信息存儲(chǔ)技術(shù)大會(huì)（IST），2011.