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

?

一種基于改進(jìn)人工蜂群的K-means聚類算法

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

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

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

1 引 言

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

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

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

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

2.1K-means算法

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

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

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

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

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

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

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

|E2-E1|＜ε（2）

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

2.2人工蜂群算法

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

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

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

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

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

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

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

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

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

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

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

3 改進(jìn)的人工蜂群算法研究

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

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

3.2食物源位置更新公式

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

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

4 基于改進(jìn)人工蜂群的K-means算法

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

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

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

b.對(duì)蜂群進(jìn)行一次聚類劃分，每個(gè)蜜蜂代表一種聚類劃分，并按照公式（6）計(jì)算每個(gè)蜜蜂對(duì)應(yīng)的適應(yīng)度f(wàn)i。

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

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

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

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

g.如果某個(gè)引領(lǐng)蜂在經(jīng)過(guò)limit次迭代后位置沒(méi)有發(fā)生改變，則該位置會(huì)被放棄，此時(shí)，引領(lǐng)蜂變?yōu)閭刹旆?，由偵察蜂按照公式?）隨機(jī)產(chǎn)生新的位置取代原位置。

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

5 算法實(shí)現(xiàn)與性能測(cè)試

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

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

5.2基于改進(jìn)人工蜂群的K-means算法性能測(cè)試

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

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

表1 鳶尾花的實(shí)驗(yàn)數(shù)據(jù)

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

文獻(xiàn)［8］中作者給出了鳶尾花數(shù)據(jù)集的實(shí)際類中心位置：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中看出，采用改進(jìn)的人工蜂群的K-means聚類算法所得的結(jié)果與實(shí)際結(jié)果非常接近，聚類中心與實(shí)際的聚類中心幾乎一致。說(shuō)明經(jīng)過(guò)改進(jìn)的人工蜂群算法后的聚類中心比較接近最終的聚類中心，能夠克服K-means聚類算法容易受到初始聚類中心影響這一缺點(diǎn)，能夠提高算法的穩(wěn)定性。

表2 最終的聚類中心

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

表3 IABCK-means聚類算法與WEKA中其他算法準(zhǔn)確率對(duì)比

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

6 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

［1］Han Jiawei，Kamber M.數(shù)據(jù)挖掘：概念與技術(shù)［M］.范明，譯.北京：機(jī)械工業(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］韓凌波，王強(qiáng)，蔣正鋒，等.一種改進(jìn)的k-means初始聚類中心選取算法［J］.計(jì)算機(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］周涓熊，熊忠陽(yáng)，張玉芳，等.基于最大最小距離法的多中心聚類算法［J］.計(jì)算機(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］熊忠陽(yáng)，陳若田，張玉芳，等.一種有效的K-means聚類中心初始化方法［J］.計(jì)算機(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］劉雷，王洪國(guó).一種基于蜂群原理的劃分聚類算法［J］.計(jì)算機(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)峰，劉三陽(yáng)，焦合華，等.引入人工蜂群搜索算子的粒子群算法［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ìn)化算法［J］.小型微型計(jì)算機(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

中圖分類號(hào)：TP301.6

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1002-2279（2016）02-0047-04

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

收稿日期：2015-05-25