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

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

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

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

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