基于自適應(yīng)布谷鳥搜索的模糊聚類算法

高妍妍 繆祥華，b

（昆明理工大學(xué)a. 信息工程與自動化學(xué)院；b. 云南省計(jì)算機(jī)技術(shù)應(yīng)用重點(diǎn)實(shí)驗(yàn)室）

聚類是根據(jù)數(shù)據(jù)之間屬性的相似度將其劃分為不同類簇的過程， 類內(nèi)相似度盡可能大，類間相似度盡可能小［1］。 模糊C均值（FCM）［2］主要用來解決分類邊界過于絕對化的問題，算法簡單明了、易于實(shí)現(xiàn)。 因?yàn)槟：垲惤Y(jié)果的質(zhì)量很大程度上取決于初始聚類中心的選擇，在聚類過程中易陷入局部最優(yōu)［3］。 因此許多專家學(xué)者提出了改進(jìn)方法。 ZHAO K等利用不動點(diǎn)定理和Banach壓縮映射原理，提出了一種適用于使用閔可夫斯基度量作為相似性度量的模糊聚類算法，拓寬了傳統(tǒng)模糊聚類算法的應(yīng)用范圍，同時(shí)也在算法的全局搜索能力和收斂速度上有了明顯提升［4］。 邢海燕等利用粒子群優(yōu)化算法（PSO）高效的計(jì)算能力和全局搜索能力優(yōu)化了模糊聚類的初始聚類中心和權(quán)值， 并建立了高正確率的分類模型［5］。DEY S等利用量子粒子群算法生成數(shù)據(jù)的模糊聚類中心，并用此聚類多維數(shù)據(jù)［6］。王龍等在自適應(yīng)煙花算法優(yōu)化中引入了多維相似性距離改進(jìn)模糊C均值算法， 改進(jìn)后的算法在彩色圖像分割方面取得了良好的效果［7］。 肖滿生等兼顧區(qū)間中值和區(qū)間大小并利用控制區(qū)間大小的因子改進(jìn)了模糊聚類算法，優(yōu)化了模糊聚類算法在區(qū)間不確定性數(shù)據(jù)上的劃分系數(shù)和正確等級［8］。 呂冰垚等將粒子群算法與遺傳算法結(jié)合進(jìn)行全局搜索優(yōu)化模糊聚類算法的聚類中心，提高了圖像的分割精度［9］。SUBRAMANIAM M等在進(jìn)行語義分析時(shí)，根據(jù)相似性在改進(jìn)的螢火蟲算法的幫助下找到最優(yōu)特征，并將此用于模糊聚類，提高了語義分析系統(tǒng)的準(zhǔn)確性［10］。 KUMAR A等在工蜂群算法的幫助下使模糊聚類算法跳出了局部最優(yōu)，利用UCI常見的數(shù)據(jù)集對改進(jìn)后算法的性能進(jìn)行了驗(yàn)證［11］。 高云龍等利用K最近鄰的方式來估計(jì)樣本是噪聲的可能性，自適應(yīng)調(diào)整參數(shù)，降低噪聲對模糊聚類的影響，提高了模糊聚類算法的蘭德指數(shù)和魯棒性［12］。 湯正華利用改進(jìn)的蝙蝠算法自動確定簇中心和簇?cái)?shù)目， 將蝙蝠位置作為簇中心，利用Levy飛行擺脫局部最優(yōu)［13］。 董發(fā)志等針對模糊聚類算法的缺陷，將遺傳算法優(yōu)化用于優(yōu)化初始聚類中心，從而達(dá)到優(yōu)化聚類的目的［14］。 PANTULA P D等為提高聚類效率，將人工神經(jīng)網(wǎng)絡(luò)引入模糊聚類之中， 提出了神經(jīng)模糊C均值聚類算法［15］。 ZHANG Z X和GU B P將模糊聚類和PSO算法相結(jié)合，將其用在入侵檢測領(lǐng)域，提高了檢測的效率和準(zhǔn)確度［16］。 上述算法，尤其是各類型群智能算法的使用提高了聚類結(jié)果的準(zhǔn)確率，但群智能算法最終結(jié)果的好壞依賴于參數(shù)與閾值設(shè)定的合理性，增加了結(jié)果的不確定性。

