許竣瑋，徐蔚鴻

長沙理工大學(xué)計算機與通信工程學(xué)院，長沙 410114

基于擾動免疫粒子群和K均值的混合聚類算法

許竣瑋，徐蔚鴻

長沙理工大學(xué)計算機與通信工程學(xué)院，長沙 410114

1 引言

聚類是信息處理和數(shù)據(jù)挖掘領(lǐng)域的重要技術(shù)之一，人們對它的關(guān)注度已經(jīng)越來越高。K均值聚類算法在數(shù)據(jù)識別方面有著重要的作用，該方法是選取距離來作為相似性度量，然后確定評價聚類結(jié)果質(zhì)量的準(zhǔn)則函數(shù)，最后采用迭代的方法找出使準(zhǔn)則函數(shù)達到極值的最優(yōu)聚類結(jié)果。該方法由于簡單、高效而且需要設(shè)置和調(diào)整的參數(shù)少等優(yōu)點被應(yīng)用到了很多領(lǐng)域。但是該方法存在對初始化的依賴性較高、在多峰函數(shù)中容易過早收斂等問題，因此，算法有時候會出現(xiàn)陷入局部最優(yōu)解的現(xiàn)象。

為解決這類問題，學(xué)者們對這一領(lǐng)域做了大量的研究，文獻[1-3]將遺傳算法等優(yōu)化技術(shù)用來解決陷入局部極值的問題，但是實驗表明，當(dāng)聚類規(guī)模較大時，這些算法容易出現(xiàn)早熟收斂的現(xiàn)象。和遺傳算法相比，粒子群算法（PSO）具有較強的全局搜索能力，通過調(diào)整參數(shù)，PSO的局部搜索能力也可以得到提高，適合編程處理。文獻[4]提出的免疫接種粒子群的聚類算法在粒子的迭代過程中加入了免疫算子，但是該算法中的疫苗是全局最優(yōu)解，因此疫苗的多樣性不高，從而影響了整個種群的多樣性。文獻[5]提出的改進的粒子群和K均值混合算法中的隨機變異操作導(dǎo)致粒子變異不具備優(yōu)化特性，而且單個粒子變異搜索的空間非常有限，找到全局最優(yōu)解的概率較小。文獻[6]提出的基于粒子群的聚類算法采用基于K-中心點算法的改進策略，減少了迭代時間。但是該算法沒有從根本上解決容易陷入局部最優(yōu)解的問題。文獻[7]提出的基于粒計算的K-medoids聚類算法對算法的初始化方式進行了改進，克服了傳統(tǒng)K均值算法初始化的隨機性和快速K-均值算法初始中心可能出現(xiàn)在同一類簇的缺陷，提高了聚類的收斂效率，但該算法中粒子的多樣性較差，算法容易陷入局部最優(yōu)解。文獻[8]提出的一種新的粒子群優(yōu)化聚類方法通過引入改進的交叉、變異算子在一定程度上提高了粒子的多樣性。但算法通過變異跳出局部最優(yōu)的能力較弱，且收斂精度不高。文獻[9]提出的基于人工魚群的優(yōu)化K-means聚類算法提高了K均值聚類算法的初始化質(zhì)量，算法中的“魚”會逐漸向食物增多的方向移動，在處理較規(guī)則數(shù)據(jù)時，算法的聚類效果較好。但算法在處理不規(guī)則數(shù)據(jù)時，尤其對于在某個較大空間中有較大“食物濃度”的數(shù)據(jù)時，算法的聚群行為容易使其陷入該空間中，從而找不到最高的“食物濃度”，而且算法的聚群行為導(dǎo)致算法跳出局部最優(yōu)解的能力較弱。文獻[10]提出的一種有效的K-means聚類中心初始化方法在一定程度上提高了算法初始化質(zhì)量，但是算法中的密度參數(shù)MinPts不易確定，過大會導(dǎo)致那些距離較遠、密度較稀疏的粒子不能單獨成為一類，從而導(dǎo)致聚類效果不佳，過小會導(dǎo)致算法的粒子中心點過多而失去算法原有的優(yōu)勢，不能達到預(yù)期的聚類效果。文獻[11]提出的融合K-調(diào)和均值的混沌粒子群聚類算法利用變尺度混沌搜索提高了算法收斂效率、粒子的多樣性和跳出局部極值的能力，但該方法僅對陷入局部極值的單個粒子進行了混沌變異，粒子搜索空間非常有限，因此，找到全局最優(yōu)解的概率相對較小。

