基于灰狼優(yōu)化的模糊C—均值聚類算法

謝亮亮+劉建生+朱凡

摘要：針對模糊C-均值聚類算法（FCM）存在易受初始聚類中心影響和容易陷入局部最優(yōu)的問題，提出了一種將灰狼優(yōu)化算法（GWO）和模糊C-均值相結(jié)合的新聚類算法（GWO-FCM）。該算法利用GWO算法強大的全局尋優(yōu)能力對FCM算法的聚類中心進行優(yōu)化，模擬灰狼優(yōu)秀的搜尋獵物行為找到一組最佳聚類中心來提高FCM的聚類效果。通過UCI數(shù)據(jù)集的仿真結(jié)果和算法比較驗證了該算法的有效性。關(guān)鍵詞： 聚類分析；灰狼優(yōu)化算法；模糊C-均值聚類；初始聚類中心；全局優(yōu)化DOI：10.11907/rjdk.171030中圖分類號：TP312文獻標(biāo)識碼：A文章編號：16727800（2017）0040028030引言 聚類是數(shù)據(jù)挖掘領(lǐng)域中必不可少的技術(shù)，是在事先沒有分類規(guī)則下，根據(jù)事物間的特征相似度對事物進行區(qū)分和分類。它的主要任務(wù)是按準(zhǔn)則把所有數(shù)據(jù)按不同特性劃分成各個不同的簇，即最小化每個簇內(nèi)部數(shù)據(jù)間的差異性，并且最大化屬于任意不同簇的數(shù)據(jù)間的差異性[1]。在模糊集理論提出之后，研究者使用模糊集理論來作聚類分析[2]。FCM聚類算法由Dunn[3]于1974年第一次提出，隨后由Bezdek進一步完善。但FCM在聚類分析中存在易受隨機產(chǎn)生的初始聚類中心的影響以及容易早熟收斂等缺點，對聚類的結(jié)果有很大影響。針對傳統(tǒng)的FCM存在的缺陷，本文提出一種基于灰狼優(yōu)化的模糊C-均值聚類算法（GWOFCM）。GWO具有結(jié)構(gòu)簡單，需要設(shè)置的參數(shù)較少，有強大的全局尋優(yōu)能力，在實驗編碼中容易實現(xiàn)等優(yōu)點，對FCM聚類結(jié)果有顯著提高。1灰狼優(yōu)化算法GWO算法由Seyedali Mirjalili[4]于2012年受大自然中灰狼尋找和捕捉獵物行為的啟發(fā)而提出，是一種新的元啟發(fā)式算法。本文從以下幾個方面介紹算法步驟。1.1社會等級灰狼是食物鏈頂端的群體獵食者，狼群一般由5～12只灰狼組成。在種群中有著嚴(yán)格的社會等級。在GWO算法設(shè)計中，突出了灰狼的狩獵技術(shù)和社會等級層次。它們的社會等級由高級到低級依次為：α、β、δ、w [5]。α是灰狼中的頭狼，占有統(tǒng)治地位，有各項決策的優(yōu)先權(quán)；β是頭狼的下屬狼，聽從頭狼并且可以命令較低等級的灰狼，再反饋信息給頭狼；δ服從α、β的命令，可以指揮最底層的灰狼；w是最底層的狼，服從等級高的灰狼?；依巧鐣燃壏浅?yán)格，逐級遞減。狩獵主要由α、β、δ決定引導(dǎo)完成，w服從等級高的狼群支配來完成狩獵任務(wù)。1.2包圍獵物行為灰狼在狩獵過程中首先需要將獵物包圍[6]，建立這種行為的數(shù)學(xué)模型，用以下公式來描述其中，t為當(dāng)前迭代次數(shù)；A和C為協(xié)調(diào)系數(shù)向量；Xp為獵物的位置向量；X為灰狼的位置向量。a的值在迭代過程中從2下降到0；r1和r2是范圍為[0，1]的隨機向量。1.3狩獵行為灰狼在狩獵行為中有識別獵物方位的能力，并且可以縮小范圍來圍剿獵物。狩獵行為一般情況下是由α，β，δ來引導(dǎo)，直至結(jié)束。然而在抽象的搜索空間，灰狼也不會知道最佳（獵物）位置[5]。用數(shù)學(xué)公式來模仿灰狼的狩獵過程，并且α（最佳候選解），β和δ獲得獵物具體方位的能力比其它灰狼更強。所以在每次迭代過程中保留目前獲得的最好的3只灰狼，也就是α，β，δ。再通過它們的位置來使其它候選灰狼更新自己當(dāng)前的位置。數(shù)學(xué)公式表示如下[4]： α，β，δ灰狼先預(yù)測判斷獵物的大概位置，再通過引導(dǎo)其它灰狼在獵物周圍更新位置，從而鎖定獵物的具體位置。1.4攻擊獵物行為一旦獵物的位置鎖定，灰狼將捕抓獵物。由式（3）可知，減小a的值，A的值也會減小，在迭代過程中a值會由2線性下降為0，A的取值范圍則為[-2a，2a]。當(dāng)A在范圍[-1，1]中，灰狼的位置會出現(xiàn)在與獵物距離之間范圍中的任何可能位置上。當(dāng)|A|<1時，灰狼開始攻擊獵物。1.5搜索獵物行為搜索獵物過程中灰狼是根據(jù)α，β，δ的位置情況來搜索的。它們開始是相互獨立地出去搜索獵物，最后再由獵物的位置聚集起來攻擊獵物。分散過程中需要用一個A>1或者A<1的值讓候選灰狼遠(yuǎn)離獵物，可以實現(xiàn)并提高全局尋優(yōu)效果。在GWO算法中的另外一個全局搜索系數(shù)是C，通過式（4）可知，C是范圍在[0，2]中的隨機數(shù)。隨機增加或者減少C的值會影響到式（5）、式（6）和式（7）中的距離，改變獵物的隨機權(quán)重，并且C的值不是線性下降的，而是隨機數(shù)，可以使GWO在迭代過程中從局部最優(yōu)結(jié)果中跳出來，達到增強全局尋優(yōu)的效果。2模糊C-均值聚類算法

