基于自適應(yīng)蟻群算法的模糊聚類算法

白亞男，司應(yīng)碩

(1.平頂山學(xué)院，河南 平頂山467000;2.鄭州航空工業(yè)管理學(xué)院，河南鄭州450046)

聚類分析作為無監(jiān)督分類的一種方法是一種硬劃分，模糊集合理論被引入到聚類分析領(lǐng)域即發(fā)展為模糊聚類分析理論.目前研究的熱點(diǎn)是基于目標(biāo)函數(shù)的模糊聚類方法，這種方法是把聚類歸結(jié)為一個帶有約束的非線性規(guī)劃問題，通過優(yōu)化求解獲得數(shù)據(jù)集的模糊劃分和聚類.該方法設(shè)計(jì)簡單，解決問題范圍廣，易于實(shí)現(xiàn).模糊C均值(Fuzzy C-Means，F(xiàn)CM)理論［1］是此類方法中最為完善，應(yīng)用最為廣泛的算法.而FCM算法的缺點(diǎn)也是顯然的，由于目標(biāo)函數(shù)是非凸的，而FCM算法是迭代爬山算法，很容易陷入局部最優(yōu)點(diǎn)或者鞍點(diǎn)，而不能收斂到全局的最優(yōu)解.此外，算法耗時大，需要先驗(yàn)知識來確定待聚類的類別數(shù)目和類型.FCM算法存在的這些問題使模糊聚類問題變得更加復(fù)雜.蟻群算法［2］(Ant Colony Algorithm)是人們受蟻群群體行為的啟發(fā)提出的一種基于種群的模擬進(jìn)化算法，由意大利學(xué)者M(jìn).Dorigo等人首先提出［3］.該模型已成功應(yīng)用于求解旅行商問題、二次分配問題［4］、job-shop調(diào)度問題、NP-完全的組合最優(yōu)化問題等.為了克服蟻群算法收斂慢、容易出現(xiàn)停滯現(xiàn)象、算法的運(yùn)算時間長等缺點(diǎn)，人們提出了大量改進(jìn)算法.近年來，蟻群算法應(yīng)用于模糊聚類分析的算法的研究還不夠深入，蟻群聚類算法由Deneubour提出，Lumer等改進(jìn)了此算法并提出了LF算法，將數(shù)據(jù)隨機(jī)均勻散布在二維表格中，每只螞蟻隨機(jī)選擇一個數(shù)據(jù)，根據(jù)該數(shù)據(jù)在局部鄰域的相似性得到的概率，決定螞蟻對它是否拾起、移動或放下.表格內(nèi)的數(shù)據(jù)經(jīng)過有限次的迭代，按其相似性而聚集，最后得到聚類結(jié)果和聚類數(shù)目.算法的不足是運(yùn)行效率低，當(dāng)數(shù)據(jù)集的規(guī)模增加時，其效率將不斷下降.另外一類研究是將蟻群算法應(yīng)用于FCM的算法［5］，其思想是由將初始聚點(diǎn)為食物源，其余數(shù)據(jù)樣本為螞蟻，數(shù)據(jù)聚類過程即為螞蟻尋找最近食物源的過程，再結(jié)合FCM算法不斷的修改聚類中心，達(dá)到預(yù)定閾值算法停止.此算法的缺點(diǎn)是需要初始化聚類原型，降低了并行搜索能力.

通過把自適應(yīng)蟻群算法引入到模糊聚類問題上，筆者提出了一種新的模糊聚類算法——AACA－FC算法(Adaptive Ant Colony Algorithm－Fuzzy Clustering Algorithm)基于自適應(yīng)蟻群算法的模糊聚類算法.此算法在對目標(biāo)函數(shù)的優(yōu)化上，利用蟻群算法的并行計(jì)算、正反饋的優(yōu)點(diǎn)，保證了算法能跳出局部最優(yōu)解而收斂到全局最優(yōu)解;設(shè)計(jì)改進(jìn)的蟻群算法——自適應(yīng)的蟻群算法用于模糊聚類有助于改善蟻群算法初期收斂速度慢和易停滯的缺點(diǎn).通過仿真實(shí)驗(yàn)和對比實(shí)驗(yàn)證明，AACA－FC算法不僅可有效地解決FCM算法存在的問題，而且達(dá)到了聚類準(zhǔn)確度高、類內(nèi)緊密度高和類間分離度大的目標(biāo).

