1 引言

聚類（Clustering）是數據挖掘領域最為重要的技術之一。是根據相似性對數

據庫中的對象進行分組, 使得不同類中的數據盡可能相異而同一類中的數據盡

可能相同，從而發現數據空間的分布特征。聚類分析在很多領域有著廣泛的應

用，如模式識別、圖象處理和數據壓縮等等；另外也在數據挖掘的初級階段，

也常常采用聚類來去除異常值的影響。目前存在的聚類算法總體來說可以分為

基于密度的聚類方法、分割的聚類方法、層次聚類方法、網格的聚類方法等幾

類，其中的代表算法分別有DBSCAN, k-means, Birch，Clique等等。

隨著數據庫規模的擴大，實際的應用需求對聚類分析任務提出了更高的要求：

要求算法具有能快速準確對大規模數據庫聚類。這種情況下，傳統的串行算

法，無論是內存還是運算速度都無法滿足實際需求。這時，并行計算，尤其是

分布式并行計算逐漸引起了人們的注意。

計算機集群是一種新興的分布式計算系統。由于其出色的性價比、靈活性和良

好的并行處理能力，計算機集群目前已經引起數據挖掘領域一些研究者的關

注。例如，文獻[1]利用集群系統實現了k-means算法的并行化。然而，相對于

串行算法或者在共享內存的系統中實現的并行算法來說，面向集群計算系統的

并行算法更難實現，這方面的研究剛剛起步，至今鮮有相關研究成果。

本文提出一種新的基于DBSCAN算法的并行聚類算法，并在計算機集群系統中實

現了該算法，實驗證明此并行算法是行之有效的，幾乎具有線性加速的能力。

2 DBSCAN算法介紹

DBSCAN算法^[2]是基于密度的聚類算法，主要面向諸如地理信息等空間數據庫進行聚類

分析。其主要思想為：如果一個對象在半徑為ε的領域內包含至少MinPts個對象，那么該

區域是密集的。對數據庫中任何一個點，對其進行區域查詢，判斷是否是核心點，如是，

建立新類C，p及其鄰域內的點均屬于該類�？疾�C中尚未被考察過的點q，若q是核心點，

則將其領域內未屬于任何一類的點追加到類C。不斷重復此過程，直到沒有新的點可以追

加為止。類C是一個密度相連的，基于密度可達性最大的點集。以同樣程序尋找其它的

類，不屬于任何類的點為噪聲

DBSCAN算法的復雜度為O(n²)，其中n是對象的總數。為了提高聚類效率,DBSCAN算法采用

空間數據庫索引R*-樹^[3]來實現區域搜索（region query），使計算復雜度降

為O(nlogn)。

DBSCAN算法的優點是能夠發現任意形狀的類，并且不受噪聲的影響。然而空間數據庫的規

模通常很大，當面臨大規模數據庫時，DBSCAN算法的I/O開銷很大，聚類速度不能適應實

際需要：DBSCAN算法在聚類前,需要建立R*-樹，另外,DBSCAN要求用戶指定一個全局EPS參

量。為了確定EPS值,需要計算數據庫中任意點與它的第k個最鄰近點間的距離.然后,根據

求得的距離由小到大進行排序,并繪出排序后的圖，稱作k-dist圖，通常將k固定為4。R*-

樹的建立和k-dist圖的繪制都是非常消耗時間的過程，當面對的數據庫規模很大時，

DBSCAN串行算法的計算效率低下。

針對DBSCAN算法在內存及計算速度方面的限制，本文提出一種面向計算機集群

的新的并行聚類算法。因為要把數據庫劃分成塊分配到計算機集群網格中進行

計算，此算法也稱作Grid Parallel DBSCAN, 簡稱GP-DBSCAN.

3 GP-DBSCAN算法

3.1 計算機集群計算系統

并行計算領域中，計算機集群是個很新的概念，它是利用網絡，將一組高性能

工作站或PC機，按照某種結構連接起來，形成一個高效并行處理的計算網格。

每個結點上都有完整的操作系統、網絡和用戶界面，結點之間是平等的。從結

構和結點間的通信方式來看，它屬于分布存儲系統，主要利用消息傳遞方式實

現各主機之間的通信，由建立在一般操作系統之上的并行編程環境完成系統的

資源管理及相互協作，下圖一為計算機集群系統的簡單圖示。

圖1 計算機集群圖示

3.2 GP-DBSCAN算法流程

第一步，讀入數據庫

讀入數據之后，根據k-dist圖來確定參數，即EPS與 MinPts。

第二步，劃分數據庫

 在并行計算之前，首先需要對數據庫進行劃分，具體方法為：掃描數據庫，將

