基于MCMC的DBSCAN改進算法

李建伏，巴建軍

(中國民航大學 計算機科學與技術學院，天津 300300)

0 引 言

目前已有多種聚類算法，主要分為劃分聚類、層次聚類和基于密度的聚類算法[1]。其中，由于能發現任意形狀的簇，且能很有效地處理噪聲數據，基于密度的聚類算法得到了廣泛應用。基于密度的聚類有很多實現算法，其中DBSCAN[2,3]算法(density based clustering of application with noise)最為流行。然而，DBSCAN的一個缺點是其時間復雜度較高，文獻[4,5]證明了DBSCAN算法的時間復雜度為O(n2)，其中n為待聚類對象個數。這限制了其處理大規模數據的能力，尤其是在大數據時代，算法的運行時間變得尤為重要[6]。

為了降低算法的運行時間，人們已提出多種策略改進DBSCAN。第一類改進思路是通過借助一定的策略來加速對象的鄰域查詢操作，如文獻[7-9]。第二類加快DBSCAN算法的方法是采用并行化的策略，如文獻[10-12]。第三類改進策略是選擇性地擴展部分核心對象。導致DBSCAN算法時間復雜度高的主要原因在于其需要對所有核心對象進行逐一擴展。而實際上，核心對象的鄰域之間存在著大量的重疊，沒有必要對所有核心對象進行擴展。因此，選擇性地擴展部分核心對象是提高DBSCAN效率的一個有效途徑。基于不同的核心對象選擇方法形成了不同的改進算法。如文獻[13]選擇核心對象鄰域的邊界對象作為待擴展對象；文獻[14]隨機選擇處于以當前核心點為圓心，介于半徑為ε和2ε兩個圓之間的環狀區域內的對象作為下一個擴展對象；文獻[15]首先利用一個快速的聚類算法將原始數據劃分為多個簇，然后將這些簇的代表節點作為待擴展節點。

本文提出一種基于部分核心對象擴展策略的DBSCAN改進算法，稱為DBSCAN++。DBSCAN++的基本思想是優先擴展拓展能力較強的核心對象，其中核心對象的拓展能力通過從密度和與已經擴展過的對象的最短距離兩個角度來衡量，即密度越高且距離已擴展過的對象越遠的對象的拓展能力越強。實際上，按照以上兩個角度來確定當前拓展能力最強的節點是一個雙目標優化問題，求解該雙目標優化問題非常耗時，且不一定能夠找到滿足條件的解。本文借助MCMC采樣策略來選擇當前擴展對象。

1 基礎知識

1.1 DBSCAN

DBSCAN算法借助ε和MinPts兩個參數、利用簇的密度連通特性來發現簇，其中涉及的關鍵術語定義如下。

鄰域：與對象p的距離不大于ε的對象集合，稱為p的鄰域，表示為Nε(p)={q|dis(p,q)≤ε}。

密度：對象p的密度Dε(p)=|Nε(p)|。

核心對象：如果對于對象p，有 |Nε(p)|≥MinPts，則p被稱為核心對象，反之稱為非核心對象。

直接密度可達：對于核心對象p，如果對象q∈Nε(p)，則稱q相對于p是直接密度可達的或q是p的直接可達對象。

密度可達：對于對象p和q，如果存在一系列的對象p1=q，p2，…，pn=p，使得pi+1相對于pi是密度可達的，則稱p相對于q是密度可達的，p1，p2，…，pn都稱為p的密度可達對象。

對象擴展操作：對于核心對象p，對其進行擴展操作即為確定其鄰域Nε(p)。

DBSCAN的基本思想是將所有密度可達對象作為一個簇，基本處理過程是從某一個核心對象p開始，首先對p進行擴展，接著對Nε(p) 中的每個核心對象進行擴展，不斷進行以上對象擴展操作直至p的所有密度可達節點都被遍歷一次，將p與所有這些密度可達節點標記為同一簇；然后再從其它某一個沒被標記的核心對象q開始，尋找q的所有密度可達節點；按照以上步驟，直至所有核心節點都被標記為某一類簇為止。其偽代碼如算法1所示。

算法1： 基本DBSCAN算法

輸入： 待聚類對象集S，參數ε、MinPts

輸出： 每個對象的簇編號

(1)For each pointpinSdo

(2)label(p)←-1

(3)c←0

(4)for each pointpinSdo

(5) if(label(p)≠-1) thencontinue

(6)Nε(p)←Expand(S,p,ε)

