基于自適應布谷鳥搜索的模糊聚類算法

高妍妍 繆祥華，b

（昆明理工大學a. 信息工程與自動化學院；b. 云南省計算機技術應用重點實驗室）

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

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

1 布谷鳥搜索算法的自適應

1.1 布谷鳥搜索算法

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

1.2 步長控制因子和發現概率自適應的CS算法

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

其中，T為總迭代次數，ti為當前迭代次數。

則改進后的更新解位置的式（1）可更新為：

當新解產生后，發現概率Pa與在［0，1］區間內產生的隨機數r進行比較， 如果r＜Pa則保留當前解，反之則按偏好隨機行走方式生成新解：

隨著迭代的進行， 解的質量也在不斷提高，在傳統CS算法中發現概率Pa大多取值為0.25，固定的發現概率在應對不同迭代周期、不同優質程度的解時應變能力不足，無法做出均衡調節。 自適應發現概率定義如下：

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

圖1 α和Pa隨迭代次數變化曲線

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

1.3 實驗與分析

為驗證ACS算法 的性能，選f1（Eggholder）、f2（Rastrigin）、f3（Schwefel）、f4（Michalewicz） 和f5（Sphere）（表1）5個標準測試函數進行實驗，其中測試函數f1～f3中，由于存在許多局部最小值，因此算法尋找全局最優解的難度要高于另外兩個函數。

表1 標準測試函數

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

圖2 5種測試函數的收斂曲線

表2 兩種算法在標準測試函數上的優化結果

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

2 基于ACS的模糊聚類算法

FCM算法是按隸屬度將樣本劃分為C個聚類的過程，其目標函數為：

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

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

2.1 編碼與目標函數

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

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

采用式（6）目標函數J（U，P）來衡量解的優越性。 目標函數J（U，P）的值越小，表明其解的質量越高，聚類效果越好。

2.2 算法流程

在保持FCM算法思想的基礎上， 結合ACS算法，新算法ACSFCM的實現步驟如下：

a. 初始化種群， 將數據集D中的各個數據作為一個可行解，生成一組隨機解A1，A2，…，An，定義目標函數；

b. 計算各個解的目標函數值，得到當前的最優解Abest；

d. 計算新解的目標函數值，并與更新前的Abest比較，如果新解的質量更高則更新Abest；

e. 以發現概率Pa隨機淘汰部分解， 按式（4）的方式獲得一組新解；

f. 執行上述過程， 判斷是否達到結束算法的迭代次數要求，沒有達到則執行步驟c，達到則輸出全局最優解Abest；

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

3 ACSFCM算法的實驗與分析

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

表3 數據集詳細信息

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

圖3 Iris數據集聚類準確率對比

圖4 Wine數據集聚類準確率對比

圖5 Car數據集聚類準確率對比

圖6 Zoo數據集聚類準確率對比

表4 4種數據集的聚類結果

4 結束語

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