并行DBSCAN聚類算法

[摘 要] 本文針對DBSCAN算法在計算速度方面的瓶頸，提出了一種新的基于內存的并行DBSCAN算法:合理劃分數據庫，各個處理器并行聚類，之后合并聚類結果，可以達到很好的聚類結果效果和計算效率。通過對一臺雙核計算機的實驗，發現實驗速度可以提高50%左右。

[關鍵詞] 聚類;DBSCAN算法;并行DBSCAN算法

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2010 . 05 . 034

[中圖分類號]TP301.6 [文獻標識碼]A [文章編號]1673 - 0194(2010)05 - 0078 - 03

聚類分析是根據相似性對數據庫中的對象進行分組， 使得不同類中的數據盡可能相異而同一類中的數據盡可能相同，從而發現數據空間的分布特征，是數據挖掘的主要任務之一。目前已經有了很多經典的聚類算法，總體來說可以分為基于密度、分區、分層、網格幾類。

隨著信息技術的高速發展，出現了越來越多諸如地理信息、衛星圖像等大規模空間數據庫。大規模空間數據庫對于聚類算法的要求更高，要求算法能夠發現任何形狀的類并能高效聚類。DBSCAN是面向空間數據庫的基于密度的聚類算法，其主要思想為:如果一個對象在半徑為ε的領域內包含至少MinPts個對象，那么該區域是密集的。其優點是能夠發現任意形狀的類，并且不受異常值(噪聲)的影響，然而當數據庫規模增大時，該算法要求較大的內存支持，I/O消耗大，采用串行算法，無論是運算速度還是內存，都無法滿足對大規模數據庫聚類的需求。

針對該算法的計算效率問題，本文提出一種基于內存的并行DBSCAN算法。首先基于投影進行數據分區，之后在每一處理器上分別聚類，最后合并聚類結果。實驗證明該算法較DBSCAN算法速度有很大提高，并且聚類的準確程度亦有所改善。

1DBSCAN算法介紹[1]

首先給出DBSCAN算法的幾個基本概念，其中D為數據庫， Eps和MinPts為給定閾值。

