結(jié)合膜計(jì)算與人工蜂群算法的K均值算法

黃文成

（西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院，成都 610039）

0 引言

聚類(lèi)是一種重要的無(wú)監(jiān)督學(xué)習(xí)技術(shù)，其目標(biāo)是將數(shù)據(jù)集合分成若干簇，使得同一簇內(nèi)的樣本相似度盡可能大，而不同簇間的樣本相似度盡可能小，目前該技術(shù)在機(jī)器學(xué)習(xí)、模式識(shí)別、Web挖掘以及圖像量化等領(lǐng)域得到了廣泛的應(yīng)用[14]。

K均值（K-means）算法是解決聚類(lèi)問(wèn)題的經(jīng)典算法之一。但由于K均值聚類(lèi)算法敏感于初始值和易受孤立點(diǎn)影響,容易陷入局部最優(yōu),并且全局搜索能力較弱,這些致命點(diǎn)嚴(yán)重影響聚類(lèi)的性能[16]。為解決函數(shù)優(yōu)化問(wèn)題，由Karaboga于2005年提出了人工蜂群算法（Artificial Bee Colony Algorithm，ABC）[12,13]，該算法是一種模擬生物群體智能的優(yōu)化方法，具有實(shí)現(xiàn)簡(jiǎn)單、參數(shù)數(shù)量較少、全局搜索能力好、魯棒性強(qiáng)等多種優(yōu)點(diǎn)。但ABC算法還是存在收斂速度較慢、較容易陷入局部最優(yōu)等問(wèn)題。

近年，研究人員考慮到兩種算法有許多互補(bǔ)之處，著手研究將兩種算法進(jìn)行結(jié)合。李海洋等人[17]提出IABC-K算法，將ABC算法和K-means算法進(jìn)行合理切換，應(yīng)用于圖像分割。曹永春等人[18]提出IABCC算法，使用ABC算法和K-means算法對(duì)數(shù)據(jù)進(jìn)行交替迭代。喻金平等人[3]提出IABC-Kmeans算法，使用ABC算法和K-means算法在對(duì)數(shù)據(jù)進(jìn)行交替迭代的同時(shí)，并對(duì)適應(yīng)度函數(shù)及初始值的獲取進(jìn)行了改良。Janani等人[19]提出ABC-BK算法及新的適應(yīng)度函數(shù)，并將此算法應(yīng)用于文本聚類(lèi)。Alam等人[20]提出WDC-KABC算法應(yīng)用于網(wǎng)頁(yè)文獻(xiàn)聚類(lèi)。Cong等人[21]提出EABCK算法，將K-means算法應(yīng)用于由ABC算法得到的全局最優(yōu)值的再次尋優(yōu)。Giuliano等人[22]提出ABCk算法，將K-means算法嵌入到ABC算法的雇傭蜂和觀察蜂階段，加快算法收斂速度。Bonab等人[23]提出CCIAABC-K算法，應(yīng)用于對(duì)數(shù)據(jù)的聚類(lèi)和圖像的分割。這些混合算法大多克服了K-means算法對(duì)初始值敏感，ABC算法收斂速度慢的問(wèn)題。但是，初始值的選取還是對(duì)混合算法的結(jié)果有影響，也存在著容易陷入局部最優(yōu),求解精度和算法不太穩(wěn)定的問(wèn)題。

鑒于以上的問(wèn)題，本文將膜計(jì)算（Membrane Computing，MC）[24]的概念組合到 K-means和ABC的混合算法中，提出一種結(jié)合膜計(jì)算與人工蜂群算法的K均值算法（K-means algorithm:Combining P system with Artificial Bee Colony Algorithm，PABC-K）來(lái)優(yōu)化聚類(lèi)問(wèn)題。

1 準(zhǔn)備知識(shí)

1. 1 K均值算法

K均值算法因其簡(jiǎn)單性和易于實(shí)現(xiàn)而被廣泛使用。K均值算法根據(jù)參數(shù)K將給定數(shù)據(jù)集聚類(lèi)為K個(gè)簇，以每個(gè)數(shù)據(jù)點(diǎn)到其聚類(lèi)中心的距離平方和為目標(biāo)函數(shù),通過(guò)求解函數(shù)極小值方式反復(fù)迭代,直到目標(biāo)函數(shù)收斂。

K均值聚類(lèi)目標(biāo)函數(shù)為：

K均值聚類(lèi)中心迭代公式為：