布谷鳥搜索算法相較于其他發(fā)展成熟的算法，更易于理解、使用到的參數(shù)更少、全局尋優(yōu)能力也有所提高， 并且可以和多種算法相結(jié)合，適用程度更廣泛。 然而，在傳統(tǒng)的布谷鳥算法中步長控制因子與發(fā)現(xiàn)概率是固定不變的，因此算法容易出現(xiàn)早熟、最優(yōu)解精度低、甚至找不到全局最優(yōu)值以及收斂速度慢等弊端。 基于以上分析，筆者令步長控制因子和發(fā)現(xiàn)概率隨著搜索階段自適應(yīng)變化來進(jìn)一步提升布谷鳥算法的搜索性能，并將其用于搜索模糊聚類算法中最優(yōu)的初始聚類中心，從而進(jìn)一步提高模糊聚類的準(zhǔn)確率。

1 布谷鳥搜索算法的自適應(yīng)

1.1 布谷鳥搜索算法

CS算法通過隨機(jī)行走的Levy飛行進(jìn)行高效搜索，但在不同的搜索階段，步長控制因子α和發(fā)現(xiàn)概率Pa一成不變， 對全局搜索和局部搜索的精度產(chǎn)生了極大的影響。 如果搜索步長相對較小，則算法偏向于局部的精細(xì)搜索， 全局搜索能力差；如果搜索步長偏大，則算法全局搜索能力增強(qiáng)，局部搜索能力降低，容易略過全局最優(yōu)解。 同樣，如果發(fā)現(xiàn)概率Pa過小，則容易陷入局部最優(yōu)，收斂到當(dāng)前的壞結(jié)果， 反之Pa過大時(shí)則很難收斂于全局最優(yōu)解。 因此兩者的設(shè)置對算法的收斂速度會產(chǎn)生較大影響。

1.2 步長控制因子和發(fā)現(xiàn)概率自適應(yīng)的CS算法

自適應(yīng)布谷鳥 （Adaptive Cuckoo Search，ACS）算法通過判斷當(dāng)前的搜索階段，動態(tài)設(shè)置α和Pa，使其可以自適應(yīng)當(dāng)前的搜索環(huán)境。在算法前期， 應(yīng)該注重全局搜索能力，α應(yīng)該取較大的值；在算法后期， 已經(jīng)收斂到全局最優(yōu)解的附近，因此α應(yīng)該取較小的值，注重局部的精細(xì)搜索，提高解的精度。 將式（1）中的固定的α值更新為：

其中，T為總迭代次數(shù)，ti為當(dāng)前迭代次數(shù)。

則改進(jìn)后的更新解位置的式（1）可更新為：

當(dāng)新解產(chǎn)生后，發(fā)現(xiàn)概率Pa與在［0，1］區(qū)間內(nèi)產(chǎn)生的隨機(jī)數(shù)r進(jìn)行比較， 如果r＜Pa則保留當(dāng)前解，反之則按偏好隨機(jī)行走方式生成新解：

隨著迭代的進(jìn)行， 解的質(zhì)量也在不斷提高，在傳統(tǒng)CS算法中發(fā)現(xiàn)概率Pa大多取值為0.25，固定的發(fā)現(xiàn)概率在應(yīng)對不同迭代周期、不同優(yōu)質(zhì)程度的解時(shí)應(yīng)變能力不足，無法做出均衡調(diào)節(jié)。 自適應(yīng)發(fā)現(xiàn)概率定義如下：

其中，Pa，max和Pa，min分別 表示Pa的最大 值和最小值；M是非線性因子， 當(dāng)M=1時(shí)，Pa是線性變化的， 到迭代后期Pa會長時(shí)間保持較小值影響搜索效率，因此Pa采用非線性方式減小。根據(jù)大量的仿真實(shí)驗(yàn)證實(shí)Pa，max=0.75，Pa，min=0.1，M=0.5時(shí)效果最好。 在迭代過程中Pa隨著解的質(zhì)量不斷提高逐漸減小，與自適應(yīng)步長相適應(yīng)。 在早期迭代中，較高的發(fā)現(xiàn)概率會促進(jìn)解多樣性的增加，在迭代后期減小對新解的發(fā)現(xiàn)概率， 可以更好地保留最優(yōu)解，增強(qiáng)算法的尋優(yōu)能力。 Pa和α隨迭代次數(shù)變化曲線如圖1所示。

