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

許竣瑋，徐蔚鴻

長(zhǎng)沙理工大學(xué)計(jì)算機(jī)與通信工程學(xué)院，長(zhǎng)沙 410114

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

許竣瑋，徐蔚鴻

長(zhǎng)沙理工大學(xué)計(jì)算機(jī)與通信工程學(xué)院，長(zhǎng)沙 410114

1 引言

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

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

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

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

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

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

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

粒子速度更新公式：

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

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

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

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

引入擾動(dòng)算子后的粒子i速度更新公式為：

3 K均值聚類算法

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

算法的步驟：

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

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

（3）計(jì)算各聚類域的中心點(diǎn)（每個(gè)聚類中所有對(duì)象的均值）。

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

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

評(píng)價(jià)函數(shù)為：

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

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

傳統(tǒng)的基于粒子群的K均值聚類算法中，粒子的初始化方式是隨機(jī)生成一組中心點(diǎn)，然后按照最近鄰準(zhǔn)則將數(shù)據(jù)進(jìn)行聚類，再采用粒子群的尋優(yōu)方式找到較優(yōu)的粒子。該方法的缺點(diǎn)是隨機(jī)生成的粒子中心點(diǎn)經(jīng)常出現(xiàn)在數(shù)據(jù)的外圍，導(dǎo)致運(yùn)算效率降低。為提高粒子群算法的收斂效率，本文在初始讀入數(shù)據(jù)集時(shí)，記錄數(shù)據(jù)集各維的最大值和最小值，記第d維最大值xmaxd、最小值，然后在xmaxd和xmind之間隨機(jī)生成數(shù)據(jù)中心點(diǎn)的第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個(gè)聚類中心點(diǎn)的第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個(gè)聚類域的中心點(diǎn)，xlj表示粒子群的第l個(gè)聚類域中心點(diǎn)的第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è)置對(duì)算法的收斂結(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個(gè)體最優(yōu)解的適應(yīng)度值，fi(t)表示第t代粒子群的全局最優(yōu)解與粒子i的個(gè)體最優(yōu)解的適應(yīng)度值比值。

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

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

（1）疫苗的提取

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

步驟4采用K均值聚類算法更新各聚類域，設(shè)經(jīng)過(guò)s次更新后，聚類域中心的變化幅度小于設(shè)置的閥值ε，此時(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ū)間生成的一個(gè)隨機(jī)數(shù)，g∈1,2,…,K×D。因此該疫苗集具有較優(yōu)的適應(yīng)度值和較好的多樣性。

（2）疫苗的接種

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

粒子i的接種概率為：

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

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

（3）免疫選擇

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

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

算法的流程圖如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)語(yǔ)

本文針對(duì)K均值聚類算法對(duì)初始聚類中心的高敏感性、算法容易陷入局部最優(yōu)解等問(wèn)題提出基于擾動(dòng)免疫粒子群和K均值的混合聚類算法。該算法的疫苗集具有較強(qiáng)的多樣性和較高的平均適應(yīng)度值，并采用了基于濃度和適應(yīng)度值的免疫選擇策略，使該算法在一定程度上提高了粒子的多樣性；同時(shí)，擾動(dòng)算子的引入極大地提高了算法的遍歷性和算法跳出局部最優(yōu)解的能力。最后，對(duì)各個(gè)粒子進(jìn)行K均值操作，提高收斂精度。實(shí)驗(yàn)證明，該算法聚類效果較好，且比較穩(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ìn)化型遺傳算法[J].電子學(xué)報(bào)，2006，34（7）：1294-1300.

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

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

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

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

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

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

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

[11]沈明明，毛力.融合K-調(diào)和均值的混沌粒子群聚類算法[J].計(jì)算機(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].計(jì)算機(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é)報(bào)，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é)報(bào)，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

針對(duì)傳統(tǒng)K均值聚類算法對(duì)初始化敏感和容易陷入局部最優(yōu)的缺點(diǎn)，提出了一種基于擾動(dòng)免疫粒子群和K均值的混合聚類算法。該算法采用K均值將粒子群進(jìn)行分類，選擇平均適應(yīng)度值最高的聚類域用于產(chǎn)生疫苗，在粒子更新過(guò)程中采用疫苗接種機(jī)制和免疫選擇機(jī)制提高粒子的多樣性。當(dāng)個(gè)體極值和全局極值連續(xù)停滯代數(shù)超過(guò)所設(shè)置的閥值時(shí)，算法使用擾動(dòng)算子改變粒子群的運(yùn)動(dòng)方向，提高算法跳出局部極值的能力。當(dāng)擾動(dòng)次數(shù)達(dá)到設(shè)置的最大值時(shí)，對(duì)各個(gè)粒子進(jìn)行K均值操作，提高收斂精度。實(shí)驗(yàn)結(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.

湖南省科技計(jì)劃項(xiàng)目（No.FJ3005）。

許竣瑋（1986—），男，碩士，研究領(lǐng)域?yàn)橹悄苄畔⑻幚恚恍煳跌櫍?963—），男，教授，博士生導(dǎo)師，主要研究領(lǐng)域?yàn)槿斯ぶ悄芗皯?yīng)用、機(jī)器學(xué)習(xí)、圖像處理與模式識(shí)別。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