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

谷文祥，郭麗萍，殷明浩

(東北師范大學(xué)計(jì)算機(jī)科學(xué)與信息技術(shù)學(xué)院，吉林長(zhǎng)春 130117)

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

谷文祥，郭麗萍，殷明浩

(東北師范大學(xué)計(jì)算機(jī)科學(xué)與信息技術(shù)學(xué)院，吉林長(zhǎng)春 130117)

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

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

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

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

1 模糊c－均值算法

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

FCM算法的目標(biāo)函數(shù)為

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

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

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

3)計(jì)算每個(gè)樣本數(shù)據(jù)到各個(gè)簇的歐氏距離:

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

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

5)如果算法仍未收斂，轉(zhuǎn)2).

這里，評(píng)價(jià)算法的收斂條件包括2個(gè)，一個(gè)是達(dá)到算法設(shè)定的最大迭代次數(shù)，另一個(gè)是目標(biāo)函數(shù)(4)的值在指定迭代次數(shù)內(nèi)無法再變小.

2 萬有引力搜索算法

2.1 標(biāo)準(zhǔn)的萬有引力搜索算法

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

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

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

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

式中:randj是一個(gè)［0，1］區(qū)間內(nèi)的隨機(jī)數(shù)，增加了算法的隨機(jī)性.

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

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

式中:(t)是個(gè)體i在第d維空間上的速度，(t)是個(gè)體i在第d維空間上的位置，randi是一個(gè)［0，1］區(qū)間內(nèi)的實(shí)數(shù)，可以增強(qiáng)算法的隨機(jī)搜索能力.

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

引力質(zhì)量和慣性質(zhì)量通過適應(yīng)度函數(shù)計(jì)算得出，假設(shè)引力質(zhì)量和慣性質(zhì)量相同，通過如式(9)更新個(gè)體的引力質(zhì)量和慣性質(zhì)量:

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

2.2 改進(jìn)的萬有引力搜索算法

為了增強(qiáng)算法的全局搜索能力，本文提出了一種新的速度更新方式:首先，隨機(jī)生成一個(gè)［0，1］區(qū)間的實(shí)數(shù)r，如果r＜0.5，就按照式(8)對(duì)速度進(jìn)行更新，否則，按照式(11)更新速度:

實(shí)驗(yàn)結(jié)果表明，這種方式能夠有效地?cái)U(kuò)大了算法的搜索域，對(duì)于避免算法陷入局部最優(yōu)值有一定效果.

2.3 模糊萬有引力搜索算法

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

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

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

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

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

2)如果矩陣中的某一行元素全為0，則用［0，1］區(qū)間內(nèi)的隨機(jī)實(shí)數(shù)重新對(duì)其進(jìn)行賦值;

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

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

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

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

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

4)按照式(4)計(jì)算適應(yīng)度函數(shù)值;

5)更新G;

6)為每個(gè)個(gè)體更新慣性質(zhì)量;

7)計(jì)算每個(gè)個(gè)體受到的合力F及加速度a;

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

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

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

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

在FGSAFCM算法中，每個(gè)個(gè)體的位置由一個(gè)n行c列的矩陣表示，第i行第j列的元素表示樣本i屬于簇j的程度，在存儲(chǔ)時(shí)，把每個(gè)個(gè)體的位置轉(zhuǎn)換成一個(gè)行向量表示.結(jié)構(gòu)圖如圖1.

圖1 FGSAFCM算法中的個(gè)體結(jié)構(gòu)圖Fig.1 The presentation of an object in FGSAFCM

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

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

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

3)設(shè)置迭代次數(shù):Gen1=Gen2=Gen3=0;

4)FGSA算法).

①利用FGSA算法更新種群的每個(gè)個(gè)體;

②Gen2=Gen2+1;如果 Gen2＜8，轉(zhuǎn)4);

5)對(duì)每個(gè)個(gè)體i:

①個(gè)體i的位置對(duì)應(yīng)于樣本和簇之間的隸屬度;

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

③Gen3=Gen3+1;如果 Gen3＜4，轉(zhuǎn)5);

6)Gen1=Gen1+1;如果 Gen1＜ maxt，轉(zhuǎn)4).

4 仿真實(shí)驗(yàn)

實(shí)驗(yàn)環(huán)境為:Pentium 2.0 GHz處理器，1.00 GB內(nèi)存，采用Visual Studio 2008編碼.

4.1 數(shù)據(jù)集

實(shí)驗(yàn)數(shù)據(jù)包括 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個(gè)數(shù)據(jù)集.這些數(shù)據(jù)集涵蓋了低維、中維、高維的不同數(shù)據(jù)，具有一定的代表性.

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

表1 數(shù)據(jù)集描述Table 1 The description of datasets

4.2 實(shí)驗(yàn)結(jié)果

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

該函數(shù)的形式化描述為

PC的值越大，分類的有效性就越大.表2和表3分別是FCM算法和FGSAFCM算法的目標(biāo)函數(shù)值、有效性評(píng)價(jià)函數(shù)值的實(shí)驗(yàn)結(jié)果對(duì)比.從表2和表3可以看出，無論是目標(biāo)函數(shù)值，還是有效性函數(shù)值，F(xiàn)GSAFCM算法都要優(yōu)于FCM算法，并且隨著數(shù)據(jù)集維數(shù)的增加，這種優(yōu)越性更加明顯，充分體現(xiàn)了新算法的有效性和魯棒性.

表2 FCM、FGSAFCM算法的目標(biāo)函數(shù)值對(duì)比Table 2 The comparison of objective function for FCM，F(xiàn)GSAFCM

表3 FCM、FGSAFCM算法的有效性函數(shù)PC對(duì)比Table 3 The comparison of validity function for FCM，F(xiàn)GSAFCM

5 結(jié)束語

提出了一種改進(jìn)的萬有引力搜索算法，并在此基礎(chǔ)上，提出了模糊的萬有引力搜索算法;通過結(jié)合模糊的萬有引力搜索算法和模糊c－均值算法，提出了一種新的求解模糊聚類問題的方法——FGSAFCM算法，實(shí)驗(yàn)結(jié)果表明，新算法的目標(biāo)函數(shù)值和有效性評(píng)價(jià)函數(shù)值都要優(yōu)于模糊c－均值算法，并且隨著數(shù)據(jù)集維數(shù)的增加，優(yōu)越性更加明顯，體現(xiàn)了新算法的有效性.

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

［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］谷文祥，李向濤，朱磊，等.求解流水線調(diào)度問題的萬有引力搜索算法［J］.智能系統(tǒng)學(xué)報(bào)，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年生，教授，博士生導(dǎo)師，主要研究方向?yàn)橹悄芤?guī)劃與規(guī)劃識(shí)別、形式語言與自動(dòng)機(jī)理論、模糊數(shù)學(xué)及其應(yīng)用.主持國(guó)家自然科學(xué)基金項(xiàng)目3項(xiàng)，發(fā)表學(xué)術(shù)論文100余篇.

郭麗萍，女，1989年生，碩士研究生，主要研究方向?yàn)橹悄芤?guī)劃、智能信息處理.

殷明浩，男，1979年生，副教授，主要研究方向?yàn)橹悄芤?guī)劃與自動(dòng)推理.主持國(guó)家自然科學(xué)青年基金項(xiàng)目1項(xiàng)，參與多項(xiàng)國(guó)家自然科學(xué)基金項(xiàng)目.發(fā)表學(xué)術(shù)論文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.

國(guó)家自然科學(xué)基金資助項(xiàng)目(60803102，61070084).

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