林阿弟　陳曉鋒

摘要：DBSCAN是一種簡單、有效的基于密度的聚類算法，用于尋找被低密度區(qū)域分離的高密度區(qū)域。DBSCAN是最經(jīng)常被使用、在科學(xué)文獻(xiàn)中被引用最多的聚類算法之一。在數(shù)據(jù)維度比較高的情況下， DBSCAN的時(shí)間復(fù)雜度為[O（n2）]。然而，在現(xiàn)實(shí)世界中，數(shù)據(jù)集的大小已經(jīng)增長到超大規(guī)模。對此，一個(gè)有效率的并行的DBSCAN算法被提出，并在MapReduce平臺下實(shí)現(xiàn)它。首先，對已經(jīng)預(yù)處理過的數(shù)據(jù)進(jìn)行劃分。接下來，局部的DBSCAN算法將對每一塊劃分好的數(shù)據(jù)空間實(shí)現(xiàn)聚類。最終，利用合并算法對上一階段的聚類結(jié)果進(jìn)行合并。實(shí)驗(yàn)結(jié)果驗(yàn)證了并行算法的有效性。

關(guān)鍵詞：DBSCAN； MapReduce； 聚類算法； 并行算法； 數(shù)據(jù)挖掘

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2015）10-0161-04

DBSCAN[1]于1996年被提出以后便被廣泛使用。DBSCAN基本時(shí)間復(fù)雜度是（n*找出樣本點(diǎn)的Eps鄰域中的點(diǎn)所需要的時(shí)間），其中n是樣本點(diǎn)的大小。低維數(shù)據(jù)空間下，利用一些空間索引結(jié)構(gòu)，如kd樹[2]、R樹[3]、R*樹[4]等，時(shí)間復(fù)雜度可以降到[Onlogn].高維數(shù)據(jù)空間下，DBSCAN的時(shí)間復(fù)雜度為[O（n2）]。PDBSCAN[5]首次采用dR*-tree提出了一個(gè)有效的DBSCAN并行算法。然而，創(chuàng)建dR*-tree在海量數(shù)據(jù)情況下非常的困難，而在數(shù)據(jù)是高緯度時(shí)則毫無效率。MR-DBSCAN[6]提出了基于MapReduce[7]平臺下的DBSCAN并行算法。MR-DBSCAN提出了巧妙的數(shù)據(jù)劃分方法，很好的解決了在海量的低維度的數(shù)據(jù)集進(jìn)行數(shù)據(jù)劃分時(shí)可能產(chǎn)生的負(fù)載平衡問題。然而這兩個(gè)算法均無法有效處理海量的高緯度的數(shù)據(jù)集。通過對這兩個(gè)算法進(jìn)行改進(jìn)，結(jié)合它們的優(yōu)點(diǎn)，提出了一個(gè)適用于海量的高緯度的數(shù)據(jù)集的DBSCAN并行算法。DBSCAN并行算法分為四階段。首先，選擇數(shù)據(jù)在選中二維上的劃分點(diǎn)。在選中的維度上，依據(jù)該維的數(shù)據(jù)域，將數(shù)據(jù)分成m份，記下每份數(shù)據(jù)的點(diǎn)的數(shù)目，之后從這m份數(shù)據(jù)的邊界點(diǎn)中選出a個(gè)作為劃分點(diǎn)。然后，根據(jù)各個(gè)維的劃分點(diǎn)，得到了數(shù)據(jù)劃分。接著，調(diào)整得到的數(shù)據(jù)劃分作為局部DBSCAN算法的輸入，實(shí)施局部DBSCAN算法。最后，利用合并算法對上一階段的聚類結(jié)果進(jìn)行合并。

1 DBSCAN算法介紹

1.1 DBSCAN的簇

DBSCAN聚類算法需要用戶自己確定兩個(gè)參數(shù)Eps和MinPts。其中，Eps為用戶定義的半徑，MinPts為定義一個(gè)點(diǎn)為核心點(diǎn)時(shí)其鄰域內(nèi)要求的最少點(diǎn)數(shù)。點(diǎn)的鄰域的定義將在下文闡述。在給出DBSCAN的簇的定義之前，我們需要知道如下的一些定義：

