基于分層遺傳的新聚類算法應用于數據分類

吳盛平 馬永光 莊恒悅 趙魏 常志偉

摘?要：針對FCM（模糊C均值聚類算法）對初始聚類中心的選取敏感以及梯度法易收斂到鞍點，在此基礎上提出了一種分層遺傳算法（HGA）優化的核模糊C均值聚類算法（HGAKFCM）來提升聚類性能，首先用分層遺傳算法（HGA）在全局篩選出高品質聚類中心以替代FCM的隨機產生的聚類中心，再利用高斯徑向核函數改變FCM中的距離函數并且重新定義目標函數，最終根據新參數進行迭代流程。在仿真實驗中用兩種數據集作為實驗數據，利用FCM、HGAKFCM以及其他三種聚類算法進行聚類測試，結果顯示HGAKFCM在一定程度上解決了FCM的缺陷，此外將新算法與另外三種性能不錯的聚類算法在抗局部收斂能力，迭代次數和精度上比較，結果顯示新算法具有良好的聚類性能。

關鍵詞：模糊C均值聚類;核模糊C均值聚類;遺傳算法;分層遺傳;高斯核函數;聚類中心優化

1?概述

從古至今，聚類都是一個非常有價值的問題，從某種程度上來說，聚類就是按照一定的規律來對事物進行劃分的過程。Dunn[1]和Bezdek[2]提出的模糊C均值聚類算法（FCM）是一種基于目標函數的聚類算法。但是FCM算法依然存在缺點，如對初始聚類中心敏感，容易收斂到局部極值等。

為了消除FCM算法的種種缺陷，學者們從不同的方面對FCM算法進行了改進。Chen?S?C[34]將核化技術引入模糊C均值算法中，利用核徑向函數來替代FCM中的歐氏距離函數來重新定義目標函數，提出了核模糊C均值聚類算法（KFCM），經試驗證明KFCM的聚類性能確實優于FCM，但是其算法依舊沿用FCM的隨機化初始聚類中心，依然對初始聚類中心敏感。文傳軍[5]提出了粒子群高斯誘導核模糊C均值聚類算法，利用粒子群算法在整個全局解空間尋優，避免了梯度法的局部極值陷阱，提升了聚類性能。陳書文等[6]提出了一種最優正則化參數的核FCM算法，在KFCM的目標函數中引入正則化參數，并用L曲線法更新迭代公式，取得不錯的效果，但并未解決局部收斂的問題。梁冰、徐華[7]提出了一種改進的人工蜂群與KFCM算法相結合的聚類算法，旨在解決初始聚類中心敏感和局部最優陷阱問題。

在上述研究的基礎之上，提出了分層遺傳優化的核模糊C均值聚類算法（HGAKFCM）。HGA算法更新的初始聚類中心的目的是在一定程度上消除FCM的初始聚類中心敏感的問題，并且HGA算法具有全局尋優的特點。

2?核化距離的模糊c均值聚類（KFCM）

KFCM算法是將核函數替代FCM中的歐式近距離，得到的優化的模糊c均值聚類算法，KFCM相比FCM具有更優的性能，能達到更佳的聚類效果，在此處引入的常用的徑向函數——高斯核函數，形式如式（1）：

K（xj，ci）=e-‖xj-ci‖12δ2（1）

此時的目標函數可以寫成：

JKFCM（uij，ci）=2·∑Nj=1∑ki=1umij（1-K（xj，ci））∑ki=1uij=1uij∈[0，1]（2）

再通過引入拉格朗日乘數因子，得到最終的劃分矩陣和群類中心更新公式：

uij=（1-K（xj，ci））-1m-1∑kl=1（1-K（xl，ci））-1m-1（3）

ci=∑Nj=1umijK（xj，ci）xj∑Nj=1umijK（xj，ci）（4）

KFCM算法與FCM算法運行流程極為相似，都是根據劃分矩陣和群類中心更新公式的不斷更新來尋找極小值點，算法根據式（3）、（4）不斷迭代循環更新隸屬度矩陣直到找到最優聚類中心，然后去模糊化得出最終的聚類結果[8]。

3?HGAKFCM算法設計

HGAKFCM算法的思路是運用分層遺傳算法對KFCM的初始聚類中心進行優化，旨在改善局部收斂和對初參數敏感問題。

3.1?分層遺傳簡述

遺傳算法是根據生物進化理論提出的一種基于種群搜索的優化算法[9]，在傳統的遺傳算法中，交叉、變異、選擇等遺傳算子作用在整個群體上，有可能是各個個體在未達到最優點之前就停留在某一局部最優點，從而產生早熟現象。為克服早熟現象，引入遺傳算法中利用并行遺傳算方法的思想，將群體劃分為一些子群體，各子群體按一定的模式分別進行獨立進化。在適當的時候，某一些子群體之間交換一些信息，這樣可以維持群體的多樣性，從而達到抑制早熟現象的效果，稱作分層遺傳算法[1011]。

3.2?HGAKFCM流程

HGAKFCM算法分為兩個循環，第一個是HGA循環，目的是找到KFCM的合適的初始聚類中心。第二個是主KFCM循環，根據HGA提供的聚類中心進行接下來的聚類。HGA循環的步驟：

第一步是初始化各項初參數。

第二步是設置計數器為零并隨機產生n個初始種群。

第三步是定義高低層次計數器并計算其個體的適應度函數。

第四步判斷是否滿足適應度條件，若滿足則解碼輸出聚類中心，若不滿足則回到第三步直到滿足適應度條件。KFCM循環與FCM極度相似，反復迭代，滿足迭代結果后輸出結果。

4?仿真實驗

