基于自適應混沌粒子群的聚類算法

顧忠偉，徐福緣

（1.上海理工大學 管理學院，上海200093；2.浙江科技學院 經濟管理學院，浙江 杭州310023）

0 引 言

經典的聚類算法［1－6］有模糊c 均值、K－means、PSO－c均值、CURE等。其中模糊c均值聚類算法的研究和應用相當廣泛。為了使模糊c 均值聚類算法的性能更加優越，許多學者基于不同角度對它進行了改進。如Jingwei Liua等提出了一種新型的基于核化的模糊c－均值聚類算法，對聚類中心的權重系數進行了修正，并利用標準Iris數據庫和正常腫瘤基因芯片上的數據樣本進行測試［7］；Du－Ming Tsai等對距離度量的方法進行了改進，并將聚類中心與質心結合起來研究，提出了一種新的基于距離度量的模糊c－均值聚類算法［8］；Dan Li等提出了基于最近鄰間隔的模糊c－均值聚類算法，該算法通過使用數據的分布間隔時間表示最近鄰集，對部分缺失數據集進行深度挖掘［9］。

模糊c－均值聚類算法在處理小規模低維數據集時效果良好，但是，該算法在處理高維數據集時表現出自適應性不強、易陷入局部極小值和聚類效果不理想等缺陷，針對此問題，本文提出了一種基于自適應混沌粒子群的聚類算法，理論分析結果和實驗結果表明，其聚類效果優于現有的C－means、標準PSO 等算法。

1 粒子群算法

粒子群算法，也稱粒子群優化算法 （particle swarm optimization，PSO）［10，11］。算法中的每個粒子表示所求問題的一個解，通過迭代更新來尋找最優解。粒子通過位置和速度來進行更新，粒子的好壞程度由一個合適的適應度值來決定。PSO 算法相對于其它優化算法而言具有簡單、容易實現、所需參數較少等特點。標準粒子群算法的數學描述如下所示：

假設粒子群X ＝（X1，X2，…，Xn）由n個粒子組成，每個粒子的搜索空間為D 維，群體中第i個粒子表示為Xi＝（xi1，xi2，…，xid）。設第i個粒子在尋優過程中的最優位置為Pi＝（pi1，pi2，…，pid），群體中最優的粒子表示為Pg＝（pg1，pg2，…，pgd）。每個粒子的速度和位置按如下公式進行更新

式中：w 為慣性權重，c1和c2為加速因子，rand（）為 ［0，1］之間隨機數；i＝1，2，…，n；d＝1，3，…，D；t為迭代次數，每個粒子根據初始條件按式 （1）和式 （2）進行迭代更新。從上面的表達式可以看出，每個粒子的飛行速度由3部分來決定，第一部分為粒子自身的歷史飛行速度vid（t）；第二部分為粒子對自身最優位置的思考，表示粒子按照自身的認知水平朝最優方向飛行；第三部分為社會環境部分，表示其它粒子群體對自身位置的影響。因此，從本質上講，粒子的運動軌跡由粒子自身部分、認知部分和社會環境部分來引導。

2 基于自適應混沌粒子群的聚類算法

2.1 編碼方式

模糊c均值聚類算法是利用隸屬度函數將種群中的個體劃歸為某個類別的算法，該算法首先將數據劃分為c個模糊類，然后利用公式求出每個模糊類的聚類中心，最后將隸屬度函數和聚類中心結合起來使模糊目標函數最小化。由于模糊c均值聚類算法的目標函數存在許多局部極小值，所以在迭代的過程中，目標函數很可能會陷入局部極小值，從而使算法無法找到全局最優解。特別是當聚類的數據向量比較多并且維數較大時，模糊c均值聚類算法更易呈現早熟現象。為了克服這種缺點，本文將改進的粒子群算法與模糊c均值聚類算法進行整合，構造出自適應混沌粒子群聚類算法。自適應混沌粒子群聚類算法的編碼方式如下：

設X ＝｛x1，x2，…，xn｝為數據集樣本，簇的數目為c，采用實數編碼方式，每個粒子用一個三維矩陣X［i］［k］［d］表示，其中i＝1，2，…，n；k＝1，2，…，c；d＝1，2，…，D。對數據集樣本各簇中心vj進行初始化，然后賦值給各個粒子X［i］［k］［d］。

結合兩種算法的特點，新算法適應度目標函數值設為

式中：m——模糊聚類的權重指數，uij——粒子X［i］［k］［d］歸屬于第j類的模糊隸屬度，uij可表示為

式中：γj——第j類的聚類中心，γj可表示為

2.2 自適應粒子群聚類

PSO 算法在尋優的過程中，每個粒子都試圖朝著最優的方向飛行，當某個粒子找到一個最優位置時，在認知部分和社會環境部分的影響下，其它粒子將迅速向其靠擾，因此算法很容易進入局部最優的狀態。式 （1）中加速因子c1和c2設置不當的情況下，算法進入局部最優的狀態更為明顯，此時算法將會出現早熟的現象。針對此問題，本文對粒子群的加速因子c1和c2進行自適應動態設置，使c1和c2的大小根據粒子群的實時狀態進行調節。

