基于混合人工蜂群的模糊聚類算法?

姚雅 高尚

（江蘇科技大學(xué)計算機科學(xué)與工程學(xué)院 鎮(zhèn)江 212000）

1 引言

由于聚類（clustering）可以作為獲取數(shù)據(jù)的分布狀況的工具，并在此基礎(chǔ)上進一步地分析，聚類（clustering）分析已經(jīng)成為數(shù)據(jù)挖掘的主要任務(wù)。聚類就是把不同數(shù)據(jù)對象集合劃分成不同組群的過程，即把數(shù)據(jù)對象分成多個類或簇，同一聚類中的數(shù)據(jù)相似度高而不同聚類中的數(shù)據(jù)相似性低［1］。聚類算法已經(jīng)廣泛應(yīng)用在諸如市場分析、Web文檔、信息安全、金融等很多方面。然而，在現(xiàn)實生活中，有些問題擁有嚴(yán)格的劃分界限，有些問題并沒有嚴(yán)格的界限劃分，具有模糊性。因此，針對這類聚類問題，人們提出了用模糊的方法進行處理。由Dunn［2］和 Bezdek［3］提出的模糊 C-均值聚類算法（FCM），就是一種被普遍應(yīng)用的基于目標(biāo)函數(shù)的模糊聚類算法。該算法簡單、快速，具有比較直觀的幾何意義，但同時也存在著對初始值條件與噪聲數(shù)據(jù)敏感，容易使目標(biāo)函數(shù)陷入局部最優(yōu)的缺點。

近年來，為了取得更為理想的聚類效果，已經(jīng)產(chǎn)生許多對FCM算法的改進算法，如文獻［4］將點對約束與FCM算法結(jié)合，文獻［5］將屬性權(quán)重區(qū)間監(jiān)督運用到FCM算法中，文獻［6］提出一種新的選取聚類中心的方法對FCM算法進行了改進。現(xiàn)如今又掀起了一股新的將智能優(yōu)化算法與聚類算法相結(jié)合的研究潮流，將粒子群算法（particle swarm optimization，PSO）［7］、蟻群算法（ ant-colony algorithm）［8］和遺傳算法（genetic algorithm，GA）［9］等與聚類算法結(jié)合的文獻中聚類結(jié)果的穩(wěn)定性和準(zhǔn)確性已經(jīng)得到了較大的提高。人工蜂群（artificial bee colony，ABC）算法是 2005 年由 Karaboga［10］建立的一種新型的模仿蜂群采蜜行為的群智能優(yōu)化算法，并引起了廣泛的關(guān)注，如今在群智能領(lǐng)域已經(jīng)掀起了新的研究熱潮。文獻［6］中將其與粒子群優(yōu)化算法、遺傳算法和差分進化算法（differential evolution，DE）這三種算法進行對比，通過ABC算法得到的結(jié)果相對較好。因此，本文將其與FCM算法相結(jié)合，得到的新的聚類算法能夠有效地提高聚類結(jié)果的穩(wěn)定性和準(zhǔn)確性。然而，ABC算法也存在局部搜索能力較差、易于過早陷入局部最優(yōu)點等缺點。分布估計算法（Eestimation of Distribution Algorithm，EDA）［11］是一種基于概率模型的具有良好全局探索能力的新型進化算法。UMDAc是一種變量無關(guān)的分布估計算法的典型代表，它是UMDA算法的擴展，并且它描述連續(xù)解空間的概率模型時是采用了高斯分布。文獻［12］對2011年關(guān)于分布算法做了總結(jié)，文獻［13］對連續(xù)域多變量耦合問題進行了分析，還有許多學(xué)者也在分布估計算法方面做出了出色的成果。本文將人工蜂群算法與UMDAc算法相結(jié)合，提出了不同的蜜源生成策略，得到一種基于分布估計的人工蜂群算法。然后將改進后的混合人工蜂群算法與FCM算法結(jié)合，使得聚類效果得到顯著提高。

2 人工蜂群算法及其改進研究

2.1 基本人工蜂群算法

