一種基于改進人工蜂群的K-means聚類算法

劉川川，丁海軍（河海大學(xué)物聯(lián)網(wǎng)工程學(xué)院，常州　213022）

?

一種基于改進人工蜂群的K-means聚類算法

劉川川，丁海軍
（河海大學(xué)物聯(lián)網(wǎng)工程學(xué)院，常州213022）

摘 要：針對K-means算法對初始的聚類中心選擇敏感，全局搜索能力較差，聚類精度低以及穩(wěn)定性不高，算法的魯棒性較差等缺點，提出了一種基于改進的人工蜂群算法來對K-means聚類算法進行優(yōu)化。算法構(gòu)造了新的適應(yīng)度函數(shù)，改進了食物源的位置更新公式來提高迭代效率。利用改進的人工蜂群算法良好的全局尋優(yōu)能力，搜索速度快等優(yōu)點，再加上K-means收斂速度快的優(yōu)點，二者結(jié)合來提高算法的魯棒性。將改進后的算法嵌入到WEKA這一數(shù)據(jù)挖掘平臺中，充分利用了開源WEKA中的類和可視化功能，與WEKA中已有的聚類算法對比分析，可以獲得更好的聚類結(jié)果。

關(guān)鍵詞：聚類；人工蜂群算法；K-means算法；適應(yīng)度函數(shù)；位置更新公式；WEKA平臺

1 引 言

聚類分析是一種無監(jiān)督的學(xué)習(xí)，它不需要數(shù)據(jù)集的先驗知識，在圖像識別、機器學(xué)習(xí)等領(lǐng)域有廣泛的應(yīng)用，是數(shù)據(jù)挖掘領(lǐng)域中的一個重要研究方向。聚類算法就是將數(shù)據(jù)對象劃分為不同的多個簇，同一個簇中的對象盡可能相似，不同簇中的對象盡可能相異。K-means算法是目前使用廣泛的一種基于劃分的聚類算法［1］，該算法對初始聚類中心點的選擇較為敏感，選擇不同的初始聚類中心點，對聚類結(jié)果有比較大的影響。目前，已經(jīng)有很多學(xué)者針對初始聚類中心的選擇進行了研究，文獻［2］中作者提出一種通過計算每個數(shù)據(jù)對象的密度，從中選取k個高密度分布的點作為初始聚類中心，有效提高了K-means聚類算法的準確率和穩(wěn)定性。文獻［3］運用最大最小距離法選擇初始聚類中心，將原始數(shù)據(jù)集分割成各個小類，然后用合并算法形成最終類，聚類性能也優(yōu)于K-means算法。文獻［4］作者在基于密度概念的基礎(chǔ)上，采用最大距離積法選取初始聚類中心，使得改進的K-means算法有更高的準確率和準度，并且穩(wěn)定性也有一定提高。文獻［5］提出的算法中K的個數(shù)不需要預(yù)先給定就可以完成聚類。

人工蜂群智能算法（ABC）是Karabog受到蜜蜂啟發(fā)提出的一種基于蜜蜂群體采蜜行為的群體智能算法。人工蜂群算法具有搜索速度快、全局尋優(yōu)能力強、適用領(lǐng)域廣泛等優(yōu)點。但是人工蜂群算法存在迭代后期收斂速度較慢，容易陷入局部最優(yōu)等問題。文獻［6］通過引入了人工蜂群的粒子算法，利用人工蜂群的全局搜索能力和粒子群的局部搜索能力，使得優(yōu)化后的算法收斂速度較快，跳出局部最優(yōu)能力也比較強。文獻［7］通過引入反向?qū)W習(xí)的初始化，提高了求解效率和質(zhì)量。

基于K-means和ABC算法的各自優(yōu)缺點，首先對傳統(tǒng)的人工蜂群算法進行了改進，提出了改進的人工蜂群算法（Improved ABC，IABC），修改了食物源的搜索公式，并在迭代過程中使用新的適應(yīng)度函數(shù)公式來加快算法的收斂速度，并將改進后的人工蜂群算法與K-means聚類算法相結(jié)合，具有良好的聚類效果。

2 相關(guān)算法介紹

2.1K-means算法