針對上述算法的優(yōu)缺點，本文提出一種基于擾動免疫粒子群和K均值的混合聚類算法。該算法采用K均值將粒子聚類，選定具有最高平均適應(yīng)度值的聚類域用于提取疫苗，因此，從該疫苗集中隨機生成的免疫疫苗具有較強的多樣性和較高的適應(yīng)度值；當(dāng)個體極值和全局極值的連續(xù)停滯更新代數(shù)超過所設(shè)置的閥值時，算法將擾動算子引入到粒子更新公式中，從而改變粒子群的運動方向，該運動具有很好的遍歷性，因此該算法跳出局部極值的能力大大增強。最后，當(dāng)粒子的擾動次數(shù)達到設(shè)置的閥值時，采用K均值算法進一步提高收斂精度。

2 粒子群優(yōu)化算法

2.1 基本粒子群優(yōu)化算法

1995年，PSO算法由美國的Kennedy博士和Eberhart博士提出[12]，它起源于對鳥群覓食行為的仿真。該算法簡潔、易于實現(xiàn)，需要調(diào)整的參數(shù)不多，因此PSO算法引起了廣泛的關(guān)注，并應(yīng)用于目標(biāo)優(yōu)化、機器學(xué)習(xí)、數(shù)據(jù)挖掘、模式識別等領(lǐng)域。

PSO算法首先是隨機生成一組初始化值，然后通過迭代搜尋最優(yōu)值。在迭代過程中每個解都是解空間的一個粒子，粒子的搜尋速度決定了他們的飛行方向和飛行距離。最后，粒子們根據(jù)他們當(dāng)前的飛行方向和飛行距離追隨當(dāng)前最優(yōu)粒子在解空間中進行搜索，通過跟蹤局部極值和全局極值及時更新自己，再通過自適應(yīng)度函數(shù)判斷新位置的自適應(yīng)值，若不滿足結(jié)束條件，則繼續(xù)進行迭代，直到找到最優(yōu)解。

粒子速度更新公式：

2.2 帶擾動算子的粒子群優(yōu)化算法

當(dāng)PSO算法處于進化停滯時，粒子群中的粒子會出現(xiàn)聚集現(xiàn)象，文獻[13]通過嚴(yán)格的數(shù)學(xué)推導(dǎo)得到式（3）：

由式（4）可知，粒子將聚集到由自身極值pu和全局極值pg決定的極值p*上，如果粒子在向p*靠近過程中沒有找到比pg更優(yōu)的位置，則進化將處于停滯狀態(tài)，粒子會逐漸聚集到p*周圍。因此PSO算法可以通過兩種途徑擺脫局部極值：（1）在飛向p*過程中發(fā)現(xiàn)比pg更優(yōu)的位置，但是這個過程發(fā)現(xiàn)更優(yōu)位置的概率較小，因為PSO已經(jīng)陷入局部極值，pg周圍已經(jīng)過高密度的搜索。（2）調(diào)整個體極值和全局極值，使所有的粒子飛向新的位置p*'，經(jīng)歷新的搜索路徑和領(lǐng)域，這樣發(fā)現(xiàn)更優(yōu)解的概率較大。本文采用第二種方法，將連續(xù)停滯代數(shù)t作為觸發(fā)條件對個體極值和全局極值進行擾動，擾動算子為：

