圖形處理器在分層聚類算法中的通用計(jì)算研究

摘 要：ROCK是一種采用數(shù)據(jù)點(diǎn)間的公共鏈接數(shù)來衡量相似度的分層聚類方法，該方法對(duì)于高維、稀疏特征的分類數(shù)據(jù)具有高效的聚類效果。其鄰接度矩陣計(jì)算是影響時(shí)間復(fù)雜度的關(guān)鍵步驟，將圖形處理器(GPU)強(qiáng)大的浮點(diǎn)運(yùn)算和超強(qiáng)的并行計(jì)算能力應(yīng)用于此步驟，而其余步驟由CPU完成。基于GPU的ROCK算法的運(yùn)算效率在AMD 643500+ CPU和NVIDIA GeForce 6800 GT顯卡的硬件環(huán)境下經(jīng)過實(shí)驗(yàn)測試，證明其運(yùn)算速度比完全采用CPU計(jì)算速度要快。改進(jìn)的分層聚類算法適合在數(shù)據(jù)流環(huán)境下對(duì)大量數(shù)據(jù)進(jìn)行實(shí)時(shí)高效的聚類的操作。

關(guān)鍵詞：聚類分析; 圖形處理器； 通用計(jì)算； 分層聚類

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001-3695(2008)08-2319-03

Research of general purpose computation on hierarchical clustering

algorithm using graphics processing unit

LI Lin1，2， LI Ken-li1， ZHU Ya-li1，2

(1.College of Computer Communication， Hunan University， Changsha410082， China; 2.Dept. of Computer Science， HengyangNormal University， Hengyang Hunan 421008， China)

Abstract:This paper proposed a novel algorithm named robust clustering algorithm for categorical (ROCK) model to improve clustering quality and it was efficient for the data of high dimensionality， sparsity and categorical nature. A novel concept called common neighbors(links)， an appropriate selection of nearest neighbors， was adopted as similarity measure between a pair of points. The key step of computing adjacency matrix， which had a significant effect on the time complexity， could be implemented by GPU’s excellent performance such as the number of floating-point operations per second and the parallel processing on fragment vector processing， and the others could be finished by central processing units (CPU). Some experiments conducted in a PC with AMD 643500+ CPU and NVIDIA GeForce 6800 GT graphic card demonstrate that the presented algorithm is faster than the previous CPU-based algorithms， thus it is applicable for the clustering data stream that requiring for high speed processing and high quality clustering results.

Key words：clustering analysis; graphics processing units(GPU); general purpose computation; hierarchical clustering

