俞 輝, 裴振奎, 陳繼東

(中國(guó)石油大學(xué)(華東)計(jì)算機(jī)與通信工程學(xué)院 山東東營(yíng)257061)

一種改進(jìn)的蟻群聚類(lèi)算法

俞 輝, 裴振奎, 陳繼東

(中國(guó)石油大學(xué)(華東)計(jì)算機(jī)與通信工程學(xué)院 山東東營(yíng)257061)

針對(duì)現(xiàn)有蟻群聚類(lèi)中將帶聚類(lèi)樣本放于網(wǎng)格進(jìn)行聚類(lèi)的算法存在隨機(jī)移動(dòng)而延長(zhǎng)聚類(lèi)時(shí)間,及大數(shù)據(jù)集進(jìn)行蟻群聚類(lèi)時(shí)收斂速度慢的缺點(diǎn),在蟻群進(jìn)行聚類(lèi)前增加數(shù)據(jù)預(yù)處理.利用兩元素越相似屬于同一類(lèi)簇的可能性越大的思想,將樣本集中的樣本量縮小.研究了通過(guò)信息素進(jìn)行聚類(lèi)的蟻群聚類(lèi)算法,使算法中的“螞蟻”在一定指導(dǎo)下進(jìn)行聚類(lèi),達(dá)到縮短時(shí)間的目的.最后通過(guò)實(shí)驗(yàn)驗(yàn)證了所提出算法的有效性和優(yōu)越性.

蟻群算法;聚類(lèi)分析;數(shù)據(jù)挖掘;群體智能

0 引言

蟻群算法是一種新型的模擬進(jìn)化算法,用蟻群在搜索食物源的過(guò)程中所體現(xiàn)出來(lái)的尋優(yōu)能力來(lái)解決一些離散系統(tǒng)優(yōu)化中的困難問(wèn)題.蟻群算法是一種模擬螞蟻群體覓食行為的仿生優(yōu)化算法,該算法采用了正反饋并行自催化機(jī)制,具有較強(qiáng)的魯棒性、優(yōu)良的分布式計(jì)算機(jī)制及易于與其他方法相結(jié)合等優(yōu)點(diǎn),在解決許多復(fù)雜優(yōu)化問(wèn)題方面已經(jīng)展現(xiàn)出其優(yōu)異的性能和巨大的發(fā)展?jié)摿1-2].聚類(lèi)分析也稱(chēng)聚類(lèi),是多元統(tǒng)計(jì)分析的一種,同時(shí)也是數(shù)據(jù)挖掘中的重要研究領(lǐng)域,是數(shù)據(jù)分組和劃分處理的重要手段.聚類(lèi)的目標(biāo)是在沒(méi)有任何先驗(yàn)知識(shí)的前提下,根據(jù)樣本自身的相似性劃分成若干個(gè)子集,使相似的樣本盡可能歸為一類(lèi),而不相似的盡量劃分到不同的類(lèi)中.因此,聚類(lèi)又稱(chēng)無(wú)監(jiān)督分類(lèi),在圖像分割、醫(yī)學(xué)診斷、天氣預(yù)報(bào)、礦藏識(shí)別及商務(wù)領(lǐng)域等有著廣泛的應(yīng)用[3].蟻群聚類(lèi)算法研究力求對(duì)大數(shù)據(jù)集進(jìn)行聚類(lèi)時(shí)能夠在保證聚類(lèi)質(zhì)量的情況下,縮短聚類(lèi)的執(zhí)行時(shí)間,降低算法對(duì)經(jīng)驗(yàn)知識(shí)的弱依賴(lài)性.但是由于目前存在的一些聚類(lèi)算法在聚類(lèi)參數(shù)設(shè)置、聚類(lèi)結(jié)果及算法執(zhí)行時(shí)間上都不夠理想,一直沒(méi)能夠自動(dòng)控制聚類(lèi)簇?cái)?shù)目和在保證聚類(lèi)結(jié)果較好的情況下得到更理想的運(yùn)行時(shí)間.

