基于圖形處理器的劃分聚類算法效率研究

(1.衡陽師范學院 計算機科學技術系，湖南 衡陽421008; 2.湖南大學 計算機與通信學院， 長沙 410082)

摘 要：

提出一種利用GPU(圖形處理器)和CPU的協同計算模式來提高劃分聚類算法enhanced_K-means的計算效率。利用GPU多個子素處理器可以并行計算的特性，將算法中比較耗時的歐氏距離計算與比較、中心點改變后簇中沒有發生變化的點集合判斷步驟由GPU執行，算法其余步驟由CPU執行，使聚類效率得到顯著提高。在配有Pentium 4 3.4 GHz CPU和NVIDIA GeForce7800GT顯卡的硬件環境下經過實驗測試，證明其運算速度比完全采用CPU計算速度要快。這種改進的劃分聚類算法適合在數據流環境下對大量數據進行實時高效聚類操作。

關鍵詞：聚類分析; 圖形處理器; 通用計算; 劃分聚類

中圖分類號：TP301.6文獻標志碼：A

文章編號：1001-3695(2009)04-1276-03

Research of efficiency of partitioning clustering algorithmbased on graphics processing unit

LI Lin1， LI Ken-li 2

(1. Dept. of Computer Science Technology， Hengyang Normal University， Hengyang Hunan 421008，China; 2.College of Computer Communication， Hunan University， Changsha 410082， China)

Abstract:

This paper proposed a mode with CPU+GPU co-processing to improve the efficiency of enhanced_K-means algorithm. By the characterization that the parallel computing could be finished by the multiple fragment processor， the step that the calculation and comparison of Euclidean distance， the judgment on the point aggregation in the clustering that has no difference after the central point was changed， both of which would spent much time， were finished by GPU， while other steps were finished by CPU. Therefore the clustering efficiency was improved greatly. Some experiments conducted in a PC with Pentium 4 3.4GHz AMD 643500+ CPU and NVIDIA GeForce7800GT graphic card demonstrate that the presented algorithm is faster than the previous CPU-based algorithms， thus the improved partitional clustering algorithm 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; partitioning clustering algorithm

0 引言

隨著傳感器和計算機網絡技術的發展，在數據流環境下研究數據聚類方法，除了需要考慮聚類質量以外，聚類處理速度往往也是數據流挖掘算法的一個重要指標。由于GPU為圖形渲染設計[1]，超長流水線及并行計算和可編程性的出現，使其運算速度越來越快。鑒于其在一些非圖形繪制方面通用計算[2] 的廣泛應用:如代數計算、流體模擬、數據庫操作、頻譜變換和濾波等，本文提出了一種使用GPU(圖形處理器)和CPU協同處理聚類算法的模式， 以使聚類算法效率顯著提高。本文以enhanced_K-means算法為例，利用GPU多個子素處理器可以進行并行計算的特性，將算法中處理比較耗時的距離計算與比較、每次參與循環計算的點集合判斷步驟由GPU實現，同時考慮CPU與GPU之間的較小總線帶寬，將CPU與GPU之間的數據傳輸最小化。

1 數據流聚類算法分析

數據流聚類問題[3~5]概括來說是將連續產生的、沒有邊界的源源不斷到達的大量數據元素所組成的序列劃分為若干組，使得組內對象的相似性盡可能地高，而組間對象的相似性盡可能地低。基于劃分的方法[6]是將數據集D采用一個劃分準則（如距離），劃分為k個子集（簇， cluster），使同一個簇中的對象是相似的，不同簇中的對象是不相似的，使相應準則最優。典型的劃分方法包括K-平均算法、 K-中心點算法等。

1.1 Enhanced_K-means算法

傳統的K-means算法每次執行循環時均要計算每個數據點和所有k個中心點的距離，這對于大容量的數據庫來說，占用很大的執行時間。而改進的enhanced_K-means[7]先保留上次循環得到的所有數據點到最近簇的距離和標號，在下步循環中在計算每個數據點到對應的新簇心的距離后，若新距離比原來數據點到原簇心的距離小或者相等，則說明這個數據點還在原簇，沒有發生變化，則下次循環時不需要計算這個點到其他k-1個中心點的距離；否則這些遠離中心點的數據點就會被重新計算到其他簇中心的距離。因為在一次操作中有一定量數據點還在原簇，則意味著這部分點不參加與所有中心點的比較計算操作，從而節省了總的距離計算時間。