K-means算法的基本思想：首先隨機的從N個數(shù)據(jù)對象中抽取K個對象作為初始聚類中心；針對剩下的其它對象，根據(jù)它們與這些中心點的相似度，將其劃到相似度最大的聚類中；然后再更新每個聚類的聚類中心，再進行聚類劃分，重復(fù)這一過程直到偏差準則函數(shù)開始收斂。偏差準則函數(shù)一般定義如下：

其中：K為聚類簇的總個數(shù)，Xi為簇Ci的平均值。

K-means算法的步驟描述如下：

（1）隨機選擇K個數(shù)據(jù)對象作為初始簇中心；

（2）計算每一個數(shù)據(jù)對象與K個簇中心點的距離，將其劃分到距離最近的那個簇中；

（3）重新計算K個簇的中心，中心為該簇內(nèi)所有數(shù)據(jù)對象點的平均值；用公式（1）計算出此時的偏差準則函數(shù)E。

（4）如果偏差準則函數(shù)滿足：

|E2-E1|＜ε（2）

其中：ε是一個極小值，E2和E1分別代表了兩次迭代后的準則函數(shù)值。當(dāng)滿足公式（2）時，則表示偏差準則函數(shù)收斂，各個簇內(nèi)的數(shù)據(jù)對象不會再發(fā)生改變，結(jié)束聚類。

2.2人工蜂群算法

人工蜂群算法（ABC）主要由食物源、引領(lǐng)蜂、跟隨蜂和偵察蜂來組成。引領(lǐng)蜂用來維持優(yōu)良解，跟隨蜂加快算法的收斂速度，偵察蜂增強了擺脫局部最優(yōu)的能力。一般情況下，引領(lǐng)蜂和跟隨蜂各占蜂群總規(guī)模的一半，且每個食物源同時段內(nèi)只允許有一只引領(lǐng)蜂采蜜。每個食物源的位置代表所求優(yōu)化問題的一個可能解，適應(yīng)度的大小代表了解的質(zhì)量。

ABC算法中，首先根據(jù)公式（3）隨機的產(chǎn)生N個初始的解｛X1，X2，X3…XN｝，每一個Xi（i =1，2，3 …N）都是D維的，并且計算其適應(yīng)度，根據(jù)適應(yīng)度的高低排序，將前一半的蜜蜂作為引領(lǐng)蜂，后一半作為跟隨蜂。

其中：j =（1，2，3，…，D），rand（0，1）為［0，1］之間的隨機數(shù)。

搜索開始階段，引領(lǐng)蜂在當(dāng)前位置附近進行領(lǐng)域搜索，根據(jù)公式（4）產(chǎn)生一個新的位置：

Vij= Xij+φij（Xij-Xkj）（4）

其中k∈｛1，2，3…N｝，且j∈｛1，2，...D｝，φij是［-1，1］均勻分布的隨機數(shù)，Xij為當(dāng)前食物源的位置，Vij為引領(lǐng)蜂搜索后隨機產(chǎn)生的領(lǐng)域食物源位置。

引領(lǐng)蜂采蜜采取貪婪選擇的方法，將記憶中的最優(yōu)解和搜索到的解相比較，如果搜索到的解適應(yīng)度大于記憶中的最優(yōu)解時，替換搜索解為最優(yōu)解；否則，保留最優(yōu)解不變。

當(dāng)所有的引領(lǐng)蜂完成了公式（4）后，飛回交流區(qū)和跟隨蜂來共享食物源位置信息，跟隨蜂根據(jù)輪盤賭原則來進行引領(lǐng)蜂的選擇。然后跟隨蜂再根據(jù)公式（4）在引領(lǐng)蜂附近進行領(lǐng)域搜索，同樣根據(jù)貪婪原則保留最優(yōu)解。

在ABC算法中，跟隨蜂根據(jù)公式（5）的概率來選擇引領(lǐng)蜂

其中：fiti為第i個解的適應(yīng)度，適應(yīng)度越大，對應(yīng)解的質(zhì)量越高。

如果在經(jīng)過limit次迭代后某個食物源位置沒有發(fā)生變化，并且該食物源也不是全局最優(yōu)解，則放棄該食物源，同時與之對應(yīng)的引領(lǐng)蜂腳色發(fā)生變化，將轉(zhuǎn)變?yōu)閭刹旆洌蓚刹旆涓鶕?jù)公式（3）隨機產(chǎn)生新的位置代替該解。當(dāng)達到最大迭代次數(shù)后，將適應(yīng)度最大的解作為最終結(jié)果輸出。