考慮到提出的蟻群聚類(lèi)算法聚類(lèi)時(shí)所存在的缺陷[4],根據(jù)遺傳算法的機(jī)理、工作過(guò)程,將遺傳算法思想引入蟻群聚類(lèi)算法中,提出了混合遺傳算法思想的蟻群聚類(lèi)算法,研究了通過(guò)信息素進(jìn)行聚類(lèi)的蟻群聚類(lèi)算法,并通過(guò)實(shí)驗(yàn)驗(yàn)證了所提出算法的有效性和優(yōu)越性.

1 一種改進(jìn)的蟻群聚類(lèi)算法

1.1 蟻群聚類(lèi)算法的優(yōu)缺點(diǎn)

與聚類(lèi)分析的典型要求對(duì)照,可以看出采用蟻群算法進(jìn)行聚類(lèi)的優(yōu)缺點(diǎn).蟻群聚類(lèi)算法的優(yōu)勢(shì):首先,蟻群聚類(lèi)算法的聚類(lèi)中心的個(gè)數(shù)是由樣本集中數(shù)據(jù)本身的特點(diǎn)產(chǎn)生的,因此極大克服了傳統(tǒng)聚類(lèi)算法聚類(lèi)簇?cái)?shù)預(yù)先設(shè)定的缺陷,這體現(xiàn)了對(duì)先驗(yàn)知識(shí)的弱依賴(lài)性[5].其次,算法在預(yù)處理階段就將數(shù)據(jù)對(duì)象隨機(jī)地分布在一個(gè)二維的網(wǎng)格空間中,數(shù)據(jù)對(duì)象屬性個(gè)數(shù)的增加對(duì)算法的性能沒(méi)有太大影響,即算法具有很好的伸縮性;預(yù)處理同時(shí)也降低了算法對(duì)輸入樣本順序的敏感程度.由于采用了基于密度的算法,因此能夠得到不同形狀的聚類(lèi)結(jié)果,滿足了對(duì)發(fā)現(xiàn)任意形狀聚類(lèi)的要求.

蟻群聚類(lèi)算法最明顯的缺陷就是若要得到高質(zhì)量的聚類(lèi)結(jié)果,算法的計(jì)算效率不高,尤其是對(duì)大樣本集進(jìn)行聚類(lèi)時(shí)[6].另一方面,蟻群聚類(lèi)算法需要預(yù)先設(shè)定“螞蟻”的數(shù)目以及環(huán)境參數(shù),而螞蟻數(shù)目及環(huán)境參數(shù)的確定是由具體聚類(lèi)樣本集的大小決定,因此也影響了算法的可伸縮性.經(jīng)分析可知,蟻群聚類(lèi)算法的突出問(wèn)題就是算法的計(jì)算效率低,以及對(duì)大樣本集的適應(yīng)能力差[7].由于蟻群聚類(lèi)算法具有分布式計(jì)算、自組織、可擴(kuò)展性、健壯性等特點(diǎn),因此可以采用控制策略決定螞蟻的移動(dòng),從而提高算法效率.

1.2 改進(jìn)的蟻群聚類(lèi)算法分析

提出的基于信息素的蟻群聚類(lèi)算法,考慮到聚類(lèi)對(duì)象的數(shù)量過(guò)大,而螞蟻的數(shù)量又會(huì)對(duì)聚類(lèi)的速度有所影響,因此,進(jìn)行蟻群算法聚類(lèi)時(shí)先對(duì)樣本進(jìn)行數(shù)據(jù)預(yù)處理.利用越相似的樣本屬于同一類(lèi)的可能性越大的思想,在算法的預(yù)處理階段采用基于最近鄰優(yōu)先的聚類(lèi)算法進(jìn)行聚類(lèi).將待聚類(lèi)樣本集隨機(jī)分布在一個(gè)二維網(wǎng)格中,對(duì)每個(gè)樣本周?chē)I(lǐng)域相似的樣本進(jìn)行合并,縮小樣本個(gè)數(shù),減少下一步的數(shù)據(jù)處理量.為避免在傳統(tǒng)的蟻群聚類(lèi)算法中的螞蟻沒(méi)有走過(guò)路徑上的數(shù)據(jù)一直沒(méi)有被選擇的機(jī)會(huì),將經(jīng)過(guò)預(yù)處理后的待聚類(lèi)樣本視為一個(gè)一個(gè)的螞蟻,根據(jù)螞蟻的環(huán)境決定螞蟻的活動(dòng),控制螞蟻活動(dòng)的數(shù)量[8].通過(guò)信息素量以及相似度決定螞蟻移動(dòng)的位置和方向,算法執(zhí)行中調(diào)整這兩個(gè)參數(shù)在不同階段的側(cè)重點(diǎn),由算法起始主要依靠信息素濃度來(lái)選擇移動(dòng)位置到經(jīng)過(guò)一段時(shí)間的迭代后調(diào)整到依靠聚類(lèi)的相似度來(lái)決定的方法,指導(dǎo)螞蟻的運(yùn)動(dòng),提高算法的運(yùn)行效率.

