基于改進人工蜂群的核模糊聚類算法

梁 冰，徐 華

(江南大學 物聯網工程學院，江蘇 無錫 214122)(*通信作者電子郵箱joanxh2003@163.com)

基于改進人工蜂群的核模糊聚類算法

梁 冰，徐 華*

(江南大學 物聯網工程學院，江蘇 無錫 214122)(*通信作者電子郵箱joanxh2003@163.com)

針對核模糊C均值(KFCM)算法對初始聚類中心敏感、易陷入局部最優的問題，利用人工蜂群(ABC)算法的構架簡單、全局收斂速度快的優勢，提出了一種改進的人工蜂群算法(IABC)與KFCM迭代相結合的聚類算法。首先，以IABC求得最優解作為KFCM算法的初始聚類中心，IABC在迭代過程中將與當前維度最優解的差值的變化率作為權值，對雇傭蜂的搜索行為進行改進，平衡人工蜂群算法的全局搜索與局部開采能力;其次，以類內距離和類間距離為基礎，構造出適應KFCM算法的適應度函數,利用KFCM算法優化聚類中心;最后，IABC和KFCM算法交替執行，實現最佳聚類效果。采用3組Benchmark測試函數6組UCI標準數據集進行仿真實驗，實驗結果表明，與基于改進人工蜂群的廣義模糊聚類(IABC-KGFCM)相比，IABC-KFCM對數據集的聚類有效性指標提高1到4個百分點，具有魯棒性強和聚類精度高的優勢。

核模糊C均值聚類;人工蜂群算法;搜索策略;函數優化;適應度函數

聚類分析作為數學挖掘領域的重要研究方向之一，通過獲得樣本數據的分布狀況，分析每一類樣本數據的特征并作進一步的分類。著名學者Ruspini[1]在1969年首先提出了模糊劃分的概念，將模糊集理論引入到聚類分析中。 在模糊聚類分析方法中，應用最廣泛的是由Dunn[2]提出并由Bezdek[3]推廣的模糊C均值(Fuzzy C-Means, FCM)，依據樣本間的相似度而得到數據的劃分。研究學者在FCM的基礎上引入核函數，將非線性不可分數據變換到到高維空間中的可分數據集,提出了一種基于劃分的核模糊C均值聚類(Kernel-based Fuzzy C-Means, KFCM)算法。通過最小化目標函數得到各樣本點與其各聚類中心的隸屬度,一定程度上克服了對樣本數據內在形狀分布的依賴，解決了FCM不能發現非凸聚類結構問題。由于思路簡單、收斂速度等優點，KFCM目前在模式識別、圖像處理[4-5]、醫學診斷[6]、生物信息學[7]、人口統計[8]等相關領域廣泛應用。但該算法仍然存在對初始聚類中心敏感、聚類精度較低、在迭代時易陷入局部最優等問題，吸引了大量專家學者的探索與改進。文獻[9]通過最小化簇內的分散和同時最大化屬性權重的熵來改進目標函數，提高聚類的準確性。文獻[10]利用改進的自適應遺傳算法優化模糊核聚類算法，避免傳統核模糊聚類容易陷入局部最優問題。文獻[11]提出了增量核模糊聚類，通過優化初始聚類中心，為每個數據塊提高聚類結果的質量。

群體智能在全局優化領域中占有優勢地位，Karaboga通過仿效蜜蜂覓食行為來解決數值優化問題，提出了人工蜂群(Artificial Bee Colony, ABC)算法。人工蜂群算法具有易于實現、構架簡單，以及魯棒性強等優點，備受眾多學者的關注，在標準ABC算法上作出了延伸與改進。文獻[12]引入了兩個新的搜索方程，在雇傭蜂和跟隨蜂階段中產生候選解，在每一次迭代過程中被分配更多的資源，提高算法的收斂速度和開采能力。文獻[13]融合差分進化(Differential Evolution, DE)算法與人工蜂群算法，利用差分進化算法的魯棒性強和進化速度快的特點，提高算法的收斂性以及改進其開采能力。文獻[14]在偵查蜂更新階段引入廣義反向學習策略，從而提高算法的全局收斂性。