定義1：（點(diǎn)p的Εps鄰域）用NEps（P） 表示點(diǎn)P的Εps鄰域，dist（p，q）表示點(diǎn)p、q之間的距離，則點(diǎn)P的Εps鄰域定義為NEps（p） = {q? D | dist（p，q） ? Eps}。即點(diǎn)p的Εps鄰域?yàn)樗信c點(diǎn)p的距離不大于Eps的點(diǎn)的集合。

對于簇C，要求對于在簇C中的每一點(diǎn)p，則在簇C中存在一點(diǎn)q，p在點(diǎn)q的Eps鄰域內(nèi)，且q的Εps鄰域內(nèi)的點(diǎn)數(shù)>=MinPts.我們在給出簇的詳細(xì)的定義之前，先給出下面一些概念和定義。

若點(diǎn)p的Eps鄰域的點(diǎn)數(shù)>=MinPts，則點(diǎn)p為核心點(diǎn)。點(diǎn)q的Eps鄰域的點(diǎn)數(shù)

定義2：（直接密度可達(dá)）點(diǎn)p從點(diǎn)q直接密度可達(dá)僅當(dāng)：

1） p?NEps（q）

2） |NEps（q）|≥MinPts（核心點(diǎn)條件）

定義3：（密度可達(dá)）如果存在一串樣本點(diǎn)p1，p2….pn，p1=q， pn=p，假如點(diǎn)pi+1從pi直接密度可達(dá)，那么點(diǎn)p從點(diǎn)q密度可達(dá)。

在上面我們提過，對于簇C中的任意一點(diǎn)，它必處在一個(gè)核心點(diǎn)的鄰域中，可以證明，對于同個(gè)簇C中的兩個(gè)邊界點(diǎn)，必存在同一個(gè)核心點(diǎn)，使得它們同時(shí)從該核心點(diǎn)密度可達(dá)。為了能夠表達(dá)這種關(guān)系，我們引入了密度相連的定義。

定義4：（密度相連）如果存在任意一點(diǎn)o，點(diǎn)p從點(diǎn)o密度可達(dá)，并且點(diǎn)q從點(diǎn)o密度可達(dá)，那么點(diǎn)q到點(diǎn)p密度相連。

現(xiàn)在我們可以對簇進(jìn)行定義了。噪聲集可以定義為不在所有簇中的點(diǎn)的集合。

定義5：（簇）D為樣本點(diǎn)集，簇C是D的一個(gè)非空子集且滿足如下條件：

1）點(diǎn)p，q：如果p?C且q從p密度可達(dá)，則q?C。

2）點(diǎn)p，q?C：p與q密度相連。

定義6：（噪聲集）C1，…，CK為樣本點(diǎn)集D下滿足條件Epsi和MinPtsi，i=1，…，k下的簇。噪聲集是D中不屬于任何Ci的點(diǎn)的集合，表示為noise={p?D|i：p?Ci}。

下面的兩個(gè)引理對于保證下面的DBSCAN算法的正確性至關(guān)重要。從直觀上看，給定Eps和MinPts，我們可以通過下面兩個(gè)步驟來發(fā)現(xiàn)一個(gè)簇。找到樣本點(diǎn)集中任意一個(gè)核心點(diǎn)做為種子。然后，找出所有與這個(gè)種子密度可達(dá)的點(diǎn)（包括種子）從而得到了由該種子擴(kuò)展成的簇。

引理1：點(diǎn)p為樣本點(diǎn)集D的一點(diǎn)，且|NEps（p）|≥MinPts，點(diǎn)集合O = {o|o?D且o從p密度可達(dá)}為一個(gè)簇。

引理2：簇C為樣本點(diǎn)集D中的一個(gè)簇，點(diǎn)p為簇C中滿足|NEps（p）|≥MinPts的點(diǎn)，則簇C與點(diǎn)集合O = {o|o從p密度可達(dá)}等價(jià)。

1.2 DBSCAN算法

