基于人工蜂群優(yōu)化的K均值聚類算法

，，，

(中原工學(xué)院 電子信息學(xué)院，鄭州 450007)

0 引言

隨著科學(xué)技術(shù)的巨大進(jìn)步，社會(huì)經(jīng)濟(jì)也取得了迅速的發(fā)展，與人們生活和工作相關(guān)的各個(gè)領(lǐng)域也包含了越來(lái)越多的信息。人們?cè)趯?shí)際生活和工作中會(huì)頻繁地面臨擁有大量繁雜的數(shù)據(jù)信息而無(wú)法有效、準(zhǔn)確提取有價(jià)值信息的尷尬境地，數(shù)據(jù)挖掘理論與技術(shù)則應(yīng)運(yùn)而生。數(shù)據(jù)挖掘是從大量數(shù)據(jù)中挖掘有趣模式和知識(shí)的過(guò)程，獲取有用信息、隱含聯(lián)系和潛在規(guī)律，以引導(dǎo)人們發(fā)現(xiàn)大量數(shù)據(jù)中的有趣信息和規(guī)律，以及幫助科研人員進(jìn)行決策分析。聚類分析是數(shù)據(jù)挖掘的一種重要技術(shù)手段，它是一個(gè)把數(shù)據(jù)集對(duì)象或觀測(cè)劃分成若干子集的過(guò)程，是一種無(wú)監(jiān)督的學(xué)習(xí)方法[1]。聚類分析要求聚類劃分的類內(nèi)對(duì)象相似度大，而類間對(duì)象的差異性大。K均值聚類是經(jīng)典的聚類算法之一，常用歐氏距離作為相似度的標(biāo)準(zhǔn)進(jìn)行聚類劃分，類內(nèi)距離和越小表示生成的聚類結(jié)果越緊湊和類間越獨(dú)立，聚類效果越好[2]。K均值聚類算法劃分簡(jiǎn)單易行，收斂速度快；但是，K均值聚類不一定收斂于全局最優(yōu)解，常常收斂于局部最優(yōu)，聚類結(jié)果常常出現(xiàn)不穩(wěn)定的現(xiàn)象，影響聚類效果，從而影響人們獲取數(shù)據(jù)中的有效信息和決策的制定。許多研究者采用進(jìn)化算法和群體智能等方法與K均值混合聚類，包括文獻(xiàn)[3-5]分別從初始化聚類中心和優(yōu)化聚類中心位置的角度考慮，并改進(jìn)K均值聚類?？紤]到人工蜂群算法的諸多優(yōu)點(diǎn)，與K均值結(jié)合，可以同時(shí)從初始聚類中心和更新聚類中心位置改進(jìn)標(biāo)準(zhǔn)K均值算法。

人工蜂群算法是一種模擬自然界蜜蜂采蜜尋找優(yōu)良蜜源行為的元啟發(fā)式算法，優(yōu)化結(jié)果不受初始值影響。與其他智能算法相比，人工蜂群算法的優(yōu)點(diǎn)在于參數(shù)設(shè)置少，邏輯性好，計(jì)算簡(jiǎn)單易于實(shí)現(xiàn)；以較大概率跳出局部極值，具有全局收斂性，魯棒性強(qiáng)；因?yàn)槿斯し淙核惴ㄊ且环N通用性強(qiáng)的并行性優(yōu)化算法，可同時(shí)尋優(yōu)多個(gè)解，因此是組合優(yōu)化和數(shù)值優(yōu)化問題的有效優(yōu)化工具，具有良好的理論應(yīng)用和工程應(yīng)用基礎(chǔ)及價(jià)值，吸引了眾多學(xué)者的關(guān)注與研究工作。

本文綜合考慮人工蜂群算法與K均值聚類算法的優(yōu)缺點(diǎn)，提出一種基于人工蜂群優(yōu)化的K均值聚類算法。論述了該混合聚類算法的原理以及實(shí)現(xiàn)過(guò)程，設(shè)計(jì)了算法程序流程圖；最后，用Iris、Red Wine、New Red Wine數(shù)據(jù)集做聚類測(cè)試與驗(yàn)證，分析實(shí)驗(yàn)結(jié)果并得出結(jié)論。

1 相關(guān)算法簡(jiǎn)介

1.1 K均值(K-Means)聚類算法