數據庫在每

一坐標軸上進行投影，據此找到數據庫在每一維上的分布特征，從而對數據庫進行合理的

劃分，這是人機交互的過程。分割原數據庫需要遵循兩個原則：

 1）依據空間分布特點進行數據塊劃分。尋找能顯示數據分布特征的點，這里稱之為斷

點，之后從斷點處進行區域劃分。

 2）劃分數據塊的多少，要根據數據庫大小及計算環境來共同決定。當數據庫較小及計算

節點數目較少，均不宜將其劃分成過多的數據塊。原因是將消耗過多的合并成本。 

第三步，分別執行任務

每個節點分別根據DBSCAN算法聚類。

第四步，合并計算結果并輸出

    各節點將聚類結果傳遞給主節點，由主節點根據一定的合并原則進行合并，這里采用的是

文獻[4]中的合并策略；之后輸出計算結果。

3.3 動態負載平衡

為了最大程度地利用集群中的一切資源，集群需要具有動態負載平衡功能，通

過監視網格中的計算結點的負載情況動態地進行及時調整。能否合理地實現動

態負載平衡對于集群系統的計算性能來說是至關重要的。

GP-DBSCAN算法中，每個計算結點會周期性地把完成的計算結果和狀態報告給中央結點，

如果一個結點保持沉默超過一個預設的時間間隔，中央結點將記錄下這個結點的狀態為死

亡，并把分配給其的任務轉發到其他結點。每個操作使用命名操作的原子操作以確保不會

發生并行線程間的沖突。

對于一個計算結點來說，它的負載會被動態地調整：每次當有新的數據塊到

達、或現有的計算任務已經完成，都會調用沖突解決機制來決定是否接納子任

務，或者讓其在隊列中繼續等待，或者將其送到其他子結點運行，系統會根據

各計算結點負載情況及計算能力動態地調整任務分配。

3.4 異構的通訊方式

在數據分配，結果上傳及動態調整負載的過程中，結點之間是需要通訊的。一

般來說，在分布式計算系統中可以采用的通訊策略有兩種，同步通訊策略和異

步通訊策略。其中同步通訊策略是指各個結點在完成各自的計算后，同時開始

通訊過程；異步通訊策略是指各個結點不是同時開始通訊的，哪個結點先完成

計算，哪個開始通訊。很顯然，我們的算法選擇的是異步通訊：當一個計算結

點完成計算任務后，需要立刻向中央結點匯報結果，從而系統會了解到該結點

當前的狀態。采用異構通訊，與動態負載平衡是相輔相承的。

4  實驗

實驗所用設備為三臺采用windows 操作系統，Intel 2.0 GHZ（雙核）， 3 GB

 內存的筆記本，編程工具和運行環境為JDK 1.5。采用其中一臺筆記本作為中

央節點。程序代碼只需保存在中央節點上，所有的操作都在中央節點上完成，

由中央節點通過網絡去控制另一節點。數據庫為如下圖二所示帶有噪音的數據

庫來進行測試。

圖2 數據庫原圖

此數據庫文件包含257843個點，參數EPS 與MinPts分別為3，7。計算結果如下表一所示：

表1 GP-DBSCAN與DBCSAN計算效率比較

可以看出，隨著計算機節點的增加，GP-DBSCAN的計算速度也在不斷增加，與

DBSCAN相比，在計算效率上得到很大提高，在節點為3的情況下，計算速度僅為

原算法的25%。

5 結論

為了滿足對大規模數據庫的聚類需要，提出了一種面向計算機集群的并行聚類算法GP-

DBSCAN，通過適當增加計算節點，計算速度得到大幅度提高，證明該算法可以

用于大規模

數據庫的聚類分析。

參考文獻

 [1]     毛嘉麗，萬敏，陳華月。機群環境下的并行K-Means算法[J].宜賓學院學報，2007，12： 91-93

 [2]     Easter M, Kriegek H-P, Sander J, Xiaowei Xu. A density-based algorithm for discovering clusters in large databases. [C]// In: Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Portland: AAAI Press,1996: 226-231

 [3]     A. Guttman. R-trees: A dynamic index structure for spatial searching. [C]// In: Proc. SIGMOD International Conference on Management of Data, Boston, Massachusetts: ACM Press, 1984:  47-57.

 [4]     周水耿， 周傲英，曹晶。 基于分區的DBSCAN 算法[J]。計算機研究與發展, 2000, 37 (10) : 1153-1159

作者簡介：陳敏(1976－),女,博士研究生,主要研究方向為數據挖掘；

          郗玉平(1975-),男,碩士。 09877