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

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

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

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