式中，t1是個體極值的連續(xù)停滯代數(shù)，t2是全局極值的連續(xù)停滯代數(shù)，T1是個體極值擾動所需的連續(xù)停滯代數(shù)，T2是全局極值擾動所需的連續(xù)停滯代數(shù)，j1、j2是K×D維向量，j1(d)表示向量j1的第d維分量，j2(d)表示向量j2的第d維分量。

引入擾動算子后的粒子i速度更新公式為：

3 K均值聚類算法

MacQueen提出的K均值聚類算法主要用于數(shù)據(jù)對象的聚類，聚類產(chǎn)生的幾組數(shù)據(jù)稱為幾個簇，聚類的過程就是使同簇中的對象的相似性盡可能達到最大，不同簇的對象間的數(shù)據(jù)差異性達到最大，進而分成不同的類。目前，聚類算法已應(yīng)用于數(shù)據(jù)挖掘、模式識別和圖像處理等許多領(lǐng)域，但同時K均值算法存在著以下缺點：（1）聚類結(jié)果好壞受到初始聚類中心的影響，不同的聚類中心可能產(chǎn)生不一樣的聚類結(jié)果；（2）容易陷入局部最優(yōu)，得到的聚類結(jié)果可能不是全局最優(yōu)解。

算法的步驟：

（1）從S個數(shù)據(jù)對象中任意選擇K個對象作為初始聚類中心。

（2）計算樣本集中各個對象與這些聚類中心的距離，并根據(jù)最小距離進行劃分，形成K個聚類域。

（3）計算各聚類域的中心點（每個聚類中所有對象的均值）。

（4）根據(jù)新的中心點對所有對象按照最小距離重新進行聚類劃分。

（5）循環(huán)執(zhí)行（3）到（4），直到每個聚類不再發(fā)生變化為止。

評價函數(shù)為：

式中，K是樣本類數(shù)，xu是類m中數(shù)據(jù)樣本的位置矢量，om是類m的中心點位置矢量，Um是類m中的數(shù)據(jù)樣本。

4 基于擾動免疫粒子群和K均值的混合聚類算法

傳統(tǒng)的基于粒子群的K均值聚類算法中，粒子的初始化方式是隨機生成一組中心點，然后按照最近鄰準(zhǔn)則將數(shù)據(jù)進行聚類，再采用粒子群的尋優(yōu)方式找到較優(yōu)的粒子。該方法的缺點是隨機生成的粒子中心點經(jīng)常出現(xiàn)在數(shù)據(jù)的外圍，導(dǎo)致運算效率降低。為提高粒子群算法的收斂效率，本文在初始讀入數(shù)據(jù)集時，記錄數(shù)據(jù)集各維的最大值和最小值，記第d維最大值xmaxd、最小值，然后在xmaxd和xmind之間隨機生成數(shù)據(jù)中心點的第d維分量，粒子i編碼結(jié)構(gòu)記作：Xi(x11,x12,…,x1d,…,x1D,…,xm1,xm2,…,xmd,…,xmD,…,xK1,xK2,…,xKd,…,xKD),xmd∈[xmind,xmaxd]，其中xmd表示粒子i中數(shù)據(jù)的第m個聚類中心點的第d維分量，其中m∈1,2,…,K；d∈1,2,…,D；K為數(shù)據(jù)分類數(shù)，D為數(shù)據(jù)維度。

粒子群的聚類域編碼結(jié)構(gòu)記作：X(x11,x12,…,x1j,…,x1J;…;xl1,xl2,…,xlj,…,xlJ;…;xL1,xL2,…,xLj,…,xLJ),xlj∈[xminj,xmaxj]，其中，xl1,xl2,…,xlj,…,xlJ表示粒子群的第l個聚類域的中心點，xlj表示粒子群的第l個聚類域中心點的第j維分量，其中l(wèi)∈1,2,…,L，j∈1,2,…,J；L為粒子聚類數(shù)，J為粒子編碼結(jié)構(gòu)的維度即J=K×D。

