葉昌倫 韋霞

摘要

雙模糊C均值聚類算法存在對初始聚類中心位置的敏感缺點，影響了算法的應用。本文提出了基于模擬退火（SA）和遺傳算法（GA）的雙模糊C均值聚類算法。SAGA-DFCM結(jié)合了模擬退火和遺傳算法的優(yōu)勢，設置新的適應度函數(shù)，對初始聚類中心位置進行優(yōu)化。在wine數(shù)據(jù)集的分類結(jié)果中看到SAGA-DFCM相對于DFCM算法大大減小了對初始聚類中心位置的敏感程度。

【關(guān)鍵詞】僅模糊C均值聚類 遺傳算法 模擬退火 初始聚類中心

1 引言

聚類分析在各個領(lǐng)域都得到了廣泛地應用，其著名的模糊聚類算FCM，它是根據(jù)模糊理論建立的聚類算法，它是尋找一種分類，使其樣本到類別的廣義加權(quán)距離平方和最小，但這并不能保證類別到樣本整體聚類中心的廣義加權(quán)歐式距離最大，對此，引入了雙模糊C均值算法（Double Fuzzy C-Means），通過建立兩級FCM模型，以解決這一缺點?？偹苤狥CM盡管它具有很強的搜索能力，但對初始聚類中心選取、數(shù)據(jù)量大時，容易得到局部最優(yōu)解。而DFCM相當于兩個FCM模型的合成，必然受初值和數(shù)據(jù)量大的影響比FCM大。

為了解決DFCM這一缺點，結(jié)合遺傳算法（GA）具有較強的全局尋優(yōu)能力和模擬退火（SA）具有較強局部尋優(yōu)的能力，設置新的適應度函數(shù)，對DFCM算法的初始聚類中心進行優(yōu)化。改進后的DFCM算法對初始聚類中心的敏感性強度大大減小。

2 DFCM算法概述

DFCM算法是在經(jīng)典的FCM算法上建立的，而FCM算法是尋找一種分類，使其樣本到類別的廣義加權(quán)距離平方和最小，但這并不能保證類別到樣本整體聚類中心的廣義加權(quán)歐式距離最大，為了改善這一缺陷，進而引入了DFCM算法：

在式中，表示第j個樣本屬于第h個類別的隸屬度，β為模糊度參數(shù)，c為聚類數(shù)，n為樣本數(shù)，w_i表示第i個指標的權(quán)重。s_ih表示第h個類別的第i個指標的規(guī)格化值。①式是經(jīng)典FCM算法，②式類別到樣本整體的中心廣義加權(quán)歐式距離，為了達到聚類效果，只要使F取最小值，即①式達到最小，②式達到最大。其中每個樣本的隸屬度滿足以下條件：

（1）式通過拉格朗日數(shù)乘法求其最小得：

由于給定的樣本的整體聚類中心是唯一的，故不需要優(yōu)化，所以把所有樣本指標規(guī)格化值的平均值作為樣本整體聚類中心的指標值，將（6）式簡化為：

通過（3），（4）建立第一級FCM模型，（5），（7）建立第二級FCM模型，將兩個FCM模型合起來便是DFCM算法，我們知道盡管FCM算法有很強的搜索能力，但是也容易受聚類中心初值s_ih⁰的影響，得到局部最優(yōu)解，尤其在處理數(shù)據(jù)量大的時候。必然地，由于DFCM相當于兩個FCM算法的合成。也存在這樣的問題。還有當初值的選取不當時（4）式可能出現(xiàn)負值，導致迭代失敗。

3 改進的SAGA-DFCM算法步驟

為了解決DFCM存在的問題，將模擬退火和遺傳算法結(jié)合（SAGA）用于DFCM算法。為評價每一個個體，結(jié)合（1）式定義了以下適應度函數(shù)：

其中，λ為常數(shù)，從上式知，F(xiàn)（U，S，V，S₀）越小，適應函數(shù)越大，聚類效果越好。

由于遺傳算法（GA）具有較強的全局尋優(yōu)能力和模擬退火（SA）具有較強局部尋優(yōu)的能力，因此結(jié)合遺傳算法和模擬退火對聚類中心初值的優(yōu)化;SAGA-DFCM算法實現(xiàn)如下：

（1）對數(shù)據(jù)X規(guī)格化處理;

（2）初始化控制參數(shù);DFCM算法初始參數(shù)：W指標權(quán)重，MAX_die最大迭代次數(shù)，num_F為目標函數(shù)F的精度，num_S對每一個初值s_ih⁰，S的迭代精度。遺傳算法初始化參數(shù)：種群個體大小popsize，最大進化次數(shù)MAX_CEN，交叉概率P_C，變異概率P_m，模擬退火初始化參數(shù)：退火初始溫度T⁰，溫度冷卻系數(shù)ξ，終止溫度T^end;

