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

武警工程大學研究生管理大隊 陳 思

武警工程大學理學院 劉建平

武警工程大學研究生管理大隊 劉方毅

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

武警工程大學研究生管理大隊 陳 思

武警工程大學理學院 劉建平

武警工程大學研究生管理大隊 劉方毅

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

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

1 引言

美國社會心理學家Kennedy和電器工程師Eberhart受到鳥群覓食行為的啟發，提出一種模仿鳥群覓食行為的多元搜索優化算法，即粒子群（Particle Swarm Optimization，PSO）算法[1-2]。PSO算法模型簡潔，執行效率高，控制參數少，被廣泛應用于復雜優化問題[3]。

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

2 算法介紹

2.1 粒子群算法

在一個涉及到h維解空間的問題中，假設粒子群的規模為m，第i個粒子為，粒子i的速度為。依據不同粒子的適應度值來判定不同粒子的優劣，粒子i適應度最佳的個體最優粒子為，而種群中具有最佳適應度值的粒子為全局最優粒子。粒子群算法在運算過程中，根據速度更新和位置更新公式來實現粒子的移動，速度更新和位置更新的公式如下：

其中，i表示粒子數，t為迭代次數，c1與c2為加速常數，r1和r2是兩個隨機數，ω為慣性權重。

2.2 仿射傳播聚類算法

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

相似度矩陣S的對角線上的數值為偏向參數P，其表明數據點被選為簇中心的可能性的大小，P越大則可能性越大。通常將矩陣S的均值作為初始P值，此時每個數據點均是候選聚類中心，通過調整P值的大小來得到不同個數的聚類中心。

3 CGHPC算法

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

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

為了解決PSO算法的早熟收斂問題，本文提出改進Metropolis接受準則更新全局最優解和動態減少PSO算法粒子集粒子數量兩種策略，實現PSO算法和云遺傳算法的協同。

改進的Metropolis接受準則：若云遺傳算法種群全局最優粒子的適應度fc大于PSO算法的種群全局最優粒子的適應度fp，則將作為共同的全局最優粒子存儲于全局最優數據庫中，并令否則，若Er=exp[-(fc-fp)/A]大于隨機數R，則仍接受為共同全局最優粒子存儲于全局最優數據庫中，若Er小于R，則接受為共同全局最優粒子存儲于全局最優數據庫中，并令。其中A=a/log(t+T)，a為一個趨近于1的常數，T為協同算法最大迭代次數，t為算法當前迭代次數，R=t(D1)/5，t(D1)為區間[0,5]上由t分布產生的隨機數，D1公式如下：

4 收斂性和時間復雜度分析

4.1 收斂性分析

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

定義1 CGHPC算法的適應度函數f為個體空間到正實數空間的映射，則CGHPC算法的全局最優解集為：

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

定義3 CGHPC算法的交叉算子Tc是母體空間到個體空間的映射,其中 k表示可以生成Y的基因位置的個數，則CGHPC算法在執行過程中單點雜交的概率為：

定義4 CGHPC算法的變異算子Tm是個體空間到個體空間的隨機映射。

引理1[9]當PSO中加速度因子，粒子i由轉移到以為中心，任意ε為半徑的球狀區中的一步轉移概率為：

引理2[10]當粒子t時刻的狀態時，其下一時刻的狀態的概率為：

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

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

5 實驗分析

5.1 實驗環境

實驗的環境為: 操作系統Windows 7，CPU采用Intel Core Quad2 Q6600 2.4 GHz CPU、16 GB內存，使用MATLAB2014a進行實驗。

5.2 實驗結果和分析

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

表1 聚類準確度結果對比

如表1為三種算法聚類準確度結果對比，為便于對比分析，表中實驗結果均以“聚類準確度+標準差”形式給出。從表1中可以看出，CGHPC算法的聚類精度結果和雙側t-檢驗結果要優于其他兩種算法。其中，CAVPSO-K算法對Glass數據集進行聚類時，雙側t-檢驗的結果顯示與CGHPC算法的聚類精度相似，但其聚類精度平均值和標準差均劣于CGHPC算法，這也從側面表明CGHPC算法在聚類精度穩定性相對CAVPSO-K算法具有優勢。

表2 最優適應度結果對比

表3 最優適應度均值雙側t-檢驗結果符號及含義

表2和表3分別給出了三種算法的最有適應度結果對比與雙側t-檢驗結果符號及含義。從表中可以看出CGHPC算法最有適應度實驗結果均小于K-means算法和CGHPC算法，聚類效果較好，雙側t-檢驗結果也表明CGHPC算法最優適應度值相交于CAVPSO-K具有較好的穩定性。

6 結論

為了解決K-means算法對初始聚類中心的敏感性、PSO算法易受初始值影響以及PSO算法不具全局收斂性且易陷入早熟收斂等問題，本文提出一種基于仿射傳播和云遺傳的混合粒子群聚類算法，通過引入仿射傳播聚類算法進行粒子群的初始化，克服K-means算法和PSO算法對初始化的敏感性，通過自適應云算子、改進的Metropolis接受準則以及動態調整粒子集規模等策略，實現了云遺傳算法和PSO算法的協同聚類，并進行了全局收斂性證明。實驗結果證明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]劉衍民,牛奔.新型粒子群算法理論與實踐[M].北京:科學出版社,2013:11-15.

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

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

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

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

[8]陽春華,谷麗姍,桂衛華.自適應變異的粒子群優化算法[J].計算機工程,2008,34(16):188-190.

[9]梁旭,黃明,寧濤等.現代智能優化混合算法及其應用[M].北京:電子工業出版社,2014:70-72.

[10]潘峰,周倩,李位星等.標準粒子群優化算法的馬爾科夫鏈分析[J].自動化學報,2013, 39(4):381-388.

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

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

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