傳統(tǒng)的粒子群算法中，慣性權(quán)重w的設(shè)置對算法的收斂結(jié)果有著很大的影響，w較大能夠順利地跳出局部最優(yōu)解，w較小有利于算法收斂，本文采用的是基于適應(yīng)度函數(shù)的自適應(yīng)慣性調(diào)整方法[14]。

式中，t為當(dāng)前迭代次數(shù)，a、b分別表示權(quán)值w的下限和上限，fg(t)為第t代粒子群的全局最優(yōu)解的適應(yīng)度值，fui(t)為第t代粒子i個體最優(yōu)解的適應(yīng)度值，fi(t)表示第t代粒子群的全局最優(yōu)解與粒子i的個體最優(yōu)解的適應(yīng)度值比值。

隨著迭代次數(shù)的增大，fui(t)逐漸趨近于fg(t)，因此fi(t)逐漸趨近于1，從而wi(t)逐漸趨近于a。

粒子趨同性是指所有的粒子在尋優(yōu)過程中被全局最優(yōu)粒子所吸引的特性，該特性導(dǎo)致群體的多樣性大大降低，容易造成早熟收斂[13，15]。為此，學(xué)者們開始把免疫機制引入到粒子群算法中來，這在一定程度上提高了粒子擺脫局部極值的能力，但是這些算法提取的疫苗通常是以當(dāng)前最優(yōu)粒子的特征作為有效信息[16]，這仍然會導(dǎo)致大部分粒子向最好的粒子周圍聚集，同樣沒有從根本上解決趨同性問題。為更好地解決該問題，本文算法中的免疫機制采用基于K均值的疫苗提取方法和基于個體濃度的免疫選擇方法。在該算法中，一個粒子表示一組中心點，算法首先進行粒子群初始化和粒子尋優(yōu)，再采用K均值算法對尋優(yōu)后的粒子進行聚類，找到具有最高平均適應(yīng)度值的聚類域，取該聚類域的聚類域中心及其最大半徑作為疫苗的選擇特征；然后根據(jù)該特征隨機生成疫苗集，因此，該疫苗集具有較強的多樣性；最后進行疫苗接種，并根據(jù)種群多樣性保留機制對粒子進行免疫選擇操作。

（1）疫苗的提取

步驟1根據(jù)數(shù)據(jù)各維的最大值和最小值隨機生成一組中心點，每組中心點代表一個粒子，反復(fù)N次生成N個粒子。該粒子群經(jīng)過迭代后生成N個較良個體群X，從X中選出較優(yōu)的L個粒子作為初始聚類中心即：C1(0),C2(0),…,CL(0)。

步驟4采用K均值聚類算法更新各聚類域，設(shè)經(jīng)過s次更新后，聚類域中心的變化幅度小于設(shè)置的閥值ε，此時的聚類中心記為：c1(s),c2(s),…,cL(s)。

步驟5選取具有最優(yōu)平均適應(yīng)度值的聚類域Ubest，使用該聚類域中心及其聚類域的最大半徑構(gòu)建疫苗。

該疫苗是K×D維向量，記作(q1,q2,…,qg,…,qK×D)，它的第g維分量qg是在[eg-hg,eg+hg]區(qū)間生成的一個隨機數(shù)，g∈1,2,…,K×D。因此該疫苗集具有較優(yōu)的適應(yīng)度值和較好的多樣性。

（2）疫苗的接種

算法先采用疫苗提取方法生成待用疫苗，然后判斷是否滿足粒子接種條件。若滿足，則用該疫苗坐標(biāo)取代原有的粒子坐標(biāo)，反之則不進行接種。

粒子i的接種概率為：

式中，f(xi)為粒子i的適應(yīng)度值。