在第t次迭代時，整個粒子群的平均適應度fp（t）可以表示為

式中：fi（t）——第i個粒子在第t 次迭代時的適應度值。fg（t）是當前粒子群中占據最優位置的粒子適應度值，那么加速因子c1和c2可分別表示為

式中：k為協調因子。通過對粒子的尋優特點進行研究，可以發現粒子的初速度對PSO 算法的性能也有所影響。當粒子的初速度過大時，粒子很可能會飛躍局部區域，從而錯過搜索局部區域的機會；當粒子的初速度過小時，粒子又將陷入局部區域，從而使算法出現早熟現象。針對這種現象，本文將對粒子的初始速度進行處理。具體的調節方案如下

式中：σ——權重系數，vmaxid（t）——第d維的最大值，vminid（t）——第d 維的最小值，tmax——迭代的最大數目。經過改進后，粒子的速度可表示為

2.3 混沌搜索與邊界緩沖墻

混沌是非線性復雜系統中廣泛存在的一種現象，混沌優化能夠在預先設定的范圍內對特定群體進行擾動和遍歷。為了增強粒子群的多樣性，可以利用混沌優化對粒子群進行擾動，以混沌搜索替代隨機搜索，最終使整個粒子群進入最優平衡狀態。本文利用Logistic混沌系統，迭代產生相應的混沌序列，Logistic混沌系統的定義如下所示

其中，zk∈（0，1）為實值序列，k＝0，1，2，…，n，本文取μ＝4。設擾動量Δx ＝（Δx1，Δx2，…，Δxn），混沌擾動范圍為［－xmax，xmax］，將zk的各個分量載波到擾動范圍內，則

粒子群經過混沌擾動后，不僅種群的多樣性得到提高，而且全局搜索能力得到大大的增強。與此同時，粒子的位置和速度有可能會超越其最大值。為此，傳統的方法通常是預先將粒子的位置和速度設定在一定的范圍內，使超過負邊界和正邊界的粒子都限定在邊界上。傳統方法操作簡單且計算量小，但是這種預先設定固定極值的做法會帶來較大的誤差。為了避免這種缺陷，本文將利用邊界緩沖墻對越界粒子進行處理。邊界緩沖墻的思想如下

若xid（t）＜ad，則xid（t）的值為

若xid（t）＞bd，則xid（t）的值為

其中，sgn為符號函數，L∈［0，1］，ad表示粒子在第d 維的下限，bd表示粒子在第d 維的上限。邊界緩沖墻根據粒子的實際飛行情況來處理越界粒子，動態設定粒子的緩沖邊界，有效解決了傳統處理方法所帶來的問題。

3 算法具體流程

基于自適應混沌粒子群的聚類算法流程如下所示：

步驟1 初始化數據樣本集中簇的數目和聚類中心。事先確定好模糊權重指數m，然后將簇的數目c進行初始化，并對聚類中心γj進行賦值，之后對粒子進行編碼并初始化粒子的飛行速度vid（t）。

步驟2 計算隸屬度、更新每個簇的聚類中心。利用式（4）計算每個粒子X［i］［k］［d］的隸屬度uij，同時利用式（5）對每類的聚類中心γj進行更新。

步驟3 更新每個粒子的適應度目標值。利用式 （3）對每個粒子X［i］［k］［d］的適應度目標值進行計算，并根據目標值大小確定最優位置Pi和最優粒子Pg。

步驟4 更新所有粒子的位置和速度。使用式 （10）和式 （2）更新每個粒子的速度和位置，并同時啟用邊界緩沖墻，利用式 （13）和式 （14）將粒子的位置進行自適應調節。

步驟5 混沌搜索和擾動。利用式 （11）和式 （12）對粒子群進行混沌擾動優化，形成新的群體。

步驟6 結束條件判斷。當算法結束條件滿足時終止算法，并輸出最優的簇中心矩陣。若不滿足，則轉到步驟2。

算法流程如圖1所示。

圖1 算法流程

4 實驗分析

為了測試本文所提算法的有效性，現進行實驗仿真分析，并將本文所提算法的性能與其它幾種常見的聚類算法進行比較。實驗環境為：至強E5504 四核處理器，2G DDR3REG ECC內存，SATA2 500G 硬盤，英特爾5500服務器芯片組主板，操作系統為Microsoft Windows 2003 Server。

實驗中參數設置如下：C－means算法中模糊權重指數m 為4，給定的類別數為3；PSO 算法中慣性權重w 為0.5，加速因子c1和c2為1.42；文獻 ［12］算法中交叉因子和變異因子分別設置為pc＝0.9、pm ＝0.08，其中的慣性權重為0.75，加速因子為1.5；本文算法中權重系數σ＝3，協調因子k＝4，慣性權重w ＝0.5，混沌系統擾動系數u＝4，模糊權重指數m ＝3，緩沖墻的厚度L ＝0.3。

聚類實驗的數據來源于在UCI機器學習庫中的數據庫，分別是Iris.dat、wine.dat、cmc.dat和zoo.dat這4個數據庫。這4個數據庫的簡要描述見表1。