1.2 Enhanced_K-means算法描述

Procedure Distance( )[7]/*用數組clusterid[i]和pointdis[i]分別記錄每個數據點到最近簇的距離和標號*/

for i=1 to n

 for j=1 to k

 {d2(xi，mj);

/*計算當前點xi到所有中心mj的歐氏平方距離，找出xi的最近的點mj*/

mj = mj +xi;

nj= nj+ 1;

MSE= MSE+ d2(xi， mj)

ⅵclusterid[i]=到最近中心點的標號;

ⅶpointdis[i]=到最近點的歐氏距離;}

for j=1 to k

mj = mj／nj;

Procedure Distance_new( )[7]

for i=1 to n

{d2(xi，clusterid[i])

//計算點xi到對應新中心點的歐氏距離平方;

if (d2(xi，clusterid[i])<=pointdis[i])

//點mj仍然在原來的簇中;

else

for j=1 to k

d2(xi， mj);

/*計算點xi到所有中心mj的歐氏距離平方; 找出xi的最近的點mj*/

mj =mj+ xi;

nj= nj+ 1;

MSE= MSE+ d2(xi， mj)

clusterid[i]= 到最近的中心點的標號;

pointdis[i]=到最近點的歐氏距離 ;}

for j=1 to k

mj = mj／nj;

這兩個算法先執行procedure distance()，再執行procedure distance_new()。Enhanced_K-means算法時間復雜度是O(nk) [7]。其中:k表示中心點的個數; n表示數據點個數。比傳統算法的時間復雜度O(nkl)顯然少了一個表示循環次數的因子l，因此計算效率有一定提高。

2 基于GPU的enhanced_K-means算法實現

由于GPU的并行計算功能主要是通過多個渲染管道(它由多個并行處理單元組成的，在GeFore7800GTX中，并行處理單元的個數多達24個)和(r，g，b，α) 四個顏色通道同時計算來體現的，頂點程序的多個渲染管道意味著一個時鐘周期可以并行處理多個頂點。并行計算的實質[8]是對紋理的每個像素并行執行同一運算，該運算對像素的各顏色通道值進行計算并將結果存儲到紋理。因此本文將其并行處理的優異性能用在enhanced_ K-means算法中，通過GPU和CPU協同工作處理模式，使聚類效率優化。

2.1 GPU和CPU協同計算模式

如算法procedure distance( )和procedure distance_new( )分析所述，enhanced_ K-means算法主要計算步驟有：a)初始化；b)點間歐式距離計算與比較;c)新中心點計算;d)中心點改變后簇中沒有發生變化的點集合判斷;e)聚類結束條件判定。計算步驟分配如圖1所示。其中歐式距離計算與比較是影響時間復雜度的關鍵計算步驟，交由GPU完成;而因為中心點改變后簇中沒有發生變化的點集合判斷，是以距離計算與比較為基礎完成的，也由GPU完成，但是考慮到GPU處理累加運算不是很適合，而且在GPU計算時， CPU應該同時并行計算，所以生成中心點的計算交由CPU完成;同時初始化及聚類結束條件判定也由CPU完成。

當類標號計算結果從GPU中取回后，在CPU中將標號相同的數據點累加并生成新的中心點，然后由CPU傳回給GPU。這里GPU主要向CPU傳輸標號。為節省傳輸開銷，采用GL_BYTE模式傳輸標號，這一模式有8 bit限制，即值最高可取為256，當數值結果大于256時，算法將增加部分通信代價，執行過程中使CPU和GPU之間的通信開銷盡量降到最低是必要的。

2.2 計算方式變化

