基于計(jì)算智能的聚類(lèi)組合算法研究.pdf

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

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

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

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

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

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

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

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