首先針對每個粒子在（0，1）區(qū)間內(nèi)各生成一個隨機數(shù)，若接種概率大于該隨機數(shù)，則進行接種，反之不接種。從數(shù)學(xué)角度分析可以看出，適應(yīng)度值越大接種概率越大，但該方法并非絕對地對適應(yīng)度值大的粒子進行接種，因此該方法在提高粒子群整體適應(yīng)度的同時也保持了粒子群較好的多樣性。然后對接受疫苗接種的個體進行免疫檢測。即：若接種后的個體適應(yīng)度值優(yōu)于父代中所對應(yīng)的個體，則接種成功，否則該個體被父代中所對應(yīng)的個體取代。

（3）免疫選擇

在該粒子群個體更新中，本文采用了以下種群的多樣性保留機制，保證各個層次的適應(yīng)值濃度都維持在一定的水平，防止適應(yīng)值較優(yōu)的粒子濃度過高，從而失去了適應(yīng)值較差但有較好的進化趨勢的粒子，導(dǎo)致粒子的多樣性下降，使得算法容易陷入局部極值點。粒子i的免疫選擇概率公式如下：

其中i=1,2,…,N，α、β為（0，1）的可調(diào)系數(shù)，用于調(diào)整粒子濃度和適應(yīng)度值對免疫選擇概率的影響程度。

算法的流程圖如下：

圖1 基于擾動免疫粒子群和K均值的混合聚類算法流程圖

算法各類參數(shù)的設(shè)置：記錄聚類樣本每一維的最大值和最小值：xmaxd和xmind，其中d=1,2,…,D。設(shè)置數(shù)據(jù)類別數(shù)K，粒子個數(shù)N、個體極值更新所需的連續(xù)停滯代數(shù)T1、免疫選擇的可調(diào)系數(shù)α、β，全局極值更新所需的連續(xù)停滯代數(shù)T2、加權(quán)系數(shù)w的取值范圍(a,b)、系數(shù)c1、c2，提取疫苗的相隔代數(shù)λ以及最大擾動次數(shù)閥值tmax。

粒子群初始化：根據(jù)樣本每一維的最大值和最小值，在該范圍內(nèi)隨機產(chǎn)生一組維數(shù)為D的初始數(shù)據(jù)即一個聚類中心，反復(fù)進行K次，生成K個初始聚類中心即一組中心點，將這組中心點作為一個粒子。然后根據(jù)這組中心點按最近鄰準(zhǔn)則將樣本數(shù)據(jù)劃分到K個聚類域中，用式（7）計算該粒子的適應(yīng)值，同時作為該粒子的個體最優(yōu)位置，初始化速度v，反復(fù)進行N次，共生成N個粒子。比較這些粒子的適應(yīng)值和群體所經(jīng)歷的最好位置的適應(yīng)值，并把全局最優(yōu)粒子存入記憶庫中。

帶擾動算子的粒子迭代更新：粒子根據(jù)公式（5）、（6）采用自適應(yīng)加權(quán)系數(shù)進行進化，更新各個粒子的各維分量，得到數(shù)據(jù)的新聚類中心，然后按照最近鄰準(zhǔn)則進行聚類劃分，根據(jù)自適應(yīng)度函數(shù)計算粒子的適應(yīng)值，比較各粒子適應(yīng)值，并及時更新全局最優(yōu)值，并存入記憶庫中。

5 實驗結(jié)果及分析

實驗環(huán)境：CPU i5 M460@2.53 GHz；內(nèi)存2.0 GB；Windows 7操作系統(tǒng)；編譯軟件MATLAB 7.0。

本文采用常用于檢驗聚類算法效果的標(biāo)準(zhǔn)數(shù)據(jù)集：Iris、Wine、Breast cance、zoo、ionosphere。

數(shù)據(jù)集的詳細信息如表1所示。

表1 原始數(shù)據(jù)信息