這里，事先沒有給出每一個(gè)聚類的標(biāo)簽，因此這是一個(gè)無(wú)監(jiān)督學(xué)習(xí)的問題。數(shù)據(jù)集X中的對(duì)象xi與聚類中心cj的歐氏距離用‖xi-cj‖表示。算法的運(yùn)行步驟描述如下：

1)隨機(jī)初始化k個(gè)聚類中心點(diǎn)：c1,c2,...,ck∈Rd；

2)重復(fù)循環(huán)執(zhí)行以下操作，直至算法收斂：

對(duì)于數(shù)據(jù)集中的每一個(gè)對(duì)象xi：

(1)

對(duì)于每一個(gè)聚類中心cj：

(2)

在以上的算法模型中，步驟1表示在數(shù)據(jù)集X中隨機(jī)選擇k個(gè)對(duì)象作為初始聚類中心。公式(1)把每一個(gè)數(shù)據(jù)對(duì)象xi劃分到離它最近的聚類中心cj對(duì)應(yīng)的類別中；公式(2)把聚類中心cj移動(dòng)到當(dāng)前聚類中所有點(diǎn)的均值處。

K均值聚類算法在一定程度上是收斂的，對(duì)聚類公式作如下變形：

(3)

J(Cj,cj)描述的是當(dāng)前聚類劃分中的數(shù)據(jù)對(duì)象到對(duì)應(yīng)聚類中心的歐氏距離平方和。K均值聚類效果用衡量標(biāo)準(zhǔn)函數(shù)E評(píng)價(jià)[6]，衡量標(biāo)準(zhǔn)函數(shù)為：

(4)

式中，E是所有類內(nèi)歐氏距離之和，dist(xi-cj)描述的是數(shù)據(jù)對(duì)象xi到其所屬聚類中心cj之間的歐氏距離。E越小表示聚類的劃分結(jié)果越緊湊和獨(dú)立，聚類的效果也越好。同時(shí)，衡量標(biāo)準(zhǔn)函數(shù)E可作為人工蜂群算法的優(yōu)化目標(biāo)函數(shù)，為兩種算法的結(jié)合提供切入點(diǎn)。

1.2 標(biāo)準(zhǔn)人工蜂群(ABC)算法

人工蜂群算法的基本要素包括蜂群、蜜源和蜜源適應(yīng)度[7]，算法將蜂群分為采蜜蜂、觀察蜂和偵察蜂3種。ABC算法一般通過(guò)較大的適應(yīng)度值引導(dǎo)算法向全局最優(yōu)進(jìn)化[8]，對(duì)于最大值優(yōu)化問題，可用待優(yōu)化問題的目標(biāo)函數(shù)f表示適應(yīng)度函數(shù)fit；對(duì)于最小值優(yōu)化問題，適應(yīng)度函數(shù)用式(5)表示：

(5)

ABC算法步驟敘述如下：

蜂群的初始化產(chǎn)生解：ABC算法的初始化階段，包括種群規(guī)模SN，最大迭代次數(shù)MCN，開采度次數(shù)Limit。蜂群中蜜蜂數(shù)量和食物源數(shù)量相等，且所有蜜蜂都是偵察蜂模式。通過(guò)式(6)隨機(jī)產(chǎn)生SN個(gè)解并計(jì)算其適應(yīng)度，將適應(yīng)度按由大到小的順序排列，前一半作為采蜜蜂，后一半作為觀察蜂和偵察蜂。

xid=xidmin+rand(0,1)(xidmax-xidmin)

(6)

對(duì)于任一解xi的任一分量xid(d=1,2,...,D)都進(jìn)行初始化，xidmin代表可行解空間分量的最小值，xidmax代表可行解空間分量的最大值。

采蜜蜂搜索階段：采蜜蜂在初始階段的蜜源附近，通過(guò)方程(7)搜索產(chǎn)生一個(gè)新解，即為候選蜜源進(jìn)行開采。

vid=xid+rand(-1,1)(xid-xjd)

(7)

式中，j∈{1,2,...,N},j≠i表示在N個(gè)蜜源中隨機(jī)選取一個(gè)不同于xi的蜜源。計(jì)算新解的適應(yīng)度f(wàn)iti并進(jìn)行適應(yīng)度大小評(píng)價(jià)，在vi和xi之中采用貪婪策略進(jìn)行選擇[9]。

