武警工程大學(xué)研究生管理大隊(duì) 陳 思

武警工程大學(xué)理學(xué)院 劉建平

武警工程大學(xué)研究生管理大隊(duì) 劉方毅

基于云遺傳的混合粒子群聚類算法

武警工程大學(xué)研究生管理大隊(duì) 陳 思

武警工程大學(xué)理學(xué)院 劉建平

武警工程大學(xué)研究生管理大隊(duì) 劉方毅

針對(duì)K-means算法對(duì)初始聚類中心敏感、粒子群算法易陷入早熟收斂且易受初始值影響以及粒子群算法不能以概率1全局收斂的問題，提出一種基于仿射傳播和云遺傳的改進(jìn)混合粒子群聚類算法，通過(guò)在初始化過(guò)程中引入仿射傳播聚類算法，克服初始值對(duì)算法的影響，通改進(jìn)的Metropolis接受準(zhǔn)則和動(dòng)態(tài)調(diào)整粒子集規(guī)模策略，實(shí)現(xiàn)了云遺傳算法和粒子群算法的協(xié)同聚類，并進(jìn)行了全局收斂性證明、時(shí)間復(fù)雜度分析和實(shí)驗(yàn)分析。

仿射傳播聚類算法；云遺傳算法；粒子群算法；K-means算法

1 引言

美國(guó)社會(huì)心理學(xué)家Kennedy和電器工程師Eberhart受到鳥群覓食行為的啟發(fā)，提出一種模仿鳥群覓食行為的多元搜索優(yōu)化算法，即粒子群（Particle Swarm Optimization，PSO）算法[1-2]。PSO算法模型簡(jiǎn)潔，執(zhí)行效率高，控制參數(shù)少，被廣泛應(yīng)用于復(fù)雜優(yōu)化問題[3]。

為了提高傳統(tǒng)K-means聚類算法的收斂速度和效果，文獻(xiàn)[4]使用PSO算法進(jìn)行初始聚類，將PSO算法得到的聚類結(jié)果作為K-means算法的初始聚類中心；文獻(xiàn)[5]通過(guò)引入變異操作，提高了PSO和K-means混合聚類算法的全局搜索能力。以上算法不能兼顧K-means算法對(duì)初始聚類中心的敏感性和PSO算法易陷入早熟收斂且易受初始值影響的問題，雖然算法的全局搜索能力有所提高，但是文獻(xiàn)[7]指出PSO算法不能以概率1收斂到全局最優(yōu)解，不一定能夠搜索到最佳的聚類結(jié)果。針對(duì)以上問題，本文提出一種基于云遺傳的混合粒子群聚類(Cloud Genetic Hybrid PSO Clustering, CGHPC)算法，通過(guò)在初始化階段引入仿射傳播聚類算法(Aff i nity propagation, AP)進(jìn)行簡(jiǎn)單初始聚類，以克服算法對(duì)初始聚類中心和初始值的敏感性，實(shí)現(xiàn)了云遺傳算法和PSO算法的協(xié)同聚類，并對(duì)算法進(jìn)行了全局收斂性證明、時(shí)間復(fù)雜度分析和實(shí)驗(yàn)分析。

2 算法介紹

2.1 粒子群算法

在一個(gè)涉及到h維解空間的問題中，假設(shè)粒子群的規(guī)模為m，第i個(gè)粒子為，粒子i的速度為。依據(jù)不同粒子的適應(yīng)度值來(lái)判定不同粒子的優(yōu)劣，粒子i適應(yīng)度最佳的個(gè)體最優(yōu)粒子為，而種群中具有最佳適應(yīng)度值的粒子為全局最優(yōu)粒子。粒子群算法在運(yùn)算過(guò)程中，根據(jù)速度更新和位置更新公式來(lái)實(shí)現(xiàn)粒子的移動(dòng)，速度更新和位置更新的公式如下：

其中，i表示粒子數(shù)，t為迭代次數(shù)，c1與c2為加速常數(shù)，r1和r2是兩個(gè)隨機(jī)數(shù)，ω為慣性權(quán)重。

2.2 仿射傳播聚類算法

AP算法將相似度矩陣 S=[s(i,k)]N×N作為輸入，其中s(i,k)的表達(dá)式如下：

相似度矩陣S的對(duì)角線上的數(shù)值為偏向參數(shù)P，其表明數(shù)據(jù)點(diǎn)被選為簇中心的可能性的大小，P越大則可能性越大。通常將矩陣S的均值作為初始P值，此時(shí)每個(gè)數(shù)據(jù)點(diǎn)均是候選聚類中心，通過(guò)調(diào)整P值的大小來(lái)得到不同個(gè)數(shù)的聚類中心。

3 CGHPC算法

在傳統(tǒng)的PSO算法中，隨著算法的進(jìn)行和迭代次數(shù)的增加，粒子群種群多樣性不斷損失，直到算法陷入早熟收斂[8]。因此，定義種群密度（Population Density, PD）來(lái)衡量粒子群種群多樣性水平，作為判斷是否進(jìn)入早熟收斂的依據(jù)。