表1 實驗數據描述

分別用C－means、PSO、文獻 ［12］中的算法和本文所提算法對以上4個數據集進行聚類分析，為了避免其它外來隨機因素的影響，將這4種算法各運行100 次，取平均值作為最后的對比結果，并對相應的結果進行統計分析。

從表2中可以看出，用C－means、PSO、文獻 ［12］中的算法和本文所提算法對以上4個數據集進行聚類時，本文所提出的算法實現數據聚類的平均迭代次數最少，適應度目標值也最小。本文所提出的算法聚類Iris時，在第26次迭代時算法收斂，所得到的平均適應度值為86.6；Cmeans聚類Iris時，在第76次迭代時算法收斂，所得到的平均適應度值為97.3；標準PSO 聚類算法聚類Iris時，在第48次時算法收斂，所得到的平均適應度值為94.2；文獻［12］算法聚類Iris時，在第32 次迭代時算法收斂，所得到的平均適應度值為89.4。本文所提出算法的聚類時間是C－means聚類算法的34.2%，是標準PSO 聚類算法的54.2%，是文獻 ［12］算法的81.3%。同時，本文所提算法的聚類適應度目標值相對于其它3 種算法分別減少了11%、8.1%和3.1%。圖2為各種算法聚類精度對比。

表2 各算法迭代次數及適應度值

圖2 各種算法聚類精度對比

從圖2可以看出，在聚類Iris、wine、cmc和zoo這4種數據樣本集時，本文所提算法的平均精度分別為89.1%、67.4%、68.3%和66.9%，要優于其它3種算法的聚類效果。本文所提算法在聚類zoo時，聚類精度為86.2%，相比于其它3種算法，其聚類精度分別提高了28.8%、23.9%和8.02%。

5 結束語

本文提出的基于自適應混沌粒子群的聚類算法將模糊c均值聚類和改進的PSO算法進行了有效的整合，避免了原模糊c均值聚類算法在處理高維數據集時表現出自適應性不強、易陷入局部極小值和聚類效果不理想等缺陷。通過選取UCI機器學習庫中的4種數據樣本集進行測試，測試結果表明，相比于C－means、PSO、文獻 ［12］中的算法，本文所提出的算法在聚類精度、收斂速度及適應性上具有明顯的優勢。

［1］Hu Wei，Xu Fuyuan.An improved localization algorithm for performance improvement［J］.International Journal of Mobile Communications，2012，10 （4）：337－349.

［2］HU Wei，XU Fuyuan，MA Qingguo.Research of data stream clustering algorithms based on artificial immune principle ［J］.Computer Science，2012，39 （2）：195－197 （in Chinese）.［胡偉，徐福緣，馬慶國.基于人工免疫原理的數據流聚類算法研究 ［J］.計算機科學，2012，39 （2）：195－197.］

［3］HU Wei，XU Fuyuan.Data clustering algorithm based on improved immune algorithm ［J］.Computer Engineering and Design，2012，33 （10）：3940－3944 （in Chinese）.［胡偉，徐福緣.基于改進免疫算法的數據聚類策略研究 ［J］.計算機工程與設計，2012，33 （10）：3940－3944.］

［4］Abdolreza Hatamlou，Salwani Abdullah，Hossein Nezamabadipour.A combined approach for clustering based on K－means and gravitational search algorithms ［J］.Swarm and Evolutionary Computation，2012，6 （10）：47－52.

［5］Liu Ruochen，Zhang Xiangrong.Immunodomaince based clonal selection clustering algorithm ［J］.Applied Soft Computing，2012，12 （1）：302－312.

［6］Mohammad Taherdangkoo，Mohammad Hadi Bagheri.A powerful hybrid clustering method based on modified stem cells and fuzzy C－means algorithms［J］.Engineering Applications of Artificial Intelligence，2013，26 （5）：1493－1502.

［7］Liu Jingwei，Xu Meizhi.Kernelized fuzzy attribute C－means clustering algorithm ［J］.Fuzzy Sets and Systems，2008，159（18）：2428－2445.

［8］Tsai Du－Ming，Lin Chung－Chan.Fuzzy C－means based clustering for linearly and nonlinearly separable data ［J］.Pattern Recognition，2011，44 （8）：1750－1760.

［9］Li Dan，Gu Hong，Zhang Liyong.A fuzzy c－means clustering algorithm based on nearest－neighbor intervals for incomplete data［J］.Expert Systems with Applications，2010，37 （10）：6942－6947.

［10］Tang Jun，Zhao Xiaojuan.An enhanced opposition－based particle swarm optimization ［C］//Global Congress on Intelligent Systems，2009：149－153.

［11］Wang Hui，Wu Zhijian，Liu Yong，et al.Particle swarm optimization with a novel multi－parent crossover operator［C］//The 4th International Conference on Natural Computation，2008：664－668.

［12］Kuo RJ，Syu YJ，Chen Zhen－Yao，et al.Integration of particle swarm optimization and genetic algorithm for dynamic clustering［J］.Information Sciences，2012，195 （15）：124－140.