模糊c－均值算法和萬有引力算法求解模糊聚類問題

谷文祥，郭麗萍，殷明浩

(東北師范大學計算機科學與信息技術學院，吉林長春 130117)

模糊c－均值算法和萬有引力算法求解模糊聚類問題

谷文祥，郭麗萍，殷明浩

(東北師范大學計算機科學與信息技術學院，吉林長春 130117)

針對單純使用模糊c－均值算法(FCM)求解模糊聚類問題的不足，首先，提出一種改進的萬有引力搜索算法，通過一定概率按照不同方式對速度進行更新，有效增大了種群的搜索域.其次，提出了模糊萬有引力搜索算法(FGSA).最后，在模糊萬有引力搜索算法(FGSA)和模糊c－均值算法(FCM)的基礎上，提出了一種新算法(FGSAFCM)來求解模糊聚類問題，有效避免了單純使用模糊c－均值算法時對初始值敏感且易于陷入局部最優的缺點.采用目標函數和有效性評價函數作為評價標準，選取10個經典數據集作為測試數據，實驗結果表明，新算法比單一的模糊c－均值算法有更高的準確性和魯棒性.

模糊聚類;模糊c－均值算法;萬有引力搜索算法;模糊萬有引力搜索算法

聚類分析是中非監督模式識別的一個重要分支.它試圖將數據分成幾個不同的組，要求組內的數據相似性大，組間的數據相似性小，這樣的組在聚類中被稱為“簇”.目前，求解聚類問題主要包括硬聚類、模糊聚類、可能性聚類3種方法.硬聚類方法［1］在分類時具有絕對性，即“非此即彼”，這種方式雖然時間消耗非常少，但是也割斷了數據之間的聯系.模糊聚類方法［2］把Zadeh的模糊理論引入到聚類中，使每個樣本對各個類別的隸屬度擴展到［0，1］區間，這種方法在處理各類別之間含有交集的聚類問題時，效果明顯優于硬聚類方法.可能性聚類［3］方法在模糊聚類方法的基礎上，不再限定樣本對每個類別的隸屬度之和為1.

模糊 c－均 值 算 法 (fuzzy c－means algorithm，FCM)［2］是求解模糊聚類問題最經典的算法之一.然而，模糊c－均值算法對初始值非常敏感，而且很容易陷入局部最優.萬有引力算法(gravitational search algorithm，GSA)［4］是由 Rashedi和 Nezamabadi－pour在2009年提出來的一種模擬物理學中的萬有引力進行優化的新算法.它通過群體中各微粒之間的萬有引力來指導整個種群的搜索.實驗證明，萬有引力搜索具有較強的全局搜索能力.本文首先利用萬有引力算法找到較好的初始解，然后用模糊c－均值算法進行深入搜索，最終找到較優的解.

1 模糊c－均值算法

模糊 c－均值算法［2，5－6］是由 J.C.Bezdek 等人于1973年提出的，該算法試圖把n個數據O={o1，o2，…，oi，…，on}分成k(1 ＜k＜n)類，利用隸屬度矩陣μ表示樣本數據屬于各個類別的程度，元素μij表示第i個樣本數據屬于第j類的程度，矩陣μ應該滿足如下約束條件:

FCM算法的目標函數為

式中:m(m＞1)是一個調節聚類結果的模糊程度的參數，m越大，聚類的結果就越模糊.FCM算法可以描述如下:

1)選定m，初始化迭代次數t及隸屬度矩陣元素 μij，i=1，2，…，n;j=1，2，…，k.

2)按照式(5)計算聚類中心:

3)計算每個樣本數據到各個簇的歐氏距離:

4)對于任意的i和l，如果dil＞0，則按照式(6)更新隸屬度.

否則，如果存在dil=0，則μil=1，且對于任意的j≠l，μij=0.

5)如果算法仍未收斂，轉2).

這里，評價算法的收斂條件包括2個，一個是達到算法設定的最大迭代次數，另一個是目標函數(4)的值在指定迭代次數內無法再變小.

2 萬有引力搜索算法

2.1 標準的萬有引力搜索算法

萬有引力搜索算法［4，13］(gravitational search algorithm，GSA)是2009年由Rashedi等提出的，該算法模擬物理學中的萬有引力定律“宇宙中任意2個質點之間存在吸引力，該引力的大小與它們質量的乘積成正比，與它們之間的距離成反比”，通過個體間的萬有引力作用引導搜索.在該算法中，每個個體包含4個屬性:位置、慣性質量、主動引力質量和被動引力質量，個體的位置就是問題的解.由N個個體組成的種群 X={X1，X2，…，Xi，…，Xn}，其中，