云遺傳算法在傳統(tǒng)的遺傳算法思想中集合了云模型理論[9]，借助云模型的隨機(jī)性和穩(wěn)定傾向性的特點(diǎn)，采用云模型更新個(gè)體，保證了個(gè)體的多樣性和全局最佳定位，從而有效克服了傳統(tǒng)遺傳算法的早熟收斂和易陷入局部收斂等缺點(diǎn)。

為了解決PSO算法的早熟收斂問題，本文提出改進(jìn)Metropolis接受準(zhǔn)則更新全局最優(yōu)解和動(dòng)態(tài)減少PSO算法粒子集粒子數(shù)量?jī)煞N策略，實(shí)現(xiàn)PSO算法和云遺傳算法的協(xié)同。

改進(jìn)的Metropolis接受準(zhǔn)則：若云遺傳算法種群全局最優(yōu)粒子的適應(yīng)度f(wàn)c大于PSO算法的種群全局最優(yōu)粒子的適應(yīng)度f(wàn)p，則將作為共同的全局最優(yōu)粒子存儲(chǔ)于全局最優(yōu)數(shù)據(jù)庫(kù)中，并令否則，若Er=exp[-(fc-fp)/A]大于隨機(jī)數(shù)R，則仍接受為共同全局最優(yōu)粒子存儲(chǔ)于全局最優(yōu)數(shù)據(jù)庫(kù)中，若Er小于R，則接受為共同全局最優(yōu)粒子存儲(chǔ)于全局最優(yōu)數(shù)據(jù)庫(kù)中，并令。其中A=a/log(t+T)，a為一個(gè)趨近于1的常數(shù)，T為協(xié)同算法最大迭代次數(shù)，t為算法當(dāng)前迭代次數(shù)，R=t(D1)/5，t(D1)為區(qū)間[0,5]上由t分布產(chǎn)生的隨機(jī)數(shù)，D1公式如下：

4 收斂性和時(shí)間復(fù)雜度分析

4.1 收斂性分析

設(shè)Sm={Z=(Z1,Z2,…,Zm)，Zi∈Z(i≤m}為CGHPC算法的種群（優(yōu)化解）空間，S2={(Z1,Z2),Z1,Z2∈S}被定義為母體空間，S被定義為個(gè)體空間，Zi被定義為個(gè)體，h為其維數(shù)，m為種群規(guī)模（優(yōu)化解），t為協(xié)同算法迭代次數(shù)，P為Sm上的概率分布。將CGHPC算法看做采用最優(yōu)保留策略的遺傳算法的拓展，則CGHPC算法由四部分組成：選擇算子Ts，交叉算子Tc，變異算子Tm，粒子移動(dòng)算子Tp。

定義1 CGHPC算法的適應(yīng)度函數(shù)f為個(gè)體空間到正實(shí)數(shù)空間的映射，則CGHPC算法的全局最優(yōu)解集為：

定義2 CGHPC算法的選擇算子Ts是從一個(gè)種群中選擇一個(gè)個(gè)體的隨機(jī)映射。

定義3 CGHPC算法的交叉算子Tc是母體空間到個(gè)體空間的映射,其中 k表示可以生成Y的基因位置的個(gè)數(shù)，則CGHPC算法在執(zhí)行過(guò)程中單點(diǎn)雜交的概率為：

定義4 CGHPC算法的變異算子Tm是個(gè)體空間到個(gè)體空間的隨機(jī)映射。

引理1[9]當(dāng)PSO中加速度因子，粒子i由轉(zhuǎn)移到以為中心，任意ε為半徑的球狀區(qū)中的一步轉(zhuǎn)移概率為：

引理2[10]當(dāng)粒子t時(shí)刻的狀態(tài)時(shí)，其下一時(shí)刻的狀態(tài)的概率為：

引理3[11]采用最優(yōu)保留策略的遺傳算法種群序列{Zt;t≥0}是有限齊次馬爾科夫鏈。

引理4[12]帶有正態(tài)分布變異機(jī)制的粒子群優(yōu)化算法種群序列{Zt;t≥0}是有限齊次馬爾科夫鏈。

5 實(shí)驗(yàn)分析

5.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)的環(huán)境為: 操作系統(tǒng)Windows 7，CPU采用Intel Core Quad2 Q6600 2.4 GHz CPU、16 GB內(nèi)存，使用MATLAB2014a進(jìn)行實(shí)驗(yàn)。

5.2 實(shí)驗(yàn)結(jié)果和分析

實(shí)驗(yàn)數(shù)據(jù)為三組UCI數(shù)據(jù)，分別是Wine、Iris和Glass數(shù)據(jù)集。實(shí)驗(yàn)中分別運(yùn)行K-means算法、CAVPSO-K算法算法以及CGHPC算法。c1=c2=2, ωmax=0.9,ωmin=0.4, λ1=λ2=1.6。種群密度閾值0.05，三個(gè)數(shù)據(jù)集粒子群數(shù)目為50，最大迭代次數(shù)為50次。實(shí)驗(yàn)獨(dú)立進(jìn)行20次，對(duì)實(shí)驗(yàn)結(jié)果求平均值。