圖1 α和Pa隨迭代次數(shù)變化曲線

從圖1可以看出，α和Pa的值與迭代次數(shù)呈負(fù)相關(guān)。 在迭代前期，α下降快，Pa保持較大值，可以快速進(jìn)行全局搜索，提高全局尋優(yōu)的性能；在迭代后期，算法已經(jīng)收斂于全局最優(yōu)解的周圍，α和Pa都保持較小值進(jìn)行更為精細(xì)的搜索， 從而提高解的精度。

1.3 實(shí)驗(yàn)與分析

為驗(yàn)證ACS算法 的性能，選f1（Eggholder）、f2（Rastrigin）、f3（Schwefel）、f4（Michalewicz） 和f5（Sphere）（表1）5個(gè)標(biāo)準(zhǔn)測試函數(shù)進(jìn)行實(shí)驗(yàn)，其中測試函數(shù)f1～f3中，由于存在許多局部最小值，因此算法尋找全局最優(yōu)解的難度要高于另外兩個(gè)函數(shù)。

表1 標(biāo)準(zhǔn)測試函數(shù)

為驗(yàn)證ACS算法的性能， 將其與CS算法在Python3.7環(huán)境下進(jìn)行對比實(shí)驗(yàn)。 實(shí)驗(yàn)參數(shù)如下：寄生鳥巢個(gè)數(shù)為20，最大迭代次數(shù)為50，步長控制因子α和發(fā)現(xiàn)概率Pa分別按式（2）和式（5）動態(tài)調(diào)整，更新解的位置按式（3）進(jìn)行調(diào)整。 為了降低偶然性對實(shí)驗(yàn)結(jié)果的影響，基于相同條件將兩個(gè)算法獨(dú)立，取運(yùn)行50次的結(jié)果作為評定算法性能的依據(jù)。 通過平均值和最優(yōu)值可以看出解質(zhì)量的好壞，通過標(biāo)準(zhǔn)差可以看出算法是否穩(wěn)定。 具體實(shí)驗(yàn)結(jié)果見表2，收斂曲線如圖2所示。

圖2 5種測試函數(shù)的收斂曲線

表2 兩種算法在標(biāo)準(zhǔn)測試函數(shù)上的優(yōu)化結(jié)果

由表2可知，ACS算法無論在高維、低維，還是在多模態(tài)函數(shù)方面的求解精度都優(yōu)于CS算法。 在搜索范圍較大的函數(shù)f1、f3上求解的質(zhì)量有了有效的改善，在搜索范圍較小的函數(shù)f2、f4、f5上，可以觀察到ACS算法解的精度相較于CS算法有進(jìn)一步的提升。 通過對比表2中ACS與CS算法的標(biāo)準(zhǔn)差，可證實(shí)前者計(jì)算的穩(wěn)定性要高于后者的。 將圖2a～e進(jìn)行對比可以看出，ACS算法可以在較短的迭代周期內(nèi)迅速搜索到全局最優(yōu)值，且收斂速度高于CS算法。 對于搜索范圍大的函數(shù)f1、f3， f1中兩個(gè)算法都以較好的收斂速度靠近最優(yōu)解，相對于CS算來說，ACS算法的尋優(yōu)效率更高；在函數(shù)f3中，雖然在迭代前期CS算法解的質(zhì)量要優(yōu)于ACS算法，在迭代中期時(shí)兩個(gè)算法同時(shí)陷入局部最優(yōu)，但在算法迭代后期，ACS算法憑借自身的優(yōu)勢擺脫局部最優(yōu)陷阱，繼續(xù)向全局最優(yōu)解靠攏。 對于搜索范圍較小的函數(shù)f2、f4、f5，ACS算法和CS算法均在50次迭代內(nèi)找到了高質(zhì)量的解， 但是ACS算法在收斂速度和解的精確度方面都優(yōu)于CS算法。