其中，N為數(shù)據(jù)樣本數(shù)；K為聚類(lèi)中心數(shù)；Xj為第j個(gè)數(shù)據(jù)點(diǎn)；Ci為第i個(gè)聚類(lèi)中心；wji為權(quán)重，當(dāng)?shù)趈個(gè)數(shù)據(jù)點(diǎn)屬于第i個(gè)聚類(lèi)中心時(shí)，其值為1，如不屬于，則為0。

1. 2 ABC算法

ABC算法通過(guò)模擬蜂群分工合作尋找最優(yōu)蜜源的過(guò)程求解優(yōu)化問(wèn)題，是一種基于蜜蜂群體智能的優(yōu)化算法[1]。ABC算法具有控制參數(shù)少、易于實(shí)現(xiàn)等優(yōu)點(diǎn)，在函數(shù)優(yōu)化方面具有比較好的表現(xiàn)。在ABC算法中，蜜蜂被分為雇傭蜂、觀察蜂和偵查蜂這3類(lèi)。食物源的位置表示一個(gè)可行解，每個(gè)食物源只對(duì)應(yīng)一只雇傭蜂，即雇傭蜂的數(shù)量等于食物源的數(shù)量。觀察蜂的數(shù)量則設(shè)置為和雇傭蜂相同。ABC算法的基本步驟如下：

步驟1：種群的初始化。設(shè)具有n個(gè)樣本點(diǎn)的數(shù)據(jù)集X={xi∈Rd,i=1,2,…,n},xi為d維向量；設(shè)算法的最大迭代次數(shù)為MCN，每個(gè)蜜源的最大開(kāi)采次數(shù)為limit，蜜源個(gè)數(shù)為SN。

步驟2：根據(jù)如下公式（3）隨機(jī)選擇蜜源，作為初始可行解：

其中，j∈{1,2,…,d}；Xij表示第 i個(gè)蜜源的第 j維分量；Lj表示所有樣本中第j維的數(shù)值下限；Uj表示所有樣本中第j維的數(shù)值上限。

步驟3：雇傭蜂根據(jù)公式（4）在當(dāng)前蜜源的鄰域范圍內(nèi)更新蜜源。運(yùn)用貪婪選擇法，比較新舊解的適應(yīng)度，保留質(zhì)量好的解：

其中，i,k∈{1,2,…,SN}，且i≠k。

步驟4：每個(gè)雇傭蜂更新蜜源后，觀察蜂選擇一只雇傭蜂，跟隨其前往蜜源采蜜。觀察蜂選擇雇傭蜂的概率計(jì)算公式如式（5）所示：

其中，fi為第i個(gè)蜜源的適應(yīng)度值。觀察蜂通過(guò)公式（5）選著比較好的蜜源，隨后根據(jù)公式（4）再次更新蜜源。

步驟5：某蜜源的搜索次數(shù)達(dá)到最大開(kāi)采次數(shù)Limit,但蜜源適應(yīng)度不再變化時(shí),放棄該蜜源。同時(shí),將雇傭蜂轉(zhuǎn)換為偵察蜂。偵察蜂根據(jù)公式（3）搜尋新的蜜源，以代替被放棄的蜜源。

步驟6：判斷是否達(dá)到最大迭代次數(shù)達(dá)或滿(mǎn)足循環(huán)終止條件。若是,算法結(jié)束并輸出適應(yīng)度最好的蜜源作為最優(yōu)解。若不是,返回步驟3。

1. 3 膜計(jì)算

膜計(jì)算又稱(chēng)為P系統(tǒng)，是羅馬尼亞科學(xué)院院士Gheorghe Paun于1998年11月基于細(xì)胞膜結(jié)構(gòu)提出的一種自然計(jì)算方法[2]。Nishida[4]在2004年將膜計(jì)算引入到遺傳算法中，第一次提出了膜優(yōu)化算法的概念。膜計(jì)算還被引入到了粒子群算法[5]、人工魚(yú)群算法[6]及K-medoids[7]、KNN[8]等算法中。膜優(yōu)化算法已成為了膜計(jì)算領(lǐng)域中的一個(gè)重要分支。同時(shí)，P系統(tǒng)也被大量應(yīng)用于圖像分割方向[9-11],并且獲得了比較好的結(jié)果。

P系統(tǒng)具有分布式、極大并行性和非確定性的特點(diǎn)。根據(jù)膜結(jié)構(gòu)的特點(diǎn)，P系統(tǒng)可以分為細(xì)胞型P系統(tǒng)、組織型P系統(tǒng)和神經(jīng)型P系統(tǒng)。其中細(xì)胞型P系統(tǒng)是其他兩種P系統(tǒng)的基礎(chǔ)[2]。細(xì)胞型P系統(tǒng)的基本結(jié)構(gòu)如圖1所示。最外層的細(xì)胞膜（1號(hào)膜）稱(chēng)為表層膜，它分隔開(kāi)外部環(huán)境和內(nèi)部空間；膜內(nèi)部沒(méi)有其他膜存在的細(xì)胞膜，被稱(chēng)為基本膜（2、4、5號(hào)膜）。在P系統(tǒng)中，各個(gè)膜的空間中可以具有各自不同的對(duì)象和運(yùn)算規(guī)則。