3GWO優(yōu)化FCM的混合聚類算法模糊C-均值聚類要達到最佳聚類效果需使得它的目標(biāo)函數(shù)最小[7]，但由于在這個過程中隨機的初始聚類中心對算法的影響很大，使聚類效果差。針對此問題，通過引入一種新群體智能算法GWO與之結(jié)合，達到更佳的聚類效果。由于GWO是一種全局尋優(yōu)很強的算法，并且能跳出局部收斂，找到一組全局最優(yōu)的聚類中心，使FCM的聚類中心達到最優(yōu)。這樣可以使FCM的聚類正確率明顯提高，從而獲得更好的聚類效果。3.1種群初始化根據(jù)群體智能算法初始化常用方法，使得算法中的種群具有多樣性、隨機性，初始化公式設(shè)定為：其中的upperj，lowerj表示第j個元素的上、下解，n表示灰狼種群大小，d表示灰狼種群的維數(shù)。3.2適應(yīng)度函數(shù)設(shè)置適應(yīng)度函數(shù)是篩選個體好壞程度的基準(zhǔn)，越大表示個體越好，越小則表示個體越差，是由目標(biāo)函數(shù)設(shè)定的[5]，在GWO中也是用來判斷狼群中灰狼層次的準(zhǔn)則。在GWO中，適應(yīng)度前三的α、β、δ狼保留下來引導(dǎo)w以及更低層次的灰狼去搜索獵物。因為在FCM聚類中，目標(biāo)函數(shù)值越小，聚類的結(jié)果會更好。所以結(jié)合GWO和FCM算法，本文將GWO的適應(yīng)度函數(shù)設(shè)定為：由式（16）可得，當(dāng)FCM的JFCM越小，也就是聚類結(jié)果更好時，GWO的fitness會越大，通過對算法中的α、β、δ不斷迭代，最后得出最好的適應(yīng)度函數(shù)值α，將α設(shè)定為FCM的聚類中心。3.3更新設(shè)置根據(jù)GWO的搜索方法，通過包圍、狩獵、攻擊行為更新灰狼位置。在迭代過程中，獲得最優(yōu)灰狼位置xα。通過總結(jié)上述過程，GWO-FCM算法流程如下：Step1：初始化參數(shù)a，A和C；Step2：初始化狼群種群xi（i=1...n）；Step3：計算狼群適應(yīng)度fitness，選出最好的3只灰狼xα，xβ，xδ；Step4：如果T

