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

《一種基于群體智能的聚類算法》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在應用文檔-天天文庫。

1、一種基于群體智能的聚類算法摘要：作者：吳斌-相關文章關鍵詞：類別：專題技術來源：牛檔搜索（Niudown.COM）12　　本文系牛檔搜索（Niudown.COM）根據(jù)用戶的指令自動搜索的結果，文中內(nèi)涉及到的資料均來自互聯(lián)網(wǎng)，用于學習交流經(jīng)驗，作品其著作權歸原作者所有。不代表牛檔搜索（Niudown.COM）贊成本文的內(nèi)容或立場，牛檔搜索（Niudown.COM）不對其付相應的法律責任！12一種基于群體智能的聚類算法CSI吳斌史忠植（中科院計算技術研究所智能信息處理開放實驗室北京100080）摘要：　群居性生物的群體行為涌

2、現(xiàn)的群體智能正在成為人工智能的研究熱點。本文對基于群體智能的聚類算法進行了研究，在蟻群打掃巢穴的基本解釋模型基礎上提出了群體相似度及群體相似系數(shù)、概率轉換函數(shù)等重要概念，系統(tǒng)地形成了一種基于群體智能的聚類算法；本文還提出了一種簡化的概率轉換函數(shù)，減小了概率轉換函數(shù)參數(shù)選取的難度；接著本文分析了群體相似系數(shù)對聚類算法的重要性。實驗結果表明這種基于群體智能的聚類算法具有較好的聚類性能。關鍵字：群體智能　自組織聚類　群體相似度　概率轉換函數(shù)1．引言科學家從豐富多彩的自然界獲得了無數(shù)啟迪。群居性生物的群體行為涌現(xiàn)的群體智能正在成

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

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

5、不是隨機地分散在蟻巢內(nèi)，而是按類別分別堆放。Deneubourg等人提出了一種行為解釋的基本模型[7]，巢的空間結構產(chǎn)生于簡單的局部的相互作用而不需要任何集中控制或者全局環(huán)境的表示。Beckers等人將這個模型應用于機器人技術，證明了使用幾個簡單機器人而不是一個復雜的機器人快速完成復雜任務的可能性[8,9]。Lumer和Faieta將這個模型擴展到對可以依據(jù)相似性測量比較的對象處理，證實了基本模型在數(shù)據(jù)分析中的應用[10]。Kuntz等人則將模型擴展應用于圖的分割問題及VLSI設計[11,12]。本文對基于群體智能的聚類

6、算法進行了研究，在基本解釋模型的基礎上提出了群體相似度及群體相似系數(shù)、概率轉換函數(shù)等重要概念，系統(tǒng)地形成了一種基于群體智能的聚類算法,并提出了一種簡化的概率轉換函數(shù)。與Lumer和12Faieta的模擬實驗數(shù)據(jù)不同，本文選用了三個標準的機器學習數(shù)據(jù)庫作為測試數(shù)據(jù)庫。算法的基本思路是：將待聚類的對象隨機放置一個兩維網(wǎng)格的環(huán)境中，每一個對象有一個隨機初始位置，每一只螞蟻能夠在網(wǎng)格上移動，并測量當前對象在局部環(huán)境的群體相似度，通過概率轉換函數(shù)將群體相似度轉換成移動對象的概率，以這個概率拾起或放下對象。蟻群聯(lián)合行動導致屬于同一等

7、價類的對象在同一個空間區(qū)域能聚積在一起。與經(jīng)典的分級聚類算法和K均值動態(tài)聚類算法相比，基于群體智能的聚類算法CSI具有群體智能算法的共同特點，它利用個體與個體和個體與環(huán)境的交互作用，不必預設聚類中心的數(shù)目，實現(xiàn)自組織聚類過程，具有健壯性、可視化等特點。自組織是指具有耗散結構、具有自催化和定向漲落機制的開放式系統(tǒng)在演變過程中呈現(xiàn)出來的全局有序現(xiàn)象，如生命現(xiàn)象、熱對流現(xiàn)象等?；谌后w智能的聚類算法CSI同樣具備自組織計算的主要特征：（1）問題結構組成的不明確性，結構的形成是系統(tǒng)在對環(huán)境信息的不斷處理中自發(fā)生成的；（2）結構變

8、化沒有明確的方向，其知識的積累完全取決于所處理的環(huán)境信息中存在的規(guī)律性；（3）它強調(diào)大量個體的協(xié)調(diào)作用，是一個高度自主協(xié)同的過程，它通過大量的局部相互作用可以產(chǎn)生全局的整體效應。通過設計局部的個體的交互規(guī)則，可以實現(xiàn)全局自組織的功能[14]。本文組織如下：第2節(jié)介紹Deneubourg提出的基本模型和相關的數(shù)據(jù)分析算