陳葉旺 曹海露 陳 誼 康 昭 雷 震 杜吉祥,6

1（華僑大學計算機科學與技術學院 福建廈門 361021）

2（食品安全大數(shù)據(jù)技術北京市重點實驗室（北京工商大學）北京 100048）

3（電子科技大學計算機科學與工程學院 成都 611731）

4（模式識別國家重點實驗室（中國科學院自動化所）北京 100190）

5（廈門市數(shù)據(jù)安全與區(qū)塊鏈技術重點實驗室（華僑大學）福建廈門 361021）

6（福建省大數(shù)據(jù)智能與安全重點實驗室（華僑大學）福建廈門 361021）

7（江蘇省計算機信息處理技術重點實驗室（蘇州大學）江蘇蘇州 215006）

（ywchen@hqu.edu.cn）

大數(shù)據(jù)時代，數(shù)據(jù)信息呈爆炸式增長，如何從海量的信息中提取隱含在其中的有效信息，并進行分析與預測未來的發(fā)展趨勢和模式是信息技術領域的重要課題.因而，數(shù)十年來，數(shù)據(jù)挖掘、機器學習、深度學習等相關技術不斷推陳出新，取得了長足的進展，結出了豐碩的成果.

然而，許多相關技術和算法需要大量的有標簽數(shù)據(jù)來進行學習和訓練.面對大數(shù)據(jù)，人為的標記將耗費大量的時間與人工成本.因此，作為無監(jiān)督學習中能自動地對數(shù)據(jù)進行分類的聚類算法，成為解決樣本標記難等問題的重要手段.

聚類算法是數(shù)據(jù)挖掘、模式識別、機器學習等領域的基礎算法，可以作為一個獨立的工具進行數(shù)據(jù)的相似性度量，觀察數(shù)據(jù)的分布情況，對每一簇數(shù)據(jù)進行進一步分析，將數(shù)據(jù)進行劃分.聚類算法已經(jīng)在眾多領域有具體應用案例，如在異常檢測、數(shù)據(jù)挖掘、圖像處理等領域.

至今為止，聚類算法的研究一直是科研人員的研究熱點.經(jīng)典的聚類算法有層次化聚類、基于圖聚類、基于密度聚類、基于網(wǎng)格聚類、基于模型聚類等.但在聚類算法中依然存在不少挑戰(zhàn)，如針對特征值缺失的數(shù)據(jù)進行聚類、對大規(guī)模數(shù)據(jù)進行聚類、對高維數(shù)據(jù)進行聚類等一直是現(xiàn)實中面臨的難題.

DBSCAN（density-based spatial clustering of applications with noise）算法是Ester 等人[1]于1996 年提出的算法.該算法是一種典型的基于密度的算法，用于發(fā)現(xiàn)任意形狀的聚類以及檢測異常值.與常見的k-means 算法[2]相比，DBSCAN 不需要事先劃分好簇，只需要輸入?yún)?shù)ε（指定鄰域半徑）和MinPts（鄰域密度閾值）就可以將緊密相連的數(shù)據(jù)劃為一類.該算法從問世至今，在理論和實踐中都受到廣泛關注，并于2014 年在ACM 大會上獲得the Test of Time 獎.

然而，DBSCAN 也存在眾多不足：1）時間復雜度較高，對大規(guī)模數(shù)據(jù)集進行聚類代價過大；2）參數(shù)難以確定，調整困難；3）不適應高維數(shù)據(jù)，對高維數(shù)據(jù)聚類效果不佳；4）無法對多密度數(shù)據(jù)進行聚類等.其中該算法復雜度過大，難以對大數(shù)據(jù)進行有效處理嚴重阻礙了其在工業(yè)界的應用.

分析表明，DBSCAN 復雜度過大主要原因在于需要雙重循環(huán)對所有數(shù)據(jù)點進行歐氏距離計算，對每個數(shù)據(jù)點找出給定鄰域內的近鄰，其間存在著大量的冗余.如何有效地過濾冗余的計算，對DBSCAN進行加速，使之能處理大規(guī)模數(shù)據(jù)，成為近年來的一個研究熱點.

為此，許多學者分別從不同的技術角度加速DBSCAN，取得了不少進展.從這些算法的加速手段所針對的目標劃分，可以分為減少冗余計算和并行化兩大類.但從具體的加速手段上來看，本文從這些工作的基本原理出發(fā)，按3 點規(guī)則對這些進展進行分類：1）是否硬件加速；2）加速結果是否為近似解；3）按何種方式減少冗余距離計算.

按上述3 點規(guī)則，本文主要針對近年來DBSCAN算法的快速化工作進行了整理與分析.就具體的加速技術而言，現(xiàn)有的算法主要分為6 種類別：基于分布式、基于采樣、基于近似模糊、基于快速近鄰、基于空間劃分、基于GPU 加速等技術.圖1（a）主要展示了這些加速工作的發(fā)展歷程，列出了這6 種主要類別的代表性方法.其中，有許多方法融合了多重技術，分別在DBSCAN 的不同階段進行加速.比如：分布式技術常與空間劃分技術相結合，快速近鄰技術常與近似模糊技術、空間劃分技術相融合等.圖1（b）展示了多重加速算法的主要技術手段.

Fig.1 Summary of fast DBSCAN algorithms圖1 快速化DBSCAN 算法匯總圖

我們對本文中使用的主要變量和符號進行整理，如表1 所示.

Table 1 Description of Main Variables and Symbols Used in the Paper表1 本文中使用的主要變量和符號的描述

1 DBSCAN 的發(fā)展歷史、符號、定義

DBSCAN 是依賴于基于密度的聚類概念，旨在發(fā)現(xiàn)任意形狀的聚類.有關DBSCAN 的7 個重要概念定義如下：

定義1.對p∈D，數(shù)據(jù)集D中與p的距離小于ε的數(shù)據(jù)，即Nε(p)={q∈D|dist(p,q)≤ε}，稱為p的ε-鄰域，其中，dist(p,q)=‖p-q‖2.

定義2.若 |Nε(p)|≥MinPts，則稱數(shù)據(jù)點p為核心點，其中MinPts為預先定義的自然數(shù)閾值.

定義3.若p∈Nε(q)且 |Nε(q)|≥MinPts，則稱數(shù)據(jù)點p從數(shù)據(jù)點q密度直達.

定義4.若存在點p1,p2,…,pn,p1=q,pn=p，對于序列中任意一個點pi，使得pi+1從pi密度直達，則稱數(shù)據(jù)點p從數(shù)據(jù)點q密度可達.

定義5.若存在數(shù)據(jù)點o，使得點p和點q都能從點o密度可達，則稱數(shù)據(jù)點p與數(shù)據(jù)點q密度相連.

圖2 展示了密度直達、可達、相連定義圖，依據(jù)定義2～5.x為核心點，y由x密度直達，z由x密度可達.o為核心點，點p，q分別由點o密度可達，則p與q密度相連.

Fig.2 Definition diagram of density direct,accessible,connected圖2 密度直達、可達、相連定義圖

定義6.若q為非核心點，?p∈D滿足p為核心點且q∈Nε(p)，則稱q為邊界點.

定義7.假設數(shù)據(jù)集D被聚類為k個類簇集C1,C2,…,Ck，若p不屬于任何類別，即 ?i:p?Ci，稱p為噪聲點.所有噪聲點構成噪聲集，即noise={p∈D|?i:p?Ci}.

根據(jù)上述核心點、邊界點以及噪聲點的定義，在圖3 中進行了展示.

Fig.3 Classification of core points,boundary points,outlier points圖3 核心點、邊界點、噪音點的分類

2 基于分布式的加速改進

