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

姚雅 高尚

（江蘇科技大學計算機科學與工程學院 鎮江 212000）

1 引言

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

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

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

2.1 基本人工蜂群算法

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

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

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

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

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

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

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

4）偵察蜂行為階段。當某蜜源的收益率連續limit次仍沒有被更新時，則表明該蜜源已經陷入局部最優，此時應當放棄該蜜源，與此同時，引領蜂轉換變為偵察蜂，并根據式（1）產生一個隨機的新蜜源。

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

1）算法原理

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

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

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

因此，引領蜂在進行鄰域搜索時蜜源的更新公式變為式（7）。

2）具體實現步驟

UMDAc-ABC算法的具體實現步驟如下所示。

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

（2）執行如下的循環:

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

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

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

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

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

⑤重復步驟③；

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

⑦記錄當前的最優蜜源，檢查是否滿足終止條件，如果滿足則輸出最優蜜源（解）；否則則繼續進行循環。

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

3.1 模糊C-均值聚類算法

模糊C-均值聚類算法是一種基于最小二乘法原理的迭代優化算法，現如今已經成為被廣泛應用的模糊聚類算法。

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

輸入:聚類數目c和數據集。

2）根據式（9）計算隸屬度Uk；

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

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

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

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

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

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

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

2）根據UMDAc-ABC算法的實現步驟計算出聚類中心；

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

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

4 實驗仿真

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

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

表1 兩種算法對測試函數Sphere進行仿真的測試結果

圖1 兩種算法對測試函數Sphere的結果對比

表2 兩種算法對測試函數Ackley進行仿真的測試結果

圖2 兩種算法對測試函數Ackley的結果對比

由以上實驗結果可以看出，基于連續分布估計的人工蜂群算法在精度和收斂速度方面都比標準的ABC有著顯著的增強。

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

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

表3 Wine數據的聚類結果

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

5 結語

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