數(shù)據(jù)聚類是將具體或抽象的數(shù)據(jù)集劃分為若干組或類，同一類中的數(shù)據(jù)具有盡可能大的相似性，而不同類中的數(shù)據(jù)具有盡可能大的相異性。在聚類過程中無須用戶提供先驗(yàn)的分類知識(shí)，而是根據(jù)數(shù)據(jù)實(shí)際的分布情況得到自然的聚集結(jié)果。聚類分析能夠從研究對(duì)象的特征數(shù)據(jù)中挖掘出關(guān)聯(lián)規(guī)則，發(fā)現(xiàn)在數(shù)據(jù)庫中未知的對(duì)象類，為數(shù)據(jù)挖掘提供有力的支持，是數(shù)據(jù)挖掘的重要分支，作為一種強(qiáng)有力的信息處理方法而被廣為研究。當(dāng)前主要的聚類算法有^[1]基于劃分的方法、基于層次的方法、基于密度的方法、基于網(wǎng)格的方法、基于模型的方法等。早期的聚類算法是采用距離來度量兩個(gè)數(shù)據(jù)點(diǎn)間的相似程度，如K-平均算法和K中心點(diǎn)算法。但是這種度量函數(shù)不適合分類屬性數(shù)據(jù)集的聚類，分類屬性的屬性值之間通常不存在大小等順序關(guān)系，而且分類屬性數(shù)據(jù)集通常具有高維、稀疏特征，所以采用數(shù)據(jù)點(diǎn)間的公共鏈接數(shù)來衡量相似度，筆者提出了ROCK(robust clustering algorithm for categorical)分層聚類算法^[2]。然而，隨著傳感器和計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的發(fā)展，在越來越多的實(shí)際應(yīng)用中，當(dāng)數(shù)據(jù)是以流的形式出現(xiàn)時(shí)，在數(shù)據(jù)流環(huán)境下研究數(shù)據(jù)聚類方法除了需要考慮聚類質(zhì)量以外，聚類處理速度往往也是數(shù)據(jù)流挖掘算法的一個(gè)重要指標(biāo)。由于GPU圖形處理器為圖形渲染設(shè)計(jì)，超長流水線及并行計(jì)算^[3，4]和可編程性的出現(xiàn)使其運(yùn)算速度越來越快。于是越來越多的人開始用其做一些非繪制方面的通用計(jì)算^[5]，如代數(shù)計(jì)算、流體模擬、數(shù)據(jù)庫操作、頻譜變換和濾波等。本文在分析現(xiàn)有的數(shù)據(jù)流聚類方法^[6]的同時(shí)，提出了一種使用GPU進(jìn)行計(jì)算的ROCK算法，利用GPU強(qiáng)大的浮點(diǎn)運(yùn)算能力來處理ROCK聚類算法中表示點(diǎn)間連接度的鄰接矩陣計(jì)算，通過將連接度計(jì)算操作轉(zhuǎn)移到GPU，提升了聚類挖掘速度。若將其應(yīng)用到數(shù)據(jù)流聚類操作，可滿足流聚類對(duì)實(shí)時(shí)高效處理速度的要求。同時(shí)，考慮CPU與GPU之間的較小總線帶寬，將CPU與GPU之間的數(shù)據(jù)傳輸最小化。

1 數(shù)據(jù)流聚類算法分析

數(shù)據(jù)流聚類問題概括來說是將連續(xù)產(chǎn)生的、沒有邊界的、源源不斷到達(dá)的大量數(shù)據(jù)元素所組成的序列劃分為若干組，使得組內(nèi)對(duì)象的相似性盡可能要高，而組間對(duì)象的相似性要盡可能地低。 層次聚類算法是發(fā)展較早、應(yīng)用較廣泛的一類聚類分析方法，它是采用自頂向下(分解型層次聚類方法)或自底向上(聚結(jié)型層次聚類方法)的方法在不同層次上對(duì)對(duì)象進(jìn)行分組，形成一種樹型的聚類結(jié)構(gòu)。在層次聚類方法中，要按照一定的相似性判斷標(biāo)準(zhǔn)合并最相似的部分， 或者分割最不相似的兩個(gè)部分。本文提出ROCK算法，即聚結(jié)型層次聚類方法。

1.1 ROCK聚類算法的幾個(gè)定義

定義1 兩個(gè)數(shù)據(jù)點(diǎn)間的相似度^[2]由Jaccard coefficient定義，令pi、pj

1.2 計(jì)算鄰接矩陣(adjacency matrix)

假設(shè)有N個(gè)數(shù)據(jù)點(diǎn)參加聚類， N×N表示鄰接矩陣A， 矩陣中的每個(gè)元素A[i][j]取1或0，表示數(shù)據(jù)點(diǎn)pi、pj是否是鄰居，S=A×A，S中元素表示任意兩個(gè)數(shù)據(jù)點(diǎn)之間的鏈接數(shù)。也可以采用如文獻(xiàn)[2]的方法，更加高效地計(jì)算鄰接矩陣。設(shè)C為待聚類的數(shù)據(jù)集合；鄰居列表nbrlist[i]保存數(shù)據(jù)點(diǎn)的鄰居。 計(jì)算任意兩點(diǎn)連接度的算法如下：

Procedure compute_links(C)

begin

Compute nbrlist[i] for every point i in S

Set link[i，j] to be zero for all i，j