在數(shù)據(jù)規(guī)模非常大的今天，即使是最簡單的數(shù)據(jù)分析任務也可能超過任何一臺機器的處理能力.像其他同類型算法一樣，DBSCAN 具有計算成本高、當數(shù)據(jù)無法裝入內存時I/O 速度變慢等問題.因此，很有必要并行執(zhí)行DBSCAN 以減少處理時間.MapReduce 和Spark 是2 種非常重要的并行處理數(shù)據(jù)框架.MapReduce 具有可伸縮、高度并行化和抽象化的優(yōu)點.Spark 框架除了擁有MapReduce 所有的重要特性外，它還具有一些新特性，在Spark 中，RDD（resiliennt distributed datasets）允許程序員在聚類上執(zhí)行內存計算且支持流數(shù)據(jù)、復雜分析、實時分析.

PDBSCAN[3]（parallel DBSCAN）是最早的分布式DBSCAN，該算法采用分布式空間索引結構dR*-Tree實現(xiàn)分布式并行化，具有近乎線性的加速，但是其如今的數(shù)據(jù)規(guī)模已經(jīng)遠遠超過了當時的數(shù)據(jù)量.

Patwary 等人[4]則指出PDBSCAN 采用類似于主從模式的方法，導致主服務器和從服務器之間的通信開銷很大，并且在合并過程中并行效率很低.因此，提出了PDSDBSCAN（parallel DBSCAN using disjointset）.該算法最初為數(shù)據(jù)集的每個點創(chuàng)建一個單節(jié)點樹，然后使用disjoint-set[5]數(shù)據(jù)結構對屬于同一簇的樹進行合并，直到發(fā)現(xiàn)所有簇為止，合并可以按照任意順序執(zhí)行.這打破了固有的數(shù)據(jù)訪問順序，實現(xiàn)了高數(shù)據(jù)并行，其性能顯著優(yōu)于主從方法.

MR-DBSCAN[6]（MapReduce-DBSCAN）算法先計算數(shù)據(jù)的大小以及一般的空間分布，以生成一個維度索引列表.然后根據(jù)分區(qū)配置文件，對子空間進行劃分.在最后階段合并子空間時處理跨邊界問題，它將從邊界子空間中找出2 個簇對的列表，以便為每個邊界合并.MR-DBSCAN 的執(zhí)行時間隨數(shù)據(jù)大小的增加而緩慢增加.但是這個算法不能正確地平衡并行任務之間的負載，尤其是在數(shù)據(jù)嚴重傾斜的情況下.

為此，在MR-DBSCAN 算法的基礎上，提出了一種基于CBP（cost-based partitioning）的方法[7]，以實現(xiàn)對嚴重傾斜數(shù)據(jù)的負載均衡.該算法首先執(zhí)行一個MapReduce 作業(yè)來收集數(shù)據(jù)分布的統(tǒng)計信息.在Shuffle 階段，這些點按它所屬的單元分組，Reduce 函數(shù)生成一個概要文件，記錄每個單元中的點數(shù)，根據(jù)統(tǒng)計數(shù)據(jù)分布估計的計算代價來計算最小完全劃分集.分區(qū)結束后，開始進行局部聚類，為了實現(xiàn)對鄰域的高效查詢，用R-Tree[8]在聚類之前索引分區(qū)中的所有點.對于每個分區(qū)，將全局合并階段涉及的點輸出到2 個單獨的文件中，建立局部聚類到全局聚類的映射.最后調整局部聚類的中間結果，將局部聚類替換為全局聚類，從而得到最終結果.該算法在空間數(shù)據(jù)集非常不均勻、嚴重傾斜的情況下能夠很好地聚類并且對大規(guī)模數(shù)據(jù)集有良好的加速性能.

為解決數(shù)據(jù)分區(qū)之間的負載不平衡，Song 等人[9]則開發(fā)了一種新穎的并行DBSCAN 算法，即RPDBSCAN（random partitioning-DBSCAN）.該算法將偽隨機分區(qū)與2 級單元字典一起使用，找到每個數(shù)據(jù)分區(qū)的局部聚類，然后合并這些局部聚類以獲得全局聚類.算法的整體流程如圖4 所示，整個算法可以分為3 個階段：階段1 為數(shù)據(jù)劃分，首先執(zhí)行偽隨機分區(qū)P，如圖4 左上角的圖所示，整個數(shù)據(jù)空間被劃分為這些單元格，空區(qū)域不創(chuàng)建任何單元格，這些單元被分配到P1和P2這2 個不同的分區(qū).階段2 創(chuàng)建核心圖，使用2 級單元字典，對每個分區(qū)中存在的所有內部單元執(zhí)行區(qū)域查詢，以區(qū)分核心和非核心單元.例如，如果確定圖4“數(shù)據(jù)分區(qū)”圖中的Cnc1到Cnc5為非核心（C表示數(shù)據(jù)點單元），則將這些非核心單元排除在外.然后通過從每個分區(qū)的每個核心單元中搜索所有完全或部分直接可達的單元來構造核心圖.在圖4“單元構建”圖中，圖中單元之間的有向邊表示2 個單元完全或部分直接可達.階段3 執(zhí)行全局聚類，該算法會合并所有圖并確認每個邊是否指示完全或部分直接可達的關系，然后，基于此合并圖擴展聚類.在圖4“單元合并”圖中，群集Q1（Q表示點集）由位于P1和P2左下角的單元形成.經(jīng)過空間劃分、單元構建與合并這3 個階段，RP-DBSCAN實現(xiàn)了完美的負載平衡，其性能遠遠高于此前的同類法[1,5,7]，此外，RP-DBSCAN 能夠處理的數(shù)據(jù)量高達362 GB，提高了DBSCAN 算法在大數(shù)據(jù)時代的可用性.

Fig.4 The overall flow of RP-DBSCAN[9]圖4 RP-DBSCAN 的整體流程[9]

除此之外，還有不少基于分布式的DBSCAN.如DBSCAN-MR[10]，MR-IDBSCAN[11]，RDD-DBSCAN[12]，SDBSCAN[13].在DBSCAN-MR[10]（reduce-based partition DBSCAN）中，算法可以在云上執(zhí)行，不需要全局索引，但是分區(qū)機制會影響每個節(jié)點的執(zhí)行效率和負載均衡.因此，提出了減少邊界點的分區(qū)方法來提高每個節(jié)點的執(zhí)行效率和負載均衡.MR-IDBSCAN[11]（MR-incremental DBSCAN）則是將增量DBSCAN 嵌入到MapReduce 分布式框架中以降低運行時的復雜性.Cordova 等人[12]提出了RDD-DBSCAN，該算法為了均勻分割數(shù)據(jù)空間，采用二進制空間分區(qū)，遞歸地將所需空間劃分為代價大致相等的區(qū)域，從而提高了速度.大多數(shù)分布式并行化DBSCAN 幾乎都是針對2 維數(shù)據(jù)進行聚類.這是因為隨著數(shù)據(jù)維數(shù)的增加，高維空間的拆分和整合將消耗大量的時間.為了解決這一問題，Luo 等人[13]提出了S-DBSCAN（DBSCAN on Spark），該算法通過質心對數(shù)據(jù)分區(qū)進行合并，從而提高了高維數(shù)據(jù)聚類的效率.

Lulli 等人[14]提出的NG-DBSCAN（neighbor graph DBSCAN）同樣能夠對高維數(shù)據(jù)集進行良好聚類.該算法是一種近似的基于密度的聚類算法，可以對任意數(shù)據(jù)和任何對稱距離度量進行操作.這一算法的分布式設計使其可擴展到非常大的數(shù)據(jù)集，它的近似特性使它快速產(chǎn)生高質量的聚類結果.算法分2 個階段進行：第1 階段創(chuàng)建了空間圖，將用于避免空間鄰域查詢；第2 階段以空間圖作為輸入，計算類別.結果表明，NG-DBSCAN 即使是在大的、高維的或任意數(shù)據(jù)的情況下也能夠高效地近似DBSCAN.