鑒于此，將人工蜂群優化算法引入到核模糊聚類中，達到快速收斂、優化聚類精度的目的。本文提出一種基于改進人工蜂群的核模糊聚類的算法。該算法在人工蜂群算法的雇傭蜂階段，利用每次迭代所產生的當前維度最優解，根據離最優解的距離動態來改變人工蜂群的搜索距離，并構造新的適應度函數平衡類內和類間距離。通過3組Benchmark測試函數和6組經典UCI(University of California-Irvine)的實驗數據集的仿真實驗，驗證了提出的改進人工蜂群算法在函數優化問題上的優勢，同時解決了核模糊聚類對于初始中心敏感和容易陷入局部最優的問題，提高聚類精度和魯棒性。

1 基本算法

1.1 核模糊C均值算法

核模糊C均值算法通過最小化目標函數將含有n個樣本點的向量xj(j=1,2,…,n)劃分到c個類別中。vi(i=1,2,…,c)表示第i個聚類的中心，uij(i=1,2,…,c;j=1,2,…,n)表示第j個樣本屬于第i類的隸屬度。

KFCM步驟:

1)設置聚類數目c，模糊度m的值，目標函數允許最小誤差ε，最大迭代次數T。

2)初始化c個聚類中心，在n個樣本點中隨機選取c個數據進行聚類中心初始化。

3)直至目標函數|J(t)-J(t-1)|<ε結束聚類。

①聚類目標函數：

(1)

原始輸入數據通過非線性映射函數φ(x)映射到高維特征空間中再進行聚類，核函數采用高斯函數。

‖φ(xj)-φ(vj)‖2=K(xj,xj)-2K(xj,vj)+K(vj,vj)

(2)

對于高斯函數，當K(x,x)=1時，式(1)可表示為：

(3)

②聚類中心

(4)

③隸屬度

(5)

1.2 人工蜂群算法

在人工蜂群算法中，首先引入蜜源，代表優化問題的各種可行解，用可行解的質量即適應度函數值來衡量蜜源。再引入三種不同類型的蜂：雇傭蜂、跟隨蜂、偵查蜂。雇傭蜂負責尋找蜜源并記憶蜜源的花蜜量，通過“搖擺舞”與跟隨蜂共享蜜源信息。跟隨蜂根據傳回的信息以一定的概率選擇蜜源。雇傭蜂找到的蜜源質量未有改善時，放棄現有的蜜源，會轉變成偵查蜂繼續尋找新的食物來源。通過3種蜂群之間相互協作，從而找到優化問題的全局最優解。

1.2.1 初始化階段

在ABC算法中，首先根據式(6)在搜索空間內隨機初始化生成SN個蜜源，D是待優化問題的維數。設置最大迭代次數maxcycle，蜂群終止循環次數limit。

(6)

1.2.2 雇傭蜂階段

每一個雇傭蜂都到達目標點后，根據式(7)在蜜源鄰域內進行搜索，生成一個新蜜源。

zij=xij+φij(xij-xkj)

(7)

其中，k∈{1,2,…,SN}，j∈{1,2,…,D}是隨機選擇的下標，且k不等于j，φij為[-1,1]的隨機數，它控制了鄰域的搜索范圍。在產生新的候選蜜源之后，計算其適應度，利用貪婪選擇原則，將新位置的適應度與記憶中最優解進行比較：如新蜜源的適應度大于原蜜源，則替換；否則，保持原位置不變。

1.2.3 跟隨蜂階段

跟隨蜂根據雇傭蜂分享的蜜源信息，通過適應度值衡量蜜源優劣，用適應度度值計算跟隨蜂選擇蜜源的概率。

(8)

其中:fiti表示第i個蜜源的適應度的值，對應的Pi是指第i個蜜源被選擇的概率，并基于輪盤賭原則選擇雇傭蜂，Pi越大說明相應的蜜源越好，被跟隨蜂選中的概率越大。

1.2.4 偵查蜂階段

若蜜源經過limit次迭代循環后，蜜源質量仍沒有提高，該處的雇傭蜂轉變成偵查蜂，其擁有的蜜源也會被放棄。偵查蜂按式(6)重新隨機搜索一個新蜜源。

