改進(jìn)的粒子群模糊聚類方法

黃新建，牛 強(qiáng)

（中國(guó)礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州221116）

0 引 言

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

1 模糊C均值聚類算法

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

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

并給出式子

在式 （2）條件下通過(guò)反復(fù)迭代式 （3）和式 （4），使FCM的目標(biāo)函數(shù)式 （1）取得極小值，即為FCM［12］。

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

2.1 PSO算法

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

式 （5）和式 （6）中：i＝1，2，…，m——不同的粒子；C1、C2——大于0的學(xué)習(xí)因子，分別調(diào)節(jié)該粒子向自身歷史最優(yōu)位置和族群歷史最優(yōu)位置方向飛行的最大步長(zhǎng)，取C1＝C2＝1.5；R1、R2為介于 ［0，1］之間的隨機(jī)數(shù)；n為迭代次數(shù)［15］。

2.2 基于PSO的模糊聚類算法

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

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

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

設(shè)wik為第樣本k對(duì)類i的隸屬度，算法運(yùn)行時(shí)wik限定在 ［－5，5］內(nèi)。計(jì)算粒子適應(yīng)度時(shí)先采用sigmoid函數(shù)式（7）將 wik轉(zhuǎn)化為uik∈ ［0，1］

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

當(dāng)樣本對(duì)各類的隸屬度之和不為1時(shí)，文獻(xiàn) ［9］的方法把不足或多出的部分平均地進(jìn)行了增加或減少，對(duì)離樣本近的類和離樣本遠(yuǎn)的類同等對(duì)待，沒(méi)有考慮樣本與各個(gè)類之間的距離，收斂速度較慢，聚類效果較差。

本文提出的改進(jìn)方法為：設(shè)uik為樣本k對(duì)類i的隸屬度，且uik∈ ［0，1］，li為樣本k與類i的距離?！?時(shí)，根據(jù)li決定uik增加或減少的幅度。

當(dāng)樣本對(duì)各類的隸屬度之和不為1時(shí)，文獻(xiàn) ［9］的方法把不足或多出的部分平均地進(jìn)行了增加或減少。本文改進(jìn)方法考慮了樣本與各類之間的距離關(guān)系，對(duì)于距離近的類，和小于1時(shí)隸屬度加的多，和大于1時(shí)減的少；對(duì)于距離遠(yuǎn)的類，和小于1時(shí)隸屬度加的少，和大于1時(shí)減的多。

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

3 實(shí)驗(yàn)測(cè)試與比較分析

實(shí)驗(yàn)分別使用了經(jīng)典的FCM算法、文獻(xiàn) ［9］中方法以及本文的改進(jìn)方法進(jìn)行比較研究。使用的兩組典型數(shù)據(jù)集來(lái)自文獻(xiàn) ［9］中比較方法時(shí)所使用的數(shù)據(jù)集，測(cè)試的數(shù)據(jù)集分別為：

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

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

取粒子個(gè)數(shù)為10，迭代次數(shù)為100，表1至表2給出了運(yùn)行各算法后對(duì)各項(xiàng)聚類指標(biāo)取平均后的值，各表中的值具體體現(xiàn)了各方法的最優(yōu)優(yōu)化結(jié)果。其中DIC表示平均類內(nèi)距離，DBC表示平均類間距離，OFV表示目標(biāo)函數(shù)值，SCR表示成功分類率。

表1 Single Outlier數(shù)據(jù)集

表2 Lung Cancer數(shù)據(jù)集

由表1知，當(dāng)數(shù)據(jù)集含噪音時(shí)，本文改進(jìn)方法同F(xiàn)CM一樣在各種性能上優(yōu)于文獻(xiàn) ［9］中方法，本文改進(jìn)方法與FCM在小數(shù)據(jù)集中的差別并不明顯。

由表2知，本文改進(jìn)方法文獻(xiàn) ［9］中方法明顯優(yōu)于FCM，即基于PSO的FCM以隸屬度編碼時(shí)可較好處理樣本維數(shù)大于樣本數(shù)的數(shù)據(jù)集，且本文改進(jìn)方法在樣本維數(shù)大于樣本數(shù)的數(shù)據(jù)集中的效果明顯優(yōu)于文獻(xiàn) ［9］中方法。

取粒子個(gè)數(shù)為10，迭代次數(shù)從1遞增至100，隨迭代次數(shù)的增加，圖2至圖5給出各方法的分類成功率和目標(biāo)函數(shù)值的變化情況，各圖體現(xiàn)出各方法隨迭代次數(shù)的變化所取得的優(yōu)化結(jié)果。其中DIC表示平均類內(nèi)距離，DBC表示平均類間距離，OFV表示目標(biāo)函數(shù)值，SCR表示成功分類率。

由圖2及圖3知，本文改進(jìn)方法和FCM在各種性能上均優(yōu)于文獻(xiàn) ［9］中方法，且與FCM在較小數(shù)據(jù)集上區(qū)別并不明顯。相比FCM，本文改進(jìn)方法在目標(biāo)函數(shù)值中的波動(dòng)較大，而在分類成功率中區(qū)別極小。

圖4和圖5表明此時(shí)FCM效果較差，即基于PSO的FCM以隸屬度編碼時(shí)較FCM有明顯優(yōu)勢(shì)。同時(shí)本文改進(jìn)方法顯著優(yōu)于文獻(xiàn) ［9］方法，即本文方法在樣本維數(shù)大于樣本數(shù)的數(shù)據(jù)集中明顯優(yōu)于文獻(xiàn) ［9］中方法。

圖5 Lung cancer數(shù)據(jù)集目標(biāo)函數(shù)值比較

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

4 結(jié)束語(yǔ)

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

［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）.［曲福恒.一類模糊聚類算法研究及其應(yīng)用 ［D］.長(zhǎng)春：吉林大學(xué)，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）. ［李峻金，向陽(yáng)，蘆英明，等.粒子群聚類算法綜述 ［J］.計(jì)算機(jī)應(yīng)用研究，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）. ［溫重偉，李榮鈞.改進(jìn)的粒子群優(yōu)化模糊C均值聚類算法 ［J］.計(jì)算機(jī)應(yīng)用研究，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］.計(jì)算機(jī)工程與應(yīng)用，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）.［蒲蓬勃，王鴿，劉太安.基于粒子群優(yōu)化的模糊C－均值聚類改進(jìn)算法 ［J］.計(jì)算機(jī)工程與設(shè)計(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）.［楊廣全，朱昌明.基于粒子群優(yōu)化的模糊核聚類方法 ［J］.上海交通大學(xué)學(xué)報(bào)，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）.［牛強(qiáng)，夏士雄，周勇，等.改進(jìn)的模糊C－均值聚類算法 ［J］.電子科技大學(xué)學(xué)報(bào)，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）. ［黃少榮.粒子群優(yōu)化算法綜述［J］.計(jì)算機(jī)工程與設(shè)計(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）.［王杰文，李赫男.粒子群優(yōu)化算法綜述 ［J］.現(xiàn)代計(jì)算機(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òng)態(tài)拓?fù)浣Y(jié)構(gòu)的研究［D］.重慶：西南大學(xué)，2008.］