Han 等人[15]利用新的大數(shù)據(jù)框架Spark，提出了一種新的并行DBSCAN 算法.為了減少搜索時間，在算法中使用了Kd-tree[16].利用隊列來包含數(shù)據(jù)點的鄰居，在檢查和處理數(shù)據(jù)點時使用Hash 表.此外，還使用了Spark 的其他高級特性來提高效率.結果表明，該算法在高維數(shù)據(jù)集下實現(xiàn)良好的加速.

在并行KNN-DBSCAN[17]（k-nearest neighbor DBSCAN）中，算法使用OpenMP（open multi-processing）共享內存和MPI（massage passing interface）分布式內存實現(xiàn)并行化.這使得算法可以在不到1 s 的時間內聚類10 億個3 維的數(shù)據(jù)點，還能夠對上百億個20 維的數(shù)據(jù)開展聚類.證實了該算法無論是在高維還是低維的情況下都能展開聚類.

表2 對上述基于分布式技術的DBSCAN 加速算法進行了梳理.分布式技術能夠高效地聚類大規(guī)模數(shù)據(jù)，甚至是上億規(guī)模的數(shù)據(jù)[4,6-7,9,17]，但對于嚴重傾斜的數(shù)據(jù)，平衡并行任務之間的負載是關鍵問題[7-10].大多數(shù)分布式算法關注低維數(shù)據(jù)聚類[3,6-7,10-13]，只有少數(shù)算法能夠處理高維數(shù)據(jù)集[4,9,15,17]，其原因是高維數(shù)據(jù)巨大的復雜性和難處理性.在并行算法的基礎上，若算法是近似的則能夠處理任意維度的數(shù)據(jù)集，由此可見近似性的優(yōu)越之處.

Table 2 Distribution Based DBSCAN Acceleration Algorithm表2 基于分布式的DBSCAN 加速算法

3 基于采樣技術的加速改進

DBSCAN 擁有良好的聚類效果且能夠有效地處理噪聲，但它需要對整個數(shù)據(jù)集進行雙重循環(huán)檢測，內存支持量高.DBSCAN 從1 個核心對象p開始擴展1 個類別，它通過對p鄰域中每個對象執(zhí)行鄰域查詢來擴展，但是p中對象的鄰域會互相相交.假設q是p鄰域中的1 個對象，如果q的鄰域被p中其他對象的鄰域所覆蓋，則可以省略對q的鄰域查詢操作，這意味著q不需要被選擇作為簇擴展的種子.因此，可以減少q的鄰域查詢操作消耗的時間和存儲q作為核心對象的內存需求.

IDBSCAN[18]（improved DBSCAN）基于此想法，通過對一些代表性對象進行采樣，而不是將核心對象鄰近的所有對象都作為新的種子，從而降低內存使用量和I/O 代價，加快DBSCAN 算法的速度.IDBSCAN選取8 個不同的點作為MBO（marked boundary object），如圖5 所示.對于每一個MBO，都將找到與對象P相鄰且最接近的對象作為一顆種子.如果同一點被識別為多個MBO 的最近點，那么這個點只能被視為種子1 次.因此，1 次最多有8 個點是種子，這個數(shù)字小于DBSCAN 中的對應數(shù)量.IDBSCAN 的時間復雜度可以控制在O（nlogn），不過，IDBSCAN 中MBO 的采樣將不必要的點分配給種子會導致執(zhí)行冗余，影響執(zhí)行時間.

Fig.5 Eight different points on the circle[15]圖5 圓上8 個不同的點[15]

基于此，Tsai 等人[19]提出了KIDBSCAN（k-means IDBSCAN），利用k-means[2]對高密度中心點快速定位，再使用IDBSCAN 從這些高密度中心點展開聚類，減少冗余步驟.KIDBSCAN 提高了聚類結果的準確性，同時降低了I/O 成本，其性能優(yōu)于IDBSCAN.

QIDBSCAN[20]（quick IDBSCAN）則使用 4 個MBO 直接擴展計算.不選擇數(shù)據(jù)點的擴展會增加計算成本，但也會提高速度，因此，QIDBSCAN 的速度明顯快于IDBSCAN.

l-DBSCAN（leaders DBSCAN）[21]是一種混合聚類算法，其原型是使用leaders 聚類方法派生的.leaders 工作方式為：給定一個距離閾值τ，對于領導集L，初始為空，并以增量的方式構建.對于數(shù)據(jù)集D中的每個模式x，如果有一個leader，l∈L且 ||l-x||≤τ，那么x分配給l所屬的類別，這時x稱為l的追隨者.如果沒有這樣的leader，那么x本身就會成為一個leader，加入到L中.通過這種方法，l-DBSCAN 可以找到與DBSCAN 相同的聚類結果，但所花費的時間要比DBSCAN 短得多.

Rough-DBSCAN[22]也是一種混合聚類技術.該算法首先應用leaders 聚類方法從數(shù)據(jù)集中導出原型，與原型一起保存密度信息；然后使用leader 來導出基于密度的聚類.此外，Rough-DBSCAN 還增加了一個計數(shù)值用于統(tǒng)計leader 的數(shù)量，從而可以估算密度.這一技術的時間復雜度僅為O（n）.然而，Rough-DBSCAN 算法的不足之處是會產(chǎn)生密度錯誤，因此Luchi 等人[23]提出Rough*-DBSCAN.Rough*-DBSCAN密度根據(jù)與每個leader 相關聯(lián)的元素數(shù)量來估計，可以獲得更好的結果.而Rough-DBSCAN 密度是根據(jù)算法返回的每個聚類中的元素數(shù)量來計算的，會導致聚類效果不佳.此外，研究人員還提出了一個啟發(fā)式的算法來為DBSCAN 進行采樣，稱為I-DBSCAN[23]（intersection DBSCAN）.該算法主要通過找到在球體交點的元素來展開聚類，I-DBSCAN 不需要附加任何參數(shù)，只需要原始算法中的 ε和MinPts即可且速度非常快.

DBSCAN++[24]先在數(shù)據(jù)集X中選擇m個均勻采樣點來組成子集S，然后計算S中點的密度.確定核心點后，將其余未標記的點聚類到離它們最近的核心點.選擇子集的時候，可以使用K中心[25]找到大小為m的子集，使X中任意點到子集最近點的最大距離最小化.換句話說，它試圖找到樣本點的最有效覆蓋.DBSCAN++的時間復雜度為O（nm），其中m的值是子集數(shù)，m?n.

SNG-DBSCAN[26]（subsampledε-neighborhood graph DBBSCAN）是DBSCAN 的簡單變體，算法基于一個下采樣的鄰域圖，只需要查詢點對的相似度.初始化圖的頂點為數(shù)據(jù)點，對所有數(shù)據(jù)點對進行采樣，如果點對小于ε，則添加到圖的邊緣部分，處理圖的剩余階段與DBSCAN 相同.SNG-DBSCAN 的時間復雜度可達到O（nlogn），在保持聚類質量的同時能夠很好地節(jié)省計算資源.

結合前文可知，IDBSCAN 是最早將DBSCAN 和采樣技術相結合的算法，KIDBSCAN 和QIDBSCAN都是在IDBSCAN 的基礎上改進的算法，但這3 種算法都只針對2 維數(shù)據(jù).其他幾種基于采樣技術的算法能夠有效降低DBSCAN 的時間復雜度，處理的數(shù)據(jù)維度較高，但能處理的數(shù)據(jù)量有限.

4 基于近似模糊的加速改進

由于精確聚類太過耗時，研究人員對近似方法產(chǎn)生了興趣，嘗試使用近似模糊的思想來提高DBSCAN 的性能.近似意味著聚類結果可能不同于原始DBSCAN 的結果.比如在原始DBSCAN 中，一個數(shù)據(jù)點p可以被分類到一個簇中，而近似的DBSCAN可以被指定到另一個類別中.

