一種基于群體智能的聚類算法CSI

1、一種基于群體智能的聚類算法CSI吳斌 史忠植（中科院計算技術研究所智能信息處理開放實驗室 北京 100080）摘要：群居性生物的群體行為涌現(xiàn)的群體智能正在成為人工智能的研究熱點。本文對基于群體智能的聚類算法進行了研究，在蟻群打掃巢穴的基本解釋模型基礎上提出了群體相似度及群體相似系數(shù)、概率轉換函數(shù)等重要概念，系統(tǒng)地形成了一種基于群體智能的聚類算法；本文還提出了一種簡化的概率轉換函數(shù)，減小了概率轉換函數(shù)參數(shù)選取的難度；接著本文分析了群體相似系數(shù)對聚類算法的重要性。實驗結果表明這種基于群體智能的聚類算法具有較好的聚類性能。關鍵字：群體智能自組織聚類群體相似度概率轉換函數(shù)1 引言科學家從豐富多彩的自然

2、界獲得了無數(shù)啟迪。群居性生物的群體行為涌現(xiàn)的群體智能正在成為人工智能的研究熱點。啟發(fā)于群居性生物的尋食、打掃巢穴等行為而設計的解決實際問題的算法獲得了令人驚奇的成功。這些算法在組合優(yōu)化、通信網(wǎng)絡和機器人領域的應用實例的數(shù)量正成指數(shù)地增長1,2,3。如果一個團隊的生存能力對于個體的生存能力是必需的則稱這個團隊提供了集體智能。Bonabeau等人認為群體智能是任何啟發(fā)于群居性昆蟲群體和其它動物群體的集體行為而設計的算法和分布式問題解決裝置4,5。群體智能的特點是最小智能但自治的個體利用個體與個體和個體與環(huán)境的交互作用實現(xiàn)完全分布式控制，并具有自組織、可擴展性、健壯性等特性。蟻群算法是群體智能具有代

3、表性的解決組合優(yōu)化問題的算法。Marco Dorigo等人將蟻群算法先后應用于TSP問題、資源二次分配問題等經(jīng)典優(yōu)化問題，得到了較好的效果3。蟻群算法在電信路由控制方面的應用被認為是目前較好的一種算法6。蟻群算法啟發(fā)于蟻群合作獲取食物的模型，它通過信息素的發(fā)布和蒸發(fā)調節(jié)螞蟻個體尋食行為，由此找到最短路徑。解決組合優(yōu)化問題的蟻群算法來源于蟻群尋食行為，而啟發(fā)于蟻群合作蟻巢分類的相關技術因為沒有系統(tǒng)的性能評價，目前還處于初步研究和概念證實的階段1 。觀察群居螞蟻的昆蟲學家發(fā)現(xiàn)：螞蟻的幼蟲和食物不是隨機地分散在蟻巢內(nèi)，而是按類別分別堆放。Deneubourg 等人提出了一種行為解釋的基本模型7，巢的

4、空間結構產(chǎn)生于簡單的局部的相互作用而不需要任何集中控制或者全局環(huán)境的表示。Beckers等人將這個模型應用于機器人技術，證明了使用幾個簡單機器人而不是一個復雜的機器人快速完成復雜任務的可能性8,9。Lumer 和 Faieta將這個模型擴展到對可以依據(jù)相似性測量比較的對象處理，證實了基本模型在數(shù)據(jù)分析中的應用10。Kuntz等人則將模型擴展應用于圖的分割問題及VLSI設計11,12。本文對基于群體智能的聚類算法進行了研究，在基本解釋模型的基礎上提出了群體相似度及群體相似系數(shù)、概率轉換函數(shù)等重要概念，系統(tǒng)地形成了一種基于群體智能的聚類算法,并提出了一種簡化的概率轉換函數(shù)。與Lumer 和 Fai

5、eta的模擬實驗數(shù)據(jù)不同，本文選用了三個標準的機器學習數(shù)據(jù)庫作為測試數(shù)據(jù)庫。算法的基本思路是：將待聚類的對象隨機放置一個兩維網(wǎng)格的環(huán)境中，每一個對象有一個隨機初始位置，每一只螞蟻能夠在網(wǎng)格上移動，并測量當前對象在局部環(huán)境的群體相似度，通過概率轉換函數(shù)將群體相似度轉換成移動對象的概率，以這個概率拾起或放下對象。蟻群聯(lián)合行動導致屬于同一等價類的對象在同一個空間區(qū)域能聚積在一起。與經(jīng)典的分級聚類算法和K均值動態(tài)聚類算法相比，基于群體智能的聚類算法CSI具有群體智能算法的共同特點，它利用個體與個體和個體與環(huán)境的交互作用，不必預設聚類中心的數(shù)目，實現(xiàn)自組織聚類過程，具有健壯性、可視化等特點。自組織是指具