對于標(biāo)準(zhǔn)數(shù)據(jù)集，正確率是評價聚類算法好壞的重要指標(biāo)，本文算法分別對數(shù)據(jù)集Iris、Wine、breastCancer、zoo、ionosphere進行20次測試，計算20次的平均正確率，并與K-means算法、PSO+K-means算法、K-medians[17]算法、K-medoids[7]、文獻[6]算法進行比較。

本實驗參數(shù)確定方法如下：

首先根據(jù)參考文獻[18]選取權(quán)重系數(shù)區(qū)間為（0.1，0.9）即a、b分別為0.1和0.9；根據(jù)參考文獻[19]的結(jié)論，選取學(xué)習(xí)因子c1、c2分別為2和2.5；根據(jù)學(xué)術(shù)經(jīng)驗選取粒子數(shù)為20、最大擾動次數(shù)為80、免疫選擇的可調(diào)系數(shù)α、β均為0.5、個體極值和全局極值最大停滯步數(shù)均為5、疫苗提取相隔代數(shù)10；然后，在其他參數(shù)不變的情況下逐個改變根據(jù)學(xué)術(shù)經(jīng)驗選取的參數(shù)設(shè)置，直到取得相對較好、較穩(wěn)定的實驗效果，此時該參數(shù)確定為初步實驗參數(shù)；最后采用初步實驗參數(shù)進行測試，根據(jù)實驗效果對各參數(shù)進行微調(diào)，以獲得更優(yōu)的聚類效果，此時的參數(shù)確定為最終試驗參數(shù)。

經(jīng)確定，實驗參數(shù)權(quán)重w的范圍a、b分別為0.1和0.9、c1、c2為2和2.5、最大擾動次數(shù)30，粒子數(shù)30，個體極值最大停滯步數(shù)和全局極值最大停滯步數(shù)均為3、提取疫苗的相隔代數(shù)8、免疫選擇的可調(diào)系數(shù)α、β分別為0.3、0.7，實驗結(jié)果如表2所示。

表2 各算法的聚類結(jié)果（%）

從表2可以看出，基于擾動免疫粒子群和K均值的混合聚類算法的聚類結(jié)果優(yōu)于其他算法。

為檢驗該聚類算法的穩(wěn)定性，采用以上算法對Iris和zoo數(shù)據(jù)集進行測試，連續(xù)運行50次，并記錄最優(yōu)解出現(xiàn)次數(shù)和迭代次數(shù)，計算出各算法收斂的平均迭代次數(shù)，記最好實驗結(jié)果的正確率為最好正確率，最差實驗結(jié)果的正確率為最差正確率，50次試驗結(jié)果的平均值為平均正確率，采用方差公式計算該50次實驗正確率的方差。各算法對Iris和zoo數(shù)據(jù)集的測試結(jié)果如表3、表4所示。

表3 各算法對Iris數(shù)據(jù)集的正確率比較

從表3、表4可以看出，和其他算法相比，本文算法的平均正確率較高，出現(xiàn)最優(yōu)解的次數(shù)較多，正確率方差最小，且平均迭代次數(shù)較少。因此，該算法的聚類效果較好，收斂結(jié)果比較穩(wěn)定。

該算法對zoo數(shù)據(jù)集的收斂曲線如圖2所示，對iris數(shù)據(jù)集的收斂曲線如圖3、圖4、圖5所示。

從表4可以看出本文算法對zoo數(shù)據(jù)集的收斂最穩(wěn)定，50次實驗找到的最優(yōu)解相同，從圖2可知，該收斂曲線比較平滑，經(jīng)過多次擾動沒有找到更優(yōu)的收斂結(jié)果。

圖2 zoo數(shù)據(jù)集收斂曲線圖

圖4 iris數(shù)據(jù)集收斂曲線圖

表4 各算法對zoo數(shù)據(jù)集的正確率比較