Brecheisen 等人[27]使用OPTICS 計算的枚舉對數(shù)據(jù)進行分區(qū)，使得相似的對象具有相鄰的枚舉值，再通過將多步驟查詢處理范式直接集成到聚類算法中.NG-DBSCAN[14]是一種高效的近似算法，其時間復雜度為O（ρnk2），其中k為近鄰數(shù)，參數(shù)ρ和k的取值都很?。é?3 和k=10），故計算成本主要由n主導.

AA-DBSCAN[28]（approximate adaptive DBSCAN）使用近似自適應ε距離來確定最小化參數(shù)所需要的額外成本計算，同時可以找到具有變化密度的簇.更具體地說，AA-DBSCAN 基于4 叉樹將3 維數(shù)據(jù)集劃分為均勻的單元，并創(chuàng)建密度層樹，形成了一個由稀疏到密集的不同密度區(qū)域構成的數(shù)據(jù)集，從而能夠找到不同密度的簇.該算法在聚類性能和運行時間上都有所提高.

ρ-Approximate DBSCAN[29]也是一種近似DBSCAN算法，并且時間復雜度可以控制在線性時間內.Gan等人[29]證明了在維度大于等于3 時，DBSCAN 問題需要O（n4/3）來解決，解釋了原有算法中DBSCAN 可以達到O（nlogn）時間復雜度的說法是錯誤的，認為ρ-Approximate DBSCAN 的概念將代替DBSCAN.

Schubert 等人[30]肯定了Gan 等人[29]的觀察，即在索引結構的支持下，DBSCAN 算法的時間復雜度可達到O（nlogn）的說法是不正確的.但也指出在文獻[29]中包含了誤導的陳述，如“在限定歐氏距離的條件下，所有的DBSCAN 都是難以忍受的緩慢”.但實際上，DBSCAN 原文[1]中清楚地表明該算法適用于任何距離.原始的DBSCAN 通過有效的指標合理地選擇參數(shù)，其性能不輸ρ-Approximate DBSCAN.因此對于ρ-Approximate DBSCAN 將取代大數(shù)據(jù)上的DBSCAN 提出了質疑.

Chen 等人[31]提出2 種簡單而快速的近似DBSCAN算法：1）KNN-BLOCK DBSCAN 使用快速近似KNN算法來識別核心塊、非核心塊和噪音塊.2）BLOCKDBSCAN[32]使用快速近似算法判斷2 個內核塊是否彼此密度可達.2 種算法都能高效地近似DBSCAN.

根據(jù)圖1 多重技術算法匯總表可知，近似技術通常不單獨作為一種加速技術，多作為其他加速技術的輔助，如分布式技術、空間劃分技術以及快速近鄰技術.由于近似技術不追求精確的聚類，當與其他技術相結合時，算法的性能可以顯著提高，這也是近似技術的一個強大優(yōu)勢.

5 基于快速近鄰的加速改進

近鄰搜索是在點集當中搜索點的最近鄰居，是許多研究鄰域一個重要而廣泛的問題，不少科研人員都在這一鄰域有所研究[33-38].快速近鄰在空間數(shù)據(jù)庫、信息檢索、數(shù)據(jù)挖掘、模式識別等領域都有廣泛的應用[39-41].將近鄰搜索技術與DBSCAN 算法相結合，可以有效提高DBSCAN 算法的性能.

LSH-DBSCAN（locality-sensitive hashing DBSCAN）[42]最近鄰搜索是通過Hash 優(yōu)化[33]來實現(xiàn)的.其原理是通過建立多個Hash 函數(shù)將原始數(shù)據(jù)點映射到Hash 表，映射過程需要滿足映射后相似距離的原始數(shù)據(jù)仍然相似.算法的時間復雜度為O（N·KlogC）（N為數(shù)據(jù)量，K為每個Hash 表的維度，C為聚類數(shù)），盡管該算法可以在線性時間復雜度下有效地降低數(shù)據(jù)維數(shù)并執(zhí)行最近鄰查詢，但缺點是參數(shù)增加并且參數(shù)難以確定.

Li[43]發(fā)現(xiàn)DBSCAN 使用暴力查詢來檢索每個點的鄰居，使得聚類過程中存在很多冗余的距離計算.因此提出了一種改進的基于鄰域相似度的DBSCAN算法（neighbor similarity DBSCAN，NS-DBSCAN）.該算法認為一個點應該與它的鄰居有相似的密度，因此，使用三角不等式對許多不必要的距離計算進行過濾.算法還使用Cover Tree[34]并行檢索每個查詢點的最近鄰居，從而識別出全局數(shù)據(jù)中核心點、邊界點、離群點.使用三角不等式、近鄰相似度、快速近鄰搜索等算法，可以極大地減少聚類過程中距離計算的次數(shù)，有效地提高了DBSCAN 算法的效率.

鄰居的鄰居也有可能是鄰居這一思想在NQDBSCAN（neighbor query DBSCAN）[44]算法中也有體現(xiàn).該算法利用鄰域搜索技術和索引技術來過濾掉大量不必要的密度計算.其基本思想是：當點p和點q很接近時，p和q應該有相似的鄰居.給定參數(shù)ε，2點離得越近，近鄰越相似.如圖6 所示，圖6（a）中的p和q比圖6（b）中的p和q擁有更多相似的鄰居.NQDBSCAN 利用這一思想，有效地減少了大量不必要的距離計算，并且在索引技術的幫助下該算法的平均時間復雜度為O（nlogn）.

Fig.6 Diagram of p and q similar neighbors[44]圖6 p，q 相似近鄰點圖[44]

Chen 等人[31]發(fā)現(xiàn)，DBSCAN 中識別每個點的類型本質上是KNN 問題，并且一個點的密度分布和它的相鄰點相似.這意味著一個點極有可能具有與其鄰近點相同的類型.基于此發(fā)現(xiàn)，研究人員首先使用FLANN[35]（fast library for approximate nearest neighbors）來檢測所有點中的塊.算法的時間復雜度如表3 所示，其中 β為數(shù)據(jù)分布因子，L為FLANN 中檢測的點數(shù)，χ為FLANN 的分支因子.

Table 3 Seven Nearest Neighbor DBSCAN Algorithms表3 7 種近鄰DBSCAN 算法

此外，Chen 等人[32]提出L2和L∞版本的BLOCKDBSCAN.算法使用Cover Tree[34]來識別內部核心塊、外部核心點以及邊界點.該算法的時間復雜度可以控制在O（nlogn），L2版本的算法能夠處理相對高維的數(shù)據(jù)，L∞版本則能夠適應高維數(shù)據(jù).

Kumar 等人[45]提出GDBSCAN（groups-DBSCAN），該算法使用分組的方法來加速搜索查詢.算法主要分為2 個階段：第1 階段在整個數(shù)據(jù)集上運行索引結構組以獲得1 組數(shù)據(jù)集；第2 階段通過使用在第1 階段派生的組來運行常規(guī)的DBSCAN 方法，以進行快速的ε-鄰域操作.分組法將每個模式分為主模式或從模式，通過將數(shù)據(jù)擬合到一個基于圖的結構來分割數(shù)據(jù)集.其中每個頂點是一個組，如果它們是可達的，則在2 組之間畫一條邊，然后將附近的模式不斷歸并到組.每一組都是一個以中心為主圖案的超球體，如果一個模式不屬于任何組，那么自身創(chuàng)建一個新的組.分組的方法確?？偸菫橐粋€給定的模式進行近鄰搜索，而不需要像DBSCAN 一樣搜索整個數(shù)據(jù)集.與DBSCAN 相比，GDBSCAN 的時間復雜度為線性，速度提升了1.5～2.2 倍.