觀察蜂跟隨階段：所有采蜜蜂完成搜索之后，采蜜蜂會(huì)把蜜源信息及適應(yīng)度分享給觀察蜂。觀察蜂通過(guò)選擇概率Pi決定每只采蜜蜂被跟隨的概率

(8)

觀察蜂根據(jù)選擇概率，采用輪盤賭策略選擇采蜜蜂跟隨；輪盤賭成功，跟隨采蜜蜂并再次更新其對(duì)應(yīng)的蜜源。若新蜜源對(duì)應(yīng)解的適應(yīng)度比之前的好，觀察蜂會(huì)將新解保存；反之，觀察蜂將會(huì)保留原來(lái)的解，同時(shí)解的迭代搜索次數(shù)iteration會(huì)加1。

偵察蜂階段：如果某一食物源在被搜索開采Limit次之后仍沒有被更新，相應(yīng)的采蜜蜂和觀察蜂則會(huì)放棄該蜜源，轉(zhuǎn)換為偵察蜂模式，按照公式(6)進(jìn)行全局隨機(jī)搜索，尋找一個(gè)新的蜜源代替被舍棄的蜜源。然后返回到采蜜蜂的搜索階段，3種蜜蜂依次進(jìn)行工作，重復(fù)循環(huán)搜索，最終找到待優(yōu)化問題的最優(yōu)解。

1.3 人工蜂群算法的改進(jìn)

對(duì)人工蜂群算法的改進(jìn)研究，主要從提高收斂精度和加快收斂速度兩個(gè)方面進(jìn)行。在標(biāo)準(zhǔn)人工蜂群算法中，主要采用貪婪選擇和輪盤賭策略來(lái)選擇新解和選擇采蜜蜂進(jìn)行跟隨，但是兩種方法都是依靠個(gè)體蜜源的適應(yīng)度進(jìn)行選擇。這種做法的結(jié)果是過(guò)度貪婪選擇適應(yīng)度高的蜜源，解的多樣性丟失，放棄了具有開發(fā)價(jià)值的解，最終導(dǎo)致收斂精度降低。本文在應(yīng)用人工蜂群算法時(shí)，為了提高收斂精度，做了算法的改進(jìn)工作。首先，采用比例選擇的方法代替輪盤賭策略，比例選擇可以使每一個(gè)采蜜蜂都有機(jī)會(huì)得到跟隨，進(jìn)而使每一個(gè)解都會(huì)得到進(jìn)一步開發(fā)；當(dāng)然適應(yīng)度高的蜜源，根據(jù)比例選擇會(huì)被更多的觀察蜂跟隨，對(duì)應(yīng)解的開發(fā)力度會(huì)更大；但是測(cè)試結(jié)果并不好，最終的選擇概率會(huì)平均分布，目標(biāo)函數(shù)值會(huì)穩(wěn)定在精度更低的優(yōu)化結(jié)果處。因此，輪盤賭在蜂群算法中還是一種優(yōu)秀的策略。輪盤賭策略是采用一個(gè)(0,1)之間的隨機(jī)數(shù)與選擇概率Pi進(jìn)行比較，若隨機(jī)數(shù)小于Pi，觀察蜂跟隨采蜜蜂；否則，觀察蜂不跟隨，繼續(xù)比較下一個(gè)采蜜蜂的選擇概率，直到所有觀察蜂都進(jìn)行了跟隨工作。為了使選擇概率不完全依靠個(gè)體蜜源的適應(yīng)度值，設(shè)計(jì)新的選擇概率計(jì)算公式如下：

(9)

這是一種較為有效的改進(jìn)方法，測(cè)試結(jié)果優(yōu)于標(biāo)準(zhǔn)人工蜂群算法。

2 基于人工蜂群優(yōu)化的K均值聚類實(shí)現(xiàn)方法

2.1 食物源的編碼與更新方法

根據(jù)聚類分析的問題背景，建立樣本數(shù)據(jù)集X={x1,x2,...,xn}，其中xi(i=1,2,...,n)是d維數(shù)據(jù)，說(shuō)明每個(gè)數(shù)據(jù)對(duì)象有d個(gè)屬性。K均值算法將數(shù)據(jù)集X劃分成k個(gè)簇，可設(shè)置人工蜂群算法要素，初始化蜂群有SN/2個(gè)采蜜蜂，每個(gè)蜜蜂代表一個(gè)數(shù)據(jù)集劃分，Z={Z1,Z2,...,Zk}，其中zi(i=1,2,...,k)為d維向量是，表示Zi的聚類中心，k是聚類數(shù)目，即每個(gè)蜜蜂為k個(gè)d維向量的聚類中心。

