基于計算智能的聚類組合算法研究.pdf

1、Internet的迅速發(fā)展，使得Web成為人們獲取信息的重要手段。如何幫助用戶從Web這樣海量的、動態(tài)的、半結(jié)構(gòu)化的分布式環(huán)境中發(fā)現(xiàn)潛在有用的知識已成為信息技術(shù)領(lǐng)域的熱點問題。Web數(shù)據(jù)挖掘就是為解決這一問題而產(chǎn)生的研究領(lǐng)域，研究范圍涉及關(guān)聯(lián)分析、分類分析、聚類分析、特征分析、模式序列分析、趨勢分析等。其中聚類分析作為數(shù)據(jù)挖掘的一種強有力的分析工具，得到了人們的廣泛關(guān)注，近來不斷有新的聚類分析算法出現(xiàn)。
　　 計算智能作為智能信

2、息科學(xué)發(fā)展最有生命活力的一個研究方向，正受到人們的強烈關(guān)注。它從模擬自然界生物體系和人類智能現(xiàn)象發(fā)展而來，用計算機模擬和再現(xiàn)人類的某些智能行為。計算智能包含人工神經(jīng)網(wǎng)絡(luò)、模糊邏輯和進化計算三個主要方面，它己在醫(yī)療診斷、圖象處理、模式識別、計算生物學(xué)、財經(jīng)分析、Web分析等領(lǐng)域獲得成功應(yīng)用。
　　 為改善聚類分析算法的性能，本文對基于計算智能的聚類組合方法進行了較為系統(tǒng)的研究，提出了基于多蟻群聚類組合以及基于自適應(yīng)諧振理論(ART

3、)聚類組合兩種新算法；并分析了聚類性能評價方法，提出基于有效性指數(shù)的蟻群聚類算法，它在評價性能的同時求得最佳聚類數(shù)目，并且減少孤立點。實驗結(jié)果表明，本文提出的一系列有關(guān)聚類組合的新思想和新方法都取得了良好的效果，并對文檔聚類有一定的指導(dǎo)意義。
　　 歸納起來，本文的研究工作和創(chuàng)新內(nèi)容主要表現(xiàn)在以下幾個方面：
　　 (1)改進用于聚類分析的傳統(tǒng)蟻群算法。蟻群聚類算法首先將數(shù)據(jù)對象隨機地投影到一個平面，然后每個螞蟻隨機地選擇

4、一個數(shù)據(jù)對象，根據(jù)該對象在局部鄰域的相似性而得到的概率，決定螞蟻是否“拾起”、“移動”或“放下”該對象，最后數(shù)據(jù)對象按其相似性而聚集。本文將螞蟻運動速度由單一常數(shù)設(shè)計成幾種不同類型，使之更加符合螞蟻運動規(guī)律；采用Sigmoid函數(shù)作為概率轉(zhuǎn)換函數(shù)，運算中只需調(diào)整一個參數(shù)，收斂速度更快；針對孤立點，通過參數(shù)的分時調(diào)整加快算法收斂。
　　 (2)提出蟻群聚類與蟻群優(yōu)化結(jié)合的新算法。蟻群優(yōu)化算法是模擬蟻群覓食的群體行為而提出的。如果把

5、聚類中心看作是螞蟻所要尋找的食物源，則數(shù)據(jù)聚類過程就看作是螞蟻尋求最短路徑過程。依據(jù)這一思想，本文提出基于蟻群聚類與蟻群優(yōu)化結(jié)合的聚類算法，它先由改進的單蟻群聚類算法進行聚類，生成聚類中心，再由基于蟻群轉(zhuǎn)移概率的K-means算法進行二次優(yōu)化。兩種蟻群算法巧妙結(jié)合，可以改善聚類性能。
　　 (3)提出基于聚類有效性指數(shù)的蟻群聚類算法，該算法能求得最佳聚類數(shù)目，同時減少孤立點。聚類分析是一種無監(jiān)督的學(xué)習(xí)，沒有關(guān)于分類的先驗知識，因

6、此對它們的性能進行評價非常困難。常用的評價方法分為：外部評價法、內(nèi)部評價法和相對評價法。外部評價法基于預(yù)先指定的結(jié)構(gòu)，如F-measure法。內(nèi)部評價法利用數(shù)據(jù)的固有性質(zhì)進行評價。相對評價法用于評價相同算法的參數(shù)設(shè)置不同時的結(jié)果，主要有聚類密集性、聚類鄰近性等指標。本文用基于外部評價法的F-measure和相對評價法的有效性指數(shù)評價聚類性能，同時利用基于多代表點的評價指數(shù)自動求得最佳聚類數(shù)目，并減少孤立點，克服大多數(shù)聚類算法需要事先輸入

7、聚類數(shù)目的難題。
　　 (4)提出基于超圖的蟻群聚類組合算法和多蟻群并行聚類組合算法。聚類組合的思想借鑒于分類組合，其目的是從多個聚類結(jié)果中找到一個最佳的共識聚類。這是一個具有挑戰(zhàn)性的工作，已被證明是一個NP完全型難題。一方面，聚類的模式是未標記的，由不同聚類算法得到的標記之間無明顯的聯(lián)系；另一方面，各種劃分可能含有不同的聚類個數(shù)，這就涉及到標記對應(yīng)問題。本文提出兩種基于蟻群的聚類組合新算法：一種是考慮運動速度類型各異的多個蟻群

8、，獨立進行聚類分析，然后組合其聚類結(jié)果為超圖，再用蟻群算法對超圖進行二次劃分。另一種考慮多蟻群和蟻王并行模型。兩種算法均能明顯改善聚類質(zhì)量，且能處理文檔數(shù)據(jù)集。
　　 (5)借鑒神經(jīng)網(wǎng)絡(luò)組合思想，提出基于自適應(yīng)諧振理論的聚類組合算法。自適應(yīng)諧振理論是一種能自組織地產(chǎn)生對環(huán)境識別編碼的神經(jīng)網(wǎng)絡(luò)理論模型，是無教師的學(xué)習(xí)網(wǎng)絡(luò)。本文提出一種基于自適應(yīng)諧振理論的聚類組合方法，由任意聚類算法如蟻群算法得到的初步聚類結(jié)果，作為ART神經(jīng)網(wǎng)絡(luò)的