DBSCAN是一種基于密度的空間聚類算法。如在點(diǎn)p鄰域范圍內(nèi)的點(diǎn)達(dá)到一定數(shù)量則點(diǎn)p稱為核心點(diǎn)，若點(diǎn)q在p的鄰域范圍內(nèi)，則p直接密度可達(dá)q，且p、q屬于同一密集區(qū)域。由這種關(guān)系連接的最大數(shù)據(jù)點(diǎn)集形成一個(gè)簇。DBSCAN算法有檢測(cè)任意形狀的簇、不需要提前知道檢測(cè)簇的數(shù)量等優(yōu)點(diǎn)。隨著近年來(lái)大規(guī)模并行化的熱潮，又出現(xiàn)了許多并行DBSCAN算法。大多數(shù)并行DBSCAN算法中，為并行地發(fā)現(xiàn)直接密度可達(dá)關(guān)系，相鄰的點(diǎn)被分配到相同的數(shù)據(jù)分區(qū)中進(jìn)行并行處理，以方便計(jì)算相鄰點(diǎn)的密度。但是，這種數(shù)據(jù)分區(qū)方案會(huì)導(dǎo)致一些問(wèn)題，如分割成本大、子區(qū)域重疊、數(shù)據(jù)分區(qū)之間的負(fù)載不平衡等，其中負(fù)載問(wèn)題在分布不均勻的數(shù)據(jù)集中尤為體現(xiàn)。

為了解決這些問(wèn)題，本文提出了一種新的并行DBSCAN算法，隨機(jī)分區(qū)DBSCAN，簡(jiǎn)稱RP-DBSCAN，它使用偽隨機(jī)劃分和兩級(jí)單元格字典。偽隨機(jī)劃分是一種基于單元格的數(shù)據(jù)劃分方案，它可以隨機(jī)采樣小的單元格，而不是點(diǎn)本身。無(wú)論數(shù)據(jù)如何分布，它都可以實(shí)現(xiàn)負(fù)載平衡，同時(shí)保持DBSCAN所需的數(shù)據(jù)連續(xù)性。兩級(jí)單元格字典是整個(gè)數(shù)據(jù)集的一個(gè)高度凝煉的摘要，來(lái)表示每個(gè)隨機(jī)分區(qū)。該算法能夠?qū)崿F(xiàn)同時(shí)找到每個(gè)數(shù)據(jù)分區(qū)的局部聚類，然后將這些局部聚類合并得到全局聚類。

一．偽隨機(jī)劃分

本文定義d維空間中的一個(gè)單元格是一個(gè)對(duì)角線長(zhǎng)度為ε 的d維超立方體，ε 是一個(gè)表示鄰域半徑的參數(shù)。如果至少有一個(gè)數(shù)據(jù)點(diǎn)位于一個(gè)密集區(qū)域內(nèi)，則可以保證該單元格中的所有數(shù)據(jù)點(diǎn)都屬于同一簇。這大大簡(jiǎn)化了之后的聚類合并過(guò)程。在進(jìn)行數(shù)據(jù)分區(qū)時(shí)，我們隨機(jī)采樣單元格，而不是采樣數(shù)據(jù)點(diǎn)，因此稱為偽隨機(jī)劃分。然后，將相同顏色的單元格及其內(nèi)部的數(shù)據(jù)點(diǎn)劃分為同一個(gè)分區(qū)。由于ε 遠(yuǎn)小于整個(gè)空間的長(zhǎng)度，這種劃分也可以實(shí)現(xiàn)真正的隨機(jī)劃分的效果。圖 1 說(shuō)明了偽隨機(jī)分區(qū)的思想，不同顏色代表不同分區(qū)。

圖1 偽隨機(jī)劃分

二．兩級(jí)單元格字典

兩級(jí)單元格字典是整個(gè)數(shù)據(jù)集的一個(gè)摘要。本質(zhì)上它是一個(gè)兩級(jí)的樹(shù)。第一級(jí)的節(jié)點(diǎn)對(duì)應(yīng)單元格，第二級(jí)的節(jié)點(diǎn)對(duì)應(yīng)子單元格，其邊長(zhǎng)為單元格的h分之一，其中h由用戶給出以指定近似度。每個(gè)節(jié)點(diǎn)編碼每個(gè)（子）單元格的密度及其位置。密度是其內(nèi)部的點(diǎn)數(shù)，而位置可以用它們所屬單元內(nèi)的子單元的順序來(lái)表示，故只用d(h? 1)位。（d是維度，h是字典級(jí)數(shù)）如圖 2，h = 2，d= 2，只需兩位來(lái)表示子單元格位置（00，01，10，11）。

圖2 兩級(jí)單元格字典的構(gòu)建

因此，可以得出兩級(jí)單元格字典總大小為

如果數(shù)據(jù)集非常大，由于內(nèi)存的限制，有可能無(wú)法立即加載整個(gè)兩級(jí)單元格字典，因此把字典劃分成較小的子字典，它由根節(jié)點(diǎn)集合的一個(gè)子集以及與它們連接的葉節(jié)點(diǎn)組成。

三. 算法實(shí)現(xiàn)的三個(gè)階段

1. 數(shù)據(jù)分區(qū)