3 改進的人工蜂群算法研究

3.1適應(yīng)度函數(shù)

其中E為K-means算法中的偏差準則函數(shù)，也可稱為所有簇的類內(nèi)距離和。

3.2食物源位置更新公式

在傳統(tǒng)的人工蜂群算法中，引領(lǐng)蜂和跟隨蜂都是根據(jù)公式（4）來更新位置的，由于引領(lǐng)蜂和跟隨蜂都是在一個范圍內(nèi)隨機搜索附近的食物源，沒有具體的方向和范圍，勢必會具有盲目性。而在實際尋優(yōu)的過程中，搜索范圍在不同的時期要求是不一樣的。在算法剛開始的階段，希望引領(lǐng)蜂能夠在較大的范圍內(nèi)進行搜索，從而能夠快速找到最優(yōu)解的大概方向；而隨著迭代次數(shù)的增加，即到了算法后期，此時由于已經(jīng)比較接近最優(yōu)解，希望能夠在較小的范圍內(nèi)搜索最優(yōu)解。即越到算法的后期，搜索范圍相比初始階段，也應(yīng)該相應(yīng)的越來越小，所以改進后的領(lǐng)域搜索公式為：

其中：MCN為最大迭代次數(shù)，T為當(dāng)前迭代次數(shù)。dmin和dmax用來控制領(lǐng)域搜索的最小、最大范圍，根據(jù)經(jīng)驗值，取dmin=0.4，dmax=1.0。

4 基于改進人工蜂群的K-means算法

基于改進人工蜂群的K-means算法的實現(xiàn)過程：首先隨機產(chǎn)生初始蜂群，每個蜜蜂代表一種聚類劃分，利用人工蜂群算法得到多個聚類中心，再將每個聚類中心進行K-means迭代，從而得到新的聚類中心，兩個算法相互迭代，交替進行，直到聚類結(jié)束。

算法的具體步驟描述如下：

a.設(shè)置引領(lǐng)蜂、跟隨蜂以及偵察蜂的數(shù)量（引領(lǐng)蜂數(shù)量=跟隨蜂數(shù)量=蜂群規(guī)模的一半），設(shè)置最大迭代次數(shù)MCN，當(dāng)前迭代次數(shù)T，T的初始值為1，聚類數(shù)K，設(shè)置預(yù)先的試驗次數(shù)上限limit，并隨機產(chǎn)生｛Z1，Z2，Z3…ZN｝個初始蜜蜂。

b.對蜂群進行一次聚類劃分，每個蜜蜂代表一種聚類劃分，并按照公式（6）計算每個蜜蜂對應(yīng)的適應(yīng)度fi。

c.將適應(yīng)度從高到低排序，將前50%的作為引領(lǐng)蜂，剩下的50%作為跟隨蜂。

d.引領(lǐng)蜂根據(jù)公式（7）進行領(lǐng)域搜索，按照貪婪選擇的方法更新得到新位置，如果新位置的適應(yīng)度值大于舊位置的適應(yīng)度，則用新位置代替舊位置；反之，保持不變。

e.跟隨蜂依據(jù)輪盤賭原則來選擇引領(lǐng)蜂，選擇跟隨完成后也按照公式（7）進行領(lǐng)域探索，同樣根據(jù)貪婪選擇的方法來更新位置，將新位置作為新的聚類中心。

f.當(dāng)全部跟隨蜂完成了領(lǐng)域搜索后，得到多個新的聚類中心，將聚類中心作為K-means的初始聚類中心，進行一次K-means聚類算法，更新得到新的聚類中心，用新的聚類中心再去更新蜂群。

g.如果某個引領(lǐng)蜂在經(jīng)過limit次迭代后位置沒有發(fā)生改變，則該位置會被放棄，此時，引領(lǐng)蜂變?yōu)閭刹旆洌蓚刹旆浒凑展剑?）隨機產(chǎn)生新的位置取代原位置。

h.如果當(dāng)前迭代次數(shù)等于最大迭代次數(shù)，輸出適應(yīng)度最大的聚類結(jié)果，算法結(jié)束。否則，轉(zhuǎn)向步驟b），T = T +1。

5 算法實現(xiàn)與性能測試

5.1基于改進人工蜂群的K-means算法實現(xiàn)