6、有耗散結構、具有自催化和定向漲落機制的開放式系統(tǒng)在演變過程中呈現(xiàn)出來的全局有序現(xiàn)象，如生命現(xiàn)象、熱對流現(xiàn)象等?；谌后w智能的聚類算法CSI同樣具備自組織計算的主要特征：（1）問題結構組成的不明確性，結構的形成是系統(tǒng)在對環(huán)境信息的不斷處理中自發(fā)生成的；（2）結構變化沒有明確的方向，其知識的積累完全取決于所處理的環(huán)境信息中存在的規(guī)律性；（3）它強調大量個體的協(xié)調作用，是一個高度自主協(xié)同的過程，它通過大量的局部相互作用可以產(chǎn)生全局的整體效應。通過設計局部的個體的交互規(guī)則，可以實現(xiàn)全局自組織的功能14。本文組織如下：第2節(jié)介紹Deneubourg 提出的基本模型和相關的數(shù)據(jù)分析算法；第3節(jié)說明基于群體

7、智能的聚類算法的基本概念和思路及算法描述；第4節(jié)介紹實驗結果和分析；最后是結論。2 基本模型Chretien用Lasius niger螞蟻做了大量實驗研究的巢穴組織。工蟻能在幾小時內(nèi)將大小不同的尸體聚成幾類。在這種聚集現(xiàn)象之上的基本機制是工蟻搬動不同對象之間的吸引度：小的對象聚類中心通過吸引工蟻存放更多的同類對象變大。這是一個正反饋導致形成更大的聚類中心。在這種情況下，在環(huán)境中聚類中心的分布起到了非直接通信（stigmergy）的作用。Deneubourg等人提出蟻群聚類現(xiàn)象解釋模型。這個模型以下稱基本模型（BM）依靠的一般思想是單獨的對象將被拾起并放到其它有更多這種類型對象的地方。假設環(huán)境中

8、只有一種類型的對象，由一個當前沒有負載對象的隨機移動的螞蟻拾起一個對象的概率是： (1)其中f 是在螞蟻附近對象觀察分數(shù)(perceived fraction)，k1是門限常數(shù)：若f k1，pp接近1，（即當周圍沒有多少對象時，拾起一個對象的概率很大），若k1 f ，pp接近0，（即在一個稠密的聚類中，一個對象不大可能被移動）。一個隨機移動的負載螞蟻放下一個對象的概率是： (2)其中k2是另一個門限常數(shù)：若f k2，pd接近1，若k2 Pr則螞蟻放下此模式，將螞蟻的坐標賦給此模式，螞蟻狀態(tài)改為無負載，再隨機賦給螞蟻一個模式值，否則螞蟻繼續(xù)攜帶此模式，螞蟻狀態(tài)仍為有負載，再次隨機給螞蟻一個新坐標

9、。；步驟11、若此組所有螞蟻完成循環(huán)，則繼續(xù)，否則選取下一只未循環(huán)螞蟻轉向步驟5；步驟12、以一定的步長調整；步驟13、 若循環(huán)次數(shù)小于最大循環(huán)次數(shù)MAXCYCLENUMBER，轉向步驟4，否則程序結束。算法的結束條件可以是直接設定最大循環(huán)次數(shù)，也可用各聚類中心不再有模式移動為標準即算法已收斂。其中步驟12調整的方法可以是連續(xù)微調，也可以每循環(huán)一個固定次數(shù)后再調整，本文采用了后一種方式，此外在這一步還可調整其它參數(shù)如觀察半徑等。4. 實驗結果及分析本文測試數(shù)據(jù)都來自于UCI的() 機器學習數(shù)據(jù)庫。本文選取了三組測試數(shù)據(jù)。它們分別是動物（zoo）、鳶草（iris）和圖像(image) 數(shù)據(jù)庫。其

10、中動物數(shù)據(jù)庫為101個記錄，16個條件屬性，1個決策屬性，7 個類別分別是哺乳動物、鳥類、爬行動物、兩棲動物、魚類、昆蟲和節(jié)肢動物。鳶草是經(jīng)典聚類測試數(shù)據(jù)庫，有150個記錄，4個條件屬性，1個決策屬性，3個類別。在圖像數(shù)據(jù)庫選取了BRICKFACE、SKY和PATH共3類990個記錄，19個條件屬性，1個決策屬性。a) CSI聚類算法有效性實驗實驗1 測試數(shù)據(jù)庫ZOO記錄數(shù)101參數(shù)：=6-4, ant_number=6, r= 15,k=0.1，MAXCYCLENUMBER=200X900；size=350X350圖1ZOO實驗結果圖圖1是ZOO實驗結果圖，其中紅色表示哺乳動物；蘭色表示鳥類