for i=1 to n do {

N=nbrlist[i]

for j=1 to |N|-1 do

for l=j+1 to |N| do

link{N[j]，N[l]}=link{N[j]，N[l]}+1}

end

1.3 ROCK聚類算法描述

輸入:待聚類的數(shù)據(jù)集合S; 聚類簇?cái)?shù)k。

輸出:m_clusters，保存聚類結(jié)果的數(shù)組，其長度為|S|。

Cluster(S， k)

a) begin

b) link=compute_links(S)

c) for each s in S do

d) q[s]=build_local_heap(link， s)

e) Q=build_global_heap(S， q)

f) while |Q|>k do {

g) u=extract_max(Q)

h) v=max(q[u])

i) w=merge(u， v)

j) for x in (q[u] or q[v]){

k) link[x，w]=link[x，v]+link[x，u]

l) delete(q[x]，v) delete(q[x]，u)

m) insert(q[x]，w，g(x，w))

insert(w，q[x]，g(x，w))

n) update(Q，w，q[w])

o) }

p) }

q) end

1.4 ROCK聚類算法性能分析

ROCK算法時(shí)間復(fù)雜度^[2]為O(n2+nmmmα+n2log n)，空間復(fù)雜度為O(min{ n2， nmmmα}) 。其中：n為總數(shù)據(jù)點(diǎn)數(shù)，mm和 mα為一個(gè)點(diǎn)的平均近鄰數(shù)和最大近鄰數(shù)。總的建堆時(shí)間為O(n2)，執(zhí)行循環(huán)的次數(shù)為O(n2log n)。其中，鄰接矩陣的計(jì)算復(fù)雜度為O(nmmmα)，因?yàn)?mα為鄰接矩陣中每行非零元素?cái)?shù)的平均值， mm為其最大值， 鄰接矩陣的計(jì)算復(fù)雜度會(huì)隨相似度大于0的數(shù)據(jù)對(duì)的數(shù)目增長，在最壞情況下其復(fù)雜度為O(n2mα)。由此可見鄰接矩陣計(jì)算是影響時(shí)間復(fù)雜度比較關(guān)鍵的一步。

由于數(shù)據(jù)流聚類算法通常基于經(jīng)典的聚類算法，而ROCK算法正是一種采用數(shù)據(jù)點(diǎn)間的公共鏈接數(shù)作為對(duì)象間的相似性度量的經(jīng)典高效分層聚類方法。在此算法中，隨著數(shù)據(jù)流中數(shù)據(jù)塊的不斷到達(dá)，數(shù)據(jù)塊中各個(gè)數(shù)據(jù)點(diǎn)需要進(jìn)行任意兩個(gè)數(shù)據(jù)點(diǎn)之間的連接度計(jì)算，如STREAM算法對(duì)數(shù)據(jù)塊大小為B，長度為N的數(shù)據(jù)流至少需要[N/B]nmmmα次連接度計(jì)算。在每個(gè)數(shù)據(jù)塊內(nèi)數(shù)據(jù)點(diǎn)間的連接度計(jì)算過程是不變的，但是當(dāng)不斷有新的數(shù)據(jù)進(jìn)入數(shù)據(jù)塊時(shí)，數(shù)據(jù)點(diǎn)間連接度計(jì)算過程是不斷變化的，也會(huì)產(chǎn)生新的計(jì)算過程。

從上述分析可以看出， ROCK聚類算法的鄰接矩陣計(jì)算是數(shù)據(jù)流聚類中的核心操作，因而加速該核心操作可顯著提升數(shù)據(jù)流聚類算法的性能。本文是用GPU來加速數(shù)據(jù)流聚類過程中的連接度計(jì)算。下面介紹這種基于圖形處理器的ROCK算法。

2 基于圖形處理器的聚類算法