式中:表示第i個個體在第d維空間的位置.在第t次迭代過程中，個體j作用于個體i的力定義為

式中:G(t)是時間t下的萬有引力常量，Maj(t)是個體j的主動引力質量，Mpi(t)是個體i的被動引力質量.ε是一個非常小的常量，Rij(t)表示個體i和個體j之間的歐氏距離，

個體i在第d維空間上受到其他個體的合力表示為

式中:randj是一個［0，1］區間內的隨機數，增加了算法的隨機性.

個體i在第d維空間上的加速度按照式(7)計算得出:

式中:Mii(t)表示個體i的慣性質量.個體i的位置按照式(8)進行更新:

式中:(t)是個體i在第d維空間上的速度，(t)是個體i在第d維空間上的位置，randi是一個［0，1］區間內的實數，可以增強算法的隨機搜索能力.

G0是萬有引力常量G的初始值，隨著迭代次數的增加，G會逐漸減小來控制搜索的精確性.G是關于G0和t的一個函數:

引力質量和慣性質量通過適應度函數計算得出，假設引力質量和慣性質量相同，通過如式(9)更新個體的引力質量和慣性質量:

式中:fiti(t)表示個體i在時間t的適應度值，best(t)和worst(t)定義如式(10):

2.2 改進的萬有引力搜索算法

為了增強算法的全局搜索能力，本文提出了一種新的速度更新方式:首先，隨機生成一個［0，1］區間的實數r，如果r＜0.5，就按照式(8)對速度進行更新，否則，按照式(11)更新速度:

實驗結果表明，這種方式能夠有效地擴大了算法的搜索域，對于避免算法陷入局部最優值有一定效果.

2.3 模糊萬有引力搜索算法

Pang等［7］在2004年提出了一種修改的粒子群算法(particle swarm optimization，PSO)用于求解旅行商問題(traveling salesman problem，TSP)，它采用粒子的位置和速度表示變量之間的模糊關系.本文把這種方法用在萬有引力搜索算法中來求解模糊聚類問題，提出了模糊萬有引力搜索算法(fuzzy gravitational search algorithm，FGSA).

在FGSA中，用粒子的位置矩陣X表示樣本和簇之間的隸屬程度.X的形式化表示如式(12):

式中:μij表示個體i屬于簇j的程度，它必須滿足式(1)～(3)的約束條件.這樣，就把粒子的位置和隸屬度矩陣對應起來，每個粒子的位置和速度均由一個n行c列的矩陣來表示，并按照如下方式進行更新:隨機生成一個［0，1］區間內的實數r，若r＜0.5，則

式中:⊕、Θ和?分別表示矩陣加法、減法和乘法運算.更新結束之后，可能會有些元素違背式(2)、(3)中的約束，則需要對其進行標準化，標準化過程如下:

1)如果矩陣中的元素為負，就把該元素賦為0;

2)如果矩陣中的某一行元素全為0，則用［0，1］區間內的隨機實數重新對其進行賦值;

3)如果矩陣中的所有元素都不違背約束，則按如式(16)進行轉換:

在FGSA算法中，采用式(4)作為適應度函數，適應度函數的值越小，解的質量也越高.FGSA算法求解模糊聚類問題的流程如下:

1)初始化最大迭代次數maxt及其他參數;

2)生成初始種群，初始化種群中每個個體的位置和速度;

3)按照式(5)計算聚類中心;

4)按照式(4)計算適應度函數值;

5)更新G;

6)為每個個體更新慣性質量;

7)計算每個個體受到的合力F及加速度a;

8)按照式(13)～(15)更新每個個體的位置和速度;

9)重復3)～8)，直到滿足算法的停止條件.

3 混合新算法求解模糊聚類問題

和FGSA算法相比，FCM算法由于需要的參數少，所以它的收斂速度比FGSA快，但是它也很容易陷入局部最優值;FGSA算法由于出色的全局搜索能力，往往能找到較好的解.因此，在FCM算法和FGSA算法的基礎上，設計了一種新的算法——FG－SAFCM算法.在FGSAFCM算法中，算法初期采用FGSA算法尋找較好的初始解，然后利用FCM算法進行深入搜索.該算法繼承了FGSA和FCM算法的優點，有效避免了對初始值敏感和易于陷入局部最優的缺點.