為了驗證HGAKFCM聚類算法的有效性，選取了來自UCI機器學習數據庫的兩種真實數據集進行測試，分別為Iris（鳶尾花卉數據集）、Pageblocks（頁塊分類數據集）。數據集的詳細數據如表1所示。

實驗結果及分析。通過HGA=FCM算法和FCM、FCS、KFCM、GAFCM四種算法進行比較，通過對UCI四種數據集用以上五種聚類算法進行聚類，每種算法運行20次。

FCM存在的容易陷入局部收斂的問題是直接表現為目標函數的最終值都會收斂到一個較大的數值，理想的目標函數是趨近于0的正數，在這里選取目標函數迭代曲線的最終值的大小來評估陷入局部收斂的程度，數值越小則表明在抵抗局部收斂的能力越強。圖1、圖2，分別為Iris、Pageblocks兩種經典數據集在運行五種聚類算法的目標函數值的收斂曲線，其橫坐標為迭代次數，縱坐標為目標函數值的對數。

首先，FCM與改進后的算法HGAKFCM的收斂曲線進行對比，可以通過圖2直觀地了解到HGAKFCM的目標函數收斂值大幅度小于FCM，這就可以得到新算法的抗局部收斂能力相較于FCM有很大提升。此外，再將新算法HGAKFCM與性能不錯的三種經典算法（分別為FCS模糊子空間聚類、KFCM核模糊C均值、FCM遺傳算法優化的模糊C均值）進行對比，四種算法的目標函數收斂值大小排序如下：

（1）在Iris數據集中：GAFCM>FCS>KFCM>HGAKFCM。

（2）在Pageblocks數據集中：GAFCM>KFCM>FCS>HGAKFCM。HGA算法在Iris和Pageblocks數據集中與其他三種算法排序最小，而目標函數收斂值越小，其抗局部收斂能力就越強，新算法在這四種數據集的抵抗局部收斂能力良好。

FCM算法的初始聚類中心敏感會導致各種聚類性能指標的不同程度的下降，最直接地反映在迭代次數和精度方面，新算法用分層遺傳來優化初始聚類中心得到較為優質的初始聚類中心，在此選取聚類到最終結果所需的迭代次數和精度作為衡量指標，迭代次數越小和精度越高則表示新算法較好地解決了FCM初始聚類中心敏感這個問題。表2是兩個數據集在測試五種聚類算法20次的迭代次數和精度數據。

HGAKFCM算法與FCM算法在迭代次數上進行了三個小方面的對比，分別是在20次實驗中的最多迭代次數，最少迭代次數以及平均迭代次數，可以明顯看出HGAFCM在迭代次數少于FCM，究其深層原因，HGAFCM算法用分層遺傳多次迭代篩選出更加合適的初始聚類中心，從而讓算法的主循環的迭代次數明顯減少。在精度方面，HGAKFCM算法在兩種數據集測試20次的平均精度依次為：0.9141、0.9005。FCM算法則為：0.8933、0.3573，通過對比，新算法HGAKFCM相較于FCM算法有很大的精度提升。此外，將新算法與FCS、GAFCM、KFCM三種算法在精度和迭代次數上進行對比，如表2所示，在精度上，對比四種數據集上的精度測試，HGAKFCM皆不同程度地優于其他三種算法，在迭代次數上，新算法在四種數據集上的平均迭代次數分別為：5.1、17.8，均小于其他三種算法。

結語

提出的HGAKFCM算法用分層遺傳優化初始聚類中心，得到合適的初始聚類中心后，用高斯徑向函數替代FCM的距離函數得到新的目標函數，通過新的目標函數進行迭代完成聚類，通過仿真實驗與FCM算法對比，在一定程度上解決了FCM的局部收斂和初始聚類中心敏感問題。另外，將新算法與經典的三種聚類算法在抗局部收斂能力、迭代次數和精度三個方面進行實驗比較，結果顯示新算法擁有不錯的性能。

參考文獻：

[1]Bezdek?James?C.，Ehrlich?Robert，Full?William.FCM：The?fuzzy?cmeans?clustering?algorithm[J].Pergamon，1984，10：23.

[2]J.C.Dunn.A?Fuzzy?Relative?of?the?ISODATA?Process?and?Its?Use?in?Detecting?Compact?WellSeparated?Clusters[J].Cybernetics?and?Systems，1973，3（3）：3257.

[3]Zhang?D?Q，Chen?S?C.Fuzzy?clustering?using?kernel?method[C]//?International?Conference?on?Control?&?Automation.IEEE，2003.

[4]Zhang?D?Q，Chen?S?C.A?novel?kernelized?fuzzy?Cmeans?algorithm?with?application?in?medical?image?segmentation[J].Artificial?Intelligence?in?Medicine，2004，32（1）：3750.

[5]文傳軍，詹永照.粒子群高斯誘導核模糊C均值聚類算法[J].科學技術與工程，2018，18（08）：7884.

[6]陳書文，覃華，蘇一丹.最優正則化參數的核FCM聚類算法[J].小型微型計算機系統，2018，39（07）：15371541.

[7]梁冰，徐華.基于改進人工蜂群的核模糊聚類算法[J].計算機應用，2017，37（09）：26002604.

[8]劉奕麟，安建成.優化的核模糊C均值聚類算法[J].微電子學與計算機，2018，35（02）：7983.

[9]崔慶磊.基于多目標分層遺傳算法的溢流粒度軟測量[D].大連理工大學，2015.

[10]劉樹榮.基于分層遺傳算法的測試數據自動生成方法研究[D].北京理工大學，2015.

[11]牟威.分層遺傳算法在圖像模板匹配中的應用[D].北京郵電大學，2011.

作者簡介：吳盛平（1996—?），男，漢族，安徽樅陽人，碩士，研究方向：模式識別。