圖3、圖4、圖5是該算法對iris數(shù)據(jù)集測試時出現(xiàn)的三種典型的收斂曲線圖。從圖3可知，該收斂曲線比較平滑，較容易找到了較優(yōu)解，尋優(yōu)過程最順利。從圖4可知，本次收斂的起始全局最優(yōu)適應(yīng)度值為48.77，迭代到第2次時，全局最優(yōu)解的進化出現(xiàn)停滯，到第3次迭代時算法找到了適應(yīng)度值為47.955的較優(yōu)解。從圖5可知，算法的起始全局最優(yōu)適應(yīng)度值為48.21，算法迭代到第3次時陷入局部最優(yōu)，到第12次迭代時算法跳出局部最優(yōu)，從迭代次數(shù)可知，本次收斂從陷入局部最優(yōu)到跳出局部最優(yōu)共經(jīng)歷了3次擾動，通過第3次擾動才找到適應(yīng)度值為47.98的較優(yōu)解，此時，算法再次陷入局部最優(yōu)，通過4次擾動才找到適應(yīng)度值為47.955的較優(yōu)解。

6 結(jié)語

本文針對K均值聚類算法對初始聚類中心的高敏感性、算法容易陷入局部最優(yōu)解等問題提出基于擾動免疫粒子群和K均值的混合聚類算法。該算法的疫苗集具有較強的多樣性和較高的平均適應(yīng)度值，并采用了基于濃度和適應(yīng)度值的免疫選擇策略，使該算法在一定程度上提高了粒子的多樣性；同時，擾動算子的引入極大地提高了算法的遍歷性和算法跳出局部最優(yōu)解的能力。最后，對各個粒子進行K均值操作，提高收斂精度。實驗證明，該算法聚類效果較好，且比較穩(wěn)定。

圖3 iris數(shù)據(jù)集收斂曲線圖

圖5 iris數(shù)據(jù)集收斂曲線圖

[1]Krishma K，Murty M N.Genetic Kmeans algorithm[J]. IEEETransactionsonSystem，ManandCybernetics，Part B，1999，29（3）：433-439.

[2]Maulik U，Bandyopadhay S.Genetic algorithm-based clusteringtechnique[J].PatternRecognition，2000，33（9）：1455-1465.

[3]孟偉，韓學(xué)東.蜜蜂進化型遺傳算法[J].電子學(xué)報，2006，34（7）：1294-1300.

[4]鄭曉鳴，呂士穎，王曉東.免疫接種粒子群的聚類算法[J].電子科技大學(xué)學(xué)報，2007，36（6）：1264-1267.

[5]陶新民，徐晶，楊立標(biāo)，等.一種改進的粒子群和K均值混合聚類算法[J].電子與信息學(xué)報，2010，32（1）：92-97.

[6]姚麗娟，羅可，孟穎.一種基于粒子群的聚類算法[J].計算機工程與應(yīng)用，2012，48（13）：150-153.

[7]馬箐，謝娟英.基于粒計算的K-medoids聚類算法[J].計算機應(yīng)用，2012，32（7）：1973-1977.

[8]盤俊良，石躍祥，李娉婷.一種新的粒子群優(yōu)化聚類方法[J].計算機工程與應(yīng)用，2012，48（8）：179-181.

[9]于海濤，賈美娟，王慧強，等.基于人工魚群的優(yōu)化K-means聚類算法[J].計算機科學(xué)，2012，39（12）：60-64.

[10]熊忠陽，陳若田，張玉芳.一種有效的K-means聚類中心初始化方法[J].計算機應(yīng)用研究，2011，28（11）：4188-4190.

[11]沈明明，毛力.融合K-調(diào)和均值的混沌粒子群聚類算法[J].計算機應(yīng)用研究，2011，47（27）：144-151.

[12]Kennedy J，Eberhart R C.Particle swarm optimization[C]// Proc of the IEEE International Conference on Neural Networks.Pisataway，NJ：IEEEServiceCenter，1995：1942-1948.