圖1 細(xì)胞型P系統(tǒng)的結(jié)構(gòu)

形式上，一個(gè)細(xì)胞型P系統(tǒng)定義如下：

其中：O是對(duì)象的有限字母表；Σ?O是輸入字母表；μ是由q個(gè)膜組成的膜結(jié)構(gòu)，q稱(chēng)為P系統(tǒng)Π的度數(shù)；Mi（1≤i≤q）表示q個(gè)膜中各自包含的對(duì)象；Ri（1≤i≤q）表示q個(gè)膜中各自包含的規(guī)則；i0∈{0,1,2,…,q}是系統(tǒng)Π的輸出膜。

規(guī)則Ri是二元組（u,v），通常寫(xiě)成u→v,u是字母表O中的字符串,v是O×{here,out,in}上的一個(gè)字符串。其 中，v具 有（a,tar）的 形 式，其中a∈O,tar∈{here,out,in}。如果tar=here，則a位于規(guī)則所在的區(qū)域中；如果tar=out，則a被傳送到規(guī)則所在的區(qū)域的高一級(jí)區(qū)域中；如果tar=in，則a被傳送到規(guī)則所在的區(qū)域的低一級(jí)區(qū)域中。

2 PABC-K算法

2. 1 最大最小距離積法初始化

無(wú)論K均值算法還是人工蜂群算法都對(duì)初始值敏感,而隨機(jī)的初始化影響著算法的收斂速度和最優(yōu)解的質(zhì)量。文獻(xiàn)[3]針對(duì)最大最小距離法和最大距離積法的不足，提出最大最小距離積法來(lái)對(duì)初始值進(jìn)行初始化，以解決初始點(diǎn)過(guò)于密集等問(wèn)題。

算法流程圖如圖2所示。其中，D是包含所有數(shù)據(jù)的集合；k是要選取的初始點(diǎn)個(gè)數(shù)；Z是存儲(chǔ)k個(gè)初始點(diǎn)的集合，算法開(kāi)始前為空集；Temp是存儲(chǔ)Z中各元素到D中各元素的距離的數(shù)組。

該算法所需參數(shù)少；可以選取到點(diǎn)密度較大的點(diǎn)，稀疏了初始點(diǎn)的分布；通過(guò)乘積法放大了點(diǎn)與點(diǎn)之間的差異，選取過(guò)程更具區(qū)分度。

2. 2 膜系統(tǒng)結(jié)構(gòu)

PABC-K算法建立在細(xì)胞型P系統(tǒng)的基礎(chǔ)上，采用單層膜結(jié)構(gòu)，如圖3所示。0號(hào)膜為表層膜，分隔開(kāi)外部環(huán)境和內(nèi)部空間。表層膜內(nèi)部具有n個(gè)細(xì)胞膜，全部都為基本膜。基本膜之間可以相互交流，基本膜和表層膜也可以相互交流。

圖2 最大最小距離積算法流程圖

圖3 單層膜結(jié)構(gòu)

PABC-K算法中，多種群蜂群與P系統(tǒng)結(jié)合，每個(gè)基本膜中存在一個(gè)蜂群，表層膜中不包含蜂群。在每次的迭代過(guò)程中，每個(gè)基本膜中的信息通過(guò)表層膜進(jìn)行交互，每個(gè)基本膜中的蜂群相互間不產(chǎn)生影響。表層空間能夠獲取各基本膜滲透出來(lái)的局部最優(yōu)食物源，通過(guò)貪婪選擇法，選出全局最優(yōu)食物源。表層膜空間將全局最優(yōu)食物源，分別滲透回每個(gè)基本膜中，用以影響各基本膜中下一次進(jìn)行的迭代。

該P(yáng)系統(tǒng)的定義如下：

（1）Π =(O,μ,(M0,...,Mn),R,i0)

（2）O是整個(gè)樣本集

（3）膜結(jié)構(gòu)包含n個(gè)細(xì)胞膜，具體結(jié)構(gòu)μ=[[]1,[]2,[]3,...,[]n]0，其中0表示表層膜。

（4）初始種群的分布為：

M0=φ1=O,M2=O,…,Mn=O