在人工蜂群（ABC）算法［14］中，主要由蜜源、被雇傭的蜜蜂和未被雇傭的蜜蜂三個基本部分組成。其中，蜜源是指可采得花蜜的地點，在算法中其價值由適應(yīng)度值來表示；被雇傭的蜜蜂是指已經(jīng)發(fā)現(xiàn)蜜源的蜜蜂，也稱其為引領(lǐng)蜂；未被雇傭的蜜蜂是指未找到蜜源的蜜蜂，主要負(fù)責(zé)尋找和開采蜜源，根據(jù)分工的不同分為兩種:偵察蜂和跟隨蜂。該模型定義了蜜蜂擁有三種最基本的行為模式:當(dāng)引領(lǐng)蜂找到豐富蜜源時，就會招募其他的蜜蜂跟隨到此處進行采蜜；當(dāng)蜜源的花蜜變得較少時，則放棄該蜜源，與該蜜源相關(guān)的引領(lǐng)蜂也隨即變成了偵察蜂；偵察蜂隨機尋找一個新蜜源并進行開采，隨即就變成引領(lǐng)蜂執(zhí)行任務(wù)。ABC算法的實現(xiàn)過程如下:

1）初始化階段。初始化循環(huán)的最大次數(shù)MCN，蜜源被廢棄的條件參數(shù)limit，隨機生成SN個初始解（SN 即為跟隨蜂的個數(shù)或引領(lǐng)蜂的個數(shù)），其中是一個 d 維的向量，并依照式（1）對其進行初始化蜜源i的位置。

每個蜜源的位置相當(dāng)于一個優(yōu)化問題的可行解，其“收益率”對應(yīng)于可行解的適應(yīng)度值 fit(xi)，可依據(jù)式（2）進行計算:

式中:f(xi)是人工蜂群算法的目標(biāo)函數(shù)值。

2）引領(lǐng)蜂行為階段。在此階段，引領(lǐng)蜂利用“貪婪選擇”法則，將舊蜜源和通過鄰域搜索獲得的新蜜源的適應(yīng)度值進行比較，當(dāng)新蜜源優(yōu)于舊蜜源時，則用其替換掉舊蜜源，否則仍然保持不變。在進行鄰域搜索時，根據(jù)下式由舊蜜源xi產(chǎn)生新蜜源vi。

3）跟隨蜂行為階段。當(dāng)引領(lǐng)蜂完成任務(wù)返回蜂巢時，它們會通過跳搖擺舞將把蜜源信息傳遞給跟隨蜂。跟隨蜂根據(jù)獲得的蜜源信息通過輪盤賭方式選擇自己將要開采的蜜源。收益率越高的蜜源吸引到的跟隨蜂就越多。在ABC算法中，跟隨蜂依據(jù)概率值決定蜜源，因此蜜源xi被跟隨蜂選擇的概率為

當(dāng)跟隨蜂選擇好一個蜜源進行開采時，它也依據(jù)式（3）進行鄰域搜索，并同樣采用貪婪原則進行選擇。

4）偵察蜂行為階段。當(dāng)某蜜源的收益率連續(xù)limit次仍沒有被更新時，則表明該蜜源已經(jīng)陷入局部最優(yōu)，此時應(yīng)當(dāng)放棄該蜜源，與此同時，引領(lǐng)蜂轉(zhuǎn)換變?yōu)閭刹旆洌⒏鶕?jù)式（1）產(chǎn)生一個隨機的新蜜源。

2.2 基于連續(xù)分布估計的人工蜂群算法

1）算法原理

分布估計算法是一種基于概率模型的新型的進化算法，它是將遺傳算法和統(tǒng)計學(xué)習(xí)相結(jié)合，依照當(dāng)前種群的概率模型來引導(dǎo)產(chǎn)生下一代種群，該算法是對生物進化“宏觀”層面上的建模，具有良好的全局探索能力。

分布估計算法在編碼方式上可以分成兩種:離散型編碼和連續(xù)型編碼，孫增圻和周樹德的論文《分布估計算法綜述》［15］對離散型編碼的分布估計算法進行了詳細(xì)的闡述。PBILc和UMDAc分別是由PBIL和UMDA算法擴展而得的變量無關(guān)的連續(xù)分布估計算法的典型代表。而現(xiàn)在對人工蜂群（ABC）算法的研究主要是針對連續(xù)人工蜂群算法［16～17］的，因此為了提高人工蜂群算法的全局探索能力，本文將人工蜂群算法與連續(xù)分布估計算法UMDAc相結(jié)合，提出一種基于連續(xù)分布估計的人工蜂群（Univariate Marginal Distribution Continuation-artificial Bee Colony，UMDAc-ABC）算法，主要是通過改進人工蜂群（ABC）算法的新蜜源生成公式，利用優(yōu)質(zhì)蜜源的概率分布來引導(dǎo)產(chǎn)生新蜜源，使得算法在收斂速度、魯棒性等方面得到明顯的改善。而關(guān)于二進制人工分群算法的研究，可以參考文獻［18］提出了一種易于實現(xiàn)的差分演化二進制人工蜂群算法，文獻［19］提出了一種基于分布估計的二進制人工蜂群算法。