4.2實驗結(jié)果及分析 實驗參數(shù)設(shè)置中，F(xiàn)CM的加權(quán)指數(shù)都設(shè)置為m=2，粒子群種群規(guī)模大小設(shè)置為NP=20，wφ1從0.9線性減小到0.4，η1=η2=0.5，迭代次數(shù)T=100。在本文提出的GWOFCM中，設(shè)最大的迭代數(shù)T=100，灰狼的種群大小NP=20，F(xiàn)CM算法的加權(quán)指數(shù)m=2，a從2線性下降到0，r1、r2為[0，1]的隨機數(shù)。在與對比實驗環(huán)境和參數(shù)設(shè)置相同的情況下，將GWOFCM算法運行30次，取實驗結(jié)果的平均值與FCM和PSOFCM在Iris和Car中的聚類正確率作比較，F(xiàn)CM和PSOFCM實驗數(shù)據(jù)引自文獻[7]，如表2所示。

通過表2實驗結(jié)果可以看出，上述3種聚類算法的結(jié)果都有明顯的差別。本文提出的GWO-FCM在數(shù)據(jù)集Iris和Car的實驗結(jié)果中聚類正確率均高于其它模糊聚類算法，而且較原始的FCM有很大的提高，在用PSO改進的FCM上也有明顯提高，說明灰狼優(yōu)化算法對FCM聚類算法的優(yōu)化效果比用PSO優(yōu)化的效果更有優(yōu)勢，能更大程度地解決全局最優(yōu)問題。 在Iris，Car兩個數(shù)據(jù)集上，GWO-FCM算法在運行30次后每次運行結(jié)果的正確率穩(wěn)定性如圖1所示。 由圖1可見，算法在執(zhí)行30次后，在Iris數(shù)據(jù)集上聚類的準(zhǔn)確率較平穩(wěn)，有一定波動，但總體上保持在一個穩(wěn)定范圍。Car數(shù)據(jù)集上每次運行的結(jié)果中正確率都非常穩(wěn)定，浮動范圍很小，不會出現(xiàn)跳躍性的變化，因此表明GWOFCM算法的穩(wěn)定性很高。5結(jié)語 本文將GWO巧妙地運用在FCM上，首次用一種新的群體優(yōu)化算法GWO對FCM加以改進，GWO結(jié)構(gòu)簡單，需要設(shè)置的參數(shù)少，具體強大的全局尋優(yōu)能力，有效地解決了模糊C-均值聚類算法對初始聚類中心的過度依賴、易出現(xiàn)早熟收斂等缺點。并且通過與傳統(tǒng)的FCM以及PSOFCM聚類算法比較，在聚類正確率以及算法穩(wěn)定性上取得了較好的實驗結(jié)果。參考文獻：

[1]劉慧.改進的FCM和插值理論在數(shù)字圖像修復(fù)中的應(yīng)用研究[D].贛州：江西理工大學(xué)，2014.

[2]王縱虎，劉志鏡，陳東輝.基于粒子群優(yōu)化的模糊C-均值聚類算法研究[J].計算機科學(xué)，2012，39（9）：166169.

[3]胡蒙，苑迎春，王雪陽. 改進模糊聚類的云任務(wù)調(diào)度算法[J].計算機工程與設(shè)計， 2015， 36（9）：24372441.

[4]MIRJALILI S， MIRJALILI S M， LEWIS A. Grey wolf optimizer[J]. Advances in Engineering Software， 2014， 69（3）：4661.

[5]呂新橋，廖天龍.基于灰狼優(yōu)化算法的置換流水車間調(diào)度[J].武漢理工大學(xué)學(xué)報，2015，37（5）：111116.

[6]龍文，趙東泉，徐松金.求解約束優(yōu)化問題的改進灰狼優(yōu)化算法[J].計算機應(yīng)用，2015，35（9）：25902595.

[7]蒲蓬勃，王鴿，劉太安.基于粒子群優(yōu)化的模糊C均值聚類改進算法[J].計算機工程與設(shè)計，2008，29（16）：42774279.（責(zé)任編輯：陳福時）