（3）隨機初始化c個聚類中心，并產(chǎn)生初始種群c，對每個聚類中心用式（4），算出v_h，再用式（2），（3）反復迭代當|S_i+1-S_i|j+1-F_i|F或達到最大迭代次數(shù)MAX_die時，退出整個程序，通過（1）式得到F，并運用適應度分配函數(shù)FintS⁰=ranking（F）求出每個個體的適應度值。當F的值越小時，個體的適應度值f_i越大;

（4）設置循環(huán)計數(shù)變量index_gen=0;

（5）選擇：這里采用隨機遍歷抽樣（sus）選擇個體;

（6）重組：單點交叉;

（7）變異：以概率為P^m變異;

（8）對新產(chǎn)生的個體使用$（4），（5），（2），（3）$循環(huán)迭代得到c個類的聚類的中心矩陣，各樣本的隸屬矩陣，還有每個個體的適應度值f_i。

（9）替換：如果f_i>f_i，替換舊的個體，否則通過模擬退火以Pe^{（（fi-fi）T）}替換舊個體。

（10）計數(shù)：若index_gengen，index_gen=index_gen+1，回到第（5）步，否則到達步驟（11）。

（11）若T_iend，結(jié)束，輸出全局最優(yōu)解;否則，開始執(zhí)行降溫T_i+1=ξT_i，重新回到（4）。

4 實驗與分析

為了驗證SAGA-DFCM的性能，使用UCI（University of California Irvine）數(shù)據(jù)集中的Wine數(shù)據(jù)和DFCM對比進行測試;其中UCI中的Wine數(shù)據(jù)樣本共178個，指標值共有有13項，共三類，第一類有59個樣本，第二類有72個樣本，第三類有47個樣本，一共有13個指標值，設置參數(shù)S的迭代精度num_S=0.1，設置參數(shù)F的迭代精度num_F=10^-6，最大進化次數(shù)MAX_GEN=150，運用MATLAB，分別調(diào)用DFCM，SAGA-DFCM結(jié)果如下：

其中SSAGA-DFCM為SAGA-DFCM算法最終迭代聚類中心，S_DFCM為DFCM算法最終迭代聚類中心，可以看出盡管num_S=0.1，SAGD-DFCM算法的精度遠大于DFCM，已經(jīng)非常接近精確值。

其中F_in表示所有樣本到類別的加權(quán)歐式距離之和，F(xiàn)_out表示所有類別到整體樣本的加權(quán)歐式距離之和。從運行的結(jié)果來看，在參數(shù)設置相同的情況下，顯然是SAGA-DFCM的性能好，由于S的初值不同DFCM算法F的值會在[0.18，0.19]之間波動，波動范圍較大，受初始聚類中心敏感性強，而SAGD-DFCM算法F的值穩(wěn)定在0.1710，波動范圍很小，受初始聚類中心的影響大大降低，正確率也比DFCM很高。因此SAGA-DFCM是值得推廣的。

5 結(jié)論

雙模糊C均值聚類算法是一種局部收索算法，如果初始聚類中心選擇不當，則會得到局部最優(yōu)點。本文提出了基于模擬退火和遺傳算法的雙模糊C均值聚類算法（SAGA-DFCM），不僅使其類別到樣本整體聚類中心的廣義加權(quán)歐式距離最大，同時增強了DFCM算法的全局尋優(yōu)能力。在wine數(shù)據(jù)集的分類結(jié)果中，可以看到，每次F的迭代值基本不變，SAGA-DFCM算法大大減小了初值的敏感程度，但算法的全局和局部搜索能力還需要進一步加強。

參考文獻

[1]白莉媛，胡聲艷，劉素華.一種基于模擬退火和遺傳算法的模糊聚類方法[J].計算機工程與應用，2005，41（09）：56-58.

[2]牛向陽，倪前月，高成修.基于遺傳算法和模擬退火算法的混合算法[J].明理工大學學報（自然科學版），2008，33（02）：25-28.

[3]夏趙建，杜友福.基于樸素貝葉斯對wine數(shù)據(jù)集分類[J].電腦知識與技術(shù)，2017，13（29）：224-226.

[4]董國華.一種改進的聚類算法及其在說話人識別上的應用[J].微計算機信息，2004，20（09）：134-135.

[5]郁磊.MATLAB智能算法30個案例分析（第2版）[M].北京：北京航空航天大學出版社，2015.

[6]李希燦.模糊數(shù)學方法及其應用[M].北京：化學工業(yè)出版社，2016.

[7]Li Li，Renxiang Wang，and Xican Li.Double fuzzy c-means model andits application in the technologyinnovation of china.Journal ofIntelligent and Fuzzy Systems，pages1-7.