KNN-DBSCAN[17]算法在高低維度的數(shù)據(jù)集下都是有效的，該算法使用基于隨機投影的近似算法[36]構造k-NNG，這是算法最昂貴的部分.DBSCAN 需要輸入數(shù)據(jù)集的ε-NNG（ε-nearest-neighbor graph），它的內存開銷達到O（n2），然而構造k-NNG 的內存開銷始終保持在O（nk），這比構造ε-NNG 的內存開銷要低得多.

KNN 技術主要通過加速鄰域搜索操作來提升算法的效率.表3 對7 種近鄰算法使用的近鄰技術以及時間復雜度進行了匯總.結合表3 和圖1 發(fā)現(xiàn)，相比于DBSCAN 算法的時間復雜度O（n2），KNN 加速技術最顯著的優(yōu)勢在于快，算法時間復雜度近乎線性.

6 基于空間劃分的加速改進

基于空間劃分的加速技術是將數(shù)據(jù)空間量化為有限數(shù)目的單元，從而形成一個網(wǎng)格結構，并在網(wǎng)格上進行聚類.常見的基于空間劃分的聚類算法有Grid-Clustering[46],STING（statistical information grid）[47],CLIQUE[48].相比于DBSCAN，基于空間劃分的聚類可以有效地降低時間復雜度.因此，不少研究人員將空間劃分的思想應用于DBSCAN 算法中，從而提升算法性能.

GriDBSCAN（grid DBSCAN）[49]使用網(wǎng)格來劃分周圍的空間，并相應地將數(shù)據(jù)點分為多個區(qū)域，每個分區(qū)分別進行DBSCAN.然后將所有分區(qū)的結果合并，從而得到數(shù)據(jù)的全局聚類.算法一開始使用d-1維的軸平行等距在超平面構造網(wǎng)格，如圖7 所示.網(wǎng)格的數(shù)量留給用戶選擇，但粒度對算法性能有很大影響.太細的粒度會降低性能，所以網(wǎng)格的寬度必須在所有維度上都大于2ε.

Fig.7 Use a grid to partition space[49]圖7 使用網(wǎng)格劃分空間[49]

根據(jù)網(wǎng)格單元對數(shù)據(jù)分區(qū)，每個分區(qū)都由單元內的所有點（內部點）加上單元周圍ε-包圍的點（外部點）組成，如圖8 所示.這樣，外部點會被包括在多個分區(qū)，但是內部點只在一個分區(qū)，這樣確保所有內部點的范圍查詢是準確的.考慮區(qū)分核心點和邊界點，為每個分區(qū)保留一組單獨的聚類標志.GriDBSCAN 通過網(wǎng)格的劃分和網(wǎng)格的合并可有效地提高DBSCAN 的性能，時間復雜度為O（n2/C），其中C為網(wǎng)格的數(shù)量.

Fig.8 The ε range of the cell[49]圖8 單元格的ε 范圍[49]

Huang 等人[50]提出的GNDBSCAN 以網(wǎng)格為聚類單元，在網(wǎng)格上建立SP-Tree 索引樹[51].這種方法大大提高了數(shù)據(jù)查詢的效率，再利用基于密度的思想對算法進行聚類，在提高效率的同時保證了聚類精度.Gunawan 等人[52]提出了一種基于2 維網(wǎng)格的算法，該算法也能將時間復雜度控制在O（nlogn），但是只適用于2 維數(shù)據(jù).

Chen 等人[53]提出了基于空間索引和網(wǎng)格技術的GMDBSCAN（multi-density DBSCAN cluster based on grid）算法.該算法利用空間劃分技術將單個網(wǎng)格定義為一部分，并根據(jù)網(wǎng)格密度獲取每個部分的局部MinPts參數(shù)，以此聚類多密度數(shù)據(jù).再使用SPTree[51]建立索引，采用位圖的鄰域關系，以避免重復查詢和計算.GMDBSCAN 算法中如果數(shù)據(jù)集維數(shù)不是很高，則運行時復雜度會隨著數(shù)據(jù)量的增加而線性增加.

GCMDDBSCAN[54]（multi-density DBSCAN based on grid and contribution）同樣也是對多密度數(shù)據(jù)進行改進的算法.在GCMDDBSCAN 中，引入空間劃分、貢獻值、遷移系數(shù)和樹索引結構對DBSCAN 進行優(yōu)化和改進.該算法顯著降低了運行時間，對大型數(shù)據(jù)庫的聚類能力得到了明顯提高.算法的時間復雜度為O（g2），g是所有數(shù)據(jù)點網(wǎng)格的總數(shù)，遠小于DBSCAN的O（n2），同時聚類結果的準確性沒有降低.

Wang 等人[55]研究了基于空間劃分和密度相結合的聚類算法，提出了GDStream（grid and density for data stream）算法.該算法將每個流數(shù)據(jù)點映射到對應的網(wǎng)格單元格中，利用每個數(shù)據(jù)點對鄰近單元格質心的影響系數(shù)，得到網(wǎng)格單元格的密度，從而較好地處理了網(wǎng)格單元中邊界點的問題.GDStream 能夠快速準確地識別聚類，具有一定的可行性.

GridDBSCAN[56]利用空間信息和減少鄰域查詢來降低時間復雜度.GridDBSCAN 首先對數(shù)據(jù)集進行虛擬網(wǎng)格化，然后識別單元格的類型，如果一個單元至少包含MinPts數(shù)量的點，那么它就是一個核心單元.如果一個單元和它的直接鄰域單元中存在的點的數(shù)量至少是最小的，那么這個單元就是密集的；反之，它被稱為稀疏的.最后使用union-find[5]算法來合并單元格，得到全局聚類.GridDBSCAN 的時間復雜度在最壞的情況下為O（nlogn），最壞的情況是所有的單元格都是稀疏的，需要對所有的點進行鄰域查詢.但即使是最壞的情況，GridDBSCAN 也比DBSCAN快很多.

Sakai 等人[57]提出了一種精確版本的基于網(wǎng)格的DBSCAN 算法，使用最小邊界矩形對連接單元步長進行高速處理，該算法可運行在高維情況下.

Boonchoo 等人[58]發(fā)現(xiàn)基于空間劃分的DBSCAN算法存在2 個問題：相鄰網(wǎng)格的數(shù)量隨維數(shù)呈指數(shù)級增長，即鄰域爆炸和合并時的冗余.為此，提出了一種名為GDCF（grid-based DBSCAN with cluster forest）的新算法.該算法利用位圖索引來支持高效的鄰域網(wǎng)格查詢.其次，基于union-find[5]算法的概念，設計了一種類似森林的結構，稱為聚類森林，以減少合并過程中的冗余.采用均勻隨機的順序執(zhí)行合并步驟，以優(yōu)化合并操作的次數(shù).實驗結果表明，GDCF算法的運行速度比傳統(tǒng)的基于空間劃分的DBSCAN算法快3 個數(shù)量級.

ρ-Approximate DBSCAN[29]采用樹形索引結構，將空間通過網(wǎng)格劃分為d維超平面，記錄所有單元包含的數(shù)據(jù)點數(shù)，再使用索引結構展開聚類.該算法的時間復雜度可以控制在線性時間內.

然而，Chen 等人[31]證明了ρ-Approximate DBSCAN的線性時間僅限于非常低的維度.因此，研究人員提出KNN-BLOCK DBSCAN.該算法相對優(yōu)勢在于按塊來處理數(shù)據(jù)，每個塊都有一個動態(tài)空間范圍，通過FLANN 識別核心塊、非核心塊以及噪聲塊.然后使用快速算法將彼此密度可達的核心塊合并，并將非核心塊中的每個點分配給適當?shù)娜杭罱K得到全局聚類.圖9 為KNN-BLOCK DBSCAN 的基本流程.在4～256 維數(shù)據(jù)的實驗中表明，相較于ρ-Approximate DBSCAN，KNN-BLOCK DBSCAN 計算速度提高了1.5～35 倍.