1 基本算法描述

1.1 蟻群算法

螞蟻是群體生活的社會性昆蟲，社會成員之間存在有組織的分工、相互的通訊和信息的傳遞［6］.蟻群有著獨(dú)特信息系統(tǒng)，通過信息素的不同組合，觸角信號和身體動作等策動其他的個體共同協(xié)作完成任務(wù).信息素是螞蟻在從食物源到蟻穴返回過程中，在走過的路徑上分泌的一種化學(xué)物質(zhì)，這些物質(zhì)在路徑上形成了信息素軌跡.螞蟻在運(yùn)動過程中可以感知這種物質(zhì)的存在和強(qiáng)度，以此指導(dǎo)自己的運(yùn)動方向，并且使螞蟻趨向于朝著信息素強(qiáng)度高的方向移動.由于信息素的存在，螞蟻能在沒有可見提示下，找到從蟻穴到食物源的最短路徑，而且能夠隨著環(huán)境的變化而變化的搜索出新的路徑，產(chǎn)生新的選擇.在蟻群算法中，人工螞蟻被賦予了以下的特性:

1)螞蟻在運(yùn)動過程中或者完成一次循環(huán)后，在路徑上釋放信息素.

2)螞蟻以一定的概率選擇下一個將要訪問的結(jié)點(diǎn)，這個概率是兩個結(jié)點(diǎn)間存在的信息素軌跡量的函數(shù).

3)在完成一次循環(huán)以前，螞蟻經(jīng)過的結(jié)點(diǎn)不可重復(fù).

1.2 FCM 算法

問題描述:對于待聚類的M個數(shù)據(jù)，每個數(shù)據(jù)N維屬性，類別個數(shù)為c，求出第i類的聚類原型矢量 pi=(pi1，pi2，…，piN)和隸屬度矩陣 U=［μik］c×N其中i=1，2，…，c，k為第k個樣本數(shù)據(jù).目標(biāo)函數(shù)為

式中dik為第k個樣本與聚類原型pi的歐式距離.FCM算法中，對于給定的類別數(shù)c，設(shè)定迭代停止閾值ε，初始化聚類中心模式P(0)，設(shè)置迭代計(jì)算器b=0，

步驟1 計(jì)算或者更新隸屬矩陣U(b)

步驟2 更新聚類中心矩陣p(b+1):

2 AACA－FC算法

2.1 算法設(shè)計(jì)思想

2.1.1 優(yōu)化函數(shù)

在AACA算法當(dāng)中，優(yōu)化函數(shù)為一元函數(shù)，而基于目標(biāo)函數(shù)的模糊聚類算法中的目標(biāo)函數(shù)卻是一個關(guān)于U和P的二元函數(shù)，文獻(xiàn)［1］對多維有約束函數(shù)優(yōu)化進(jìn)行了研究，但是利用蟻群算法直接對多維函數(shù)進(jìn)行優(yōu)化比較復(fù)雜，因此把二元目標(biāo)函數(shù)轉(zhuǎn)換為一元目標(biāo)函數(shù)，可以簡化研究.通過對模糊C均值聚類算法(FCM)的研究，其目標(biāo)函數(shù)

式中:μik∈［0，1］，Ai，k;dik表示第 k個樣本與聚類原型pi的歐式距離，m∈［1，+∞)為加權(quán)指數(shù)，又稱為平滑參數(shù).M為待聚類的數(shù)據(jù)個數(shù).利用拉格朗日乘數(shù)法，根據(jù)約束條件

得出

代入公式(3)，從而使得目標(biāo)函數(shù)F轉(zhuǎn)化為關(guān)于pi的一元函數(shù)，即