2 算法的基本原理

改進(jìn)的蟻群聚類(lèi)算法是基于具有睡眠與活躍兩種狀態(tài)相結(jié)合的一種蟻群聚類(lèi)算法,通過(guò)螞蟻所處的環(huán)境決定螞蟻的活動(dòng).這不僅動(dòng)態(tài)地決定了螞蟻的數(shù)量,也解決了螞蟻隨機(jī)移動(dòng)而浪費(fèi)大量時(shí)間進(jìn)行無(wú)用移動(dòng)的缺陷,使算法在更快的時(shí)間內(nèi)達(dá)到聚集成簇的活動(dòng).

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

改進(jìn)的蟻群聚類(lèi)算法中將數(shù)據(jù)視為一個(gè)一個(gè)的螞蟻,螞蟻根據(jù)周?chē)h(huán)境的適應(yīng)度函數(shù)值來(lái)決定自身的狀態(tài),即是繼續(xù)呆在原地還是移動(dòng).由螞蟻所處的環(huán)境決定其行動(dòng),可以避免遺漏待聚類(lèi)樣本,一定程度地提高聚類(lèi)質(zhì)量.

每個(gè)螞蟻即待聚類(lèi)樣本,被視為一個(gè)agenti,它的狀態(tài)記為qi,qi=(xi,yi,ci),1≤i≤N,其中xi,yi為agenti的橫坐標(biāo)與縱坐標(biāo),ci為類(lèi)號(hào).這里使用Moo re型領(lǐng)域,每個(gè)agenti鄰居為其3×3區(qū)域的其他agent,并記為N(agenti).

定義agenti當(dāng)前位置的適應(yīng)度函數(shù)值f(agenti)為:

其中,d(agenti,agentj)表示agenti與agentj的相似距離,也叫相異度函數(shù).在本文中算法都采用歐氏距離作為相似距離.通常,d(agenti,agentj)越大表示越不相似,當(dāng)d(agenti,agentj)接近于零或等于零時(shí)表示agenti與agentj相似或相等.適應(yīng)函數(shù)f(agenti)越大,表明agenti與周?chē)腶gent越不相似,需要跳離這個(gè)環(huán)境;當(dāng)f(agenti)越小時(shí),則表明與周?chē)h(huán)境相似,繼續(xù)停留在此處;當(dāng)f(agenti)=0時(shí),表明agenti周?chē)鷽](méi)有鄰居.

2.2 移動(dòng)策略

改進(jìn)的蟻群聚類(lèi)算法移動(dòng)策略:根據(jù)螞蟻周?chē)沫h(huán)境情況f(agenti)決定螞蟻是移動(dòng)還是留在原地,有策略性的指導(dǎo)螞蟻的活動(dòng),提高算法的運(yùn)行效率.若f(agenti)>1,則螞蟻準(zhǔn)備跳出當(dāng)前環(huán)境,選擇螞蟻所處的Moo re領(lǐng)域外最相似的螞蟻,若此處將合并的螞蟻周?chē)I(lǐng)域有空位,移動(dòng)到此位置;若0

2.3 算法步驟

1)初始化參數(shù)設(shè)置,將樣本隨機(jī)放置于網(wǎng)格中;

2)進(jìn)行數(shù)據(jù)預(yù)處理;

for(i=0;i≤n;i++)//n為樣本集中的樣本個(gè)數(shù),

每個(gè)待聚類(lèi)樣本在各自的Moore領(lǐng)域內(nèi)比較領(lǐng)域中樣本相似度;