2 基于ACS的模糊聚類算法

FCM算法是按隸屬度將樣本劃分為C個(gè)聚類的過程，其目標(biāo)函數(shù)為：

其中，U為模糊隸屬度矩陣；uij為j類中第i個(gè)樣本的隸屬度；dij是從第i個(gè)數(shù)據(jù)樣本到第j個(gè)聚類中心的歐幾里得距離；P為聚類中心矩陣；m為模糊指數(shù)，通常取m=2。

FCM算法的初始聚類中心產(chǎn)生方式具有高度隨機(jī)性，如果聚類中心的質(zhì)量越高則聚類的效果越好， 相反較差的聚類中心則會得到質(zhì)量不好的聚類結(jié)果， 從而使得算法在計(jì)算過程中產(chǎn)生一定的波動性。 因此，利用ACS優(yōu)越的搜索能力尋找到質(zhì)量最佳的初始聚類中心， 然后再進(jìn)行后續(xù)的聚類過程，從而改善FCM算法對初始聚類中心敏感性這一缺點(diǎn)，并幫助模糊聚類跳出局部最優(yōu)解。 筆者結(jié)合ACS算法和FCM算法的優(yōu)點(diǎn)提出了基于自適應(yīng)布谷鳥搜索的模糊聚類算法（Adaptive Cuckoo Search Based Fuzzy C-Means，ACSFCM）。

2.1 編碼與目標(biāo)函數(shù)

如果待聚類樣本擁有d維特征，將被劃分為k類，則布谷鳥算法的解由k×d矩陣構(gòu)成。 其編碼結(jié)構(gòu)如下：

其中，p11，p12， …，p1d表示第1個(gè)類的聚類中心；pk1，pk2，…，pkd表示第k個(gè)類的聚類中心。

采用式（6）目標(biāo)函數(shù)J（U，P）來衡量解的優(yōu)越性。 目標(biāo)函數(shù)J（U，P）的值越小，表明其解的質(zhì)量越高，聚類效果越好。

2.2 算法流程

在保持FCM算法思想的基礎(chǔ)上， 結(jié)合ACS算法，新算法ACSFCM的實(shí)現(xiàn)步驟如下：

a. 初始化種群， 將數(shù)據(jù)集D中的各個(gè)數(shù)據(jù)作為一個(gè)可行解，生成一組隨機(jī)解A1，A2，…，An，定義目標(biāo)函數(shù)；

b. 計(jì)算各個(gè)解的目標(biāo)函數(shù)值，得到當(dāng)前的最優(yōu)解Abest；

d. 計(jì)算新解的目標(biāo)函數(shù)值，并與更新前的Abest比較，如果新解的質(zhì)量更高則更新Abest；

e. 以發(fā)現(xiàn)概率Pa隨機(jī)淘汰部分解， 按式（4）的方式獲得一組新解；

f. 執(zhí)行上述過程， 判斷是否達(dá)到結(jié)束算法的迭代次數(shù)要求，沒有達(dá)到則執(zhí)行步驟c，達(dá)到則輸出全局最優(yōu)解Abest；

g. 執(zhí)行在指定聚類中心情況下的模糊聚類算法。

3 ACSFCM算法的實(shí)驗(yàn)與分析

為了驗(yàn)證ACSFCM算法的性能， 將其與FCM算法、PSOFCM算法［16］和利用CS算法改進(jìn)FCM的CSFCM算法在UCI常用的4個(gè)數(shù)據(jù)集（表3）上進(jìn)行反復(fù)實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果詳見表4。 各算法在數(shù)據(jù)集上的聚類準(zhǔn)確率對比如圖3～6所示。 實(shí)驗(yàn)參數(shù)設(shè)置如下：模糊指數(shù)m=2，種群規(guī)模n=15，迭代次數(shù)為20次，Levy飛行參數(shù)為1.5，Levy飛行的步長控制因子和發(fā)現(xiàn)概率Pa使用ACSFCM算法采用自適應(yīng)參數(shù)，CSFCM算法則選擇固定的α=0.7、Pa=0.25。文獻(xiàn)［16］的PSOFCM算法使用改進(jìn)的PSO算法來優(yōu)化FCM算法的初始聚類中心，主要參數(shù)設(shè)置如下： 模糊指數(shù)m與種群規(guī)模n與ACSFCM算法相同，自我學(xué)習(xí)因子c1和全局學(xué)習(xí)因子c2為0.5，慣性系數(shù)w0為0.8。

