俞 輝, 裴振奎, 陳繼東

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

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

俞 輝, 裴振奎, 陳繼東

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

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

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

0 引言

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

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

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

1.1 蟻群聚類算法的優(yōu)缺點

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

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

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

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

2 算法的基本原理

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

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

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

每個螞蟻即待聚類樣本,被視為一個agenti,它的狀態(tài)記為qi,qi=(xi,yi,ci),1≤i≤N,其中xi,yi為agenti的橫坐標(biāo)與縱坐標(biāo),ci為類號.這里使用Moo re型領(lǐng)域,每個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)接近于零或等于零時表示agenti與agentj相似或相等.適應(yīng)函數(shù)f(agenti)越大,表明agenti與周圍的agent越不相似,需要跳離這個環(huán)境;當(dāng)f(agenti)越小時,則表明與周圍環(huán)境相似,繼續(xù)停留在此處;當(dāng)f(agenti)=0時,表明agenti周圍沒有鄰居.

2.2 移動策略

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

2.3 算法步驟

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

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

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

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

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

3)While(not termination);

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

5)if f(agenti)>1 then螞蟻agenti待移動,選擇除agenti的3×3區(qū)域d(agenti,agentj)最小的agent,若此處的agent周圍領(lǐng)域有空位,移動到此位置合并類號(選擇類號最小的為新的類號);

else if 0

else agenti螞蟻不移動,類號不變;

6)end for;

7)end w hile;

8)輸出所有agent的聚類信息.

2.4 算法測試與分析

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

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

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

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

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

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

3 結(jié)論

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

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

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

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

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

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

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

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

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

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

[10] 洪孫焱,陸正福,申時凱,等.基于蟻群優(yōu)化的應(yīng)用層多播路由算法[J].廣西師范大學(xué)學(xué)報:自然科學(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.