定義1.1(Eps-鄰域) 對于空間任意一個點P，其Eps領域記作NEps(p)={q∈D dist(p，q)≤Eps｝。

定義1.2(核心點) 對于一個點，如果在其Eps-鄰域內至少包含MinPts個對象，則稱該對象為核心對象。

定義1.3(直接密度可達) 點p從點q直接密度可達，若它們滿足:

(1) p∈NEps(q);

(2) NEps(q) ≥MinPts。

定義1.4(密度可達)點p從點q密度可達，若存在p1， p2，...，pn，其中p1= q，pn= p，且pi + 1從pi直接密度可達。

定義1.5(密度相連)點p和點q是密度連接的，若存在對象 o，使p和q都從o密度可達。

定義1.6(類)數據庫D的非空集合C是一個類，當且僅當C滿足以下條件:

(1) 任意點 p，q，若p∈C，且q從p密度可達，則q∈C(最大性);

(2) 任意點p，q∈C，則p，q密度連接(連通性)。

定義1.7(噪聲)數據庫D中不屬于任何類的點為噪聲。

DBSCAN算法思路如下:對數據庫中任何一個點，對其進行區域查詢，判斷是否是核心點，如是，建立新類C，p及其鄰域內的點均屬于該類。考察C中尚未被考察過的點q，若q是核心點，則將其領域內未屬于任何一類的點追加到類C。不斷重復此過程，直到沒有新的點可以追加為止。類C是一個密度相連的，基于密度可達性最大的點集。以同樣程序尋找其他的類，不屬于任何類的點為噪聲。

DBSCAN算法的復雜度為O(n2)，其中n是對象的總數。為了提高聚類效率，DBSCAN算法采用空間數據庫索引R*-TREE來實現區域查詢，使計算復雜度降為O(nlogn)。在進行聚類前，需要建立針對所有數據的R*-TREE。另外，DBSCAN要求用戶指定一個全局Eps參量。為了確定Eps值，DBSCAN計算任意點與它的第k個最鄰近點間的距離，然后，根據求得的距離由小到大進行排序，并繪出排序后的圖，稱作k-dist圖。k-dist圖中的橫坐標表示空間點，縱坐標則為該點的k-dist值。R*-TREE的建立和k-dist圖的繪制都是消耗時間的過程，當面對的數據庫規模很大時，DBSCAN串行算法在內存和計算速度方面都存在很大的障礙。

基于以上分析，本文提出一種基于數據分區的的并行DBSCAN算法——P-DBSCAN。該算法適用于共享內存的并行計算系統，例如單臺多核計算機;也同樣適用于分布式非共享內存的并行計算系統。在本文的研究中，主要針對單臺多核計算機。

2P-DBSCAN 算法

2.1并行算法相對DBSCAN的主要改進點

2.1.1針對數據空間分布特點進行數據分區

掃描數據庫通過程序計算找出數據的分布特征，對數據庫在每一坐標軸上進行投影，從而找到數據庫在每一維上的分布特征，進行合理的數據庫劃分。這是人機交互的過程。

分割原數據庫需要遵循兩個原則:

(1) 依據空間分布特點進行數據塊劃分。尋找能顯示數據分布特征的點，從該處進行區域劃分。

(2) 劃分數據塊的多少，要根據數據庫大小及計算環境來共同決定。當數據庫較小及計算節點較少時，均不宜將其劃分成過多的數據塊。原因是將消耗過多的合并成本。

此數據庫劃分原則，適應于任何維數的數據空間，為了演示方便，本文僅以如下帶有噪聲的二維數據庫進行圖示說明(如圖1所示)。

例如，對如圖1所示數據庫，將其投影至X 、Y軸，投影結果如圖2所示。

我們目前僅用雙核單臺計算機實驗，將數據庫劃分為兩塊比較合適，故可僅在X 軸的A點將數據庫進行劃分。

2.1.2合并算法

(1) 如果某點Z分別屬于類1和類2，Z至少有一次為核心對象，則類1和類2合并為一個類。

(2) 如果某點Z在類1和類2中都是邊界點，則Z可以屬于類1或類2，但類1和類2不能合并。

(3) 如果Z有一次屬于類1，而另一次是噪聲點，則Z屬于類1。

(4) 如果Z點兩次都是噪聲點，Z在全局聚類中就是噪聲點。

2.2P-DBSCAN算法流程

(1) 將數據庫進行數據分區。

(2) 將數據塊分配到各個處理器進行計算，在每一處理器上:

① 對每一數據區建立PR-TREE;

② 檢查數據塊中尚未檢查過的對象P，如果P未被處理(歸入某個類或標記為噪聲)，則檢查其Eps鄰域NEps(P)，若NEps(P)包含的對象數不小于MinPts，則建立新類C，將NEps(P)中所有點加入C;

③ 對C中所有尚未被處理的對象q，檢查其Eps鄰域NEps(q)，若NEps(q)包含至少MinPts個對象，則將NEps(q)中未歸入任何一個類的對象加入C;

④ 重復步驟③，繼續檢查C中未處理對象，直到沒有新的對象加入當前類;

⑤ 重復步驟②③④，直到所有對象都歸入了某個類或標記為噪聲。

(3) 合并各處理器的計算結果。

(4) 輸出計算結果。

3實驗

本實驗設備為一臺采用Windows 操作系統，Intel 2.0 GHz(雙核)， 3 GB 內存的筆記本;編程工具和運行環境為JDK 1.5。實驗對象為如圖1所示的數據庫。兩個處理器的聚類結果如圖3所示。

從圖3可以看出，由于數據庫先分割后由兩個處理器進行分別聚類，所以將原來原本屬于同一個類的類5與類6分割成兩個類。合并兩個處理器的聚類結果，得到正確的聚類如圖4所示。

從圖4我們了解到，并行聚類可以得到與串行聚類同樣的聚類效果;而且通過大量的實驗發現，并行聚類算法的效率比串行算法有了大幅度提高。實驗還發現，參數中的半徑，即Eps是影響搜索速度的關鍵，而在Eps確定之后，MinPts卻對速度幾乎沒有影響。在我們的實驗中，參數Eps及MinPts分別選定為2，7。采用串行算法的計算時間為30 531ms;同一臺計算機，采用并行算法的計算時間為16 781ms，僅為串行算法執行時間的 55%。

4結論

本文提出了一種并行聚類算法——P-DBSCAN，根據數據分布特征進行數據庫劃分，將其分配到多核處理器分別聚類，之后合并聚類結果。實驗證明P-DBSCAN算法不但能得到正確的聚類結果，而且在雙核處理器上的計算速度可以提高50%。該算法可以擴展到分布式并行計算環境，下一步的研究將在分布式計算環境中實現P-DBSCAN并行算法。

主要參考文獻

[1] Martin Easter，Hans-Peter Kriegek，et al. A Density-based Algorithm for Discovering Clusters in Large Databases with Noise[C] // Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining， 1996:226-231.

[2] Norbert Beckmann， Hans-Peter Kriegel，et al. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles[C] // Proceedings of SIGMOD International Conference on Management of Data， 1990:322-331.

[3] Lars Arge， Mark de Berg，et al. The Priority R-tree: A Practically Efficient and Worst Case Optimal R-tree[C] // Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data，2004: 347-358.