表3 數(shù)據(jù)集詳細(xì)信息

比較分析表4中的數(shù)值可以得出，4種算法中ACSFCM算法的目標(biāo)函數(shù)值和聚類準(zhǔn)確率均優(yōu)于其他3種算法。 在Iris數(shù)據(jù)集上（圖3），ACSFCM的目標(biāo)函數(shù)值要小于其他3種算法，聚類準(zhǔn)確率也達(dá)到了91.6%，相較于FCM算法81.3%的準(zhǔn)確率提升了10.3%， 雖然ACSFCM 的準(zhǔn)確率要高于PSOFCM算法， 但其穩(wěn)定性要低于PSOFCM算法；在Wine 數(shù) 據(jù) 集 上 （圖4），ACSFCM 的 準(zhǔn) 確 率 為88.8%， 比CSFCM算法的準(zhǔn)確率提高了12.9%，證明了ACS算法在優(yōu)化模糊聚類中心提高聚類效果上有作用，其他3種算法的波動較大；在Car數(shù)據(jù)集上（圖5），ACSFCM的準(zhǔn)確率相較于FCM算法提升了4.2%，與其他數(shù)據(jù)集的準(zhǔn)確率相比提升并不明顯，但從準(zhǔn)確率對比圖中可以看出穩(wěn)定性得到了提高；在Zoo數(shù)據(jù)集上（圖6），ACSFCM的準(zhǔn)確率相比于FCM、PSOFCM、CSFCM 分別提升了10.2%、4.2%、3.1%， 而在整體穩(wěn)定性上的表現(xiàn)與其他數(shù)據(jù)集相比波動較大。 總結(jié)圖3～6可知，ACSFCM算法在較高聚類準(zhǔn)確率的前提下，在整體的穩(wěn)定性上也具有明顯優(yōu)勢； 與PSOFCM 算法相比，ACSFCM需要人為設(shè)定的參數(shù)和閾值較少， 并且對參數(shù)設(shè)置的依賴性更低。簡而言之，ACSFCM有著較其他算法更佳的聚類準(zhǔn)確率和穩(wěn)定性。

圖3 Iris數(shù)據(jù)集聚類準(zhǔn)確率對比

圖4 Wine數(shù)據(jù)集聚類準(zhǔn)確率對比

圖5 Car數(shù)據(jù)集聚類準(zhǔn)確率對比

圖6 Zoo數(shù)據(jù)集聚類準(zhǔn)確率對比

表4 4種數(shù)據(jù)集的聚類結(jié)果

4 結(jié)束語

由于FCM算法對初始聚類中心選取敏感性的缺陷， 筆者基于ACS算法高效的搜索能力提出了ACSFCM算法。 算法在搜索的過程中根據(jù)搜索階段自適應(yīng)調(diào)節(jié)步長控制因子和發(fā)現(xiàn)概率的參數(shù)設(shè)置， 提高算法的收斂速度和尋優(yōu)精度。ACSFCM通過找到最佳的初始聚類中心， 來提升模糊聚類算法的聚類準(zhǔn)確率。 實(shí)驗(yàn)結(jié)果證明：ACSFCM算法相較于PSOFCM、FCM、CSFCM算法，在聚類的準(zhǔn)確率和穩(wěn)定性方面有了顯著提升。ACSFCM算法在一些細(xì)節(jié)上還有強(qiáng)化的空間，如ACS算法在Levy飛行的過程中方向是盲目的，影響算法的尋優(yōu)效率， 未來的研究可以對ACS算法的搜索方向加以控制，使算法可以更快、更準(zhǔn)確地向最優(yōu)解靠近，并將其應(yīng)用到更廣泛的領(lǐng)域。