if兩樣本相似度≤最小閾值d,則兩樣本合并成一個(gè),合并位置為較小者的位置,并視為一個(gè)agent;對(duì)每個(gè)agent標(biāo)號(hào),類(lèi)號(hào)設(shè)為標(biāo)號(hào);

3)While(not termination);

4)for each agent do,計(jì)算agent的適應(yīng)度函數(shù)值;

5)if f(agenti)>1 then螞蟻agenti待移動(dòng),選擇除agenti的3×3區(qū)域d(agenti,agentj)最小的agent,若此處的agent周?chē)I(lǐng)域有空位,移動(dòng)到此位置合并類(lèi)號(hào)(選擇類(lèi)號(hào)最小的為新的類(lèi)號(hào));

else if 0

else agenti螞蟻不移動(dòng),類(lèi)號(hào)不變;

6)end for;

7)end w hile;

8)輸出所有agent的聚類(lèi)信息.

2.4 算法測(cè)試與分析

改進(jìn)的蟻群聚類(lèi)算法的有效性測(cè)試采用經(jīng)典的聚類(lèi)算法K-means算法[9]與之比較,測(cè)試數(shù)據(jù)為13個(gè)二維數(shù)據(jù).K-means算法參數(shù)設(shè)定聚類(lèi)簇?cái)?shù)k=3,ε=0.1.改進(jìn)的蟻群聚類(lèi)算法的網(wǎng)格數(shù)設(shè)為ceil(sqrt(n))×ceil(sqrt(n))=16個(gè),n=13;初始數(shù)據(jù)預(yù)處理階段,最小閾值d=1;循環(huán)次數(shù)為10次.圖1是測(cè)試數(shù)據(jù)的平面分布圖.

表1是K-means算法與改進(jìn)的蟻群聚類(lèi)算法對(duì)測(cè)試數(shù)據(jù)的聚類(lèi)結(jié)果.

由表1可以看出,改進(jìn)的蟻群聚類(lèi)算法在聚類(lèi)簇?cái)?shù)及正確率上與K-means算法的正確率一致,因此可以驗(yàn)證算法的有效性,同時(shí),在得到最終結(jié)果的循環(huán)次數(shù)上相比,改進(jìn)的蟻群聚類(lèi)算法要比K-means算法更好.

圖1 測(cè)試數(shù)據(jù)的平面分布圖Fig.1 Plane distribution of test data

表1 2種算法的聚類(lèi)結(jié)果Tab.1 Clustering resultsof two algo rithm s

該算法的數(shù)據(jù)預(yù)處理很重要,算法數(shù)據(jù)預(yù)處理環(huán)節(jié)中的最小閾值設(shè)的好則能有效減少樣本,降低循環(huán)階段的樣本處理量,一定程度地提高算法的執(zhí)行效率.若最小閾值設(shè)的過(guò)小則達(dá)不到數(shù)據(jù)預(yù)處理的效果,還浪費(fèi)時(shí)間,若最小閾值設(shè)的過(guò)大則很有可能把一些距離較近的孤立點(diǎn)合并進(jìn)去,失去了蟻群聚類(lèi)算法的優(yōu)勢(shì)[10].同時(shí),由于算法在網(wǎng)格設(shè)置上是根據(jù)待聚類(lèi)的數(shù)據(jù)量來(lái)決定網(wǎng)格的多少,使得樣本的分布很集中,因此可視化效果方面不夠理想,若樣本分布在正好的網(wǎng)格中,在預(yù)處理環(huán)節(jié)的最小閾值設(shè)置不合理,則算法聚類(lèi)結(jié)果也不夠理想.若在一個(gè)大的網(wǎng)格上進(jìn)行聚類(lèi),則算法又對(duì)孤立點(diǎn)處理不理想,尤其是當(dāng)樣本分布很散的情況下.

3 結(jié)論

