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

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

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

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