傳統基于CPU計算模式的K-means聚類算法每次計算從某個數據點到k個中心點的距離并比較這k個距離值。從而獲得離該數據點最近的中心點標號值和距離值，而在本文基于GPU+CPU模式的K-means聚類算法中，因為要對參加聚類的數據組織成紋理矩陣，對紋理中的每個數據點并行進行某個操作運算，所以要調整計算順序[9]，將原有的計算順序改為所有的數據點到某個中心點間的計算，這種計算方式可以更好地利用GPU組成紋理形式并行執行。

2.3 數據存儲轉換

利用GPU計算，首先要把這些數據組織成合適的紋理格式[8，9]，再進行矩陣計算。因為按每4維屬性構成一個數據點矩陣，即一個紋理，當數據點維度d高于4維時，d維數據即按4維劃分成不同的紋理，而每個紋理中的數據點是相對應的（圖2)。對各個紋理矩陣進行計算，并累計各距離矩陣，從而得到最終的距離矩陣。當前GPU6800最多可同時支持八個紋理單元，也就是說，在一遍計算過程中，數據點被允許計算的維數是32維，若超過32維，則采用多遍渲染的方法進行計算，并將各遍渲染結果進行累加，從而獲得最終結果。例如：GPU可同時支持s個紋理單元，則對d維數據點距離計算的渲染次數為「d/(4s)。另一方面，隨著下一代GPU發展，其可同時支持的紋理單元個數會越來越多。假設數據塊中有M個d維數據點Pi(1≤i≤M)和k個中心點Ci(1≤i≤K)。首先，Pi被組織成圖2中的矩陣(1)形式(稱為數據點矩陣N)。其中A表示矩陣的列數;R表示矩陣的行數，N=A×R。矩陣中的元素a[m][n]對應于數據點P(m-1)×A+n，1≤m≤R，1≤n≤A，一般A或R取N。之后經過對紋理的渲染操作，即進行每個數據點與某個中心點ci的距離矩陣（如圖3矩陣(2)的dis(pi，ci ))計算后，將結果存儲在深度緩存中。



2.4 數據計算比較

