基于灰狼優化的模糊C—均值聚類算法

謝亮亮+劉建生+朱凡

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

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

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

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

[1]劉慧.改進的FCM和插值理論在數字圖像修復中的應用研究[D].贛州：江西理工大學，2014.

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

[3]胡蒙，苑迎春，王雪陽. 改進模糊聚類的云任務調度算法[J].計算機工程與設計， 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]呂新橋，廖天龍.基于灰狼優化算法的置換流水車間調度[J].武漢理工大學學報，2015，37（5）：111116.

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

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