Fig.9 KNN-BLOCK DBSCAN basic process[31]圖9 KNN-BLOCK DBSCAN 基本流程[31]

類似地，Chen 等人[32]還提出一個類似的算法BLOCK-DBSCAN.該算法基于近鄰搜索算法Cover Tree 尋找固定大小的ε/2 范數(shù)球塊，通過近似合并技術實現(xiàn)聚類.與ρ-Approximate DBSCAN 正好相反，BLOCK-DBSCAN 滿足DBSCAN 中定義的連通性，但不滿足極大性.

圖10 對基于空間的DBSCAN 算法建立了關系脈絡圖.空間劃分技術使用網(wǎng)格對數(shù)據(jù)空間進行劃分，以網(wǎng)格為單元開展聚類可以有效提升速度并且能夠處理多密度數(shù)據(jù)[53-54]和流數(shù)據(jù)[55].除了GDCF，空間劃分技術還常與其他技術相結合，很多并行化加速算法[6-7,9-10,12-13]也使用該技術進行分區(qū)處理.

Fig.10 Relationship graph of acceleration algorithm based on space partition圖10 基于空間劃分的加速算法關系圖

7 基于GPU 的加速改進

GPU 的主要優(yōu)勢是以低成本提供極高的并行性和高帶寬的內存?zhèn)鬏?研究人員也希望在聚類中能利用這些優(yōu)勢，因此提出了不少基于GPU 并行化的DBSCAN 改進算法.

CUDA-DClust（compute unified device architecturedensity-based clustering）[59]將對象p分配給每個線程塊，并執(zhí)行DBSCAN 來同時組成多個子類別.在每個塊中創(chuàng)建的子簇稱為鏈，通過在一個塊中的多個線程同時計算不同對象與p的距離，能夠非常有效地計算p的ε-鄰域.如果一個對象包含在2 個或多個不同的鏈中會發(fā)生碰撞，碰撞鏈將在碰撞矩陣中進行檢查.在最后階段，所有碰撞鏈被合并形成一個簇.研究人員發(fā)現(xiàn)索引結構能夠進一步提高速度，因此提出了CUDA-DClust*.CUDA-DClust 的性能比DBSCAN高15 倍，CUDA-DClust*以使用簡單的索引結構將CUDA-DClust 的速度進一步提高11.9 倍.

然而，Loh 等人[60]發(fā)現(xiàn)CUDA-DClust 需要計算數(shù)據(jù)集中所有對象之間的距離來找到相鄰對象，并且對象和計算結果存儲在GPU 昂貴的片外存儲器中.為此提出了一種新的算法CudaSCAN（CUDA-based DBSCAN），它通過更好地利用GPU 來提高DBSCAN的效率.CudaSCAN 由3 個階段組成：1）將整個數(shù)據(jù)集劃分為大小為GPU 中片內共享內存大小整數(shù)倍的子區(qū)域；2）并行子區(qū)域內的局部聚類；3）合并局部聚類結果.CudaSCAN 允許子區(qū)域之間的重疊，以確保每個子區(qū)域中獨立、并行的局部聚類.這反過來使得對象和中間結果能夠存儲在片內共享存儲器中，其訪問成本比片外全局存儲器低數(shù)百倍.CudaSCAN 的性能比CUDA-DClust 高出163.6 倍.

G-DBSCAN[61]（GPU-DBSCAN）以簡單的數(shù)據(jù)索引而著稱，其關鍵思想是使用GPU 構建與數(shù)據(jù)集相對應的密度連通圖，然后對該圖并行執(zhí)行多個BFS（breath first search）搜索.將G-DBSCAN 與CUDA-DClust進行比較，與在CPU 上運行相比，CUDA-DClust 通過GPU 實現(xiàn)了15 倍加速，而G-DBSCAN 實現(xiàn)了112 倍加速.

Thapa 等人[62]使用了鄰接矩陣法成功地實現(xiàn)了并行化的DBSCAN 算法.鄰接矩陣法利用算法中固有的數(shù)據(jù)獨立性來最大化并行性，該方法的優(yōu)點是：只需要計算1 次鄰接矩陣的單行，就可以確定每個點的類型.內存需求減少到O（n）數(shù)量級，可以很好地拓展到非常大的數(shù)據(jù)集中.Cal 等人[63]同樣通過創(chuàng)建鄰域矩陣將最耗時的鄰域搜索和對象的數(shù)據(jù)類型信息使用GPU 并行獲得，從而縮短全局計算時間.

Mustafa 等人[64]發(fā)現(xiàn)盡管提出了很多基于GPU 并行化的DBSCAN 加速算法，但是這些算法都沒有在實驗上相互比較.因此對Thapa 等人[62]的算法，CUDADClust[59]和G-DBSCAN[61]進行了實驗比較，并將它們與R-Tree[8]索引的單線程也進行了比較.實驗結果表明，G-DBSCAN 在所有數(shù)據(jù)集中始終是最快的，但是內存效率最低.CUDA-DClust 在速度和內存效率之間取得了良好的平衡，該算法幾乎與G-DBSCAN 一樣快，而消耗的內存卻少了幾個數(shù)量級，這使其成為較大數(shù)據(jù)集的不錯選擇.Thapa 等人[62]的算法，需要最少的實現(xiàn)工作，它可以比多線程CPU DBSCAN 算法更快，但僅適用于較大的數(shù)據(jù)集.此外，具有RTree 索引的原始單線程CPU DBSCAN 算法顯示的執(zhí)行時間比GPU 算法中觀察到的執(zhí)行時間慢幾個數(shù)量級.這極大地激勵了人們使用G-DBSCAN 和CUDADClust 等技術.

Mr.Scan[65]則是將基于MRNet[66]樹的分布網(wǎng)絡與配備GPU 的節(jié)點相結合，通過有效地劃分點空間和優(yōu)化DBSCAN 在密集數(shù)據(jù)區(qū)域上的計算來提高性能.結果表明，Mr.Scan 在17.3 min 內將推特數(shù)據(jù)集的65 億個點聚集在Cray Titan 上的8 192 個GPU 節(jié)點上，此前所有其他并行DBSCAN 實現(xiàn)都只展示了聚集多達1 億個點的能力.在此基礎上，文獻[67]使用消息傳遞而不是向文件系統(tǒng)寫入中間文件來減少數(shù)據(jù)分發(fā)的時間，并且通過改善GPU 的負載均衡將Mr.Scan 的總運行時間縮減到8.3 min.

除此之外，還有不少算法將GPU 與其他技術相結合來提高原算法的性能.如GSCAN（grid-based DBSCAN）[68]使用網(wǎng)格來減少不必要的距離計算.Qian 等人[69]在傳統(tǒng)網(wǎng)格的基礎上提出了一種基于多網(wǎng)格的流數(shù)據(jù)聚類算法（multi-grid），其核心是將整個網(wǎng)格空間有效合理地劃分為全局網(wǎng)格、局部網(wǎng)格、邊界網(wǎng)格，從而限制了鄰居的搜索范圍.Chang 等人[70]提出了GPGPU-DBSCAN（GPU for graph-DBSCAN），利用相似分量的點建立索引，從而快速識別核心點.同時該算法通過與核心點的并行連接部分來指定索引操作和聚類數(shù)據(jù)的搜索條件，以減少點之間的計算量.

值得注意的是，Gowanlock 等人[71]提出的HYBRIDDBSCAN 算法將GPU 與多核CPU 結合使用，進行算法吞吐量優(yōu)化，極大地降低了DBSCAN 的處理時間.這一算法使用了2 個不同的GPU 內核，再利用基于網(wǎng)格的索引方案來提高聚類性能.Prokopenko 等人[72]提出了一個新的GPU 上的DBSCAN 通用框架，并在框架內提出了2 種基于樹的算法，分別為FDBSCAN（“fused” DBSCAN）和FDBSCAN-DenseBox.2 種算法都融合了鄰域搜索來更新聚類信息，但與在處理密集區(qū)域上有所不同，F(xiàn)DBSCAN 關注低維數(shù)據(jù)并取得了卓越性能.