改進(jìn)的蟻群聚類(lèi)算法充分利用最近鄰優(yōu)先吸收的思想,在數(shù)據(jù)預(yù)處理階段降低樣本集中的樣本量,使算法執(zhí)行的處理量數(shù)據(jù)減少,本文在解決大樣本集聚類(lèi)問(wèn)題具有較大的實(shí)用價(jià)值.基于蟻群的聚類(lèi)算法研究目前仍然是一個(gè)十分活躍的研究領(lǐng)域,盡管作者的研究工作取得了一些有意義的成果,但還不是最優(yōu)的聚類(lèi)方法,同時(shí)聚類(lèi)的結(jié)果還有待進(jìn)一步提高,執(zhí)行時(shí)間也需要進(jìn)一步縮短.對(duì)算法進(jìn)行預(yù)處理的同時(shí)也增加了經(jīng)驗(yàn)閾值的設(shè)置,違背了對(duì)先驗(yàn)知識(shí)弱依賴(lài)性的初衷,而且經(jīng)驗(yàn)閾值的大小將直接關(guān)系到數(shù)據(jù)預(yù)處理后的待聚類(lèi)數(shù)據(jù)量.今后應(yīng)力求通過(guò)改進(jìn)預(yù)處理部分減少數(shù)據(jù)量,降低蟻群聚類(lèi)部分的處理時(shí)間,以及蟻群算法與遺傳算法的結(jié)合部分,使蟻群聚類(lèi)算法在更迅速地進(jìn)行聚類(lèi)的同時(shí),又避免陷入局部最優(yōu)以達(dá)到更理想的聚類(lèi)結(jié)果及效率.

[1] 段海濱.蟻群算法原理及應(yīng)用[M].北京:科學(xué)出版社,2005.

[2] 曹軍民,裴紅星,王長(zhǎng)松.基于蟻群算法的連鑄二冷優(yōu)化[J].鄭州大學(xué)學(xué)報(bào):理學(xué)版,2009,41(4):112-115.

[3] 高新波.模糊聚類(lèi)分析及其應(yīng)用[M].西安:西安電子科技大學(xué)出版社,2004.

[4] 李士勇,陳永強(qiáng),李妍,等.蟻群算法及其應(yīng)用[M].哈爾濱:哈爾濱工業(yè)大學(xué)出版社,2004:14-18.

[5] 焦李成,劉芳,緱水平,等.智能數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)[M].西安:西安電子科技大學(xué)出版社,2006.

[6] 束建華,倪志偉,楊善林.基于蟻群優(yōu)化的分類(lèi)規(guī)則挖掘方法[J].廣西師范大學(xué)學(xué)報(bào):自然科學(xué)版,2007,25(4):230-233.

[7] 胡建軍,唐常杰,李川,等.基于最近鄰優(yōu)先的高效聚類(lèi)算法[J].四川大學(xué)學(xué)報(bào):工程科學(xué)版,2004,36(6):93-99.

[8] 徐曉華,陳崚.一種自適應(yīng)的螞蟻聚類(lèi)算法[J].軟件學(xué)報(bào),2006,17(9):1884-1889.

[9] 行小帥,潘進(jìn),焦李成.基于免疫規(guī)劃的K-means聚類(lèi)算法[J].計(jì)算機(jī)學(xué)報(bào),2003,26(5):605-609.

[10] 洪孫焱,陸正福,申時(shí)凱,等.基于蟻群優(yōu)化的應(yīng)用層多播路由算法[J].廣西師范大學(xué)學(xué)報(bào):自然科學(xué)版,2008,26(3): 230-233.

An Improved Ant Colony Clustering Algorithm

YU Hui, PEIZhen-kui, CHEN Ji-dong
(College of Com puter&Comm unication Engineering,China University of Petroleum,Dongying 257061,China)

To shorten clustering time in ant colony algo rithm(ACA)and speed up convergence rate of large data sets,data p rep rocessing is adop ted before ant colony clustering algorithm (ACCA).M eanw hile,clustering speed is studied through the pheromone of ACCA,and ants in the algorithm should be guided by certain information.In order to test the validity of the algorithm s,K-means and the basic ant colony clustering are compared at the same time.The experimental results show the effectiveness of the p roposed app roach.

ant colony algorithm;clustering analysis;data mining;swarm intelligence

TP 181

A

1671-6841(2010)03-0059-04

2010-05-26

俞輝(1974-),男,講師,碩士,主要從事數(shù)據(jù)挖掘、智能算法及嵌入式系統(tǒng)研究,E-mail:huiyu@upc.edu.cn.