1999年GPU首先由NVIDIA公司提出，其發(fā)展速度是CPU速度的三倍多，平均每一年便有新一代的GPU誕生，運(yùn)算速度越來越快。2004年推出的GPU NVIDIA GeForce 6800 Ultra可達(dá)到峰值40 Gigaflops(1 Gigaflops=1秒鐘進(jìn)行10億次的浮點(diǎn)運(yùn)算)。2005年剛發(fā)布的NVIDIA GeForce 7800 GTX更是將峰值提高至令人驚訝的169 Gigaflops。GPU的浮點(diǎn)運(yùn)算速度發(fā)展如此之快，并行性以及可編程功能^[4]都為圖形處理以外的通用計(jì)算提供了良好的運(yùn)行平臺(tái)。

2.1 GPU中的數(shù)據(jù)表示及處理

首先，在基于GPU的聚類算法中將要進(jìn)行聚類的數(shù)據(jù)點(diǎn)組織成紋理圖像^[4] 。它可以看做是一個(gè)二維矩陣，紋理圖像的每個(gè)像素即矩陣上各元素包含四個(gè)顏色(紅、綠、藍(lán)和alpha)通道。每個(gè)通道用一個(gè)32位浮點(diǎn)數(shù)表示。并行計(jì)算功能主要是通過多個(gè)渲染管道(由多個(gè)并行處理單元組成，在GeFore 7800 GTX中，并行處理單元的個(gè)數(shù)多達(dá)24個(gè))和(r，g，b，α) 四個(gè)顏色通道同時(shí)計(jì)算來體現(xiàn)的。紋理圖像中的像素經(jīng)過渲染后，產(chǎn)生計(jì)算結(jié)果。頂點(diǎn)程序的多個(gè)渲染管道意味著一個(gè)時(shí)鐘周期可以并行處理多個(gè)頂點(diǎn)。并行計(jì)算的實(shí)質(zhì)是對(duì)紋理的每個(gè)像素并行執(zhí)行同一運(yùn)算，該運(yùn)算對(duì)像素的各顏色通道值進(jìn)行計(jì)算并將結(jié)果存儲(chǔ)到紋理。

當(dāng)內(nèi)存將源源不斷的數(shù)據(jù)流通過緩存并發(fā)送到GPU中，假定有M個(gè)d維數(shù)據(jù)點(diǎn)Pi(1≤i≤M)要進(jìn)行聚類，首先將它組織成紋理，如圖1中的數(shù)據(jù)矩陣形式(稱為數(shù)據(jù)點(diǎn)矩陣)。其中：A表示矩陣的列數(shù)；R表示矩陣的行數(shù)；M=A×R，A和R通常取M。這種矩陣組織形式便于圖形硬件更好地發(fā)揮子素并行計(jì)算。矩陣中的元素a[i][j]與數(shù)據(jù)點(diǎn)P(i-1)×A+j一一對(duì)應(yīng)。數(shù)據(jù)點(diǎn)的各個(gè)維度值將存儲(chǔ)在各紋理點(diǎn)的各個(gè)通道內(nèi)，由于每個(gè)紋理點(diǎn)限制(r，g，b，α)四個(gè)通道，高于四維的數(shù)據(jù)點(diǎn)將按每四維進(jìn)行劃分，存儲(chǔ)在不同的紋理中。因此，一個(gè)矩陣對(duì)應(yīng)于一個(gè)(或多個(gè))紋理(圖1)，并保證紋理中相同位置的紋理點(diǎn)對(duì)應(yīng)于相同的數(shù)據(jù)點(diǎn)。對(duì)于不足四維的數(shù)據(jù)點(diǎn)，可以采用減少紋理通道的辦法進(jìn)行存儲(chǔ)。存儲(chǔ)在紋理中的數(shù)據(jù)經(jīng)過子素處理程序計(jì)算后，將計(jì)算結(jié)果放在一個(gè)新的紋理中，之后經(jīng)過一系列的測試，如模板測試、深度測試、α測試等，子素只有通過這些測試才能被最終寫入幀緩存區(qū)(frame buffer)。其數(shù)據(jù)處理流程^[4，6]如圖1所示。

2.2 基于GPU的ROCK算法實(shí)現(xiàn)