11、；綠色表示爬行動物；品紅色表示兩棲動物；青色表示魚類；黃色表示昆蟲；灰色表示節(jié)肢動物。表2是ZOO實驗結果表。從實驗結果可知，CSI聚類算法不僅基本能將7種類型的動物分開，而且還得到了一些細分的結果，如紅色表示的哺乳動物被分為了三個部分，其中最大的一個類別是陸生哺乳動物共有36種動物，第二類別是4個是水生哺乳動物有4種動物，哺乳動物中很特別的卵生哺乳動物鴨嘴獸被單獨歸成第三類。表2ZOO實驗結果表原類別 新類別動物名稱1哺乳動物1陸生哺乳動物aardvark, antelope, bear, boar, buffalo, calf, cavy, cheetah, deer, elephant,

12、fruitbat, giraffe, girl, goat, gorilla, hamster, hare, leopard, lion, lynx, mink, mole, mongoose, opossum, oryx, polecat, pony, puma, pussycat, raccoon, reindeer, squirrel, vampire, vole, wallaby,wolf12水生哺乳動物porpoise, dolphin, seal,sealion,13卵生哺乳動物Platypus,7節(jié)肢動物4卵生節(jié)肢動物Clam,crab ,crayfish,lobster,oct

13、opus,seawasp,starfish 6昆蟲，7、節(jié)肢動物5昆蟲、素食節(jié)肢動物(2)Flea， gnat， honeybee， housefly， ladybird， moth ， termite， wasp， （7） worm ，（7）slug 2鳥類，3爬行動物6鳥類、素食爬行動物(2)chicken, crow, dove, duck, flamingo, gull, hawk, kiwi, lark, ostrich, parakeet, penguin, pheasant, rhea, skimmer, skua, sparrow, swan, vulture, wren， （

14、3）tortoise4魚類，7魚類bass ，carp ，catfish，chub，dogfish，haddock，seahorse,sole, tuna， herring, pike, piranha, stingray5兩棲動物，3爬行動物8兩棲動物, 卵生食肉爬行動物（5）frog ，frog，newt ，toad（3）pitviper slowworm tuatara 7節(jié)肢動物9非卵生節(jié)肢動物scorpion (7)3爬行動物10 非卵生爬行動物seasnake (3) 圖2IMAGE實驗結果圖實驗2測試數(shù)據(jù)庫IMAGE記錄數(shù)990參數(shù)：=2.5-1.5 MAXCYCLENUMBER

15、=1000X600；ant_number=10, r= 25,k=0.1， size=750X480實驗結果為圖2所示：圖中紅色表示BRICKFACE圖像模式，黃色表示SKY圖像模式，蘭色表示PATH圖像模式。從圖中可看出，CSI聚類算法具有聚類能力，能將相似模式聚積在一起。實驗3 測試數(shù)據(jù)庫iris記錄數(shù)150參數(shù)：=0.4-0.3, MAXCYCLENUMBER=200X300；size=480X450, r=20,k=0.1，ant_number=6圖3為=0.4-0.3時IRIS實驗結果圖，紅色表示類別Iris-setosa模式，蘭色表示類別Iris-versicolor模式，綠色表示

16、類別Iris-virginica模式，實驗結果如下：聚類后只有編號為107、120、134、135的共4個Iris-virginica模式與蘭色類別Iris-versicolor模式屬于在一個聚類中心。結果證明CSI聚類算法有較好的聚類性能。圖3IRIS 實驗結果圖 =0.4-0.3 b) CSI聚類算法群體相似系數(shù)實驗選用測試數(shù)據(jù)庫為iris，記錄數(shù)為150，不變參數(shù)為 size=480X450, r=20,k=0.1，ant_number=6，改變?nèi)后w相似系數(shù)值，研究群體相似系數(shù)對聚類結果的影響。 表3IRIS實驗群體相似系數(shù)與聚類結果對照表 收斂次數(shù)聚類結果1200X30雖然形成23個聚

17、類中心，但是三種類別的模式相互混在同一個聚類中心內(nèi)。0.4-0.3200X300形成24個聚類中心，類別混淆個數(shù)不大于10。0.2200X3600形成10個左右聚類中心，類別為Iris-virginicat 和Iris-versicolor的模式分散生成多個聚類中心，類別混淆個數(shù)更少。0.1未出現(xiàn)收斂，實驗次數(shù)為200X10000無聚類中心，模式仍隨機分散分布。表3是IRIS實驗群體相似系數(shù)與聚類結果對照表。從表中可看出群體相似系數(shù)對聚類結果影響很大。它不僅影響算法的收斂速度，而且影響聚類的結果，包括聚類中心的數(shù)目和聚類的質量。一般情況下，群體相似系數(shù)越小，算法收斂越慢，聚類中心個數(shù)增多，而群

