基于高性能計算機并行聚類算法研究.pdf

1、當今信息化時代,各種以數(shù)據(jù)形式表達的信息幾乎以指數(shù)的量級在迅速增長,許多隱含在海量數(shù)據(jù)中的知識正等待人們?nèi)ネ诰颉⑷グl(fā)現(xiàn).作為數(shù)據(jù)庫研究、開發(fā)和應用最活躍的分支,數(shù)據(jù)挖掘—從大量數(shù)據(jù)中用非平凡的方法發(fā)現(xiàn)有用的知識--有著廣泛的應用.但是,數(shù)據(jù)挖掘面臨的是海量數(shù)據(jù)和極其復雜的運算,而以往的數(shù)據(jù)挖掘技術主要是基于傳統(tǒng)的(串行)計算機系統(tǒng),盡管人們?yōu)榱私鉀Q運算的時間和空間的復雜性問題花費了大量的精力,卻仍然得不到滿意的結(jié)果.有些數(shù)據(jù)挖掘方法,即

2、使有并行挖掘的概念,也因缺乏并行運行環(huán)境而只能在串行計算機上運行,因而大大降低了挖掘效率.隨著網(wǎng)絡技術、高性能計算機的發(fā)展,對大規(guī)模數(shù)據(jù)的分布式并行處理已成為可能.并行數(shù)據(jù)挖掘技術的研究成為當前研究熱點和今后重點發(fā)展的方向,國內(nèi)外都在進行一些數(shù)據(jù)挖掘并行算法的研究.上海大學峰值速度達到每秒4500億次浮點操作的自強2000機群系統(tǒng)為我們開展并行數(shù)據(jù)挖掘技術的研究提供了良好的基礎條件.數(shù)據(jù)聚類在數(shù)據(jù)挖掘、模式識別、圖象處理和數(shù)據(jù)壓縮等領域

3、有廣泛的應用,是數(shù)據(jù)挖掘的一個重要分支.本文總結(jié)了聚類算法的基本模型,選擇DBSCAN算法,提出幾種適合在高性能機群系統(tǒng)上運行的并行DBSCAN算法,通過實驗和比較,分析幾種并行DBSCAN算法的優(yōu)缺點.這些算法都收集在基于自強2000機群系統(tǒng)并行數(shù)據(jù)挖掘系統(tǒng)中,該系統(tǒng)除了運行算法之外,還實現(xiàn)了數(shù)據(jù)清洗、數(shù)據(jù)劃分及數(shù)據(jù)發(fā)送(發(fā)送到各個處理機上)、參數(shù)選擇及聚類質(zhì)量評估等功能.具體而言,本文的工作如下:1)分析基本的聚類算法,對它們的可并

4、行性進行討論,選擇一種聚類性能好,適合并行的聚類算法——DBSCAN算法;2)在串行DBSCAN算法基礎上提出三種并行DBSCAN算法,一種是建立在全局數(shù)據(jù)庫上的全局并行DBSCAN算法——PDBSCAN,其他兩個是基于數(shù)據(jù)分區(qū)的并行DBSCAN算法——DPDBSCAN和OPDBSCAN;3)分析比較了三種算法的優(yōu)缺點;4)建立聚類性能評估模型,向用戶反饋聚類性能信息,介紹如何指導用戶選擇相關參數(shù);5)介紹基于機群系統(tǒng)并行數(shù)據(jù)挖掘系統(tǒng)的