2 基于改進的人工蜂群的核模糊聚類算法

2.1 改進局部搜索策略

在標準的ABC算法中，平衡局部搜索和全局搜索的關鍵是更新種群的步長。文獻[15]為了提高雇傭蜂的效率，通過最優值更新蜜源，提高了收斂速度，提出了新的搜索方式(9):

zij=xij+φijfb(xij-xbj)

(9)

其中：zij是新蜜源;fb是第j維最優蜜源的適應度值，xij在所選維度j中蜜源的位置i，xbj是第j維度中最優的蜜源。φij為[-1,1]的隨機數。蜂群在迭代尋優過程中只向最優解靠近，所有個體都聚集在該個體附近，并在小范圍內隨機尋找，忽略了控制人工蜂群的距離，容易陷入局部極值點且算法不穩定。搜索能力和開發能力對于群智能算法很重要。文中提出的改進人工蜂群算法，在迭代過程中動態改變與當前全局最優值差值的變化率w，通過增大減小權值φij來調節當前變化態勢。

w=(fb-fi)/fb

(10)

(11)

其中:w為第j維與最優適應度差值的變化率，fb為第j維的最優適應度的值，fi為第i個蜜源的適應度的值。當蜂群第i個蜜源的適應度fi與最優適應度fb差值較大時，說明蜂群正往新的領域擴展，增大權值φij能夠提高全局搜索能力；反之，當fi與最優適應度差值較小時，減小權值φij能夠加快收斂速度。實現對其附近解空間的搜索，增大了算法的搜索空間范圍和開發能力，保持了種群多樣性，避免算法因追求最優解產生早熟現象。動態改變權值策略契合蜂群當前變化態勢，平衡了全局搜索與局部開采能力。

2.2 構造適應度函數

原始核模糊聚類算法的目標函數如式(1)，其衡量聚類總體質量的標準是最小化最大類內距離。聚類分析的核心思想是將數據劃分到不同的類別，同一類中的樣本對象相似度最大，而不同類間的樣本對象相異度最大。而原始目標函數只考慮到同一類樣本對象之間的距離，忽略了聚類質量是由類內距離和類間距離共同評價的。基于此，本文提出一種新的目標函數作為IABC-KFCM的適應度函數，能夠有效平衡類內緊密程度和類間離散程度，充分挖掘數據之間的冗余。

設不同簇之間聚類中心的距離為：

(12)

改進的目標函數為：

Ei=Ji/Di

(13)

其中：Di表示第i類間距離之和，定義了類之間的耦合性，Ji是由式(3)得。在改進的目標函數中：Ji越小，表示類內距離達到越小，滿足類內緊密的要求；Di越大，表示類間距離越大，滿足類間遠離的要求，則Ei越小，達到最佳聚類狀態。構造新的適應度函數為式(14)。

fiti=1/(1+Ei)

(14)

其中:fiti表示第i個蜜源的適應度的值，Ei越小，fiti越大，聚類效果越好。本文提出的適應度函數以樣本與異類和同類近鄰樣本耦合度度量蜜源的優劣程度，旨在搜索類內相似度高、類間差異大的目標函數，提高聚類效果。

2.3 基于改進人工蜂群的核模糊聚類算法基本步驟

基于改進人工蜂群的核模糊聚類算法的主要思想：改進人工蜂群算法中每個蜜源代表優化問題的可行解，每個蜜源即由一組聚類中心組成。交替執行改進人工蜂群算法和核模糊聚類，對聚類中心進行優化，最后求得最優解。

第1步 隨機產生有SN個蜜源的初始蜂群，設置最大迭代次數maxcycle，蜂群終止循環次數limit，聚類個數c，模糊指數m，允許最小誤差ε。

第2步 對每個蜜源進行一次核模糊聚類，根據式(14)計算每個蜜源的適應度，按照適應度值排序，前50%作為雇傭蜂，后50%作為跟隨蜂，進入迭代階段，直到達到maxcycle迭代次數。

