俞 輝, 裴振奎, 陳繼東

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

一種改進的蟻群聚類算法

俞 輝, 裴振奎, 陳繼東

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

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

蟻群算法;聚類分析;數據挖掘;群體智能

0 引言

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

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

1 一種改進的蟻群聚類算法

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

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

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

1.2 改進的蟻群聚類算法分析

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

2 算法的基本原理

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

2.1 適應度函數

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

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

定義agenti當前位置的適應度函數值f(agenti)為:

其中,d(agenti,agentj)表示agenti與agentj的相似距離,也叫相異度函數.在本文中算法都采用歐氏距離作為相似距離.通常,d(agenti,agentj)越大表示越不相似,當d(agenti,agentj)接近于零或等于零時表示agenti與agentj相似或相等.適應函數f(agenti)越大,表明agenti與周圍的agent越不相似,需要跳離這個環(huán)境;當f(agenti)越小時,則表明與周圍環(huán)境相似,繼續(xù)停留在此處;當f(agenti)=0時,表明agenti周圍沒有鄰居.

2.2 移動策略

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

2.3 算法步驟

1)初始化參數設置,將樣本隨機放置于網格中;

2)進行數據預處理;

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

每個待聚類樣本在各自的Moore領域內比較領域中樣本相似度;

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

3)While(not termination);

4)for each agent do,計算agent的適應度函數值;

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

else if 0

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

6)end for;

7)end w hile;

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

2.4 算法測試與分析

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

表1是K-means算法與改進的蟻群聚類算法對測試數據的聚類結果.

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

圖1 測試數據的平面分布圖Fig.1 Plane distribution of test data

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

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

3 結論

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

[1] 段海濱.蟻群算法原理及應用[M].北京:科學出版社,2005.

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

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

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

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

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

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

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

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

[10] 洪孫焱,陸正福,申時凱,等.基于蟻群優(yōu)化的應用層多播路由算法[J].廣西師范大學學報:自然科學版,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-),男,講師,碩士,主要從事數據挖掘、智能算法及嵌入式系統(tǒng)研究,E-mail:huiyu@upc.edu.cn.