因?yàn)檫B接度矩陣計(jì)算是數(shù)據(jù)流聚類中的核心操作，加速該核心操作可顯著提升數(shù)據(jù)流聚類算法的性能。筆者將1.3節(jié)ROCK算法的計(jì)算相似度鄰接矩陣的第二步交由GPU實(shí)現(xiàn)，其余步驟交由CPU實(shí)現(xiàn)，通過CPU+GPU共同協(xié)作的模式來提高本算法的執(zhí)行速度。

2.2.1 在GPU上計(jì)算相似度鄰接矩陣

此矩陣也可以定義為^[2]M(S)=S2。其中若數(shù)據(jù)點(diǎn)為N個(gè)，S=N×N。這一矩陣體現(xiàn)了數(shù)據(jù)兩點(diǎn)間的互連程度，矩陣中的元素表示了點(diǎn)Pi和Pk之間的互連度，是所有既與Pi相連、又與Pk相連的點(diǎn)對(duì)其貢獻(xiàn)之和，其時(shí)間復(fù)雜度是O(n3)。因?yàn)猷徑泳仃囀且粋€(gè)稀疏矩陣，計(jì)算矩陣中的元素如果采用如前所述的分析算法，其時(shí)間復(fù)雜度是O(nmmmα)。顯然，在CPU中運(yùn)算連接矩陣，采用1.2節(jié)分析的算法，其時(shí)間復(fù)雜度O(nmmmα)比起M(S)=S2所分析的時(shí)間復(fù)雜度O(n3)要小得多。所以用CPU處理運(yùn)算時(shí)，要避免采用矩陣的乘法進(jìn)行運(yùn)算。但是如果將GPU出色的并行處理能力和杰出的浮點(diǎn)運(yùn)算能力應(yīng)用在矩陣的乘法計(jì)算中^[7，8]，有實(shí)驗(yàn)表明^[8]當(dāng)在P44.0 Gflop/sGPU、n=1 000的環(huán)境中，計(jì)算時(shí)間為0.20±0.05 s。現(xiàn)在NVIDIA GeForce系列GPU計(jì)算速度已經(jīng)達(dá)到幾百Gflop/s，所以本文采用GPU作鄰接矩陣運(yùn)算，可以顯著提高ROCK算法中相似度鄰接矩陣的計(jì)算速度，從而可以達(dá)到在流環(huán)境下的快速聚類。

2.2.2 相似度連接矩陣的計(jì)算實(shí)現(xiàn)

矩陣相乘實(shí)現(xiàn)過程^[9]如下:設(shè)有N個(gè)d維數(shù)據(jù)點(diǎn)參加聚類，首先創(chuàng)建一個(gè)或多個(gè)N×N的紋理單元A，紋理單元中像素與矩陣中的元素一一對(duì)應(yīng)，用于紋理渲染的對(duì)象(圖2)。每個(gè)紋理點(diǎn)有(r，g，b，α)四個(gè)通道，高于四維的數(shù)據(jù)點(diǎn)將按每四維進(jìn)行劃分，存儲(chǔ)在不同的紋理中。通過fragement shader單元進(jìn)行紋理渲染后，計(jì)算結(jié)果保存在新創(chuàng)建的紋理B中，最后再將結(jié)果保存到幀緩存上(大于等于四維的矩陣相乘的計(jì)算過程如圖2所示)。

3 實(shí)驗(yàn)分析