表1 聚類準(zhǔn)確度結(jié)果對(duì)比

如表1為三種算法聚類準(zhǔn)確度結(jié)果對(duì)比，為便于對(duì)比分析，表中實(shí)驗(yàn)結(jié)果均以“聚類準(zhǔn)確度+標(biāo)準(zhǔn)差”形式給出。從表1中可以看出，CGHPC算法的聚類精度結(jié)果和雙側(cè)t-檢驗(yàn)結(jié)果要優(yōu)于其他兩種算法。其中，CAVPSO-K算法對(duì)Glass數(shù)據(jù)集進(jìn)行聚類時(shí)，雙側(cè)t-檢驗(yàn)的結(jié)果顯示與CGHPC算法的聚類精度相似，但其聚類精度平均值和標(biāo)準(zhǔn)差均劣于CGHPC算法，這也從側(cè)面表明CGHPC算法在聚類精度穩(wěn)定性相對(duì)CAVPSO-K算法具有優(yōu)勢(shì)。

表2 最優(yōu)適應(yīng)度結(jié)果對(duì)比

表3 最優(yōu)適應(yīng)度均值雙側(cè)t-檢驗(yàn)結(jié)果符號(hào)及含義

表2和表3分別給出了三種算法的最有適應(yīng)度結(jié)果對(duì)比與雙側(cè)t-檢驗(yàn)結(jié)果符號(hào)及含義。從表中可以看出CGHPC算法最有適應(yīng)度實(shí)驗(yàn)結(jié)果均小于K-means算法和CGHPC算法，聚類效果較好，雙側(cè)t-檢驗(yàn)結(jié)果也表明CGHPC算法最優(yōu)適應(yīng)度值相交于CAVPSO-K具有較好的穩(wěn)定性。

6 結(jié)論

為了解決K-means算法對(duì)初始聚類中心的敏感性、PSO算法易受初始值影響以及PSO算法不具全局收斂性且易陷入早熟收斂等問題，本文提出一種基于仿射傳播和云遺傳的混合粒子群聚類算法，通過(guò)引入仿射傳播聚類算法進(jìn)行粒子群的初始化，克服K-means算法和PSO算法對(duì)初始化的敏感性，通過(guò)自適應(yīng)云算子、改進(jìn)的Metropolis接受準(zhǔn)則以及動(dòng)態(tài)調(diào)整粒子集規(guī)模等策略，實(shí)現(xiàn)了云遺傳算法和PSO算法的協(xié)同聚類，并進(jìn)行了全局收斂性證明。實(shí)驗(yàn)結(jié)果證明CGHPC算法可以有效提高聚類精度，跳出早熟收斂，算法性能得到有效提升。

[1]Poli R,Kennedy J,Blackwell T. Particle swarm optimization[J]. Swarm Intelligence,2007,1(1):33-57.

[2]Miyatake M,Veerachary M,Toriumi F,et al.Maximum power point tracking of multiple photovoltaic arrays:a PSO approach [J].IEEE Transactions onAerospace and Electronic Systems,2011,47(1):367-380.

[3]劉衍民,牛奔.新型粒子群算法理論與實(shí)踐[M].北京:科學(xué)出版社,2013:11-15.

[4]謝秀華,謝秀華,李陶深.一種基于改進(jìn) PSO的K-means 優(yōu)化聚類算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2014,24(2) :34-38.

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

[6]王縱虎,劉志鏡,陳東輝.兩階段混合粒子群優(yōu)化算法[J].西南交通大學(xué)學(xué)報(bào),2012,47(6):1034-1040.

[7]張慧斌,王鴻斌,胡志軍.PSO算法全局收斂性分析[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(34):61-63

[8]陽(yáng)春華,谷麗姍,桂衛(wèi)華.自適應(yīng)變異的粒子群優(yōu)化算法[J].計(jì)算機(jī)工程,2008,34(16):188-190.

[9]梁旭,黃明,寧濤等.現(xiàn)代智能優(yōu)化混合算法及其應(yīng)用[M].北京:電子工業(yè)出版社,2014:70-72.

[10]潘峰,周倩,李位星等.標(biāo)準(zhǔn)粒子群優(yōu)化算法的馬爾科夫鏈分析[J].自動(dòng)化學(xué)報(bào),2013, 39(4):381-388.

[11]丁建立,陳增強(qiáng),袁著祉.遺傳算法與螞蟻算法融合的馬爾可夫收斂性分析[J].自動(dòng)化學(xué)報(bào),2004,30(4):629-634.

[12]陶新民,劉福榮,劉玉,等.一種多尺度協(xié)同變異的粒子群優(yōu)化算法[J].軟件學(xué)報(bào),2012,23(7):1805-1815.

[13]張立昂,屈婉玲.Jon K,Eva T.算法設(shè)計(jì)[M].北京:清華大學(xué)出版社,2007:21-41.