在FGSAFCM算法中，每個個體的位置由一個n行c列的矩陣表示，第i行第j列的元素表示樣本i屬于簇j的程度，在存儲時，把每個個體的位置轉換成一個行向量表示.結構圖如圖1.

圖1 FGSAFCM算法中的個體結構圖Fig.1 The presentation of an object in FGSAFCM

FGSAFCM算法求解模糊聚類問題的流程如下:

1)初始化最大迭代次數maxt及其他參數;

2)生成初始種群，初始化每個個體的位置和速度;

3)設置迭代次數:Gen1=Gen2=Gen3=0;

4)FGSA算法).

①利用FGSA算法更新種群的每個個體;

②Gen2=Gen2+1;如果 Gen2＜8，轉4);

5)對每個個體i:

①個體i的位置對應于樣本和簇之間的隸屬度;

②用FCM算法更新聚類中心;

③Gen3=Gen3+1;如果 Gen3＜4，轉5);

6)Gen1=Gen1+1;如果 Gen1＜ maxt，轉4).

4 仿真實驗

實驗環境為:Pentium 2.0 GHz處理器，1.00 GB內存，采用Visual Studio 2008編碼.

4.1 數據集

實驗數據包括 ArtSet1、ArtSet2、Fisher’s Iris 、Breast－Cancer－Wisconsin(Cancer)、Glass、Wine、Contraceptive Method Choice(CMC) 、Vowel［8］、Teaching AssistantEvaluation (TAE)、Vertebral Column(VC)［14］10個數據集.這些數據集涵蓋了低維、中維、高維的不同數據，具有一定的代表性.

ArtSet1和ArtSet2是2個人造數據集;Iris包括3類鳶尾花，每類包含萼片長、萼片寬、花瓣長和花瓣寬4個特征;Cancer通過細胞大小、細胞形狀、核染色質等9個特征，將癌癥分為惡性和良性2類;Glass通過折射率、鈉、鎂、鋁等9個特征把玻璃分為6類;Wine分為3類，包括酒精、蘋果酸、花青素、色度等13個特征;CMC源于1987年印尼的避孕調查，根據社會統計學特征將被調查者分為未避孕、長期避孕和短期避孕3類;Vowel包括6種不同類型的印度泰盧固語元音發音，每種包含3個特征;VC是Henrique在一次醫學研究中整理出來的，他根據6個生物學特征將脊柱數據分為正常、椎間盤突出、脊椎前移3類;TAE是威斯康星大學麥迪遜分校整理的關于151個助教的授課評估情況，根據5個評價指標將結果分為低、中、高3類.數據集的詳細描述見表1.

表1 數據集描述Table 1 The description of datasets

4.2 實驗結果

實驗參數設置:FCM算法中，m的值設置為2，最大迭代次數maxt為100;FGSAFCM算法中，種群數目設置為20，萬有引力常量初值G0為100，最大迭代次數為20.實驗結果為10次獨立實驗的平均值.為了更全面地測試新算法的性能，引入了有效性評價函數(PC)Partition Coefficien［9］.

該函數的形式化描述為

PC的值越大，分類的有效性就越大.表2和表3分別是FCM算法和FGSAFCM算法的目標函數值、有效性評價函數值的實驗結果對比.從表2和表3可以看出，無論是目標函數值，還是有效性函數值，FGSAFCM算法都要優于FCM算法，并且隨著數據集維數的增加，這種優越性更加明顯，充分體現了新算法的有效性和魯棒性.

表2 FCM、FGSAFCM算法的目標函數值對比Table 2 The comparison of objective function for FCM，FGSAFCM

表3 FCM、FGSAFCM算法的有效性函數PC對比Table 3 The comparison of validity function for FCM，FGSAFCM

5 結束語

提出了一種改進的萬有引力搜索算法，并在此基礎上，提出了模糊的萬有引力搜索算法;通過結合模糊的萬有引力搜索算法和模糊c－均值算法，提出了一種新的求解模糊聚類問題的方法——FGSAFCM算法，實驗結果表明，新算法的目標函數值和有效性評價函數值都要優于模糊c－均值算法，并且隨著數據集維數的增加，優越性更加明顯，體現了新算法的有效性.

未來主要工作包括把該算法應用到其他聚類問題中，以及尋找更優的算法求解模糊聚類問題.

［1］DUBES R C，JAIN A K.Algorithms for clustering data［M］.Englewood Cliffs，USA:Prentice Hall，1988:1－20.