通過對(duì)一定量數(shù)據(jù)參與聚類分析，在相同聚類質(zhì)量的情況下得到GPU對(duì)聚類算法ROCK執(zhí)行效率和CPU與GPU協(xié)同合作對(duì)聚類算法ROCK的執(zhí)行效率的實(shí)驗(yàn)比較數(shù)據(jù)，從而驗(yàn)證了以上結(jié)論。

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)在一臺(tái)裝有AMD 643500+ CPU和NVIDIA GeForce 6800GT顯卡的方正PC上進(jìn)行。顯卡具有256 MB顯存，主存1 GB。實(shí)驗(yàn)真實(shí)數(shù)據(jù)集采用ＺＯＯ標(biāo)準(zhǔn)數(shù)據(jù)庫，此數(shù)據(jù)集來自UCI MachineLearning Repository(http://www.uci.com)，共有16個(gè)屬性，101條記錄，預(yù)定義分為７個(gè)類別:1（41），２（20），３（5），４（13），５（4），６(８），７(10)。數(shù)據(jù)點(diǎn)的各維屬性為32位的單精度浮點(diǎn)數(shù)。此數(shù)據(jù)集是具有高維、稀疏特征的分類屬性數(shù)據(jù)集，比較適合用ROCK方法進(jìn)行聚類。使用操作系統(tǒng)為Windows XP Professional SP2。

3.2 算法實(shí)現(xiàn)

基于GPU的聚類算法采用OpenGL API加以實(shí)現(xiàn)，使用 Microsoft Visual Studio.NET 2003C/C++ 編譯程序代碼；GPU與CPU之間的紋理和數(shù)據(jù)傳送采用PCI-Express 16x作為總線接口。此算法完全由CPU進(jìn)行運(yùn)算，以及CPU與GPU協(xié)同運(yùn)算，在這兩種環(huán)境下比較其執(zhí)行的效率。圖3是在不同數(shù)據(jù)流量（CPU/GPU值從小到大對(duì)應(yīng)下方柱形圖的順序）的情況下，ROCK算法在兩種情況下總的耗用時(shí)間。圖4是在幾種數(shù)據(jù)量一定的情況下，由CPU進(jìn)行運(yùn)算和GPU運(yùn)算鄰接度矩陣的效率比較。

4 結(jié)束語

a）采用GPU計(jì)算ROCK算法中鄰接矩陣。經(jīng)過實(shí)驗(yàn)測試，結(jié)果表明在具有相同聚類質(zhì)量的情況下，基于GPU的聚類算法比傳統(tǒng)在CPU上執(zhí)行的聚類算法的處理速度顯然要快。

b） 這種用圖形處理器進(jìn)行運(yùn)算處理的方法在有源源不斷的大量數(shù)據(jù)流到達(dá)的情況下，可以滿足聚類處理對(duì)速度實(shí)時(shí)性的要求。參考文獻(xiàn)：

[1]HAN Jia-wei. 數(shù)據(jù)挖掘概念與技術(shù)[M].范明，孟小峰，譯.北京:機(jī)械工業(yè)出版社， 2005.

[2]GUHA S，RASTOGL R， SHLM K.ROCK:a robustclustering for categorical attributes[C]//Proc of the 15th International Conference on Data Engineering. Sydney: [s.n.]，1999.

[3]TAKIZAWA H， KOBAYASHI H.Hierarchical parallel processing of large scale data clustering on a PC cluster with GPUco-processing[J].J Super Comput，2006，36(3):219-234.

[4]OWENS J.The GeForce 6 series GPU architecture[R]// GPU Gems 2: streaming architectures and technology trends. [S.l.]: NVidia， 2005.

[5]WU En-hua. State of the art and future challenge on general purpose computation by graphics processing unit[J]. Journal of Software， 2004，15(10):1493-1504.

[6]CAO Feng. Fast clustering of data streams using graphics processors[J]. Jouranal of Software， 2007，18(2):291-302 .

[7]HALL J D， CARR N A，HART J C. Cache and bandwidth aware matrix multiplication on the GPU， U1UCDCS-R-2003-2328 [R]. Champaign:University of Illinois at Urbana，2003.

[8]LARSEN E S， McALLISTER D.Fast matrix multiplies using graphics hardware[C]// Proc of Super Computing. Denver: [s.n.]，2001:55-60.

[9]LI Ken-li，LI Zhao-peng.An adaptive parallel hierarchical clustering algorithms without memory conflicts[C]// Proc of High Performance Computation Conference. Houston: [s.n.]，2007.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文