基于“90-10”規(guī)則的并行層次聚類算法研究.pdf

1、隨著計算機技術(shù)的發(fā)展，信息數(shù)據(jù)越來越多，如何從海量數(shù)據(jù)中提取對人們有價值的信息已經(jīng)成為一個非常迫切的問題。由此產(chǎn)生了數(shù)據(jù)挖掘技術(shù)，它是一門新興的交叉學(xué)科，匯集了來自機器學(xué)習(xí)、模式識別、數(shù)據(jù)庫、統(tǒng)計學(xué)、人工智能等各領(lǐng)域的研究成果。聚類分析是數(shù)據(jù)挖掘中的一個重要研究領(lǐng)域。它在圖像處理、入侵檢測和生物信息學(xué)等方面有著極為重要的應(yīng)用。 由于聚類對象在高維特征空間分布的復(fù)雜性，聚類效果評價的不確定性和靈活性，以及聚類作為一個優(yōu)化問題求解的

2、高計算復(fù)雜性，聚類算法仍然面臨著眾多的問題和挑戰(zhàn)。 本文首先提出了一種新的基于“90-10”規(guī)則的并行數(shù)據(jù)預(yù)處理算法，該算法對現(xiàn)有基于“90-10”規(guī)則的預(yù)處理方法進行了改進，以減少最小生成樹構(gòu)建時的結(jié)點數(shù)目，它可使原始輸入數(shù)據(jù)的規(guī)模最多減少為原來的1/10，而不致改變聚類效果；針對目前基于SIMD模型的并行分層聚類算法存在的無法解決存儲沖突問題，應(yīng)用預(yù)處理算法，提出一種基于SIMD-EREW共享存儲模型的并行分層聚類算法。算法

3、使用O(p)個并行處理單元，在O((λn)2/p)的時間內(nèi)對n個輸入數(shù)據(jù)點進行聚類，其中1≤p≤n/logn,0.1≤λ≤0.3。將提出算法與現(xiàn)有文獻結(jié)論進行的理論性能分析表明：本算法明顯改進了現(xiàn)有文獻的研究結(jié)果，是一種自適應(yīng)無存儲沖突的并行分層聚類算法。 為了驗證本文算法的性能，利用基準測試數(shù)據(jù)集在學(xué)校高性能計算中心的IBM P690機器上進行了計算實驗。實驗結(jié)果證明了本文算法在計算時間和空間上的比較優(yōu)勢，以及對大規(guī)模數(shù)據(jù)集所