［2］BEZDEK J C.Pattern recognition with fuzzy objective function algorithms［M］.New York，USA:Plenum Press，1981:43－93.

［3］KRISHNAPURAM R，KELL J M.The possibilistic c－means algorithm:insights and recommendation［J］.IEEE Trans FS，1996，4(3):385－393.

［4］RASHEDI E，NEZAMABADI－POUR H，SARYAZDI S.GSA:a gravitational search algorithm［J］.Information Sciences，2009，179(13):2232－2248.

［5］BEZDEK J C.Fuzzy mathematics in pattern classification［D］.Ithaca:USA Cornell University，1973:18－42.

［6］DUNN J C.A fuzzy relative of the ISODATA process and its use in detecting compact well－separated clusters［J］.Journal of Cybernetics，1973，3(1):32－57.

［7］PANG W，WANG K，ZHOU C，et al.Fuzzy discrete particle swarm optimization for solving traveling salesman problem［C］//Proceedings of the Fourth International Conference on Computer and Information Technology.Wuhan，China:IEEE CS Press，2004:796－800.

［8］PAL S K，DUTTA M R D.Fuzzy sets and decision making approaches in vowel and speaker recognition［J］.IEEE Transactions on Systems，Man，and Cybernetics，1977，7(8):625－629.

［9］BEZDEK J C.Cluster validity with fuzzy sets［J］.Cybernetics，1974，3(3):58－73.

［10］RUNKLER T A，KATE C.Fuzzy clustering by particle swarm optimization［C］//InternationalConferenceon Fuzzy Systems Vancouver Canada，2006:601－608.

［11］WANG Yingje.Fuzzy clustering analysis by using genetic algorithm［J］.ICIC，2008，2(4):331－337.

［12］MAULIK UJJWAL，BANDYOPADHYAY SANGHAM－ITA.Genetic algorithm－based clustering technique［J］.Pattern Recognition，2000，33(9):1455－1465.

［13］谷文祥，李向濤，朱磊，等.求解流水線調度問題的萬有引力搜索算法［J］.智能系統學報，2010，5(5):411－418.

GU Wenxiang，LI Xiangtao，ZHU Lei，et al.A gravitational search algorithm for flow shop scheduling［J］.CAAI Transactions on Intelligent Systems，2010，5(5):411－418.

［14］ASUNCION A，NEWMAN D J.UCI machine learning repository［DB/OL］.Irvine，USA:University of California，School of Information and Computer Science，2007.

谷文祥，男，1947年生，教授，博士生導師，主要研究方向為智能規劃與規劃識別、形式語言與自動機理論、模糊數學及其應用.主持國家自然科學基金項目3項，發表學術論文100余篇.

郭麗萍，女，1989年生，碩士研究生，主要研究方向為智能規劃、智能信息處理.

殷明浩，男，1979年生，副教授，主要研究方向為智能規劃與自動推理.主持國家自然科學青年基金項目1項，參與多項國家自然科學基金項目.發表學術論文30余篇，其中大部分被SCI和EI檢索.

A solution for a fuzzy clustering problem by applying fuzzy c-means algorithm and gravitational search algorithm

GU Wenxiang，GUO Liping，YIN Minghao
(Department of Computer Science and Information Technology，Northeast Normal University，Changchun 130117，China)

Aiming at fixing the shortcomings of using fuzzy C－means algorithm solely to solve fuzzy clustering problems，first，this paper proposed an improved gravitational search algorithm by updating the velocity of individuals according to a probability，expanding the search space effectively.Secondly，a fuzzy gravitational search algorithm(FGSA)was proposed.Finally，a novel hybrid algorithm(FGSAFCM)based on a fuzzy improved gravitational search algorithm(FGSA)and fuzzy c－means algorithm(FCM)was proposed to solve fuzzy clustering problems.Fuzzy c－means algorithm is very sensitive to initialization and easily gets into local optima，but the new algorithm may avoid these shortcomings.This paper chooses the objective function and validity function as the evaluation criterion.The FGSAFCM was tested on ten classic datasets，and the experiment results show that the new algorithm is more accurate and robust than the sole fuzzy c－means algorithm.

fuzzy clustering problem;fuzzy c－means algorithm;gravitational search algorithm;fuzzy gravitational search algorithm

TP301.6

A

1673－4785(2011)06－0520－06

book=6,ebook=345

10.3969/j.issn.1673－4785.2011.06.007

2011－06－15.

國家自然科學基金資助項目(60803102，61070084).

郭麗萍.E－mail:guolp281@nenu.edu.cn.