第3步 雇傭蜂根據式(9)進行鄰域搜索工作，產生新的蜜源，計算其適應度值并評價，通過貪婪原則選擇新舊蜜源。

第4步 跟隨蜂根據輪盤賭的原則選擇雇傭蜂，同時根據式(9)在其鄰域內搜索。將得到的蜜源作為聚類中心，再進行一次核模糊聚類，用劃分后形成的新聚類中心更新蜂群。

第5步 如果蜜源xi進行limit次迭代后，位置不變，則丟棄當前解，相應的雇傭蜂轉變成偵查蜂，按照式(6)在搜索空間內產生新解替代當前解。

第6步 記錄迄今為止最優蜜源，判斷是否滿足循環終止條件：若是，循環結束，輸出最后結果；若否，轉至第2步。

3 實驗仿真與分析

仿真環境采用CPU為Inter Core i3-2350,內存4 GB的計算機，操作系統是Window 7,開發軟件為Matlab 2015a。

3.1 改進ABC算法性能測試

為了驗證改進人工蜂群(Improved Artificial Bee Colony, IABC)算法的尋優性能，選取3個經典的Benchmark函數Sphere、Rosenbrock和Ackley作為測試集，測試函數的數學表達式及搜索空間范圍如表1所示，測試函數的理論最優值均為0。其中Sphere和Rosenbrock是高維單峰值函數，Sphere用來測試算法的收斂速度和準確定位能力，Rosenbrock是非凸、病態函數，全局最優解位于拋物線形狀的谷底處。Ackley是高維復雜多峰值函數，擁有多個局部極值點，用來檢驗算法的全局尋優能力。

表1 測試函數的表達式、搜索空間范圍

對IABC算法和ABC算法、文獻[16]算法進行對比仿真實驗，對比實驗效果并分析。文獻[16]算法是將中心解引入到跟隨蜂的局部搜索策略的改進人工蜂群算法。

對所有的測試函數，設IABC算法、標準ABC算法和文獻[16]的蜂群規模為100，每個函數獨立運行100次，對40維的Sphere、Rosenbrock、Ackley每次獨立實驗的最大迭代次數為3 000，limit值為100，即在同一蜜源迭代搜索超過100次則雇傭蜂變為偵查蜂。采用適應度值評價算法的性能，得出各個標準測試函數對兩種算法的適應度值對比曲線如圖1所示。

由圖1中可以看出，在固定的迭代次數下，IABC算法對于40維的Sphere函數和Rosenbrock函數雖然在最大迭代次數內沒有達到最優值，但仿真精度都優于ABC算法和文獻[16]，收斂曲線都以更快的速率下降。尤其是Ackley函數在153代時快速地收斂到函數的最優值，明顯優于ABC算法。ABC算法在高維單峰以及多峰函數中都出現收斂速度緩慢的情況。文獻[16]算法相對ABC算法收斂速度有所提升，在全局尋優上稍顯薄弱。IABC算法具有更好的全局尋優能力和更快的全局收斂速度，IABC算法在各標準測試函數上都優于ABC算法和文獻[16]，且算法性能穩定，證明IABC具有較好的魯棒性。

圖1 函數分別獨立運行100次得到的平均適應度值進化曲線(40維)

3.2 基于IABC算法的核模糊聚類性能測試