其中，UMDAc的過程是:每一代都由概率向量P(x)隨機產(chǎn)生M個個體，計算出這些個體的適應(yīng)度值，然后從中選出N個最優(yōu)個體，并用這N個個體更新概率向量P(x)(N ≤M ) 。其中，用Pq(x)表示第q代概率向量，即表示選擇出的最優(yōu)的N個個體，其中服從高斯分布，估計如下:

因此，引領(lǐng)蜂在進行鄰域搜索時蜜源的更新公式變?yōu)槭剑?）。

2）具體實現(xiàn)步驟

UMDAc-ABC算法的具體實現(xiàn)步驟如下所示。

（1）初始化。對SN、MCN和limit三個變量進行初始化，利用式（1）初始化蜜源其滿足在解空間中依據(jù)均勻分布隨機生成，同時根據(jù)式（2）計算每個蜜源對應(yīng)的適應(yīng)度值。

（2）執(zhí)行如下的循環(huán):

①選擇適應(yīng)度值比較高的SN 2個個體，計算出它們的均值和方差:和

diag( )σ1，σ2，…σd；

②引領(lǐng)蜂階段，由上面計算出的均值和方差可以得到一個多元正態(tài)分布利用上面改進的鄰域搜索方式，即根據(jù)式（7）產(chǎn)生一個新蜜源vi，并采用貪婪原則判斷是否需要替換舊蜜源xi；

③類似步驟①，重新選擇SN 2個優(yōu)質(zhì)蜜源，計算出他們的均值和方差；

④跟隨蜂階段，即跟隨蜂根據(jù)（1）中獲得的蜜源的適應(yīng)度值，利用式（4）計算每個蜜源被選中的概率，通過輪盤賭方式選擇自己將要開采的蜜源；根據(jù)改進的鄰域搜索方式再次產(chǎn)生新的蜜源，并利用貪婪原則在新蜜源與原來引領(lǐng)蜂對應(yīng)的舊蜜源之間進行判斷是否需要替換；

⑤重復(fù)步驟③；

⑥偵察蜂階段，即判斷是否有蜜源已經(jīng)陷入局部最優(yōu)，如果有則放棄該蜜源，同時與之對應(yīng)的引領(lǐng)蜂轉(zhuǎn)換為偵察蜂，并利用式（1）開始探尋下一個新蜜源并進行采蜜，進而又由偵察蜂轉(zhuǎn)換成引領(lǐng)蜂；

⑦記錄當(dāng)前的最優(yōu)蜜源，檢查是否滿足終止條件，如果滿足則輸出最優(yōu)蜜源（解）；否則則繼續(xù)進行循環(huán)。

3 基于混合人工蜂群的模糊C-均值聚類算法

3.1 模糊C-均值聚類算法

模糊C-均值聚類算法是一種基于最小二乘法原理的迭代優(yōu)化算法，現(xiàn)如今已經(jīng)成為被廣泛應(yīng)用的模糊聚類算法。

FCM聚類算法的基本步驟如下:

輸入:聚類數(shù)目c和數(shù)據(jù)集。

2）根據(jù)式（9）計算隸屬度Uk；

3）根據(jù)式（10）計算下一迭代的聚類中心Vk+1；

模糊C-均值聚類算法具有簡單易實現(xiàn)、收斂速度快、局部搜索能力較強的優(yōu)點。但是該算法對初始聚類中心的選擇具有很大的依賴性，同時噪聲數(shù)據(jù)也會對聚類結(jié)果的準(zhǔn)確性造成很大的影響，這些也是其不可被忽略的缺點。下面將針對其缺點對其進行改進。

3.2 基于混合人工蜂群的模糊C-均值聚類算法

如上面的研究，我們可以知道模糊C-均值聚類算法具有對初始聚類中心的選擇依賴的缺點。為了克服這一缺點，提出了基于混合人工蜂群的模糊C-均值聚類算法，其主要是通過混合人工蜂群算法來確定初始聚類中心，再利用FCM聚類算法對初始聚類中心進行優(yōu)化，最后獲得較為理想的最優(yōu)解。

在基于連續(xù)分布估計的人工蜂群算法中，一個蜜蜂的位置向量代表一個聚類中心集合。此時可以定義蜜蜂的適應(yīng)度函數(shù)如下:

該算法的具體步驟描述如下:

1）設(shè)置初始參數(shù):類別數(shù)c和模糊指數(shù)m，對終止誤差ε、跟隨蜂的個數(shù)（SN）、最大循環(huán)次數(shù)MCN、Limit這幾個參數(shù)進行初始化，并設(shè)置當(dāng)前的迭 代 次 數(shù) 為 cycle=0；利 用 式（1）初 始 蜜 源，其滿足在解空間中依據(jù)均勻分布隨機生成，同時根據(jù)式（11）計算每個蜜源對應(yīng)的適應(yīng)度值，利用式（9）和式（10）分別計算出隸屬度矩陣U0和初始聚類中心；

2）根據(jù)UMDAc-ABC算法的實現(xiàn)步驟計算出聚類中心；

3）根據(jù)式（9）更新隸屬度矩陣U ；

4）利 用 式（10）更 新 聚 類 中 心 ，并 計 算，當(dāng)E＜ε時，則停止算法；否則轉(zhuǎn)到步驟3）。

4 實驗仿真

4.1 基于連續(xù)分布估計的人工蜂群算法與人工蜂群算法的對比

為了驗證算法性能，將人工蜂群（ABC）算法與基于連續(xù)分布估計的人工蜂群（UMDAc-ABC）算法分別對測試函數(shù)Sphere和Ackley的仿真結(jié)果［20］進行比較。設(shè)置測試算法的參數(shù)分別如下:SN=100，MCN=100，limit=50。在相同的實驗環(huán)境下，進行獨立實驗50次，并記錄這50次實驗的最好值、最差值和平均值，分別用best、worst和mean表示。其中，最好值和最差值反映出解的質(zhì)量，平均值反映了該算法的收斂速度。兩種算法對測試函數(shù)Sphere進行仿真的測試結(jié)果如表1所示，它們的結(jié)果對比圖如圖1所示；兩種算法對測試函數(shù)Ackley進行仿真的測試結(jié)果如表2所示，它們的結(jié)果對比圖如圖2所示。

表1 兩種算法對測試函數(shù)Sphere進行仿真的測試結(jié)果

圖1 兩種算法對測試函數(shù)Sphere的結(jié)果對比

表2 兩種算法對測試函數(shù)Ackley進行仿真的測試結(jié)果

圖2 兩種算法對測試函數(shù)Ackley的結(jié)果對比

由以上實驗結(jié)果可以看出，基于連續(xù)分布估計的人工蜂群算法在精度和收斂速度方面都比標(biāo)準(zhǔn)的ABC有著顯著的增強。

4.2 基于混合人工蜂群的模糊C-均值聚類算法的仿真與分析

為了驗證基于混合人工蜂群的模糊C-均值聚類（UMDAc-ABCFCM）算法的有效性和可行性，這里采用了UCI機器學(xué)習(xí)數(shù)據(jù)庫中的Wine數(shù)據(jù)集對該算法進行測試。Wine數(shù)據(jù)集是產(chǎn)于意大利同一地區(qū)不同種植園的3種葡萄酒化學(xué)分析結(jié)果的樣本，它有13個參數(shù)作為特征，分為3類，每類分別有60，70，50個，共180個樣本，數(shù)據(jù)為180×13維矩陣。分別用兩種算法對Wine數(shù)據(jù)進行聚類分析，設(shè)置算法中允許最小誤差ε=10-3，模糊加權(quán)指數(shù)m=2。蜂群規(guī)模SN=100，最大循環(huán)次數(shù)MCN=100，Limit=50。將兩種算法分別運行50次，實驗結(jié)果如表3所示。

表3 Wine數(shù)據(jù)的聚類結(jié)果

從表3的實驗結(jié)果可以看出，UMDAc-ABCFCM算法比傳統(tǒng)的FCM算法聚類效果更好，不僅準(zhǔn)確率得到了提高，而且迭代次數(shù)更少，收斂速度也加快了。

5 結(jié)語

本文將連續(xù)分布估計算法引入人工蜂群算法中，利用分布估計獲得的全局信息改進了新的蜜源生成策略，從而提高了算法的全局探索能力，加快了收斂速度。并將此改進的ABC算法應(yīng)用到FCM聚類算法中，既克服了FCM算法易陷入局部最優(yōu)解的不足，又彌補了FCM算法對初始值和噪聲點比較敏感的缺陷，加快了收斂速度，聚類效果得到了明顯的改善。