通過(guò)偽隨機(jī)劃分對(duì)整個(gè)數(shù)據(jù)集進(jìn)行分區(qū)，并構(gòu)建兩級(jí)單元格字典，為并行處理做好準(zhǔn)備。向并行系統(tǒng)中的每個(gè)工作者發(fā)送一個(gè)分區(qū)和對(duì)應(yīng)的兩級(jí)單元格字典。如圖3，整個(gè)空間被劃分為諸多單元格，其中沒(méi)有為空區(qū)域創(chuàng)建單元格。將黃色和綠色單元格劃分到兩個(gè)不同的分區(qū)P1和P2中。然后為每個(gè)分區(qū)生成一個(gè)兩級(jí)單元格字典。

圖3 數(shù)據(jù)分區(qū)

2. 單元格圖的構(gòu)造

通過(guò)(ε, ρ)區(qū)域查詢的方式區(qū)分單元格是否為核心單元格，構(gòu)造單元格圖時(shí)將排除非核心單元格。如圖3中的Cnc1-Cnc5判斷為非核的，它們?cè)趫D4中將被排除。然后，從每個(gè)分區(qū)的每個(gè)核心單元搜索其所有完全或部分直接可達(dá)的單元格來(lái)構(gòu)建一個(gè)單元圖。這些單獨(dú)的關(guān)系可以在單元格級(jí)別上進(jìn)行聚合，從而生成一個(gè)單元格圖。單元格圖的頂點(diǎn)是單元格，邊是單元格之間的可達(dá)性關(guān)系。總的來(lái)說(shuō)，一個(gè)單元格圖表示從一個(gè)給定的分區(qū)中獲得的局部聚類。

圖4 單元格圖構(gòu)造

(ε, ρ)區(qū)域查詢：

如圖5所示，若點(diǎn)p與子單元格中心scn的距離小于ε ，那么，就將這個(gè)子單元格加入到點(diǎn)p的鄰居集合當(dāng)中。當(dāng)點(diǎn)p的鄰居點(diǎn)數(shù)大于等于設(shè)定的參數(shù)minPts，就把包含p的單元格標(biāo)記為核心單元格。

圖5 (ε,ρ)區(qū)域查詢

3. 單元格圖的合并

這一部分主要包括漸進(jìn)式圖合并和點(diǎn)標(biāo)記兩個(gè)過(guò)程。首先，結(jié)合從每個(gè)工作者返回的對(duì)應(yīng)每個(gè)分區(qū)的單元格圖，確認(rèn)每條邊直接可達(dá)性關(guān)系，以合并成全局單元格圖。之后，根據(jù)合并后的圖對(duì)聚類進(jìn)行擴(kuò)展，并根據(jù)最終的聚類結(jié)果來(lái)標(biāo)記所有的點(diǎn)。整個(gè)過(guò)程就是由局部聚類產(chǎn)生全局聚類。例如在圖 6 中，單元格圖簡(jiǎn)單合并后要進(jìn)行邊類型檢測(cè)，即判斷是完全邊(深色實(shí)線)，部分邊（實(shí)線箭頭）還是未知邊（虛線箭頭），還要進(jìn)行減邊操作，根據(jù)樹(shù)的結(jié)構(gòu)去除冗余邊，最終得到一個(gè)樹(shù)式的全局單元格圖。然后，圖 7 中進(jìn)行點(diǎn)標(biāo)記，圖4中位于P1和P2左下角的單元格在圖 7 中形成了一個(gè)C1簇，將單元格其中的點(diǎn)標(biāo)記為同一個(gè)顏色，即為最終聚類的結(jié)果。

圖6 漸進(jìn)式圖合并

圖7 點(diǎn)標(biāo)記

四. 總結(jié)

本文提出采用隨機(jī)劃分策略并行運(yùn)行DBSCAN。為此，提出了一種基于單元格的數(shù)據(jù)分割策略，即偽隨機(jī)劃分，它具有區(qū)域劃分策略和隨機(jī)劃分策略的優(yōu)點(diǎn)。為了能夠在隨機(jī)分割上執(zhí)行區(qū)域查詢，本文設(shè)計(jì)了兩級(jí)單元格字典，它是整個(gè)數(shù)據(jù)集的一個(gè)高度凝煉的摘要。將它們放在一起，開(kāi)發(fā)了一個(gè)高效的并行DBSCAN算法RP-DBSCAN。本文使用GeoLife，Cosmo50，OpenStreetMap等大規(guī)模數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，將RP-DBSCAN與SPARK-DBSCAN，ESP-DBSCAN等其它6種算法進(jìn)行效率和精確度的對(duì)比。結(jié)果顯示，RP-DBSCAN更快，更精準(zhǔn)，更高效且可擴(kuò)展性強(qiáng)。RP-DBSCAN顯著地超過(guò)了最先進(jìn)的并行DBSCAN算法高達(dá)180倍。此外，只有RP-DBSCAN可以處理最大的362GB數(shù)據(jù)集，而其他算法則不能，有力地驗(yàn)證了其性能的優(yōu)越性。本文的研究工作顯著地提高了DBSCAN算法在大數(shù)據(jù)時(shí)代的可用性。


審核編輯：劉清