對于不同的簇Ci取不同較為理想的Epsi和MinPtsi是非常困難的，但是存在全局的且較為理想的Eps和MinPts[1].所以，DBSCAN算法一般取全局的Eps和MinPts。為了發(fā)現(xiàn)一個(gè)簇，DBSCAN先從樣本點(diǎn)集中找到任意一點(diǎn)p，找出所有從該點(diǎn)密度可達(dá)的點(diǎn)。如果點(diǎn)p是核心點(diǎn)，由引理2知，這些點(diǎn)構(gòu)成了一個(gè)簇。如果，點(diǎn)p不是核心點(diǎn)，便沒有點(diǎn)從點(diǎn)p密度可達(dá)，DBSCAN從樣本點(diǎn)集中尋找下一點(diǎn)，重復(fù)上面的步驟。詳細(xì)的DBSCAN算法DBSCAN（SetOfPoints， Eps， MinPts）和DBSCAN調(diào)用的最重要的函數(shù)ExpandCluster見[1]。

當(dāng)兩個(gè)簇靠得很近時(shí)，它們可能會有交點(diǎn)，由簇的定義知道這些交點(diǎn)必是邊界點(diǎn)，那么它們同時(shí)屬于這兩個(gè)簇，這種情形我們稱之為平局問題。從ExpandCluster知道，這時(shí)在DBSCAN算法實(shí)施時(shí)，它們將歸于一個(gè)簇，先發(fā)現(xiàn)它們的那個(gè)簇！而一些在聚類過程中原先被劃分為噪聲的點(diǎn)，在之后的聚類中，如果發(fā)現(xiàn)它從某個(gè)點(diǎn)密度可達(dá)，則可以改變它的標(biāo)記為某個(gè)簇的標(biāo)號。

2 DBSCAN的并行實(shí)現(xiàn)

2.1 DBSCAN并行算法的數(shù)據(jù)劃分

2.1.1 選擇數(shù)據(jù)的劃分點(diǎn)

選中數(shù)據(jù)集中數(shù)據(jù)維度中的2個(gè)維度，根據(jù)第i維上的數(shù)據(jù)域?qū)?shù)據(jù)分成mi份，記下每份數(shù)據(jù)的點(diǎn)的數(shù)目，i=1，2；假設(shè)有N個(gè)計(jì)算節(jié)點(diǎn)，N=a[1]*a[2]，則從這mi份數(shù)據(jù)的邊界點(diǎn)中選出a[i]個(gè)作為數(shù)據(jù)的劃分點(diǎn)。選取規(guī)則如下：

Part（begin，end，a[i]，avg）

IF a[i]>1

previousEnd = findPartEnd（begin，end-（a[i]-1），avg）；

Part（previousEnd+1，end，a[i]-1，avg）；

RETURN previousEnd；

END IF

RETURN end；

END

找到各個(gè)劃分點(diǎn)：

findPartEnd（begin，end，avg）

sum = 0；

FOR i FROM begin TO end-1

sumNext = 0；

將第i部分的點(diǎn)的數(shù)目累加到sum中

sumNext = sum + 第i+1部分的點(diǎn)的數(shù)目

IF avg-sum <= sumNext-avg

RETURN i；

END IF

END FOR

RETURN end；

END

在上面的偽代碼中，avg為樣本點(diǎn)的數(shù)目除以a[i]，begin、end分別表示mi份中的第begin份和第end份。

2.1.2 根據(jù)已得到數(shù)據(jù)的劃分點(diǎn)劃分?jǐn)?shù)據(jù)

根據(jù)2.1.1得到的各個(gè)維度算得的劃分點(diǎn)，得到最終的數(shù)據(jù)劃分。下面舉一個(gè)例子，來說明總的數(shù)據(jù)劃分的過程。假設(shè)原始的數(shù)據(jù)集如下，