圖11 對上述文獻[71-72]所提的基于GPU 技術的加速DBSCAN 進行了梳理.可以發(fā)現(xiàn)，GPU 加速技術可以通過對數(shù)據(jù)進行劃分、分配線程以及結合索引技術等顯著提升算法的時間復雜度.與DBSCAN順序處理數(shù)據(jù)相比，GPU 加速技術能夠提升上百倍的速度，并且可以聚類上億級別的大規(guī)模數(shù)據(jù)集.但對于超高維數(shù)據(jù)而言，仍然是個挑戰(zhàn).

Fig.11 Relationship diagram of a few GPU acceleration algorithms圖11 多種GPU 加速算法關系圖

8 各種加速技術比較

我們對基于不同加速技術的DBSCAN 算法所報告的最大數(shù)據(jù)量和最大維度運行時間進行了匯總，對于部分未給出數(shù)據(jù)維度信息的文章我們不作展示，如表4 所示.表5 梳理了具有聚類性能指標的加速算法，表6 對不同加速技術的優(yōu)缺點進行了比較，結合圖1 的多重技術使用情況，我們有5 點發(fā)現(xiàn)：

Table 4 Comparison of Maximum Data Amount Running Time of Typical Algorithms with Different Acceleration Techniques表4 不同加速技術典型算法最大數(shù)據(jù)量運行時間對比

Table 5 Comparison of Clustering Performance of Different Acceleration Algorithms表5 不同加速算法聚類性能比較

Table 6 Comparison of Advantages and Disadvantages of Different Acceleration Techniques表6 不同加速技術優(yōu)缺點比較

1）從處理數(shù)據(jù)規(guī)模來看.分布式技術以及GPU并行化技術能處理的數(shù)據(jù)量最大.但分布式技術能夠處理的維度相對較高且具有更高的效率.

2）從數(shù)據(jù)維度的角度來看.相對來說，基于KNN加速與近似算法處理高維數(shù)據(jù)的報告較多，但能處理的數(shù)據(jù)量還是比較有限；基于采樣、基于分布式、基于GPU 的算法所能處理的數(shù)據(jù)維度也相對較高.但我們注意到伴隨著維度的升高，文獻中報告的數(shù)據(jù)量反而減小了，之所以有這種現(xiàn)象，是因為現(xiàn)有的這些加速算法面對大規(guī)模高維數(shù)據(jù)，還難以取得理想的效果.

3）從成本角度來看.①并行化算法成本相對較高，含有不易控制的額外成本，實現(xiàn)上較為困難.另外還不易移植.②對于GPU 的并行算法，主要通過CUDA 或OpenCL 完成，編程不便，不易調試，且需要針對要處理的數(shù)據(jù)特征設計出高效的數(shù)據(jù)訪問與調度策略，難度較大.③KNN 技術、網(wǎng)格技術、采樣技術以及近似模糊均致力于減少冗余計算來加速，這類算法成本低、實現(xiàn)容易.④近似算法損失了部分精度，但在滿足一定精度的條件下，可以極大加速DBSCAN 算法.對于大規(guī)模數(shù)據(jù)而言，要準確地完成聚類成本較高，在不要求精確計算結果且成本有限的情況下，近似算法則非常適合.

4）從技術交叉角度來看.①表4 列出的高效算法中，幾乎都是多種技術融合產(chǎn)生的.其中，并行KNN-DBSCAN 將KNN 技術與分布式結合，實現(xiàn)了對上百億規(guī)模的20 維數(shù)據(jù)的數(shù)據(jù)處理，且運行極快.②空間劃分技術在多數(shù)算法中都有應用，但空間劃分技術在高維空間中幾乎失效，因而也很難擺脫“維數(shù)災難”的困擾.③純粹的單一技術加速效果有限，如純基于近鄰搜索的加速算法處理的數(shù)據(jù)量不夠大，純分布式加速算法能處理的維度較低等.

5）從聚類性能來看.主要是通過聚類評價指標比較，如DI，CH，DBI，NMI，RI，ARI，F(xiàn)1，Purity[73-74]等.各種指標有不同的量化值來評判聚類結果的優(yōu)與劣.這些指標大體上可以分為2 類.

第1 類：內部評價指標.此類指標基本上以“類內越相似越好，類別差異越大越好”為基本原則.如DI指標通過簇間分離度與簇內緊密度的比值來衡量，CH指標通過簇內緊密度和簇間分離度的比值來評價.

第2 類：外部評價指標.此類指標則是對聚類后的結果標簽進行評價.如Rand Index通過判斷預先定義的正確類別標簽與聚類結果標簽的重疊程度來進行評價，NMI通過正確的類別標簽與聚類結果標簽的互信息進行評價.然而，實際上很少有這樣的經(jīng)過人工標注過的大規(guī)模數(shù)據(jù)集.因而，有些算法將原始DBSCAN 的聚類結果作為“標準答案”，在使用相同參數(shù)的前提下與之對比，應用匈牙利算法[75]計算出準確度，如KNN-BLOCK DBSCAN 和BLOCK DBSCAN[31-32].但是，這種比較也只能僅在小數(shù)據(jù)集上，其原因在于原始DBSCAN 時間復雜度過高，難以在大規(guī)模數(shù)據(jù)集上運行.

目前，表4 中所列的算法主要工作都是在比較速度，而性能比較的報告較少.另外，有多數(shù)算法未提供代碼，提供源碼的也有一部分因各種原因不能運行，如LSH-DBSCAN[42]缺少相關運行庫.所以，表5顯示了部分性能比較.

從表6 可以看出，不同的加速技術所采用的聚類評價指標有所不同，如近似技術通過與DBSCAN 結果的相似程度來判斷聚類效果的好壞，采樣技術則通過不同類別的相同結果進行評價.但是，這些加速算法都能獲得與DBSCAN 相當?shù)木垲愋Ч?

9 快速DBSCAN 在多個領域的應用

DBSCAN 自1996 年被提出以來，至今已有近30 年.該算法廣泛應用于各個領域，如數(shù)據(jù)挖掘、圖像處理、生物農(nóng)業(yè)及其他應用[76-81].快速化DBSCAN在異常檢測、數(shù)據(jù)挖掘、圖像處理、生物醫(yī)學、網(wǎng)絡安全等眾多領域也有不少應用.下文將對3 個主要的應用領域進行介紹.

9.1 異常檢測應用

稱重設備是散裝物料貿易的測量設備，由于長時間高負荷運行，計量不準確等故障頻繁發(fā)生，直接造成了大量的經(jīng)濟損失.因此，及時檢測、診斷是很有必要的.電子皮帶秤是使用最多的稱重設備，Zhu等人[82]以皮帶秤作為研究對象，對其進行故障檢測和診斷.為了實現(xiàn)皮帶秤的智能檢測和診斷，提出了一種方案，即提取正常數(shù)據(jù)的同時利用聚類算法檢測故障數(shù)據(jù)，然后通過對檢測到的故障數(shù)據(jù)進行分類來識別故障模式.所使用的聚類算法是利用相似性函數(shù)代替距離函數(shù)的改進DBSCAN，并將其應用于沸水在線故障檢測，以應對不同物料流量或同一流量的物料在任意稱重單元上隨時增減而導致的密度數(shù)據(jù)不均勻.使用改進的DBSCAN 的皮帶秤故障檢測模型具有良好的實時性和對處理不均勻密度數(shù)據(jù)的魯棒性.

