基于圖形處理器的聚類分析算法研究.pdf

1、聚類分析作為一種新興的數(shù)據(jù)處理技術，近年來已成為數(shù)據(jù)挖掘中一個非?；钴S的研究方向。同時隨著實際應用中數(shù)據(jù)流的廣泛出現(xiàn)，不僅需要考慮提高聚類質(zhì)量，如何提升聚類處理速度也是一個亟需解決的問題。由于目前各種聚類算法均是采用CPu進行計算實現(xiàn)，聚類效率無法完全滿足實際需要。圖形處理器(graphics processing unit：以下簡稱GPU)具有很高的并行計算能力、超常的浮點運算速度。本文將目前幾種典型聚類算法在CPU上執(zhí)行的部分關鍵計

2、算步驟轉(zhuǎn)移到GPu上，進行非圖形繪制的通用計算處理，以提高聚類速度。 與經(jīng)典K-means算法相比，enhanced K-means算法只需處理部分點集的距離計算和比較操作，因而可使聚類效率得到較大提高。以此算法為基礎，提出了基于此算法的CPU＋GPU的協(xié)同處理模式，利用GPU多個子素處理器可以進行并行計算的特性，將算法中處理比較耗時的距離計算與比較、每次參與循環(huán)計算的點集合判斷步驟由GPu實現(xiàn)，而初始化、中心點計算、聚類結束判

3、定步驟仍由CPU實現(xiàn)，在這種協(xié)同計算模式下，可使enhanced K-means算法的聚類效率提高約35％。 其次，對經(jīng)典ROCK和VBACC層次聚類算法及改進的基于動態(tài)近鄰選擇模型的DNNS算法進行分析比較。在此基礎上，借鑒Larsen提出的利用GPU進行矩陣快速相乘的思想，將此思想和GPU多子素處理器并行處理特點結合起來，應用在DNNS算法中，即將算法中的主要運算步驟連接度矩陣計算用GPu實現(xiàn)，而建堆及合并操作由CPu完成，

4、這樣可使DNNs算法的聚類時間減少25％左右。 在一臺配有Pentium IV 3.4G CPu和NVIDIA GeForce 6800 GT顯卡的計算機上實現(xiàn)了上述基于GPU的算法和·完全由CPU完成的算法，實現(xiàn)過程中注意到CPU與GPU之間較小總線帶寬，將CPU與GPU之間的數(shù)據(jù)傳輸最小化。實驗結果表明：在具有相同聚類質(zhì)量的前提下，基于GPU的聚類算法的運算速度明顯快于傳統(tǒng)的基于CPU的聚類算法的處理速度。因此，這種GPu和