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

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

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

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

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