(7) if(|Nε(p)|

(8)label(p)←noise

(9)continue

(10)c←c+1

(11)label(p)←c

(12)D←Nε(p)(〗p}

(13) whileDis not empty

(14) for eachqinDdo

(15) if(lable(q)==noise) thenlable(q)←c

(16) if(label(q)==-1)

(17)Nε(q)←Expand(S,q,ε)

(18)label(q)←c

(19) if(|Nε(q)|≥MinPts) thenD←D∪Nε(q)

(20)Output label(p) for everyp∈S.

通過算法1可以看出DBSCAN算法耗時的原因在于無論采用什么樣的順序，都要對數據集中的每個核心對象進行一次擴展操作。對于節點p，擴展節點意味著要計算其鄰域，計算鄰域需要的時間為O(nQ)，其中n為數據集大小，Q為計算兩個對象之間距離的時間復雜度。如對于歐式距離，Q為O(nd)，其中d為歐式空間的維數，則整個DBSCAN算法的時間復雜度Q為O(dn2)，即O(n2)。

1.2 MCMC技術

MCMC是一類采樣方法，主要用于對分布復雜的數據采樣，其中比較流行的是Metropolis-hastings采樣。

Metropolis-hastings的基本思路是從樣本空間X中隨機選擇一個樣本作為初始狀態x0，然后按照以下迭代過程構建馬爾可夫鏈：在第j次迭代過程中，隨機選擇一個樣本作為候選采樣點y，并按式(1)計算y的接受概率π

π=min{1,p(y)/p(xj-1)}

(1)

其中，p(y)和p(xj-1)分別表示y和xj-1的出現概率。候選采樣點y會以π的概率被接受作為xj。

當設定馬爾可夫鏈長度為m時，按照以上過程迭代m次，得到的采樣點即為xj。

在應用Metropolis-hastings在求解實際問題時，往往根據需要來定義接受概率π。

2 DBSCAN++

2.1 算法思想

DBSCAN++算法遵循了基本DBSCAN算法的框架，即從某個核心對象p開始，通過不斷地擴展核心對象直至p的所有密度可達對象都被找到；然后再從其它某一個沒被標記的核心對象q開始，尋找q的密度可達節點；按照以上步驟，直至所有核心節點都被標記為某一簇為止。

DBSCAN++與基本的DBSCAN算法最大的不同是DBSCAN需要把所有核心對象都擴展一次，而DBSCAN++只需要擴展部分核心對象。其基本思路是采用MCMC方法優先擴展拓展能力較強的核心對象直至當前被擴展對象的拓展能力低于非常低時，算法終止本類簇密度可達對象的尋找，從而開始從另一個核心對象q開始另一類簇的發現。

2.2 基于MCMC的對象選擇方法

按照DBSCAN++的基本思路，利用Metropolis-hastings采樣方法從當前所有待擴展對象中選擇拓展能力最強的核心對象作為下一個擴展對象。如前所述，本文通過密度和與已經擴展過的對象的最短距離兩個角度來衡量對象拓展能力。由于計算對象的密度比較耗時(O(n))，為了盡量減少計算對象密度的次數，本文在選擇節點時采用文獻[16]中的可達距離來近似對象的密度，只有當某對象被選擇作為當前擴展對象時再計算其密度。

根據文獻[16]，結合本文的需要，對象x的可達距離rd(x)，定義如式(2)所示

rd(x)=max{d(p,x),cd(p)|x∈Nε(p)}

(2)

其中，x∈Nε(p)，d(p,x) 為p和x之間的距離，cd(p) 為核心對象p的核心距離，定義如式(3)所示

(3)

通過式(2)和式(3)可以看出，對象x距離核心對象p的可達距離越小，x越接近于p。根據核心對象的定義，與核心對象距離越近的對象成為核心對象的可能性越高，即處于高密度區域的可能性越高，拓展能力越強。

除此之外，對于兩個待擴展對象p和q，如果d(p,A)

綜合以上對可達距離和與已擴展對象的距離的分析，具有更小的可達距離且與已擴展對象距離越遠的對象的拓展能力越強。

按照Metropolis-hastings，當選擇一個候選采樣點時，需要計算該采樣點的接受概率π。DBSCAN++中將候選采樣點的接受概率的定義如式(4)所示

(4)

其中，d(yj,A) 和d(xj-1,A) 分別為yj和xj-1到集合A中對象的最短距離。

DBSCAN++算法利用MCMC技術選擇擴展對象的偽代碼如算法2所示，其中，OPEN表用來存儲所有待擴展對象，CLS表用來存儲所有已被擴展核心對象。由于OPEN表中最多有n個對象(n為所有聚類對象個數)，因此，當采樣次數為m次時，MCMC(OPEN,m) 的時間復雜為O(mn)。

算法2： MCMC(OPEN,m)

輸入：OPEN,CLS，m

輸出： 采樣點

(1)x←OPEN.get(0)

(2)If(OPEN.size()>=2)

(3)d(x,CLS)←argminu∈CLSdis(x,u)

(4) for(intj=1;j

(5)s←rand[1,OPEN.size()-1]

(6)y←OPEN.get(s)

(7)d(y,CLS)←argminu∈CLSdis(y,u)

(8)π←min{1,d(y,CLS)*rd(x)/(d(x,CLS)*rd(y))}

(9)if(π>rand(0,1))

(10)x←y

(11)d(x,CLS)←d(y,CLS)

(12)returnx.

2.3 DBSCAN++提前終止策略

DBSCAN++中，當當前被擴展對象的拓展能力低于非常低時，DBSCAN++算法終止本類簇密度可達節點的尋找。

如前所述，在擴展節點之前通過可達距離和與已擴展對象的距離兩方面來預判節點的拓展能力，當節點p被擴展之后，可以通過擴展p新發現的對象數來衡量其拓展能力。

DBSCAN++，核心節點p的拓展能力Expan(p)可以通過式(5)來計算

Exp(p)=|{x|x∈Nε(p),label(x)=-1}|

(5)

在DBSCAN++中，當Expan(p)為0時，p節點的拓展能力被認為非常弱，算法停止本類簇密度可達節點的尋找。

2.4 DBSCAN++算法描述

整個DBSCAN++算法偽代碼如算法3所示。

算法3： DBSCAN++算法

輸入： 數據集S，參數ε、MinPts，m

輸出： 每個對象的簇編號

(1)For each pointpinSdo

(2)label(p)←-1

(3)c←0

(4)for each pointpinSdo

(5) if(label(p)≠-1) thencontinue

(6)Nε(p)←Expand(S,p,ε)

(7) if(Nε(p) is empty)

(8)label(p)←noise

(9)continue

(10)c←c+1

(11)label(p)←c

(12)OPEN←OPEN+Nε(p)(〗p}；CLS←CLS+{p}

(13) whileOPENis not empty

(14)q←MCMC(OPEN,m)

(15)OPEN←OPEN-{q}

(16) if(label(q)==noise) thenlabel(q)←c

(17) if(label(q)==-1)

(18)label(q)←c

(19)Nε(q)←Expand(S,q,ε)

(20) if(Exp(q)==0) break;

(21)OPEN←OPEN+Nε(q)

(22)CLS←CLS+{q}

(23)Output label(p) for everyp∈S.

從偽代碼可以看出，算法最耗時的部分在于第(13)步，即從當前所有待擴展對象中不斷選擇對象并擴展直至當前被擴展節點的擴展能力為0。其中最耗時的部分在于(14)步和(19)步。其中(14)步的時間復雜度為O(mn)；(19)步的主要功能為擴展當前核心對象q，其偽代碼如算法4所示,時間復雜度為O(n)。

算法4： Expand(S,p,ε,Minpts)

輸入： 數據集S，參數ε和Minpts

輸出：N

(1)N←Φ,DIS←-1

(2) for(i=0;i<|S|;i++)

(3) if(d(p,S[i])<ε)

(4)N←N+{S[i]}

(5)DIS←DIS+{d(p,S[i])}

(6)if(|N|

(7) returnΦ

(8)newDis←DIS中第Minpts小的距離

(9)cd(p)←newDis

(10)for(i=0;i<|N|;i++)

(11)N[i].cd←min(cd(p),DIS[i]) //式(2)

(12)returnN.

所以，從理論上講，整個DBSCAN++算法的時間復雜度是O(n2)，與DBSCAN算法相同。

3 實驗部分

為了驗證算法的有效性，本文通過實驗將BSCAN++算法與DBSCAN和OPTICS兩種算法從運行時間和聚類準確性兩個角度進行了對比。在實驗中，DBSCAN++、DBSCAN和OPTICS都采用Java語言編程實現，所有實驗都在同樣的軟硬件環境下完成。

測試數據為7個來自于UCI數據庫的數據集，每個數據集中對象個數、屬性個數和簇個數見表1，其中“簇個數”列給出了該數據集中包含簇的數量。

表1 7個數據集

實驗中，DBSCAN++、DBSCAN和OPTICS3種算法在不同的數據集上的ε和MinPts的取值情況見表2。另外，DBSCAN++中的參數m的取值為5。

3種算法在7個數據集上的運行時間見表3，其中“百分比”列表示DBSCAN++相對于當前算法運行時間的提高百分比，即(當前算法運行時間-DBSCAN++運行時間)/當前算法運行時間*100%。通過表3可以看出：

表2 DBSCAN、OPTICS、DBSCAN++在不同

(1)在7個數據集上，DBSCAN++最快，DBSCAN次之，OPTICS最慢；

(2)在不同的數據集上，DBSCAN++相對于DBSCAN和OPTICS運行時間提高百分比不同；且，在數據規模較大的數據集上，DBSCAN++的加速效果更加明顯。如在data5、data6和data7這3個數據集上，DBSCAN++相對于DBSCAN和OPTICS的提高百分比均在80%以上；

表3 DBSCAN、OPTICS、DBSCAN++

(3)在7個數據集上，DBSCAN++相對于DBSCAN的平均提高百分比為60.7，相對于OPTICS的平均提高百分比為70.2。可見，從運行時間看，DBSCAN++是高效的。

為了評價聚類準確性，本文采用了V-measure、ARI、NMI作為評價指標。圖1～圖3分別給出了3種算法在每個數據集上的聚類準確性對比直方圖。

圖1 以V-measure為評價指標下3種算法在7個數據集上的聚類準確性

圖2 以ARI為評價指標下3種算法在7個數據集上的聚類準確性

圖3 以NMI為評價指標下3種算法在7個數據集上的聚類準確性

通過圖1～圖3可以看出：

(1)在V-measure、ARI、NMI的任何一種評價指標下，沒有一種算法在所有數據集上都比其它算法好。如data1上，DBSCAN和OPTICS的準確性略高于DBSCAN++；在data2，data3，data4，data6上，3種指標中可以看出DBSCAN++均高于DBSCAN和OPTICS；而在data5上，OPTICS的準確性明顯高于DBSCAN和OPTICS；

(2)從V-measure評價指標看，在data2，data3，data4和data6上，DBSCAN++的準確性明顯高于DBSCAN和OPTICS；在data1上，DBSCAN++的準確性略低于DBSCAN和OPTICS；在data5上，OPTICS最準確，其次是DBSCAN++，DBSCAN的準確性最差；

(3)從ARI評價指標看，在data2，data3，data4，data6和data7上，DBSCAN++的準確性明顯高于DBSCAN和OPTICS；在data1上，DBSCAN++的準確性略低于DBSCAN和OPTICS；在data5上，OPTICS最準確，其次是DBSCAN++，DBSCAN的準確性最差；

(4)從NMI評價指標看，在data2，data3，data4和data6上，DBSCAN++的準確性明顯高于DBSCAN和OPTICS；在data1上，DBSCAN++的準確性略低于DBSCAN和OPTICS；在data5和data7上，OPTICS最準確，其次是DBSCAN++，DBSCAN的準確性最差；

(5)綜上所述，在data2，data3，data4和data6上，在任何一種評價指標下，DBSCAN++的準確性明顯高于DBSCAN和OPTICS；在data1上，DBSCAN++的準確性略低于DBSCAN和OPTICS；在data5上，OPTICS最準確，其次是DBSCAN++，DBSCAN的準確性最差。對于data7，在不同的評價指標下，3種算法的準確性不一樣，從ARI看，DBSCAN++最準確；從V-measure和NMI看，OPTICS最準確，其次是DBSCAN++，DBSCAN最差。

結合以上運行時間和聚類有效性的分析，DBSCAN++算法不僅保證了聚類效果，而且運行時間上DBSCAN++比DBSCAN平均降低了60.7%，比OPTICS平均降低了70.2%，這說明了本文算法DBSCAN++較DBSCAN、OPTICS有顯著的優勢。

4 結束語

本文針對DBSCAN算法時間復雜度高的問題，提出了一種基于MCMC的DBSCAN改進算法——DBSCAN++。本文創新之處在于引入密度和與已經擴展過的對象的最短距離兩個角度來衡量核心對象的拓展能力，并借助Metro-polis-hastings采樣方法實現具有較強的拓展能力的核心對象的選取。雖然從理論上看，DBSCAN++與DBSCAN具有相同的時間復雜度，但是實驗結果表明，DBSCAN++的實際運行時間明顯優于DBSCAN和OPTICS，且算法的準確性并沒有變差。因此，DBSCAN++算法是有效的。