基于最大最小距離法的多中心聚類算法研究.pdf

1、數(shù)據(jù)挖掘（Data Mining）又稱為數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)（簡(jiǎn)稱KDD），是從海量的數(shù)據(jù)中挖掘出隱含的、先前未知的、對(duì)決策有潛在價(jià)值的知識(shí)和規(guī)則。它是一門(mén)新興的交叉學(xué)科，匯集了來(lái)自機(jī)器學(xué)習(xí)、模式識(shí)別、數(shù)據(jù)庫(kù)、統(tǒng)計(jì)學(xué)、人工智能等領(lǐng)域的研究成果。聚類分析作為數(shù)據(jù)挖掘系統(tǒng)中的一個(gè)模塊，既可以作為一個(gè)單獨(dú)的工具以發(fā)現(xiàn)數(shù)據(jù)庫(kù)中數(shù)據(jù)分布的深層信息，也可以作為其他數(shù)據(jù)挖掘分析算法的一個(gè)預(yù)處理步驟，因此研究如何提高聚類算法的性能具有重要的意義。

2、 K-means算法是一種典型的基于劃分的方法，該算法的優(yōu)點(diǎn)是思想簡(jiǎn)單易行，時(shí)間復(fù)雜性接近線性，對(duì)大規(guī)模數(shù)據(jù)的挖掘具有高效性和可伸縮性。但是該算法存在如下缺點(diǎn)：聚類個(gè)數(shù)K需要預(yù)先給定；算法對(duì)初值敏感；算法易陷入局部極小，并且一般只能發(fā)現(xiàn)球狀簇。 本文重點(diǎn)針對(duì)K-means算法對(duì)初值的依賴性，以及采用誤差平方和函數(shù)作為聚類準(zhǔn)則的局限性，提出了一種基于最大最小距離法的多中心聚類算法（Multiseed Clustering Algo

3、rithm based on Max-min Distance Algorithm，MCAMDA）。MCAMDA結(jié)合了多次抽樣技術(shù)，在抽樣聚類獲得的備選聚類種子集合上再次利用最大最小距離法尋找到最佳初始聚類種子，較大程度上避免了初值選擇的隨機(jī)性。該算法實(shí)現(xiàn)了輸入?yún)?shù)的知識(shí)領(lǐng)域最小化，即不要求用戶事先給出聚類的個(gè)數(shù)。 MCAMDA算法不同于K-means算法，它是一種新的多中心聚類算法，先暫時(shí)將大簇或者延伸形狀的簇分割開(kāi)，然后通

4、過(guò)應(yīng)用DBSCAN算法的小類合并策略將需要合并的小類進(jìn)行了合并，體現(xiàn)了“任何一個(gè)延伸狀或者較大形狀的簇可以用多個(gè)聚類中心來(lái)聯(lián)合代表”的思想。為了測(cè)試改進(jìn)算法的聚類性能，本文將其與K-means算法在多個(gè)數(shù)據(jù)集上進(jìn)行了對(duì)比實(shí)驗(yàn)，驗(yàn)證了改進(jìn)算法在聚類質(zhì)量和聚類穩(wěn)定性上都遠(yuǎn)優(yōu)于K-means算法。 對(duì)MCAMDA算法的時(shí)間效率進(jìn)行分析，發(fā)現(xiàn)DBSCAN算法類的擴(kuò)展漫無(wú)目的，不適合小類合并階段的具體應(yīng)用。因此提出一種改進(jìn)方法，使類的擴(kuò)展