李建伏，巴建軍

(中國民航大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300)

0 引 言

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

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

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

1 基礎(chǔ)知識

1.1 DBSCAN

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

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

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

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

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

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

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

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

算法1： 基本DBSCAN算法

輸入： 待聚類對象集S，參數(shù)ε、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算法耗時的原因在于無論采用什么樣的順序，都要對數(shù)據(jù)集中的每個核心對象進(jìn)行一次擴(kuò)展操作。對于節(jié)點(diǎn)p，擴(kuò)展節(jié)點(diǎn)意味著要計(jì)算其鄰域，計(jì)算鄰域需要的時間為O(nQ)，其中n為數(shù)據(jù)集大小，Q為計(jì)算兩個對象之間距離的時間復(fù)雜度。如對于歐式距離，Q為O(nd)，其中d為歐式空間的維數(shù)，則整個DBSCAN算法的時間復(fù)雜度Q為O(dn2)，即O(n2)。

1.2 MCMC技術(shù)

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

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

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

(1)

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

當(dāng)設(shè)定馬爾可夫鏈長度為m時，按照以上過程迭代m次，得到的采樣點(diǎn)即為xj。

在應(yīng)用Metropolis-hastings在求解實(shí)際問題時，往往根據(jù)需要來定義接受概率π。

2 DBSCAN++

2.1 算法思想

DBSCAN++算法遵循了基本DBSCAN算法的框架，即從某個核心對象p開始，通過不斷地?cái)U(kuò)展核心對象直至p的所有密度可達(dá)對象都被找到；然后再從其它某一個沒被標(biāo)記的核心對象q開始，尋找q的密度可達(dá)節(jié)點(diǎn)；按照以上步驟，直至所有核心節(jié)點(diǎn)都被標(biāo)記為某一簇為止。

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

2.2 基于MCMC的對象選擇方法

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

根據(jù)文獻(xiàn)[16]，結(jié)合本文的需要，對象x的可達(dá)距離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的可達(dá)距離越小，x越接近于p。根據(jù)核心對象的定義，與核心對象距離越近的對象成為核心對象的可能性越高，即處于高密度區(qū)域的可能性越高，拓展能力越強(qiáng)。

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

綜合以上對可達(dá)距離和與已擴(kuò)展對象的距離的分析，具有更小的可達(dá)距離且與已擴(kuò)展對象距離越遠(yuǎn)的對象的拓展能力越強(qiáng)。

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

(4)

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

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

算法2： MCMC(OPEN,m)

輸入：OPEN,CLS，m

輸出： 采樣點(diǎn)

(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++中，當(dāng)當(dāng)前被擴(kuò)展對象的拓展能力低于非常低時，DBSCAN++算法終止本類簇密度可達(dá)節(jié)點(diǎn)的尋找。

如前所述，在擴(kuò)展節(jié)點(diǎn)之前通過可達(dá)距離和與已擴(kuò)展對象的距離兩方面來預(yù)判節(jié)點(diǎn)的拓展能力，當(dāng)節(jié)點(diǎn)p被擴(kuò)展之后，可以通過擴(kuò)展p新發(fā)現(xiàn)的對象數(shù)來衡量其拓展能力。

DBSCAN++，核心節(jié)點(diǎn)p的拓展能力Expan(p)可以通過式(5)來計(jì)算

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

(5)

在DBSCAN++中，當(dāng)Expan(p)為0時，p節(jié)點(diǎn)的拓展能力被認(rèn)為非常弱，算法停止本類簇密度可達(dá)節(jié)點(diǎn)的尋找。

2.4 DBSCAN++算法描述

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

算法3： DBSCAN++算法

輸入： 數(shù)據(jù)集S，參數(shù)ε、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)步，即從當(dāng)前所有待擴(kuò)展對象中不斷選擇對象并擴(kuò)展直至當(dāng)前被擴(kuò)展節(jié)點(diǎn)的擴(kuò)展能力為0。其中最耗時的部分在于(14)步和(19)步。其中(14)步的時間復(fù)雜度為O(mn)；(19)步的主要功能為擴(kuò)展當(dāng)前核心對象q，其偽代碼如算法4所示,時間復(fù)雜度為O(n)。

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

輸入： 數(shù)據(jù)集S，參數(shù)ε和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++算法的時間復(fù)雜度是O(n2)，與DBSCAN算法相同。

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

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

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

表1 7個數(shù)據(jù)集

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

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

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

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

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

表3 DBSCAN、OPTICS、DBSCAN++

(3)在7個數(shù)據(jù)集上，DBSCAN++相對于DBSCAN的平均提高百分比為60.7，相對于OPTICS的平均提高百分比為70.2?？梢?，從運(yùn)行時間看，DBSCAN++是高效的。

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

圖1 以V-measure為評價指標(biāo)下3種算法在7個數(shù)據(jù)集上的聚類準(zhǔn)確性

圖2 以ARI為評價指標(biāo)下3種算法在7個數(shù)據(jù)集上的聚類準(zhǔn)確性

圖3 以NMI為評價指標(biāo)下3種算法在7個數(shù)據(jù)集上的聚類準(zhǔn)確性

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

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

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

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

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

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

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

4 結(jié)束語

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