數據計算比較是通過硬件完成[9]的，如圖2中距離矩陣(2)。計算所有數據點與某個中心點的距離，用深度緩存保存各個數據點到中心點間的距離，每次距離矩陣都將計算完畢的結果直接存入深度緩存中，然后每次均利用硬件進行深度測試：第一次距離計算后將結果直接放入深度緩存，隨后計算出來的子素深度值如果小于深度緩存中對應的深度值，則更新深度緩存，否則保持不變；若中心點有k個，這個過程要進行k次計算，最終在深度緩存中保留每個數據點到最近的中心點的距離，從而實現距離矩陣之間距離的比較。因為模板緩存也與各像素點一一對應，用模板緩存中的模板值記錄對應數據點到最近中心點的標號值。首先將模板值初始化為1（即假設所有點是離第一個中心點最近），然后模板測試設置為通過狀態，在依次計算其他距離矩陣Di+1(1≤i

2.5 計算過程概述

算法procedure distance_new( )首先由GPU完成，在經過k個距離矩陣計算后得到計算結果，即數據點到最近中心點標號保存在模板緩存中，而數據點到到最近中心點的距離保存在深度緩存中。將數據點到到最近中心點標號送到CPU中， CPU將所有標號相同的數據點累積求平均值，得到新簇心，再將新簇心回傳給GPU。此時在圖2的紋理矩陣(2)中，因為經過初次處理后，數據分為k個子集合，各子集合中的標號是相同的，將這些標號相同的k個子集合與對應的k個新簇心ci(1

距離解出后，進行深度測試和模板測試，并在幀緩存中保留此像素。樣經過紋理矩陣的計算和測試后最終保留在幀緩存中的就應該為中心點改變后遠離原來簇中心的點集合，因此完成了中心點改變后簇中沒有發生變化的點集合判斷。

這些保留在幀緩存中的簇中心點改變后遠離原來簇中心的點集合組成新的紋理矩陣，在下次紋理渲染時，就只要對這個紋理矩陣進行上述的k次矩陣計算過程即可。此過程中CPU通過向GPU輸入新的中心點來控制聚類計算中的每一次循環。

3 實驗分析

3.1 實驗環境

實驗在一臺配有Pentium 4 3.4 GHz CPU和NVIDIA GeForce7800GT顯卡的方正PC上進行，顯卡256 MB，主存1 GB，使用操作系統為Windows XP Professional SP2。基于GPU的聚類算法采用OpenGL API加以實現，基于CPU的聚類算法用VC++6.0實現；GPU與CPU之間的紋理和數據傳送采用PCI-Express 16x作為總線接口。實驗數據采用(http://mlearn.ics.uci.edu/MLSummary.html）UCI machine learning repository中的數據集pen-based recognition of handwritten digits。這個數據集有600條記錄，將數據集的大小取在10 KB~16 MB，簇的個數為8~128，維度是4~20，數據點的各維屬性為32位的單精度浮點數。 在由CPU完全進行運算和CPU與GPU協同模式運算的兩種模式下比較算法執行的效率。

3.2 測試結果

效率評價采用算法執行時間進行度量。算法的總代價為數據I/O傳輸時間transtime和聚類計算時間clustime。基于GPU+CPU模式的算法執行時間clustime包括在GPU與CPU之間傳送數據的時間與在GPU中的計算時間(用GPU-K表示基于GPU+CPU模式的enhanced_K-means算法，用CPU-K表示基于CPU的enhanced_K-means算法，以下同此)。

圖3所示是GPU-K和CPU-K算法的聚類計算時間transtime的比較。GPU-K執行時間大概是CPU-K執行時間的45%。這是因為子素處理器的并行計算能力，現代GPU通常具有多個子素處理器，在本文進行實驗的NVIDIA GeForce 6800中有16個子素處理器，通過GPU中硬件優化的向量指令進行距離計算，從而進一步加速了聚類算法中距離計算操作。

實驗還比較了基于GPU+CPU模式和基于CPU模式的enhanced_K-means算法的總執行時間代價，如圖4所示。GPU-K執行時間約是CPU-K執行時間的65%，即GPU-K執行效率提高了35%，與圖3相比略有增加。這是因為在總的計算時間中考慮了I/O傳輸時間，這部分執行時間占總時間的一定比例，而在聚類計算分析中沒有包括I/O傳輸時間分析，所以會出現這種情況。



4 結束語

采用GPU計算enhanced_K-means算法中距離計算與比較步驟，經過測試，結果表明在具有相同聚類質量的情況下，基于GPU和CPU協同處理模式下的聚類算法效率比完全在CPU上執行的聚類算法的效率顯然要快。

這種用圖形處理器進行運算處理的方法在有源源不斷的大量數據流到達的情況下，可以滿足聚類處理對速度實時性的要求。

參考文獻：

[1]OWENS J D. The GeForce 6 series GPU architecture[K]//GPU Gems 2: streaming architectures and technology trends， 2005:453-474

[2]吳恩華.圖形處理器用于通用計算的技術、現狀及其挑戰［J］.軟件學報，2004，15(10):1495-1507.

[3]曹鋒.數據流聚類分析算法[D]:上海:復旦大學，2006:15-20.

[4]蔣盛益，李慶華，李新.數據流挖掘算法研究綜述[J]. 計算機工程與設計，2005，26(5):1130-1134.

[5]AGALWAL C C，HAN J，WANG J ， et al. A framework for clustering evolving data stream[C]//Proc of VLDB.2003:81-92.

[6]HAN Jia-wei， KAMBER M. 數據挖掘概念與技術[M].范明，孟小峰，譯.北京:機械工業出版社， 2005.

[7]FAHIM A M， SALEM A M，TORKEY F ，et al. An efficient enhanced K-means clustering algorithm[J]. Journal of Zhejiang University Science A， 2006，7(10):1626-1633.

[8]TAKIZAWA H， KOBAYASHI H. Hierarchical parallel processing of large scale data clustering on a PC cluster with GPU co-processing[J]. J Supercomput，2006，36(10):219-234.

[9]曹鋒.數據流快速聚類［J］.軟件學報， 2007，18(2):291-302.