進(jìn)而可將式(2)作為蟻群算法當(dāng)中的目標(biāo)函數(shù)進(jìn)行優(yōu)化.從而使得目標(biāo)函數(shù)F轉(zhuǎn)化為關(guān)于pi的一元函數(shù).

2.1.2 自適應(yīng)全局信息素?fù)]發(fā)系數(shù)

當(dāng)問題規(guī)模比較大時，由于信息量的揮發(fā)系數(shù)ρ的存在，使那些從未被搜索到的信息量會減小到接近于0，降低了算法的全局搜索能力.而且ρ過大時，當(dāng)解的信息量增大時，以前搜索過的解被選擇的可能性過大，也會影響到算法的全局搜索能力.通過減小ρ雖然可以提高算法的全局搜索能力，但又會使得算法的收斂速度降低;因此可以自適應(yīng)地改變ρ的值.ρ的初始值為1，當(dāng)算法求得最優(yōu)解在N次循環(huán)內(nèi)沒有明顯改進(jìn)時，ρ減為

式中ρmin為ρ的最小值，可以防止ρ過小降低算法的收斂速度.

2.2 算法步驟

步驟1 為了便于在高維數(shù)據(jù)空間使用蟻群算法，采用降維方法進(jìn)行處理.由于聚類原型pi=(pi1，pi2，…，piN)∈RN且 i=1，2，…，c ，因此上述 F表達(dá)式的c個N維變量可轉(zhuǎn)化為cN個一維變量以此實(shí)現(xiàn)降維處理.問題就轉(zhuǎn)化為求minF(p11，p12，…，p1N，p21，p22，…，p2N，…，pc1，pc2，…，pcN)時的 pi.便與描述算法步驟，將上式表示為求minF(p1，p2，p3，…，pcN);

步驟2 估計(jì)各個變量的取值范圍，將各個變量K等分;

步驟3 給信息素矩陣τij(1≤i≤cN，1≤j≤K)各個元素賦值常數(shù)c，即τ0=c，表示所有變量的所有區(qū)間有相同的信息素量.將m只螞蟻隨機(jī)分配到初始變量p1的K個子區(qū)間內(nèi);

步驟5 設(shè)t=0;

步驟6 每只螞蟻根據(jù)參數(shù)q0獨(dú)立選擇路徑，到達(dá)下一個變量pi對應(yīng)的某個區(qū)間j.m只螞蟻并行工作.

式中q∈(0，1)為隨機(jī)數(shù).J為轉(zhuǎn)移概率，可根據(jù)下式計(jì)算

步驟7 按下式局部更新每只螞蟻到達(dá)的區(qū)間的信息素量τij，且取每只螞蟻到達(dá)第i個變量對應(yīng)的第j個區(qū)間的中間值為pi的當(dāng)前解.

步驟8 當(dāng)m只螞蟻獨(dú)立并行的選擇完變量xi對應(yīng)的區(qū)間后，返回步驟6，選擇下一個變量對應(yīng)的區(qū)間，直到m只螞蟻都重新回到第一個變量p1所對應(yīng)的區(qū)間并局部更新后，一次周游完畢.

步驟9 對于每只螞蟻在每個區(qū)間取得的解，計(jì)算函數(shù)F的值，找到最小值對應(yīng)的最優(yōu)解即為本代的最優(yōu)解和最佳路徑.

步驟10 如果＜，則對于第 S 代的最優(yōu)解按照下式進(jìn)行全局更新.

步驟11 t=t+1，若t＜tmax返回步驟6，否則要找出信息素矩陣τij每行(對應(yīng)于每個變量)的最大元素(信息素量最大)的列號li(對應(yīng)于所分區(qū)間的編號)，利用下式縮小變量的取值范圍:

其中Δ為一個正數(shù)，用于控制縮小范圍的速度.t←0，轉(zhuǎn)向步驟2.

步驟12 將最優(yōu)解對應(yīng)的解進(jìn)行解碼操作，轉(zhuǎn)化為c×N的矩陣，即為最優(yōu)聚類原型矩陣.進(jìn)而可以得到隸屬度矩陣.

