改進的粒子群模糊聚類方法

黃新建，牛 強

（中國礦業大學 計算機科學與技術學院，江蘇 徐州221116）

0 引 言

模糊C均值聚類算法［1－2］（FCM）是目前使用最多的劃分式聚類方法之一。由于FCM擴展了隸屬度的取值范圍，因此有著較好的數據表達能力和聚類效果［3］，且FCM的理論已相當完善，應用也比較廣泛。但當數據集維數較高時，FCM存在聚類效果較差，很難找到全局最優等問題［4－5］。作為一種群體智能優化算法，粒子群優化算法 （PSO）的基本思想是通過種群在個體之間的信息共享和協同工作來尋找最優解。由于模糊聚類問題一定條件下可歸結為優化問題［6］，已有很多學者提出了基于粒子群的模糊聚類算法［7－9］，Thomas A.Runkler等在文獻 ［9］中提出了旨在保證模糊聚類約束條件的方法，解決了以隸屬度對粒子進行編碼時產生的問題。但基于粒子群的模糊聚類算法大多以聚類中心對粒子進行編碼［10－11］，較少以隸屬度對粒子進行編碼。文獻 ［9］中方法雖使隸屬度滿足了模糊聚類的約束條件，但仍然存在對噪音較敏感，處理樣本數小于樣本維數的數據時效果較差等問題。針對以上問題，在以隸屬度對基于粒子群的模糊聚類算法進行編碼的基礎上，本文提出一種改進的隸屬度分配方法。實驗表明改進的方法較好地處理了含噪音的數據，并在樣本數小于樣本維數的數據上取得較之前方法更為理想的效果，較好地處理了低維數據和高維數據。

1 模糊C均值聚類算法

已知樣本集X＝ ｛X1，X2，…，Xn｝有n個樣本，分成C （2≤C＜n）類，其中Xi∈RP。FCM的目標函數為

m＞1為常數，ei（i＝1，2，…，C）為類i的聚類中心。μik（i＝1，2，…，C；k＝1，2，…，n）為樣本k對類i的隸屬度，滿足

并給出式子

在式 （2）條件下通過反復迭代式 （3）和式 （4），使FCM的目標函數式 （1）取得極小值，即為FCM［12］。

2 基于粒子群的模糊聚類算法

2.1 PSO算法

D維空間中，有m個粒子，粒子i的位置為Xi＝ ［Xi1，Xi2，…，XiD］，飛行速度為Vi＝ ［Vi1，Vi2，…，ViD］，個體歷史最優位置為Pi＝ ［Pi1，Pi2，…，PiD］，群體歷史最優位置為Pg＝ ［Pi1，Pi2，…，PiD］，則用下式更新粒子的速度 和位置［13－14］

式 （5）和式 （6）中：i＝1，2，…，m——不同的粒子；C1、C2——大于0的學習因子，分別調節該粒子向自身歷史最優位置和族群歷史最優位置方向飛行的最大步長，取C1＝C2＝1.5；R1、R2為介于 ［0，1］之間的隨機數；n為迭代次數［15］。

2.2 基于PSO的模糊聚類算法

設樣本數為n，分成c類。PSO應用于模糊聚類并以隸屬度編碼時，粒子為n×c列的一維行向量，可表示為｛x11，x12，x1c，…，xn1，xn2，…，xnc｝，xij為樣本i對類j的隸屬度。采用隸屬度編碼時基本步驟為：先根據式 （4）求出粒子對應的聚類中心，后由該聚類中心和粒子值通過FCM的目標函數式 （1）求出粒子適應度。

至此，可得出基于粒子群的模糊聚類算法以隸屬度編碼時的流程如圖1所示。

在計算聚類中心時，粒子的值需滿足FCM的約束條件式 （2）。文獻 ［9］中提出的約束方法為。

設wik為第樣本k對類i的隸屬度，算法運行時wik限定在 ［－5，5］內。計算粒子適應度時先采用sigmoid函數式（7）將 wik轉化為uik∈ ［0，1］

圖1 基于PSO的模糊聚類流程

當樣本對各類的隸屬度之和不為1時，文獻 ［9］的方法把不足或多出的部分平均地進行了增加或減少，對離樣本近的類和離樣本遠的類同等對待，沒有考慮樣本與各個類之間的距離，收斂速度較慢，聚類效果較差。