為了測試基于IABC算法的核模糊聚類(KFCM based on Improved ABC, IABC-KFCM)對數值型數據的有效性，采用UCI(http://archive.ics.uci.edu)實驗數據集Iris、Wine、Balance-scale、Vote、Heart、Australia作為測試樣本。數據集的基本特征如表2所示。

選取KFCM、基于人工蜂群算法的核模糊聚類(KFCM based on ABC, ABC-KFCM)、IABC-KFCM算法、基于改進的人工蜂群的廣義模糊聚類[17](The Generalized Fuzzy Clustering algorithm based on Improved ABC, IABC-GFCM)進行對比實驗。IABC-GFCM改進雇傭蜂和跟隨蜂的搜索方式，引入混沌映射對種群進行個體變異，對目標函數、隸屬度和聚類中心的模糊指數獨立賦值，進而優化模糊聚類。選用聚類正確率作為評價指標，即正確聚類樣本數與樣本總數所得的比值。對于每個聚類運行100次，取聚類的平均正確率，其實驗結果如表3所示。設置實驗參數為：IABC-GFCM的模糊指數為m1=2，m2=3，m3=2，其余算法的模糊指數取均為2，允許最小誤差ε=0.000 1。

表2 UCI數據集基本特征

由表3可知：傳統的核模糊聚類容易受到初始聚類中心的影響，聚類效果差；在基于人工蜂群的核模糊聚類和IABC-GFCM算法中，聚類精度都有所提高；本文提出的基于IABC算法的核模糊聚類算法，由于引入了人工蜂群中的蜜蜂的智能搜索行為，防止早熟收斂，使得聚類精度高于以上幾種算法。對于Iris數據集中第二類和第三類存在交迭部分，IABC-KFCM仍保持最優聚類精度；對于Wine數據集IABC-KFCM稍劣于IABC-GFCM算法；但對于其他高維的數據集，聚類效果也在不同程度上得到提升。由此可見，在聚類的準確性以及魯棒性方面IABC-KFCM更好。

表3 四種算法正確率比較

4 結語

本文先介紹了核模糊聚類算法，并指出算法的局限性：對聚類的初始化敏感和易陷入局部最優。針對這兩個問題，本文提出一種人工蜂群和核模糊聚類相結合的算法，該算法首先將與迭代的當前維度最優解差值作為改變權值的參考依據，引導雇傭蜂的搜索趨勢，在適應度函數中引入類內距離和類間距離比值，從而改變蜂群的適應度函數并與核模糊聚類相結合，在聚類時使得類內緊密度和類間離散度均達到最優化。UCI數據集實驗表明，本文提出的算法在優化效率和優化性能上更加穩定。需要指出的是，Wine數據集上的結果稍劣于IABC-GFCM算法，此外，算法引入與最優解的差值的過程中增加了時間復雜度，因此后續的研究工作主要針對上述兩方面以及將IABC-KFCM算法應用到圖像分割和圖像檢索等領域。

References)

[1] RUSPINI E H. A new approach to clustering [J]. Information and Control, 1969, 15(1): 22-32.

[2] DUNN J C. A graph theoretic analysis of pattern classification via Tamura’s fuzzy relation [J]. IEEE Transactions on Systems, Man, and Cybernetics, 1974, SMC-4(3): 310-313.

[3] BEZDEK J C. Pattern recognition with fuzzy objective function algorithms [M]// Pattern Recognition with Fuzzy Objective Function Algorithms. New York: Plenum Press, 1981: 203-239.

[4] LI S, MA J. A kernel fuzzy clustering infrared image segmentation algorithm based on histogram and spatial restraint [C]// Proceedings of the 2016 9th International Congress on Image and Signal Processing, Biomedical Engineering and Informatics. Piscataway, NJ: IEEE, 2016: 313-318.

[5] 吳一全,李立.利用核模糊聚類和正則化的圖像稀疏去噪[J]. 光子學報, 2014, 43(3): 310001-310007.(WU Y Q, LI L. Image denoising using kernel fuzzy clustering and regularization on sparse model [J]. Acta Photonica Sinica, 2014, 43(3): 310001-310007.)

[6] GUPTA D, ANAND R S, TYAGI B. A hybrid segmentation method based on Gaussian kernel fuzzy clustering and region based active contour model for ultrasound medical images [J]. Biomedical Signal Processing and Control, 2015, 16: 98-112.

[7] KAR S S, MAITY S P. Blood vessel extraction and optic disc removal using curvelet transform and kernel fuzzy c-means [J]. Computers in Biology and Medicine, 2016, 70: 174-189.

[8] SON L H. A novel kernel fuzzy clustering algorithm for geo-demographic analysis [J]. Information Sciences, 2015, 317: 202-223.

[9] ZHOU J, CHEN L, CHEN C L P, et al. Fuzzy clustering with the entropy of attribute weights [J]. Neurocomputing, 2016, 198(C): 125-134.

[10] DING Y, FU X. Kernel-based fuzzy c-means clustering algorithm based on genetic algorithm [J]. Neurocomputing, 2016, 188: 233-238.