Chernov 等人[83]為聚類技術在工業(yè)和運輸中的應用提供了一個新的領域，提出了鐵路智能控制系統(tǒng)網(wǎng)絡子系統(tǒng)產(chǎn)生的電信業(yè)務點異常檢測技術，使用PDBSCAN[3]在IP 網(wǎng)絡數(shù)據(jù)中進行點異常檢測.考察了中國鐵路運輸協(xié)會售票服務的交通流量，這部分鐵路運輸信息系統(tǒng)是實時運行的，但它處理的運輸量并不像主要鐵路運輸過程中所涉及的子系統(tǒng)那樣龐大.PDBSCAN 技術能夠適用于鐵路智能控制系統(tǒng)網(wǎng)絡基礎設施中由各種事件引起的點異常的魯棒檢測.

Ghallab 等人[84]在DBSCAN 的基礎上，利用彈性分布數(shù)據(jù)集來檢測影響物聯(lián)網(wǎng)技術數(shù)據(jù)質量的離群點，在提高檢測質量的同時還能夠處理高維數(shù)據(jù).Garg 等人[85]則是提出了一種新的多階段異常檢測技術支持在物聯(lián)網(wǎng)的應用上執(zhí)行計算.在提出的解決方案的第1 階段，從數(shù)據(jù)集當中捕獲相關的特征集，第2 階段將特征集進行分割，第3 階段采用LSH[33]來解決最近鄰搜索問題，最后得到參數(shù)集對異常數(shù)據(jù)進行檢測.

9.2 數(shù)據(jù)挖掘應用

Web 用戶挖掘是挖掘技術在Web 日志數(shù)據(jù)庫中的應用，它用于從Web 訪問日志中查找用戶訪問模式.Santhisree 等人[86]提出了一種新的粗糙集DBSCAN聚類算法，用于識別用戶頁面訪問的行為、訪問發(fā)生的順序，使得在發(fā)現(xiàn)共同興趣的群體上具有更好的效率.

Yu 等人[87]則是通過分區(qū)的DBSCAN 高效地從日志數(shù)據(jù)中聚類大量的網(wǎng)絡文檔.改進的DBSCAN除了能在網(wǎng)絡日志中挖掘出有用信息，在地震監(jiān)測中也有應用.Scitovski[88]考慮將Rough-DBSCAN[22]應用于地震區(qū)域劃分.使用Rough-DBSCAN 不僅能對地震進行分區(qū)，識別出非凸形狀，而且能降低時間復雜度，進一步用于大型數(shù)據(jù)集.

在高分辨率雷達系統(tǒng)中，采樣密度往往是非等距的，使用普通的聚類算法往往不能達到想要的效果.為此，Kellner 等人[89]提出了基于網(wǎng)絡的DBSCAN來處理高分辨率雷達數(shù)據(jù)，在保持原有算法優(yōu)勢的同時，對雜波和非等距采樣密度具有魯棒性且在速度上優(yōu)于原始算法40%～70%.

Xia 等人[90]發(fā)現(xiàn)復雜的城市交通網(wǎng)絡為移動乘客推薦出租車等候點時有困難，且在Spark 并行處理框架下，DBSCAN 的邊界識別尤為困難.因此，提出了優(yōu)化后的SP-DBSCAN 算法，該算法不僅解決了傳統(tǒng)DBSCAN 的數(shù)敏感問題，能夠為客戶推薦最佳的候車點，而且在分布式框架上解決了大規(guī)模流量數(shù)據(jù)的數(shù)據(jù)分區(qū)和聚類時的分布式存儲和并行計算問題.

9.3 圖像處理應用

聚類算法在圖像處理中也有不少應用，Bandyopadhyay[91]將k-means[2]聚類和DBSCAN 應用于人腦核磁共振圖像中腦腫瘤的聚類和分割問題.使用了大量來自放射影像數(shù)據(jù)庫的核磁共振影像進行實驗，發(fā)現(xiàn)k-means 的聚類結果比較嘈雜，但是許多聚類還能進一步分析.而DBSCAN 由于輸入數(shù)據(jù)密度高度集中，聚類效果讓人滿意.

Baselice 等人[92]對于核磁共振圖像提出了一種新的分割方法，其基于2 個主要的創(chuàng)新：1）該方法利用每個像素的估計質子密度和弛豫時間，而不是其灰度強度，該特征使得該算法特別健壯，并且允許對識別的片段進行分類.2）該方法使用了GDBSCAN[93]方法在區(qū)域估計的有效性方面獲得了優(yōu)勢，與基于歐幾里德距離的技術相比，該技術能夠提高正確的分類率.

Kurumalla 等人[94]提出了一個高效的DBSCAN算法用于圖像分割，該方法使用了KNN 和DBSCAN技術來確定所需要的 ε和最小點數(shù).首先將RGB 彩色圖像轉換為灰度圖像，然后使用圖像處理的濾波技術從轉換的圖像中去除噪聲，從而確定參數(shù)值，即最小點數(shù)和ε值.將這些參數(shù)作為初始值，對與ε和最小點數(shù)相關的灰度圖像執(zhí)行原始的DBSCAN 聚類算法.與現(xiàn)有的圖像分割方法相比，該方法大大降低了圖像中的噪聲，分割效果也有所提高.

10 總結與展望

DBSCAN 是基于密度聚類算法中最為常見的算法之一，其算法由于思想簡單、能夠識別不同形狀的簇且有效地處理噪聲點而倍受歡迎，但是算法時間復雜度高達O（n2）以至于無法處理大型數(shù)據(jù)集.因而許多研究人員進行了深入而有成效的工作，極大地提升了DBSCAN 的速度.

本文梳理了前人對于提升DBSCAN 速度的研究，從加速手段所針對的目標角度看，可以分為減少冗余計算和并行化兩大類.但從具體的加速手段來看，本文按3 個規(guī)則提出了一個簡單的劃分方法，并將這些方法分為6 個類別：基于分布式、基于采樣技術、基于近似模糊、基于快速近鄰、基于空間劃分技術、基于GPU 加速技術.

我們發(fā)現(xiàn)，多技術融合的加速算法（特別是分布式、近似近鄰搜索技術）要遠優(yōu)于其他單技術加速算法，其中近似模糊化、并行化與分布式化是當前最為行之有效的方法，但成本較高、不易實現(xiàn).

雖然這些改進在一定程度上都可以提升算法速度，但是還有一些局限性，還存在一些挑戰(zhàn)，即未來可以研究的方向：

1）利用單種或少數(shù)幾種技術對 DBSCAN 進行加速效果還稍顯不足.近年在近鄰搜索與GPU 并行化加速工作上有不少進展，如FAISS[98]利用GPU 可實現(xiàn)數(shù)十億級別數(shù)據(jù)的快速精確/模糊KNN 檢索.通過類似FAISS 與其他技術融合來改進DBSCAN 的工作還鮮有報道.

2）當數(shù)據(jù)大規(guī)模地分布在眾多相互不能共享的環(huán)境中時（如眾多醫(yī)療數(shù)據(jù)分散在各個不同醫(yī)療機構，相互之間因競爭關系不愿或不能相互共享）[95-96]，針對這類涉及到隱私的數(shù)據(jù)，現(xiàn)有的DBSCAN 也無法完成聚類.

3）絕大多數(shù)現(xiàn)有的算法將數(shù)據(jù)一次性讀取，然而當數(shù)據(jù)達到TB 級別規(guī)模時，現(xiàn)有的算法仍然很難處理.另外，對于大規(guī)模的不均衡數(shù)據(jù)[97]，平衡好并行任務之間的負載有待深入研究[4,6-7].

作者貢獻聲明：陳葉旺提出了研究命題，設計了研究思路，負責論文的撰寫；曹海露負責論文的補充和修改；陳誼負責論文整體結構；康昭、雷震負責審核與修訂其中部分算法；杜吉祥負責最終版本修訂.