本文提出的改進方法為：設uik為樣本k對類i的隸屬度，且uik∈ ［0，1］，li為樣本k與類i的距離。≠1時，根據li決定uik增加或減少的幅度。

當樣本對各類的隸屬度之和不為1時，文獻 ［9］的方法把不足或多出的部分平均地進行了增加或減少。本文改進方法考慮了樣本與各類之間的距離關系，對于距離近的類，和小于1時隸屬度加的多，和大于1時減的少；對于距離遠的類，和小于1時隸屬度加的少，和大于1時減的多。

保證約束條件的同時，改進方法在每次迭代均使樣本向較相似的類進行靠近，同時遠離差異較大的類，以加快收斂速度，提升聚類效果。每次約束時，改進方法增加了計算距離的運算過程，也省去文獻 ［9］中方法需使用式（7）的轉換過程。

3 實驗測試與比較分析

實驗分別使用了經典的FCM算法、文獻 ［9］中方法以及本文的改進方法進行比較研究。使用的兩組典型數據集來自文獻 ［9］中比較方法時所使用的數據集，測試的數據集分別為：

（1）single outlier數據集： ［－1.2，0.5，0.6，0.7，1.5，1.6，1.7］，7組1維數據，其中 ［0.5，0.6，0.7］一類，［1.5，1.6，0.7］一類，－1.2為單異常點。

（2）lung cancer數據集：32組56維數據 （第4維和第38維中存在5個未知量，故只使用32組54維），分3類，第1類9組，第2類13組，第3類10組。

取粒子個數為10，迭代次數為100，表1至表2給出了運行各算法后對各項聚類指標取平均后的值，各表中的值具體體現了各方法的最優優化結果。其中DIC表示平均類內距離，DBC表示平均類間距離，OFV表示目標函數值，SCR表示成功分類率。

表1 Single Outlier數據集

表2 Lung Cancer數據集

由表1知，當數據集含噪音時，本文改進方法同FCM一樣在各種性能上優于文獻 ［9］中方法，本文改進方法與FCM在小數據集中的差別并不明顯。

由表2知，本文改進方法文獻 ［9］中方法明顯優于FCM，即基于PSO的FCM以隸屬度編碼時可較好處理樣本維數大于樣本數的數據集，且本文改進方法在樣本維數大于樣本數的數據集中的效果明顯優于文獻 ［9］中方法。

取粒子個數為10，迭代次數從1遞增至100，隨迭代次數的增加，圖2至圖5給出各方法的分類成功率和目標函數值的變化情況，各圖體現出各方法隨迭代次數的變化所取得的優化結果。其中DIC表示平均類內距離，DBC表示平均類間距離，OFV表示目標函數值，SCR表示成功分類率。

由圖2及圖3知，本文改進方法和FCM在各種性能上均優于文獻 ［9］中方法，且與FCM在較小數據集上區別并不明顯。相比FCM，本文改進方法在目標函數值中的波動較大，而在分類成功率中區別極小。

圖4和圖5表明此時FCM效果較差，即基于PSO的FCM以隸屬度編碼時較FCM有明顯優勢。同時本文改進方法顯著優于文獻 ［9］方法，即本文方法在樣本維數大于樣本數的數據集中明顯優于文獻 ［9］中方法。

圖5 Lung cancer數據集目標函數值比較

綜上所述，由single outlier數據集實驗知，相比本文改進方法和FCM，文獻 ［9］中方法對噪音較敏感，本文改進方法在小數據集中與FCM差別不大；由lung cancer數據集實驗知，FCM對于樣本維數大于樣本數的數據集聚類效果較差，基于PSO的FCM以隸屬度編碼時可較好解決，同時本文改進方法優于文獻 ［9］中方法。可知，本文改進方法在不同數據集中都優于文獻 ［9］中方法，顯著提升了聚類效果，進一步加快了收斂速度。

4 結束語

針對基于PSO的FCM以隸屬度編碼時出現的問題，本文改進了之前實現約束條件的方法。之前基于PSO的FCM以隸屬度編碼時不能較好地處理含噪音的數據集以及樣本維數大于樣本數的數據集。實驗表明本文的改進方法較之前方法可較好地處理噪聲，并進一步提升了在樣本維數大于樣本數的數據集上的聚類效果，取得了較優的效果，使得基于PSO的FCM以隸屬度編碼時也可較好地處理含噪音的數據和樣本維數大于樣本數的數據集。