18、體相似系數(shù)越大，算法收斂越快，聚類中心個數(shù)減少，但是不適當?shù)娜后w相似系數(shù)值可能導致算法太慢或不收斂和聚類結果無效即距離相差很大的模式聚在一起。5. 結論本文對基于群體智能的聚類算法進行了研究，在基本解釋模型的基礎上提出了群體相似度及群體相似系數(shù)、概率轉換函數(shù)等重要概念，系統(tǒng)地形成一種基于群體智能的聚類算法，并提出了一種相關的簡化概率轉換函數(shù)。實驗證明這一基于群體智能的聚類算法是一種自組織聚類算法，具備健壯性、可視化等特點，并能生成一些新的有意義的聚類模式。本文還通過實驗分析了群體相似系數(shù)對聚類算法的影響，實驗證明群體相似系數(shù)是聚類算法的一個關鍵參數(shù)。此算法是一種基于簡單個體與局部環(huán)境相互作用的

19、無集中控制的聚類算法，適應分布式環(huán)境，雖然目前在時間復雜性和空間復雜性方面與經(jīng)典的聚類算法相比并不具備優(yōu)勢，但是作為一種自組織聚類算法，它將提供一種分析復雜群體現(xiàn)象的方法，如客戶行為分析等。而算法本身也有許多值得研究的領域，如螞蟻添加記憶功能，群體相似系數(shù)的自適應生成，概率轉換函數(shù)的制定及局部環(huán)境等參數(shù)的影響分析等；在總體方面，算法還可增加后續(xù)的聚類中心模式生成及模式分類算法，并且算法目前還缺乏扎實的數(shù)學理論分析，同時怎樣充分利用群體智能中正反饋特性提高算法的效率也是一個值得探索的問題。 參考文獻1 .Bonabeau, M.Dorigo,G.Theraulaz, Inspiration fo

20、r optimization from social insect behaviour, Nature,vol 406,6 July 2000. 2 M.Dorigo, E.Bonabeau, G.Theralulaz, Ant Algorithms and stigmergy, Future Generation Computer Systems 16(2000) 851-871;3 T.Stutzle,H.Hoos, MAX-MIN Ant systems, Future Generation Computer Systems 16(2000) 889-914; 45 Bonabeau,E

21、.,Dorigo,M.& Theraulaz,G. Swarm Intelligence: From Natural to Artificial Systems ,Oxford Univ. Press, New York,1999;6Gianni Di Caro and Marco Dorigo, AntNet: Distributed Stigmergetic Control for Communications Networks, Journal of Artificial Intelligence Research 9(1998) 317-355;7 Deneubourg.J.L., G

22、oss S.,Frank,N., Sendova-hanks, A.,Detrain C.,Chrerien L., The dynamics of collective sorting: robot-like ants and ant-like robots, in: Meyer J., Wilson S.W. (Eds.), Proceedings of the First International Conference on Simulation of Adaptive Behavior: From Animals to Animats, MIT Press/Bradford Book

23、s, Cambridge, MA, 1991, pp.356-363;8 Becker R., Holland O.E. and Deneubourg J.L. From local actions to global tasks: Stigmergy and collective robotics, in Brooks R. and Maes P. Artificial Life IV, MIT Press, 1994;9 Holland O.E. and Melhuish C. Stigmergy, self-organisation, and sorting in collective

24、robotics, Artificial Life 5,1999,pp.173-202;10 E.Lumer, B.Faieta. Diversity and adaptation in populations of clustering ants . in J.-A.Meyer, S.W. Wilson(Eds.), Proceedings of the Third International Conference on Simulation of Adaptive Behavior: From Animals to Animats, Vol.3, MIT Press/ Bradford B

25、ooks, Cambridge, MA, 1994, pp 501-508;11 P.Kuntz,D.Snyers,P,Layzell, A stochastic heuristic for visualizing graph clusters in a bi-dimensional space prior to partitioning,Journal of Heuristics,5,1999,327-351;12P.Kuntz,P.Layzell, D.Snyers, A colony of ant-like agents for partitioning in VLSI technolo

26、gy,in: P.Husbans, I. Harvey(Eds.), Proceeding of the Fourth European Conference on Artificial Life, MIT Press,Cambridge, MA, 1997, pp.417-424;13T.Kohonen, Solf-Organizing Maps, 3.ed. ,Berlin , Springer,2001;14胡建軍，汪叔淳，現(xiàn)代智能制造中的關鍵智能技術研究綜述，中國機械工程，第11卷第7期，2000年7月，pp.828-835;(HU jian-jun,WANG shu-chun, Survey of the Key Intelligent Methods in Modern Intelligent ManufacturingState-of-the-art of Learning, evolution and Self-organizing, CHINA MECHANICAL ENGINEERING,Vol.11,No.7,2000.7. pp.828-835;)AN CLUSTERING ALGORITHM BASED ON SWARM INTELLIGENCEWu bin Shi zhongzhiThe key lab. of