根據(jù)以上的算法思想過程描述，在WEKA平臺上利用Java語言（Eclipse環(huán)境）實現(xiàn)了改進人工蜂群的K-means算法，并且將該算法嵌入到了WEKA平臺中。充分利用WEKA源代碼開源的這一特性，所開發(fā)的改進人工蜂群的K-means算法的主類IABCK-means充分調(diào)用了原有類如weka.core、weka.classifiers.rules、java.util等包中的一些類，最后將開發(fā)的主類IABCK-means與Cluster及RandomizableClusterer抽象類等一起封裝在weka.clusterers包中。IABCK-means類實現(xiàn)了NumberOf-ClustersRequestable、WeightedInstancesHandler這兩個接口，并且IABCK-means類繼承了RandomizableClusterer抽象類。在ABCK-means類中主要完成了聚類模型的產(chǎn)生和聚類結(jié)果的表示等。

5.2基于改進人工蜂群的K-means算法性能測試

5.2.1 實驗數(shù)據(jù)及結(jié)果分析

為了驗證改進人工蜂群的K-means算法性能，將該算法嵌入到WEKA平臺后，采用了UCI［9］數(shù)據(jù)庫中著名的鳶尾花（Iris）數(shù)據(jù)集（表1）。在該數(shù)據(jù)集中，一共包含150個鳶尾花的數(shù)據(jù)信息，每組數(shù)據(jù)包含四種屬性：花瓣長度、花瓣寬度、萼片長度和萼片寬度。數(shù)據(jù)集包含三類：Setosa、Versicolour 和Virginica。Iris數(shù)據(jù)集中3個類分類特征相對明顯，第一類與第二類、第三類完全分開，后兩個類有一定的交叉。

表1 鳶尾花的實驗數(shù)據(jù)

算法的參數(shù)設(shè)置為：最大迭代次數(shù)MCN =200，蜂群規(guī)模為N =20（即引領(lǐng)蜂=跟隨蜂=10），控制參數(shù)limit =50，聚類數(shù)目K =3。

文獻［8］中作者給出了鳶尾花數(shù)據(jù)集的實際類中心位置：Z1=（6.58，2.97，5.55，2.02），Z2=（5.00，3.42，1.46，0.24），Z3=（5.93，2.77，4.26，1.32）。從表2中看出，采用改進的人工蜂群的K-means聚類算法所得的結(jié)果與實際結(jié)果非常接近，聚類中心與實際的聚類中心幾乎一致。說明經(jīng)過改進的人工蜂群算法后的聚類中心比較接近最終的聚類中心，能夠克服K-means聚類算法容易受到初始聚類中心影響這一缺點，能夠提高算法的穩(wěn)定性。

表2 最終的聚類中心

除了Iris數(shù)據(jù)集外，還對Zoo數(shù)據(jù)集進行了實驗。Zoo數(shù)據(jù)集包含15個數(shù)值屬性和1個分類型屬性。數(shù)據(jù)集樣本一共由7個動物類別組成，分別是：哺乳類（41）、鳥類（20）、昆蟲類（8）、魚類（13）、爬行類（5）和兩棲類（4）。在Zoo數(shù)據(jù)集中，算法的參數(shù)設(shè)置為：最大迭代次數(shù)MCN =500，蜂群規(guī)模= 20，控制參數(shù)limit =100，聚類數(shù)目K =7。實驗分析計算了在不同數(shù)據(jù)集的情況下，WEKA中經(jīng)典聚類算法的準確率，結(jié)果如表3所示。

表3 IABCK-means聚類算法與WEKA中其他算法準確率對比

準確率的計算方法如下：原數(shù)據(jù)集分為K個類，Ci表示第i類，Ni為第i個類中的樣本個數(shù)，Mi為聚類完成后第i個類中的樣本個數(shù)，設(shè)準確率為P，則：

6 結(jié)束語

在人工蜂群算法基礎(chǔ)上，提出了一種改進的人工蜂群算法，采用新的適應(yīng)度函數(shù)公式，改進了食物源的位置更新公式，增強了局部尋優(yōu)能力。將改進后的算法與K-means聚類算法相結(jié)合，利用人工蜂群算法全局尋優(yōu)能力強、算法魯棒性較強等優(yōu)點去對K-means初始聚類中心點進行優(yōu)化，提高了算法的魯棒性。在數(shù)據(jù)集Iris和Zoo的實驗中，與傳統(tǒng)的K-means算法相比，該算法在穩(wěn)定性和收斂精度等方面都有了一定提高，證明該算法具有較好的聚類效果。但是也存在一定的缺點，如算法耗時較長，需要預(yù)先指定要聚類的數(shù)目，這些都可以作為下一步改進的研究方向。