蜂群初始化時(shí)，從樣本數(shù)據(jù)集中隨機(jī)選取k個(gè)數(shù)據(jù)，每個(gè)數(shù)據(jù)包含d維。因此，每只采蜜蜂對(duì)應(yīng)的食物源是一個(gè)k×d的矩陣，將蜂群選取的初始聚類中心送給K均值執(zhí)行聚類步驟，得出聚類中心和聚類衡量函數(shù)值E；接著采用標(biāo)準(zhǔn)蜂群算法中鄰域更新方法更新得到的聚類中心位置，繼續(xù)執(zhí)行K均值聚類算法，并以適應(yīng)度函數(shù)引導(dǎo)收斂；重復(fù)操作以上步驟，循環(huán)迭代，直到達(dá)到算法的終止條件。

2.2 適應(yīng)度函數(shù)設(shè)計(jì)

在人工蜂群算法中，適應(yīng)度函數(shù)的選取是影響算法穩(wěn)定性和收斂性的關(guān)鍵因素[10]。在聚類分析問題中，要求類內(nèi)成員具有較好的相似性，類間成員有較大的差異性；用歐氏距離表示這種相似度，以聚類分析的衡量標(biāo)準(zhǔn)函數(shù)描述聚類分析的效果。因此，本文把衡量標(biāo)準(zhǔn)函數(shù)作為基于人工蜂群優(yōu)化的K均值聚類算法的目標(biāo)函數(shù)，從而設(shè)計(jì)適應(yīng)度函數(shù)。每個(gè)蜜蜂可以通過(guò)式(4)計(jì)算出聚類衡量函數(shù)E，所求優(yōu)化目標(biāo)是E的最小值。因此，適應(yīng)度函數(shù)設(shè)計(jì)[11]為：

(10)

基于人工蜂群優(yōu)化的K均值聚類算法的程序流程設(shè)計(jì)如圖1所示。

圖1 蜂群優(yōu)化K均值算法流程圖

3 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證本文提出的算法確實(shí)改善了聚類效果與精度，利用Matlab進(jìn)行算法仿真。本文采用UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)聚類索引中的Iris、Red Wine和New Red Wine數(shù)據(jù)集[12]進(jìn)行混合聚類算法的測(cè)試。實(shí)驗(yàn)環(huán)境：計(jì)算機(jī)主機(jī)i3CPU、主頻3.30 GHz，運(yùn)行內(nèi)存2.0G；軟件版本為MATLABR2014a，分別運(yùn)行原始K均值聚類算法和基于人工蜂群優(yōu)化的K均值聚類算法20次。Iris、Red Wine和New Red Wine數(shù)據(jù)集中數(shù)據(jù)表示的是不同科鳶尾屬植物和不同級(jí)別紅酒各種物質(zhì)的含量值，根據(jù)這些數(shù)值劃分識(shí)別鳶尾屬植物的科目和紅酒的級(jí)別。所采用的數(shù)據(jù)集詳細(xì)信息見表3.1。

在實(shí)驗(yàn)中，對(duì)于不同的聚類數(shù)據(jù)集對(duì)象，蜂群規(guī)模SN設(shè)置不同，聚類數(shù)目設(shè)置見表1；設(shè)置蜂群算法的最大循環(huán)搜索次數(shù)MCN為500，同一蜜源的可重復(fù)開采次數(shù)為L(zhǎng)imit為10，實(shí)驗(yàn)結(jié)果的相關(guān)數(shù)據(jù)記錄如表2～4所示。

表1 實(shí)驗(yàn)所用數(shù)據(jù)集信息

表2 Iris數(shù)據(jù)集聚類結(jié)果對(duì)比

表3 Red Wine數(shù)據(jù)集聚類結(jié)果對(duì)比

表4 New Red Wine數(shù)據(jù)集聚類結(jié)果對(duì)比

分析上表數(shù)據(jù)可知，原始K均值算法收斂速度快，只需很短的時(shí)間就能輸出聚類結(jié)果；但是聚類衡量函數(shù)值E變化幅度大，說(shuō)明不同次的實(shí)驗(yàn)選擇不同的初始聚類中心，對(duì)結(jié)果影響較大，即原始K均值算法容易受初始聚類中心影響，且易于陷入局部最優(yōu)；原始K均值算法相對(duì)不穩(wěn)定，體現(xiàn)在衡量函數(shù)的標(biāo)準(zhǔn)差較大。