其中，M0為皮膚膜的初始集，是一個(gè)空集。Mi（1≤i≤n）為每個(gè)基本膜，包含對(duì)象都為整個(gè)樣本集。

（5）輸出字母表io表示表層膜的輸出，也是PABC-K算法的最終輸出，表示一組食物源。

細(xì)胞膜空間中的規(guī)則：

（1）每個(gè)基本膜中都獨(dú)立運(yùn)行K-means算法與ABC算法的混合算法；表層膜空間內(nèi)進(jìn)行貪婪選擇法的進(jìn)化規(guī)則。

（2）各基本膜將各自運(yùn)算出的最優(yōu)的食物源發(fā)送至表層膜；表層膜則將最終得到的最優(yōu)的個(gè)體復(fù)制n份發(fā)送回各基本膜。

2. 3 結(jié)合膜計(jì)算與人工蜂群算法的K均值算法

在PABC-K算法中，以膜系統(tǒng)作為總體框架，結(jié)合人工蜂群算法來(lái)優(yōu)化K-means算法的聚類(lèi)中心，用以對(duì)數(shù)據(jù)進(jìn)行聚類(lèi)運(yùn)算。本算法設(shè)計(jì)了一個(gè)細(xì)胞型P系統(tǒng)，它是一個(gè)帶有進(jìn)化規(guī)則和轉(zhuǎn)運(yùn)規(guī)則的P系統(tǒng)，使用單層膜結(jié)構(gòu)，具有一個(gè)表層膜和n個(gè)基本膜。每個(gè)基本膜中都有進(jìn)化規(guī)則和多個(gè)對(duì)象，并且每個(gè)對(duì)象都與表層膜之間有轉(zhuǎn)運(yùn)規(guī)則。由ABC算法和K-means算法相結(jié)合的混合算法作為每個(gè)基本膜中的進(jìn)化算法，作用于將要進(jìn)行聚類(lèi)的數(shù)據(jù)。各基本膜與表層膜間運(yùn)用轉(zhuǎn)運(yùn)規(guī)則，將各基本膜中得到的局部最優(yōu)解轉(zhuǎn)運(yùn)到表層膜空間中，并接收表層膜空間得到的目前狀態(tài)的全局最優(yōu)解，轉(zhuǎn)運(yùn)回各基本膜空間中。表層膜中將使用貪婪選擇法作為進(jìn)化規(guī)則，作用于從各基本膜得到的局部最優(yōu)解，得到全局最優(yōu)解，并運(yùn)用轉(zhuǎn)運(yùn)規(guī)則傳回各基本膜中。

每個(gè)基本膜中，都存在著一個(gè)蜂群，單獨(dú)運(yùn)行由ABC算法和K-means算法相結(jié)合的混合算法，尋找最優(yōu)食物源。食物源個(gè)數(shù)設(shè)置為k，每個(gè)食物源代表一個(gè)聚類(lèi)中心點(diǎn)；設(shè)置最大迭代次數(shù)MCN。

在混合算法中，使用前文介紹的最大最小距離積法對(duì)食物源進(jìn)行初始化，得到適應(yīng)度較好的初始食物源。在雇傭蜂階段，使用K-means算法來(lái)加強(qiáng)局部尋優(yōu)能力，同時(shí)加快對(duì)目標(biāo)函數(shù)的收斂速度。由于K-means算法的快速收斂，對(duì)局部最優(yōu)值能較準(zhǔn)確的搜尋，在雇傭蜂階段就能將所有食物源的局部最優(yōu)值尋出。在ABC算法中，觀察蜂主要作用于優(yōu)質(zhì)食物源，起到加快收斂的作用；而在本算法中，由于K-means算法的作用，在雇傭蜂階段就已將所有食物源的適應(yīng)度函數(shù)收斂，替代了觀察蜂的作用，故在本算法中將雇傭蜂階段省去。通過(guò)表層膜得到的全局最優(yōu)值將作用于偵查蜂階段，偵查蜂階段主要是將食物源更新，避免整體算法陷入局部最優(yōu)值；將全局最優(yōu)值加入到食物源的更新過(guò)程，加強(qiáng)了食物源更新的目的性，有利于整體算法收斂速度的加快。

PABC-K算法的總體流程圖如圖4所示。

圖4 PABC-K算法流程圖

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

為了驗(yàn)證本文中PABC-K算法進(jìn)行聚類(lèi)的有效性，從UCI數(shù)據(jù)集中選取4組真實(shí)數(shù)據(jù)集進(jìn)行試驗(yàn)。對(duì)每組數(shù)據(jù)集，分別用K-means算法、人工蜂群（ABC）算法、文獻(xiàn)[25]中提出的ABC算法的改進(jìn)算法（Cooperative ABC,CABC算法）、文獻(xiàn)[22]中提出的融合了ABC算法和K-means算法的ABCk算法以及本文提出的結(jié)合膜計(jì)算與人工蜂群算法的K均值算法（PABC-K算法）進(jìn)行算法聚類(lèi)，并對(duì)結(jié)果進(jìn)行比較分析。