3 AACA－FC算法仿真

實(shí)驗(yàn)選擇一組標(biāo)準(zhǔn)數(shù)據(jù)集IRIS數(shù)據(jù)作為測試樣本集，以比較算法的收斂速度和優(yōu)化程度.IRIS數(shù)據(jù)由四維空間中的150個樣本點(diǎn)組成，每一個樣本具有4個分量，每個類各有50個樣本.其中Setosa與其他2類間完全分類，Versicolor和Virginica之間有交叉.實(shí)驗(yàn)中采用的參數(shù)設(shè)置如下:m=50，qmin=0.5，ξ=0.55，ρmin=0.1，Q=100，ε =0.001，τmax=10，τmin=0.01，q0=0.01，α =1，Δ =5，

AACA－FC算法中目標(biāo)函數(shù)min(F)隨迭代次數(shù)的優(yōu)化過程曲線如圖1所示，由數(shù)據(jù)集的二維屬性Sepal Length和Sepal Width繪制聚類效果圖.

圖1 目標(biāo)函數(shù)min(F)隨迭代次數(shù)的優(yōu)化過程曲線

從圖1可以看出，AACA－FC算法經(jīng)過30代迭代收斂于全局最優(yōu)解，可見自適應(yīng)蟻群算法解決模糊聚類問題是有效的;通過計(jì)算，ACCA－FC算法的誤分?jǐn)?shù)為7，誤分率為4.67%，與FCM算法10.67%的誤分率相比，降低了6個百分點(diǎn)，進(jìn)一步印證了ACCA－FC算法聚類準(zhǔn)確率高的優(yōu)點(diǎn).FCM算法和ACCA－FC算法具體實(shí)驗(yàn)結(jié)果對比見表1.

表1 FCM算法和ACCA-FC算法實(shí)驗(yàn)結(jié)果對比

4 結(jié)語

提出了一種基于自適應(yīng)蟻群優(yōu)化算法和FCM算法相結(jié)合的新算法.一方面，把 FCM算法中的目標(biāo)函數(shù)通過降維操作，將其轉(zhuǎn)化為蟻群算法中的優(yōu)化函數(shù)進(jìn)行優(yōu)化;另一方面，改進(jìn)了蟻群算法，引入自適應(yīng)全局信息素?fù)]發(fā)系數(shù)，動態(tài)調(diào)節(jié)螞蟻的路徑選擇和信息量的更新，不僅提高了螞蟻的全局搜索能力，而且提高了收斂速度.仿真實(shí)驗(yàn)證明，新算法不僅可以有效地彌補(bǔ)FCM算法容易陷入局部極值點(diǎn)或者鞍點(diǎn)而得不到最優(yōu)解甚至滿意解的缺點(diǎn)，而且比FCM算法具有更好的收斂效果和更高的聚類準(zhǔn)確率.該方法把模糊聚類問題轉(zhuǎn)化為函數(shù)優(yōu)化問題，為模糊聚類分析問題提供了新的解決思路.但由于蟻群算法參數(shù)的設(shè)置理論尚不完善，且實(shí)驗(yàn)的效果一定程度受限于參數(shù)的設(shè)置，下一步需對此進(jìn)行深入探究，使算法的結(jié)果更有效.

［1］高新波.模糊聚類分析及其應(yīng)用［M］.西安:西安電子科技大學(xué)出版社，2004.

［2］李士勇.蟻群算法及其應(yīng)用［M］.哈爾濱:哈爾濱工業(yè)大學(xué)出版社，2004.

［3］ Dorigo M，Maniezzo V，Colorni A.Ant system:optimization by a colony of cooperating agents［J］.IEEE Transactions on SMC，1996，26(1):29 －41.

［4］ Gambardella L M，Taillard E D，Dorigo M.Ant colonies for the QAP［J］.Journal of the Operational Research Society.1999，50(2):167 －176.

［5］徐曉華，陳岐.一種自適應(yīng)的螞蟻聚類算法［J］.軟件學(xué)報(bào)，2006，17(9):1884 －1889.