［1］SUN JG，LIU J，ZHAO LY.Clustering algorithms research［J］.Journal of Software，2008，19 （1）：48－61 （in Chinese）.［孫吉貴，劉杰，趙連宇.聚類算法研究 ［J］.Journal of Software，2008，19 （1）：48－61.］

［2］TANG Chenglong，WANG Shigang，XU Wei.New fuzzy c－means clustering model based on the data weighted approach ［J］.Data ＆Knowledge Engineering，2010，69 （9）：881－900.

［3］QU FH.Researeh on fuzzy clustering algorithm and its applieation ［D］.Changchun：Jilin University，2009 （in Chinese）.［曲福恒.一類模糊聚類算法研究及其應用 ［D］.長春：吉林大學，2009.］

［4］CAI WL，CHEN SC，ZHANG DQ.Fast and robust fuzzy c－means clustering algorithms incorporating local information for image segmentation ［J］.Pattern Recognition，2007，40 （3）：825－833.

［5］KANG Jiayin，MIN Lequan，LUAN Qingxian.Novel modified fuzzy c－means algorithm with applications ［J］.Digital Signal Processing，2009，19 （2）：309－319.

［6］LI JJ，XIANG Y，LU YM，et al.Survey of particle swarm clustering algorithms ［J］.Application Research of Computers，2009，26 （12）：4423－4427 （in Chinese）. ［李峻金，向陽，蘆英明，等.粒子群聚類算法綜述 ［J］.計算機應用研究，2009，26 （12）：4423－4427.］

［7］WEN ZW，LI RJ.Fuzzy c－means clustering algorithm based on improved PSO ［J］.Application Research of Computers，2010，27 （7）：2520－2522 （in Chinese）. ［溫重偉，李榮鈞.改進的粒子群優化模糊C均值聚類算法 ［J］.計算機應用研究，2010，27 （7）：2520－2522.］

［8］LI LL，LI M，LIU XY.Image segmentation algorithm based on particle swarm optimization fuzzy c－means clustering ［J］.Computer Engineering and Applications，2009，45 （31）：158－160（in Chinese）.［李麗麗，李明，劉希玉.基于粒子群模糊C－均值聚類的圖像分割算法 ［J］.計算機工程與應用，2009，45 （31）：158－160.］

［9］Thomas A Runkler，Christina Katz.Fuzzy clustering by particle swarm optimization ［C］.Vancouver，BC，Canada：IEEE International Conference on Fuzzy Systems，2006：601－608.

［10］PU PB，WANG G，LIU TA.Research of improved fuzzy c－means algorithm based on particle swarm optimization ［J］.Computer Engineering and Design，2008，29 （16）：4277－4279（in Chinese）.［蒲蓬勃，王鴿，劉太安.基于粒子群優化的模糊C－均值聚類改進算法 ［J］.計算機工程與設計，2008，29 （16）：4277－4279.］

［11］YANG GQ，ZHU CM.Particle swarm optimization algorithm based fuzzy kernel clustering method ［J］.Journal of Shanghai Jiaotong University，2009，43 （6）：935－939 （in Chinese）.［楊廣全，朱昌明.基于粒子群優化的模糊核聚類方法 ［J］.上海交通大學學報，2009，43 （6）：935－939.］

［12］NIU Q，XIA SX，ZHOU Y，et al.Improved fuzzy c－means clustering algorithm ［J］.Journal of University of Electronic Science and Technology of China，2007，36 （6）：1258－1259 （in Chinese）.［牛強，夏士雄，周勇，等.改進的模糊C－均值聚類算法 ［J］.電子科技大學學報，2007，36 （6）：1258－1259.］

［13］HUANG SR.Survey of particle swarm optimization algorithm［J］.Computer Engineering and Design，2009，30 （8）：1977－1980（in Chinese）. ［黃少榮.粒子群優化算法綜述［J］.計算機工程與設計，2009，30 （8）：1977－1980.］

［14］WANG JW，LI HN.Summary of particle swarm optimization algorithm ［J］.Modern Computer，2009，26 （2）：22－27（in Chinese）.［王杰文，李赫男.粒子群優化算法綜述 ［J］.現代計算機，2009，26 （2）：22－27.］

［15］WANG XF.Research on dynamic topology of particle swarm algorithms［D］.Chongqing：Southwest University，2008（in Chinese）.［王雪飛.粒子群算法的動態拓撲結構的研究［D］.重慶：西南大學，2008.］