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

摘 要：目前聚類算法普遍存在對初始化參數和異常數據敏感，難以找到最優聚類以及聚類的有效性等問題。利用群體智能和多主體系統具有的自組織性、健壯性、可擴展性和簡單性等優點，給出了一種新型的優化聚類算法。在三維空間搭建主體運行環境，豐富主體的記憶、通信以及信息協調能力，增強主體的分析和判斷能力。實驗證明，該新型聚類算法具有運行速度快，準確性高以及對數據的輸入順序不敏感，能應付異常數據，處理高維、高復雜性數據等優點，可應用于圖像處理、模式識別、文檔歸類等多個領域。

關鍵詞：群體智能； 多主體系統； 聚類

中圖法分類號：TP301.6文獻標識碼：A

文章編號：1001—3695(2007)02—0030—03

1 引言

聚類又稱分割， 是將物理或抽象的數據對象集合分組， 成為由類似的對象組成的多個類， 使不同類間的相似性最小化， 而相同類內相似性最大化[1]。聚類是數據挖掘研究的一個重要方面，是一種無指導的學習過程[2]。數據聚類的研究能推動統計學、機器學習、空間數據庫技術、生物學以及市場營銷的發展。目前常見的幾大類聚類算法的基本思想有分裂法[3]、層次法[4]、基于密度的方法[5]和基于網格的方法[6]、基于模型的方法[7]。以上各種算法雖各有優點，但普遍存在對初始化參數敏感，處理異常數據困難，難以找到最優聚類以及聚類的有效性等問題。

本文利用群體智能理論和多主體系統具有的自組織性、健壯性、可擴展性、簡單性等優點[8]，在基于群體智能聚類的自動機和數學模型[9]的基礎上，給出一種新型的優化聚類算法。該算法在三維空間中搭建主體運行環境，豐富主體的記憶、通信以及信息協調能力，增強了主體的分析和判斷能力，從而增強了個體的智能性和靈活性，優化了算法性能。

2 基本理論

2.1 群體智能理論

群體智能是指無智能的主體通過合作表現出智能行為的特性。一些受群居生物筑巢、覓食、遷徙、清掃蟻穴等行為啟發而設計的算法成功地解決了組合優化、通信網絡和機器人等領域的實際問題。群體智能在沒有集中控制并且不提供全局模型的前提下，為尋找復雜的分布式問題的解決方案提供了基礎[10]。將群體智能應用于聚類算法，可使聚類算法具有與群體智能算法相同的特點，它利用個體與個體和個體與環境的交互作用，不必預設聚類中心的數目，實現自組織聚類過程，具有健壯性和可視化等特點。

2.2 多主體系統

多主體系統理論與技術的研究源自分布式人工智能(DAI)，20世紀90 年代它成了DAI領域的研究熱點，目前已在許多領域得到了廣泛的應用。多主體系統主要研究在邏輯上或物理上分離的多個主體之間進行協調智能行為，最終實現問題求解[11]。主體是具有信念、愿望、意圖、能力、選擇、承諾等心智狀態的實體，比對象的粒度更大，智能性更高，而且具有一定自主性。主體試圖自治地、獨立地完成任務，而且可以與環境交互，與其他主體通信，通過規劃達到目標。

3 基于群體智能的多主體聚類算法

基于群體智能的聚類算法起源于對蟻群、蟻卵的分類研究。Deneubourg等人提出了基本模型(Basic Model)，這種模型主要是基于對于單只螞蟻拾起、放下物體的行為方式進行建模。Lumer和Faieta將BM推廣應用到數據分析。吳斌等人在簡化分類模型的基礎上系統地提出了一種基于群體智能的聚類算法。本文在借鑒多主體系統相關思想的基礎上，提出了一種基于群體智能的MAC(Multi-Agent Clustering Algorithm，多主體聚類算法)，并將其成功應用于新聞文本的自動歸類中。

區別于以往的群體智能聚類算法，本文提出的新型聚類算法具有如下特點：

（1）將知識約簡后的數據矢量組隨機地放入一個三維空間的二維平面中。

（2）聚類主體具有一定的記憶特點。當其遇到或搭建起一個堆時，會將該堆的特征信息以及位置信息記錄下來。（3）聚類主體具有分析能力。主體在聚類過程中會遇到堆或物體，主體會自行區分這兩種不同情形，從而采取不同的行動來區別對待。

（4）聚類主體具有判斷能力。當主體拿起一個數據矢量，它首先去搜尋現有的記憶信息，如果當前數據矢量信息能夠與以往的堆進行合并，那么它會將此矢量直接歸并到相似堆中。

（5）聚類主體具有通信功能。它能夠將記憶信息傳播給其他主體，這樣就能實現聚類主體間的信息共享。

（6）聚類主體具有信息協調能力。為適應網格中數據矢量分布和堆分布的動態特性，主體需要能夠實時地去更新記憶鏈表中的堆信息，以保證信息的一致性。

以上的這些特點使群體智能中的個體有了自身的智能特性，加快了算法的收斂速度，提高了算法性能。

3.1 MAC算法中的聚類主體

根據MAC算法中聚類主體所具有的智能特性，其結構體及通信環境設計如圖1所示。

3.2 MAC算法的設計

（1）初始化

（2）各主體進行聚類

該部分為MAC算法的核心內容。所有的聚類主體均按照同樣的規則進行運動。算法流程如圖3所示。

（3）結果輸出

經過聚類主體對數據根據其相似性進行沿網格的多次搬運后，會將初試狀態下散亂的數據堆積在多個不同的網格中，如圖4所示。因此，MAC算法的聚類數目就是G中非空網格的數目，每一類所包含的數據項就是處于同一網格中的數據項。

4 實驗結果

本文采用如下兩種標準來評價聚類結果：

為了驗證所提出的基于群體智能的多主體聚類算法的有效性，本文采用新浪網的部分新聞文本進行了多次文本自動歸類試驗。試驗文本數據的主題包括教育、經濟、政治、體育、軍事、娛樂、醫療、科技八大類共503篇新聞報導。首先根據詞頻提取出每篇新聞報導的5—10個關鍵詞，并對其進行標注，對標注后的結果分別采用傳統的蟻群算法和MAC算法進行聚類。對比實驗運行結果如表1和表2所示。

由上面的結果可以分析得出，MAC算法的聚類收斂速度及準確性較傳統蟻群算法有了較大提高，MAC算法在螞蟻數為100左右時，聚類結果基本穩定，而此時傳統蟻群聚類算法的正確率約為75%，收縮率僅為66%。

實驗證明，本文提出的MAC算法具有運行速度快，準確性高以及對數據的輸入順序不敏感等優點。由于其高效性，因此該算法適用于處理高維、高復雜性數據，同時該算法也可應用于圖像處理、模式識別、經濟分析等多個領域。 

5 結論

聚類是一個古老的問題，是按照事物間的相似性進行區分和分類的過程，是一種無監督的分類。它伴隨著人類社會的產生和發展而不斷深化，已成為數據挖掘的常用技術，現已廣泛應用于圖像處理、文檔歸類、模式識別等多個領域。群集智能和多主體系統的研究雖處于初級階段，但由于其具有的自組織性、健壯性、可擴展性、簡單性等優點，已經引起越來越多的研究者的關注，并廣泛應用于組合優化、通信網絡和智能控制等領域，其必將成為以后計算機研究發展的一個重要方向。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。