在這里，我們的數(shù)據(jù)已經(jīng)提前歸一化到0.0-1.0，我們選取X、Y維上的數(shù)據(jù)，均分為N份，除了最后一份，每份的數(shù)據(jù)域范圍為[i*（1/N），（i+1）*（1/N） ），i=0，…，N-2，最后一份的數(shù)據(jù)域范圍是[ （N-1）*（1/N），1.0]，這里N取10。如果，假設(shè)這時(shí)有6個(gè)計(jì)算節(jié)點(diǎn)，我們希望根據(jù)X、Y維，把數(shù)據(jù)劃分成3*2份，那么這時(shí)根據(jù)2.1.1可算出在X、Y維上的數(shù)據(jù)劃分點(diǎn)，最終的得到的6個(gè)數(shù)據(jù)劃分結(jié)果如下：

2.2 DBSCAN的并行化實(shí)現(xiàn)

2.2.1 Local DBSCAN

在2.1節(jié)中最后得到的數(shù)據(jù)劃分并不是Local DBSCAN[6]的輸入，事實(shí)上Local DBSCAN的輸入是上面得到的數(shù)據(jù)劃分和它的鄰居數(shù)據(jù)劃分的一部分拷貝的總和。在闡述Local DBSCAN的輸入時(shí)，我們需要說明清楚我們DBSCAN并行算法的原理。針對2.1.1得到的數(shù)據(jù)劃分，我們知道如果僅僅在上面劃分下運(yùn)行DBSCAN算法的程序，那么可能有如下三種情況發(fā)生：劃分上運(yùn)行DBSCAN得到的簇與全數(shù)據(jù)集運(yùn)行DBSCAN得到的簇沒有差別。全數(shù)據(jù)集上運(yùn)行DBSCAN得到簇c1和c2，在劃分上得到的簇也是簇c1和c2，僅有的差別最多是平局上的處理的差異，結(jié)果可以算是一致的。在全數(shù)據(jù)集運(yùn)行DBSCAN算法時(shí)，簇c1和簇c2應(yīng)該算是同一個(gè)簇，但在當(dāng)前的數(shù)據(jù)劃分下運(yùn)行時(shí)，則變成兩個(gè)簇。

圖3 相鄰劃分上得到的兩個(gè)簇的在全數(shù)據(jù)集下為一個(gè)簇，需要合并

觀察圖1、圖2、圖3發(fā)現(xiàn)，圖2和圖3有個(gè)共同點(diǎn)，即在某個(gè)劃分內(nèi)，存在距離劃分邊界

現(xiàn)在，我們重點(diǎn)注意圖3。左邊的劃分距離劃分邊界

上面結(jié)論的嚴(yán)格證明參照[5].根據(jù)上面的結(jié)論，MR-DBSCAN提出了Local DBSCAN下的數(shù)據(jù)輸入集。它具有如下形式：

即第i個(gè)輸入數(shù)據(jù)集應(yīng)當(dāng)是2.1中得到的第i個(gè)數(shù)據(jù)劃分與距離劃分邊界<=bEps（bEps>=Eps）的點(diǎn)集的并。由上面知道Local DBSCAN的劃分內(nèi)部也有距離劃分邊界<=bEps（bEps>=Eps）的點(diǎn)集需要拷貝給相應(yīng)的相鄰的劃分。我們給定MC集的定義如下：

MC（C， S） = {o ∈ {q} ∪ （NEps（q）＼S）|q ∈ C ∩ S ∧ |NEps（q）|≥MinPts∧NEps（q）＼S≠?}。其中，C為簇，S為劃分。

現(xiàn)在，假設(shè)有某個(gè)簇跨越了劃分i和它的相鄰的劃分，那么根據(jù)上面的討論，必定存在劃分i上的MC集與它的相鄰的劃分的交集非空。關(guān)于這部分的嚴(yán)格證明參見[5]。而根據(jù)上面提到的Local DBSCAN的輸入數(shù)據(jù)集，MC集必定產(chǎn)生于劃分i的IN，IE，IS，IW和相鄰劃分的拷貝N，E，S，W，準(zhǔn)確的說，MC集是IN， IE， IS，IW上的核心點(diǎn)和其鄰域在N，E，S，W上的點(diǎn)的并集[6]，這就是Local DBSCAN的輸出，這里我們與[6]中的Local DBSCAN的輸出不同，我們只統(tǒng)一輸出MC集，而不關(guān)心它是IN， IE， IS，IW上哪一部分的核心點(diǎn)產(chǎn)生。至于Local DBSCAN的其余部分與DBSCAN基本相同。

2.2.2 DBSCAN并行算法的合并階段

DBSCAN并行算法的合并階段是結(jié)合MR-DBSCAN的Stage3和Stage4.1，在單機(jī)下實(shí)現(xiàn)。首先，我們的輸入采取冗余輸入，輸入為所有數(shù)據(jù)劃分中非噪聲的數(shù)據(jù)和該數(shù)據(jù)劃分對應(yīng)的MC集，而不僅僅是所有數(shù)據(jù)劃分中非噪聲的數(shù)據(jù)集。在求MC交集時(shí)采用的是類似MR-DBSCAN中Stage3的算法，但這個(gè)過程在單機(jī)下運(yùn)行，從而得出哪些簇需要合并。然后，根據(jù)產(chǎn)生的結(jié)果采取與Stage4.1基本相同的方法對Local DBSCAN產(chǎn)生的簇號進(jìn)行全局下的編號，最后賦予非噪聲的數(shù)據(jù)于全局下的簇標(biāo)號，這樣通過采取冗余輸入我們可以省去MR-DBSCAN下的Stage4.2。

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

我們分布式下使用的軟件是MapReduce的開源實(shí)現(xiàn)Hadoop-0.20.2版本，關(guān)于Hadoop的配置參照[8].

在單機(jī)環(huán)境下，實(shí)驗(yàn)步驟如下：數(shù)據(jù)預(yù)處理→DBSCAN算法

在分布環(huán)境下，我們通過如下的實(shí)驗(yàn)步驟得到結(jié)果：數(shù)據(jù)預(yù)處理→選擇劃分點(diǎn)→劃分→局部DBSCAN算法→合并。

我們在3.20GHZ Intel（R） Pentium（R） 4 cpu，2GB DDR2內(nèi)存，80GB5400轉(zhuǎn)的硬盤上偽分布環(huán)境下測試53052條二維數(shù)據(jù)，系統(tǒng)為ubuntu 10.04 lts，Eps=0.02，MinPts=8，我們在此實(shí)現(xiàn)的數(shù)據(jù)二劃分，即將數(shù)據(jù)根據(jù)劃分算法一分為二，實(shí)驗(yàn)結(jié)果如表3所示：

而在兩臺3.60GHZ Intel Core（TM） i7-3820，8GBDDR2內(nèi)存，200GB7200轉(zhuǎn)的硬盤的電腦組成的集群下，分布式中的局部DBSCAN費(fèi)時(shí)75（S），單機(jī)下為1+138=139（S），由于所測的數(shù)據(jù)量不夠大，在集群下沒有表現(xiàn)應(yīng)有的優(yōu)勢。但是仍然得到了加速?？梢灶A(yù)見，隨著數(shù)據(jù)規(guī)模的增大，分布式DBSCAN算法的優(yōu)勢將會更明顯。

4結(jié)論

從實(shí)驗(yàn)結(jié)果可以看出，單機(jī)下聚類所使用的時(shí)間與偽分布式環(huán)境下的時(shí)間的比為2170/724=2.997，實(shí)驗(yàn)效果顯然是比較不錯的，在以后的實(shí)驗(yàn)中，我們將實(shí)現(xiàn)數(shù)據(jù)的多劃分，并測試大數(shù)據(jù)集在集群下的實(shí)驗(yàn)結(jié)果，從而找出海量的高緯度的數(shù)據(jù)集下有效的DBSCAN并行算法。

參考文獻(xiàn)：

[1] Ester M， Kriegel H P， Sander J， et al. A density based algorithm for discovering clusters in large spatial databases[C]. Proc. 2nd Int. Conf. on Knowledge Discovery and Data Mining. Portland， 1996： 226–231.

[2] Bentley J L. Multidimensional binary search trees used for associative searching[J]. Communications of the ACM， 1975， 18（9）： 509-517.

[3] Guttman A. R-trees： a dynamic index structure for spatial searching[J]. ACM， 1984， 14（2）： 47-57.

[4] Beckmann N， Kriegel H P， Schneider R， et al. The R*-tree： an efficient and robust access method for points and rectangles[M]. ACM， 1990，19（2）： 322-331.

[5] Xu X， Jager J， Kriegel H P. A fast parallel clustering algorithm for large spatial databases[J]. Data Min. Knowl. Discov， 1999（3）： 263–290.

[6]Yaobin He， Tan Haoyu， Luo Wuman， Huajian Mao， Di Ma， Shengzhong Feng， Jianping Fan.MR-DBSCAN： An Efficient Parallel Density-based Clustering Algorithm using MapReduce[J]. 2011 IEEE 17th International Conference on Parallel and Distributed Systems，2011： 473-480.

[7] Dean J， Ghemawat S. Mapreduce： simplified data processing on large clusters[J]. Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation - Volume 6. Berkeley，CA， USA： USENIX Association， 2004： 10.

[8] 陸嘉恒.Hadoop實(shí)戰(zhàn)[M].北京：機(jī)械工業(yè)出版社，2011.