謝亮亮+劉建生+朱凡

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

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

4.2實(shí)驗(yàn)結(jié)果及分析 實(shí)驗(yàn)參數(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]的隨機(jī)數(shù)。在與對(duì)比實(shí)驗(yàn)環(huán)境和參數(shù)設(shè)置相同的情況下，將GWOFCM算法運(yùn)行30次，取實(shí)驗(yàn)結(jié)果的平均值與FCM和PSOFCM在Iris和Car中的聚類正確率作比較，F(xiàn)CM和PSOFCM實(shí)驗(yàn)數(shù)據(jù)引自文獻(xiàn)[7]，如表2所示。

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

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

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

[3]胡蒙，苑迎春，王雪陽(yáng). 改進(jìn)模糊聚類的云任務(wù)調(diào)度算法[J].計(jì)算機(jī)工程與設(shè)計(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]呂新橋，廖天龍.基于灰狼優(yōu)化算法的置換流水車間調(diào)度[J].武漢理工大學(xué)學(xué)報(bào)，2015，37（5）：111116.

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

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