參考文獻：

［1］Han Jiawei，Kamber M.數(shù)據(jù)挖掘：概念與技術(shù)［M］.范明，譯.北京：機械工業(yè)出版社，2007：223-244.HAN J，Kamber M.Data mining：Concepts and Techniques［M］.FAN M，translation.BeiJing：China Machine Press，2007：223-244.

［2］韓凌波，王強，蔣正鋒，等.一種改進的k-means初始聚類中心選取算法［J］.計算機工程與應(yīng)用，2010，46 （17）：150-152.HAN L，WANG Q，JIANG Z，et al.A modified K-means the initial clustering center selection algorithm［J］.Computer Engineering and Applications，2010，46（17）：150-152.

［3］周涓熊，熊忠陽，張玉芳，等.基于最大最小距離法的多中心聚類算法［J］.計算機應(yīng)用，2006，26（6）：1425-1427.ZHOU J，XIONG Z，ZHANG Y，et al.Multiseed clustering algorithm based on max-min distance means［J］.Journal of Computer Applications，2006，26（6）：1425-1427.

［4］熊忠陽，陳若田，張玉芳，等.一種有效的K-means聚類中心初始化方法［J］.計算機應(yīng)用研究，2011，28 （11）：4188-4190.XIONG Z，CHEN R，ZHANG Y.Effective method for cluster centers'initialization in K-means clustering［J］.Application Research of Computers，2011，28（11）：4188-4190.

［5］劉雷，王洪國.一種基于蜂群原理的劃分聚類算法［J］.計算機應(yīng)用，2011，28（5）：1699-1702.LIU L，WANG H.A partitioning clustering algorithm based on swarm principles［J］.Journal of Computer Applications，2011，28（5）：1699-1702.

［6］高衛(wèi)峰，劉三陽，焦合華，等.引入人工蜂群搜索算子的粒子群算法［J］.控制與決策，2012，27（6）：833-838.GAO W，LIU S，JIAO H，et al.The introduction of artificial colony search operator particle swarm algorithm［J］.Control and Decision，2012，27（6）：833-838.

［7］吳昱，李元春，徐星.基于群智能的新型反向混合差分進化算法［J］.小型微型計算機系統(tǒng)，2009，30（5）：903-907.WU Y，LI Y，XU X.Oppositional hybrid differential evolution algorithm based on swarm intelligence［J］.Journal of Chinese Computer Systems，2009，30（5）：903-907.

［8］CHEN Ning，CHEN An，ZHOU Long-xiang.Fuzzy K-prototypes algorithm for clustering mixed numeric and categorical valued data（in English）［J］.Journal of Software，2001，12（5）：712-716.

［9］University of California，Irvine，UCI machine learning repository［DB/OL］.［2013-06-19］.http：//archivce.ics.uci.edu/ml.

A K-means Clustering Algorithm Based on Improved Artificial Bee Colony

Liu Chuanchuan，Ding Haijun
（College of Internet of Things Engineering，Hohai University，Changzhou 213022，China）

Abstract：As the K-means clustering method has disadvantages of sensitive to the initial clustering centers，poor global search ability，low accuracy and stability and poor robustness of algorithm，based on an improved Artificial Bee Colony algorithm，this paper proposes an algorithm to optimize the K-means clustering algorithm.It will construct a new fitness function and improve the food source location update formula to enhance the efficiency of iteration.The advantages of good global optimization ability，fast search and convergence rate are combined to improve the robustness of the algorithm.The improved algorithm is embedded in the WEKA platform，compared with the existing clustering algorithms in the WEKA，the better clustering results can be obtained.

Key words：Clustering；Artificial Bee Colony；K-means algorithm；Fitness function；Position update rule；WEKA platform

DOI：10.3969/j.issn.1002-2279.2016.02.013

中圖分類號：TP301.6

文獻標(biāo)識碼：A

文章編號：1002-2279（2016）02-0047-04

作者簡介：劉川川（1989-），男，河南省洛陽市人，碩士研究生，主研方向：數(shù)據(jù)挖掘，智能數(shù)據(jù)處理。

收稿日期：2015-05-25