[13]Clerc M，Kennedy J.The particle swarm-explosion stability and convergence in amultidimensional complex space[J]. IEEE Transactions on Evolutionary Computation，2002，6（1）：58-73.

[14]廖子貞，羅可，周飛紅，等.一種自適應(yīng)慣性權(quán)重的并行粒子群聚類算法[J].計算機工程與應(yīng)用，2007，43（28）：166-168.

[15]Senthil A M，Ramana M G，RaoM V C.A novel effective particle swarm optimization like algorithm via extrapolation technique[C]//2007 International Conference on Intelligent and Advanced Systems，2007.

[16]行小帥，霍冰鵬.基于免疫的并行單親遺傳算法研究[J].通信學(xué)報，2007，28（8）：99-104.

[17]Har-Peled S，Kushal A.Smaller coresets for k-median andk-meansclustering[J].DiscreteandComputational Geometry，2006，37（1）：3-19.

[18]呂振肅，侯志榮.自適應(yīng)變異的粒子群優(yōu)化算法[J].電子學(xué)報，2004，32（3）：416-420.

[19]Bezdek J C.Pattern Recognition with Fuzzy Objective Function Algorithms[M].New York：Plenum Press，1981.

XU Junwei,XU Weihong

School of Computer and Communication Engineering,Changsha University of Sciences and Technology,Changsha 410114,China

After analyzing the disadvantages of initialization sensitive and local extremum of the K-means algorithm,this paper proposes a hybrid clustering algorithm based on disturbance immune particle swarm optimization and K-means. The new clustering algorithm uses K-means to divide the particles into several categories and then chooses the optimal clustering domain to produce vaccine.After that,it adopts the vaccination and immune selection to improve the diversity of the particles.Meanwhile,in the algorithm,the disturbed arithmetic operators is introduced to break away from the local extremum by changing the movement of the particles when the times of the continuous stagnation exceed the threshold. The K-means clustering algorithm is employed to improve the convergence precision of the algorithm when the times of the disturbance meets the maximum.The experimental results show that the convergence accuracy and stability of the algorithm are good.

particle swarm optimization algorithm;K-means clustering algorithm;vaccination;immune selection

針對傳統(tǒng)K均值聚類算法對初始化敏感和容易陷入局部最優(yōu)的缺點，提出了一種基于擾動免疫粒子群和K均值的混合聚類算法。該算法采用K均值將粒子群進行分類，選擇平均適應(yīng)度值最高的聚類域用于產(chǎn)生疫苗，在粒子更新過程中采用疫苗接種機制和免疫選擇機制提高粒子的多樣性。當(dāng)個體極值和全局極值連續(xù)停滯代數(shù)超過所設(shè)置的閥值時，算法使用擾動算子改變粒子群的運動方向，提高算法跳出局部極值的能力。當(dāng)擾動次數(shù)達到設(shè)置的最大值時，對各個粒子進行K均值操作，提高收斂精度。實驗結(jié)果表明，該算法具有較高的正確率和較好的穩(wěn)定性。

粒子群算法；K均值聚類算法；疫苗接種；免疫選擇

A

TP391.4

10.3778/j.issn.1002-8331.1401-0440

XU Junwei,XU Weihong.Hybrid clustering algorithm based on disturbance immune particle swarm optimization and K-means.Computer Engineering and Applications,2014,50（22）：163-169.

湖南省科技計劃項目（No.FJ3005）。

許竣瑋（1986—），男，碩士，研究領(lǐng)域為智能信息處理；徐蔚鴻（1963—），男，教授，博士生導(dǎo)師，主要研究領(lǐng)域為人工智能及應(yīng)用、機器學(xué)習(xí)、圖像處理與模式識別。E-mail：328214680@qq.com

2014-01-25

2014-03-17

1002-8331（2014）22-0163-07

CNKI網(wǎng)絡(luò)優(yōu)先出版：2014-06-04,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1401-0440.html