顧忠偉，徐福緣

（1.上海理工大學(xué) 管理學(xué)院，上海200093；2.浙江科技學(xué)院 經(jīng)濟管理學(xué)院，浙江 杭州310023）

0 引 言

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

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

1 粒子群算法

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

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

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

2 基于自適應(yīng)混沌粒子群的聚類算法

2.1 編碼方式

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

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

結(jié)合兩種算法的特點，新算法適應(yīng)度目標(biāo)函數(shù)值設(shè)為

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

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

2.2 自適應(yīng)粒子群聚類

PSO 算法在尋優(yōu)的過程中，每個粒子都試圖朝著最優(yōu)的方向飛行，當(dāng)某個粒子找到一個最優(yōu)位置時，在認(rèn)知部分和社會環(huán)境部分的影響下，其它粒子將迅速向其靠擾，因此算法很容易進入局部最優(yōu)的狀態(tài)。式 （1）中加速因子c1和c2設(shè)置不當(dāng)?shù)那闆r下，算法進入局部最優(yōu)的狀態(tài)更為明顯，此時算法將會出現(xiàn)早熟的現(xiàn)象。針對此問題，本文對粒子群的加速因子c1和c2進行自適應(yīng)動態(tài)設(shè)置，使c1和c2的大小根據(jù)粒子群的實時狀態(tài)進行調(diào)節(jié)。

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

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

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

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

2.3 混沌搜索與邊界緩沖墻

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

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

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

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

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

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

3 算法具體流程

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

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

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

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

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

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

步驟6 結(jié)束條件判斷。當(dāng)算法結(jié)束條件滿足時終止算法，并輸出最優(yōu)的簇中心矩陣。若不滿足，則轉(zhuǎn)到步驟2。

算法流程如圖1所示。

圖1 算法流程

4 實驗分析

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

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

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

表1 實驗數(shù)據(jù)描述

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

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

表2 各算法迭代次數(shù)及適應(yīng)度值

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

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

5 結(jié)束語

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

［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）.［胡偉，徐福緣，馬慶國.基于人工免疫原理的數(shù)據(jù)流聚類算法研究 ［J］.計算機科學(xué)，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）.［胡偉，徐福緣.基于改進免疫算法的數(shù)據(jù)聚類策略研究 ［J］.計算機工程與設(shè)計，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.