引入人工蜂群算法優(yōu)化K均值聚類算法，增加了算法的時(shí)間復(fù)雜度，而且聚類數(shù)目越多，聚類對(duì)象的屬性越多，算法收斂時(shí)間會(huì)越長(zhǎng)。但是，該算法確實(shí)克服了原始K均值算法的缺點(diǎn)，降低了聚類衡量函數(shù)E值的變化幅度，改善了聚類效果，使聚類結(jié)果更加穩(wěn)定。在時(shí)間復(fù)雜度允許的范圍內(nèi)，提高聚類的精度是十分有意義的；可以提高樣本數(shù)據(jù)集在無(wú)監(jiān)督情況下的劃分準(zhǔn)確率，更好地幫助研究者發(fā)現(xiàn)數(shù)據(jù)間的聯(lián)系與規(guī)律，做出分析與決策。

4 結(jié)論

本文提出一種基于人工蜂群優(yōu)化的K均值聚類分析算法。同時(shí)從隨機(jī)初始化聚類中心和優(yōu)化聚類中心位置入手，利用聚類衡量標(biāo)準(zhǔn)函數(shù)作為蜂群優(yōu)化的目標(biāo)函數(shù)，并以此設(shè)計(jì)適應(yīng)度函數(shù)，以較大概率引導(dǎo)聚類向全局最優(yōu)解收斂，找到更優(yōu)的聚類中心。實(shí)驗(yàn)證明，該算法有效克服了K均值聚類算法易陷入局部最優(yōu)和不穩(wěn)定的缺點(diǎn)，提高了對(duì)聚類中離群點(diǎn)和邊緣點(diǎn)

的分析精度，優(yōu)化了K均值聚類效果和以此做決策分析的準(zhǔn)確度。但是，基于人工蜂群優(yōu)化的K均值聚類算法也有其局限性，即引入很大的時(shí)間復(fù)雜度。下一步的研究目標(biāo)是，利用人工蜂群算法和K均值算法結(jié)合的混合聚類算法優(yōu)勢(shì)的同時(shí)，從進(jìn)一步改進(jìn)蜂群算法的角度，加快算法的尋優(yōu)和收斂速度，降低混合聚類算法的時(shí)間復(fù)雜度。

參考文獻(xiàn)：

[1] 孫吉貴，劉杰，趙連宇.聚類算法研究[J].軟件學(xué)報(bào)，2008,19(1):48-61.

[2] Han J W,Kamber M,Pei J.數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機(jī)械工業(yè)出版社,2012.

[3] 李春生，王耀南.聚類中心初始化的新方法[J].控制理論與應(yīng)用，2010,27(10):1435-1440.

[4] 陶新民，徐 晶，楊立標(biāo).一種改進(jìn)的粒子群和K均值混合聚類算法[J].電子與信息學(xué)報(bào)，2010,32(1):92-97.

[5] Lu B,Ju F.An optimized genetic K-means clustering algorithm[A].CSIP 2012: Proceedings of the 2012 International Conference on Computer Science and Information Processing[C].Piscataway:IEEE, 2012:1296-1299.

[6] Lloyd S P.Least squares quantization in PCM[J].Information Theory, 1982,28:128-137

[7] Karaboga D.An idea based on honey bee swarm for numerical optimization[R]. Technical Report-TR06.Kayseri: Erciyes University, 2005.

[8] Karaboga D,Akay B.On the performance of artificial bee colony optimization algorithm[J].Applied Soft Computing,2008, 8(1):687-697.

[9] Basturk B,Karaboga D.An artificial bee colony algorithm for numeric function optimization[A].IEEE Swarm Intelligence Symposium[C].Indian,2006.

[10] 畢曉君，王艷嬌.加速收斂的人工蜂群算法[J].系統(tǒng)工程與電子技術(shù)，2011,31(4):1107- 1110.

[11] Bi X,Gong R.Hybrid clustering algorithm based on artificial bee colony and K-means algorithm[J].Application Research of Computers,2012,29(6):2040-2042.

[12] UCI.Data sets[EO/OL].http://archive. ics.uci.edu/ml/datasets.html