[11] JIAO R, LIU S, WEN W, et al. Incremental kernel fuzzy c-means with optimizing cluster center initialization and delivery [J]. Kybernetes, 2016, 45(8): 1273-1291.

[12] GAO W F, LIU S Y, HUANG L L. Enhancing artificial bee colony algorithm using more information-based search equations [J]. Information Sciences, 2014, 270: 112-133.

[13] GAO W F, HUANG L L, WANG J, et al. Enhanced artificial bee colony algorithm through differential evolution [J]. Applied Soft Computing, 2016, 48: 137-150.

[14] ZHOU X, WU Z, WANG H, et al. Gaussian bare-bones artificial bee colony algorithm [J]. Soft Computing, 2016, 20(3): 907-924.

[15] BANHARNSAKUN A, ACHALAKUL T, SIRINAOVAKUL B. The best-so-far selection in artificial bee colony algorithm [J]. Applied Soft Computing, 2011, 11(2): 2888-2901.

[16] 宋月振,裴騰達,裴炳南.基于中心解的改進人工蜂群算法[J].計算機應用,2016,36(4):1022-1026.(SONG Y Z, PEI T D, PEI B N. Improved artificial bee colony algorithm based on central solution [J]. Journal of Computer Applications, 2016, 36(4): 1022-1026.)

[17] 姚洪曼.基于改進人工蜂群算法的模糊聚類研究[D].南寧:廣西大學,2016:31-39.(YAO H M. Study on the improved artificial bee colony algorithm based fuzzy clustering [D]. Nanning: Guangxi University, 2016: 31-39.)

KernelfuzzyC-meansclusteringbasedonimprovedartificialbeecolonyalgorithm

LIANG Bing, XU Hua*

(SchoolofInternetofThingsEngineering,JiangnanUniversity,WuxiJiangsu214122,China)

Aiming at the problem that Kernel-based Fuzzy C-Means (KFCM) algorithm is sensitive to the initial clustering center and is easy to fall into the local optimum, and the fact that Artificial Bee Colony (ABC) algorithm is simple and of high global convergence speed, a new clustering algorithm based on Improved Artificial Bee Colony (IABC) algorithm and KFCM iteration was proposed. Firstly, the optimal solution was obtained by using IABC as the initial clustering center of the KFCM algorithm. IABC algorithm improved the search behavior of the employed bee with the change rate of the difference from the current dimension optimal solution in the iterative process, balancing the global search and local mining ability of the artificial bee colony algorithm. Secondly, based on within-class distance and between-class distance, the fitness function of the KFCM algorithm was constructed and the cluster center was optimized by KFCM algorithm. Finally, the IABC and KFCM algorithms were executed alternately to achieve optimal clustering. Three Benchmark test functions and six sets in UCI standard data set was used to carry out simulation experiments. The experimental results show that IABC-KFCM improves the clustering effectiveness index of data set by 1 to 4 percentage points compared to IABC-GFCM (Generalized Fuzzy Clustering algorithm based on Improved ABC), which has the advantages of strong robustness and high clustering precision.

Kernel-based Fuzzy C-Means (KFCM) clustering; Artificial Bee Colony (ABC) algorithm; search strategy; function optimization; fitness function

2017- 03- 24;

2017- 04- 24。

國家留學基金委資助項目(201308320030)；江蘇省自然科學基金資助項目(BK20140165)。

梁冰(1993—)，女，山東泰安人，碩士研究生，CCF會員，主要研究方向：大數據、數據挖掘； 徐華(1978—)，女，江蘇無錫人，副教授，博士，主要研究方向：計算機智能、車間調度、大數據。

1001- 9081(2017)09- 2600- 05

10.11772/j.issn.1001- 9081.2017.09.2600

TP18

A

This work is partially supported by the National Scholarship Fund Program (201308320030), the Natural Science Foundation of Jiangsu Province (BK20140165).

LIANGBing, born in 1993, M.S.candidate. Her research interests include large data, data mining.

XUHua, born in 1978,Ph.D.,associate professor.Her research interests include computer intelligence, shop scheduling, large data.