4組測(cè)試數(shù)據(jù)集分別為UCI數(shù)據(jù)集中的Wine、Iris、CMC以及Glass數(shù)據(jù)集。

表1 各算法簇間距離的比較

對(duì)于每個(gè)數(shù)據(jù)集，每個(gè)算法單獨(dú)運(yùn)行20次。表1顯示了通過(guò)20次實(shí)驗(yàn)，各算法適應(yīng)度的最優(yōu)值，最差值，平均值以及標(biāo)準(zhǔn)差。適應(yīng)度如1.1小節(jié)中公式（1）所示，數(shù)值越小，代表聚類(lèi)效果越好。

由表1中數(shù)據(jù)可以看出：K-means算法的標(biāo)準(zhǔn)差較大，對(duì)初始值具有敏感性，容易陷入局部最優(yōu)，穩(wěn)定性偏差。ABC算法、ABCk算法、CABC算法都對(duì)數(shù)據(jù)集具有較好的聚類(lèi)效果，與K-means算法相比具有較大的提高，穩(wěn)定性提高也比較大。ABCk算法是ABC算法和K-means算法的結(jié)合算法，可以看出其聚類(lèi)效果要略差于ABC算法和CABC算法，這是由于K-means算法對(duì)初始值敏感的缺點(diǎn)對(duì)該結(jié)合算法產(chǎn)生了影響，但是ABCk算法克服了ABC算法收斂緩慢的缺點(diǎn)。本文提出的PABC-K算法對(duì)聚類(lèi)也取得了比較好的結(jié)果，在4個(gè)數(shù)據(jù)集上得到的標(biāo)準(zhǔn)差都十分低，該算法的穩(wěn)定性十分好，能很好的擺脫對(duì)初始值的敏感；同時(shí)，由于K-means算法的加入，大大加快了本算法的收斂速度。

除了在Wine數(shù)據(jù)集上的聚類(lèi)結(jié)果比其余4種算法的聚類(lèi)效果稍差外，在Iris數(shù)據(jù)集、CMC數(shù)據(jù)集和Glass數(shù)據(jù)集上，都取得了很好的聚類(lèi)效果。經(jīng)過(guò)分析，Wine數(shù)據(jù)集中的樣本某一維的數(shù)據(jù)值遠(yuǎn)遠(yuǎn)大于其余維數(shù)上的數(shù)據(jù)值，在通過(guò)歐式距離進(jìn)行聚類(lèi)時(shí)，該維的數(shù)據(jù)對(duì)聚類(lèi)的結(jié)果產(chǎn)生了嚴(yán)重的影響，掩蓋了其余維數(shù)上數(shù)值間的差別。雖然該算法對(duì)數(shù)據(jù)集具有比較好的聚類(lèi)效果，但是正確分類(lèi)的準(zhǔn)確率卻不是太高。在Iris數(shù)據(jù)集上取得了約90%的準(zhǔn)確率，但是在其余3個(gè)數(shù)據(jù)集上獲得的準(zhǔn)確率并不高。這個(gè)也再次說(shuō)明基于歐氏距離進(jìn)行的聚類(lèi)有一定的限制性，并不能適用于所有的數(shù)據(jù)集。

4 結(jié)語(yǔ)

本文根據(jù)ABC算法、K-means算法和膜計(jì)算這3種算法的優(yōu)點(diǎn)和缺點(diǎn)，在膜計(jì)算的框架下，以ABC算法為基礎(chǔ)結(jié)合K-means算法，提出了PABC-K算法。以最大最小距離積法初始化蜜源，K-means算法嵌入到雇傭蜂階段加快算法收斂速度，膜計(jì)算作為整體框架涉及整個(gè)算法的各階段。算法通過(guò)在4個(gè)公開(kāi)的標(biāo)準(zhǔn)數(shù)據(jù)集上運(yùn)行，驗(yàn)證了其具有較好的聚類(lèi)效果和較高的穩(wěn)定性。根據(jù)實(shí)驗(yàn)中算法產(chǎn)生的結(jié)果以及相應(yīng)的分析，進(jìn)一步的研究將著重于對(duì)數(shù)據(jù)的預(yù)處理（如歸一化預(yù)處理等）和算法目標(biāo)函數(shù)的改進(jìn)。