基于KD樹改進(jìn)的DBSCAN聚類算法①

陳文龍,時(shí)宏偉

(四川大學(xué) 計(jì)算機(jī)學(xué)院,成都 610065)

聚類(clustering)是數(shù)據(jù)挖掘中的重要手段,其核心思想是“同類相近,異類相遠(yuǎn)”,將數(shù)據(jù)集劃分為不同的簇,同一簇中的數(shù)據(jù)對(duì)象之間有較高的相似度,不同簇之間的數(shù)據(jù)對(duì)象差異較大.通過聚類的方法可以分析數(shù)據(jù)之間的聯(lián)系和價(jià)值,目前已被廣泛應(yīng)用于諸如數(shù)據(jù)分析,生物學(xué),模式識(shí)別[1]等多領(lǐng)域的研究工作中.

目前聚類算法主要分為基于層次的方法如BIRCH算法,基于網(wǎng)格的聚類方法如STING 算法,基于劃分的方法如K-means 算法,基于密度的方法如DBSCAN算法以及基于模型的聚類方法等[2–6].其中DBSCAN算法是密度聚類中最經(jīng)典的一種聚類算法,DBSCAN算法不需要預(yù)先指定簇的個(gè)數(shù),且能在含有“噪聲”的數(shù)據(jù)中找出任意形狀的簇,具有很好的抗干擾性,但當(dāng)數(shù)據(jù)量增大時(shí),由于算法自身的特性會(huì)導(dǎo)致時(shí)間的消耗急劇增加.

為了解決上述問題,許多學(xué)者提出了不同的改進(jìn)方案.文獻(xiàn)[7]提出的IF-DBSCAN 通過選取核心點(diǎn)鄰域中的代表對(duì)象來擴(kuò)展類,從而減少鄰域中的查詢次數(shù),但效率提升有限.文獻(xiàn)[8]通過按順序選擇鄰域外未被標(biāo)記的點(diǎn)作為種子點(diǎn),分不同情況進(jìn)行聚類擴(kuò)展,有效地減少了核心點(diǎn)鄰域重疊區(qū)域的查詢次數(shù),同時(shí)也提升聚類的質(zhì)量.文獻(xiàn)[9]提出選取距離最遠(yuǎn)且半徑內(nèi)樣本個(gè)數(shù)大于MinPts的點(diǎn)為核心點(diǎn),以避免因核心點(diǎn)隨機(jī)選取而導(dǎo)致計(jì)算量過大,但優(yōu)化效率還需提高.文獻(xiàn)[10]通過避免公共鄰域內(nèi)對(duì)象的重復(fù)查詢來優(yōu)化算法的執(zhí)行速度,但聚類質(zhì)量還需提高.文獻(xiàn)[11]采用貪心策略進(jìn)行聚類,在尋找核心對(duì)象的過程中使用鄰域查詢的方法來提升算法的運(yùn)行效率,但需手動(dòng)輸入密度閾值.文獻(xiàn)[12]采用重心點(diǎn)轉(zhuǎn)移的方法來改進(jìn)St-DBSCAN 算法,以提升聚類的時(shí)間性能和質(zhì)量,但效率還有待提高.本文提出的KD-DBSCAN 算法能減少傳統(tǒng)DBSCAN 算法在聚類時(shí)需要計(jì)算數(shù)據(jù)樣本中每個(gè)點(diǎn)Eps鄰域所帶來的開銷,從而極大的降低聚類時(shí)間,且保證了聚類的效果與傳統(tǒng)的DBSCAN 算法基本一致.

1 DBSCAN 算法分析

DBSCAN 算法是一種基于密度的空間聚類算法,該算法可以在具有“噪聲”的數(shù)據(jù)中發(fā)現(xiàn)具有一定密度條件下的任意形狀的簇.DBSCAN 中的基本概念如下.

定義1.Eps鄰域:給定某對(duì)象點(diǎn)X,其半徑Eps范圍稱為該點(diǎn)的Eps鄰域,對(duì)于X的Eps鄰域內(nèi)的任意一點(diǎn)Y都有:dist(X,Y)≤Eps.

定義2.核心點(diǎn):給定某對(duì)象點(diǎn)X,其Eps鄰域內(nèi)數(shù)據(jù)點(diǎn)數(shù)量超過MinPts的點(diǎn).

定義3.MinPts:簇的最小點(diǎn)集,即核心點(diǎn)鄰域內(nèi)的點(diǎn)數(shù)量必須不少于MinPts.

定義4.噪聲點(diǎn):既不是核心點(diǎn)也不是邊界點(diǎn)的其它點(diǎn).

定義5.邊界點(diǎn):不是核心點(diǎn),但在核心點(diǎn)的鄰域內(nèi).

定義6.直接密度可達(dá):對(duì)象點(diǎn)Y在X的Eps鄰域內(nèi),且對(duì)象點(diǎn)X是核心點(diǎn),則稱X到Y(jié)是直接密度可達(dá)的.

定義7.密度可達(dá):某一對(duì)象鏈X1,X2,···,Xn,若滿足任意Xi到Xi+1是 直接密度可達(dá)的,則稱X0到Xn密度可達(dá).

定義8.密度相連:對(duì)某一對(duì)象Z,若Z到X和Y都是密度可達(dá)的,則稱X和Y是密度相連的.

DBSCAN 算法聚類過程思想為:從給定的數(shù)據(jù)集D中隨機(jī)選取某個(gè)對(duì)象點(diǎn)X,查詢X的Eps鄰域半徑內(nèi)的所有密度可達(dá)點(diǎn)是否大于MinPts,如果大于則創(chuàng)建一個(gè)以X為核心點(diǎn)的聚類簇.之后迭代聚集核心點(diǎn)密度可達(dá)的所有對(duì)象,該過程可能會(huì)將核心點(diǎn)密度可達(dá)的簇進(jìn)行合并,在算法執(zhí)行的過程中,某些核心點(diǎn)的密度可達(dá)對(duì)象會(huì)被重復(fù)查詢.當(dāng)一個(gè)簇聚類完成后會(huì)開始選取下一個(gè)點(diǎn)開始聚類,直到?jīng)]有任何新的點(diǎn)添加到任何一個(gè)簇中時(shí),聚類結(jié)束,算法流程圖(如圖1所示)及部分偽代碼如算法1.

圖1 DBSCAN 算法流程圖

算法1.DBSCAN 算法輸入:D:包含n 個(gè)樣本點(diǎn)的數(shù)據(jù)集;Eps:半徑大小;MinPts:最少樣本點(diǎn)個(gè)數(shù);輸出:簇的集合.1) Initialize all points in D are unvisited 2) Select a point p in unvisited 3) Mark pas visited 4) Set N as Eps-neighbor of p 5) if size of N ≥ MinPts 6) Create a new cluster C,and put pin C 7) for each point p∈N 8) If p in unvisited 9) Mark p as visited 10) Set N as Eps-neighbor of p 11) if size of N ≥ MinPts 12) Put those points in N 13) endif 14) endif 15) if p is not yet a number of any cluster 16) Put p to C 17) endfor 18) else mark p as noise 19) Until all points are marked as visited

2 KD-DBSCAN 算法

傳統(tǒng)的DBSCAN 聚類算法在生成鄰域集時(shí)會(huì)掃描整個(gè)數(shù)據(jù)樣本,導(dǎo)致大量且不必要的計(jì)算開銷.因此,在聚類之前使用有效的數(shù)據(jù)結(jié)構(gòu)對(duì)數(shù)據(jù)進(jìn)行預(yù)處理,可以快速地找出給定對(duì)象的鄰域集,減少近鄰點(diǎn)的搜索時(shí)間.文中將利用KD 樹這種數(shù)據(jù)結(jié)構(gòu)對(duì)數(shù)據(jù)進(jìn)行劃分,由于KD 樹是基于數(shù)據(jù)屬性進(jìn)行構(gòu)建的,因此相似度高的數(shù)據(jù)對(duì)象在KD 樹中聯(lián)系更加緊密,在查找的過程中也更加快速,避免了在全局范圍內(nèi)查找鄰域?qū)ο蟮臅r(shí)間開銷.

2.1 相關(guān)概念

KD 樹是K-dimensional tree的縮寫,是一種在存儲(chǔ)和查詢方面非常高效的數(shù)據(jù)結(jié)構(gòu).最早由Bentley[13]提出,用于將數(shù)據(jù)點(diǎn)在K維空間中進(jìn)行構(gòu)造,是一種特殊的二叉搜索樹結(jié)構(gòu),樹中的每一層對(duì)應(yīng)一個(gè)維度.傳統(tǒng)二叉搜索樹只對(duì)一維的數(shù)據(jù)進(jìn)行構(gòu)建,KD 樹通過數(shù)據(jù)點(diǎn)的屬性個(gè)數(shù)循環(huán)的構(gòu)造K維二叉搜索樹.KD 樹中左子樹在給定維度上的值小于父節(jié)點(diǎn),而右子樹則大于父節(jié)點(diǎn),以二維數(shù)據(jù)為例,假設(shè)有一數(shù)據(jù)集為{(2,11),(9,12),(2,13),(12,12),(11,14),(10,10),(15,13)}對(duì)其進(jìn)行KD 樹的構(gòu)造,在第一層中首先按第一個(gè)維度上的值進(jìn)行排序,將中間數(shù)據(jù)值的點(diǎn)作為根節(jié)點(diǎn),如(10,10),此時(shí)將數(shù)據(jù)集劃分為兩個(gè)區(qū)域,左邊的子數(shù)據(jù)集為{(2,11),(2,13),(9,12)}在第一個(gè)維度上的數(shù)值均小于根節(jié)點(diǎn),右邊為{(11,14),(12,12),(15,13)}在第一個(gè)維度上的數(shù)值都大于根節(jié)點(diǎn),再分別在左右子樹中選擇第2 個(gè)維度上的數(shù)據(jù)進(jìn)行排序并選中間值,左子樹中以點(diǎn)(9,12),右子樹為點(diǎn)(15,13)分別構(gòu)造左右子樹,到第3 層又回到第一維進(jìn)行比較構(gòu)造,圖2為構(gòu)造的效果圖.

圖2 KD 樹樣例

2.2 算法相關(guān)步驟

利用KD 樹對(duì)數(shù)據(jù)集進(jìn)行構(gòu)造,在聚類之前生成每個(gè)數(shù)據(jù)點(diǎn)的鄰域?qū)ο蠹?遍歷每個(gè)數(shù)據(jù)點(diǎn),并通過構(gòu)造好的KD 樹進(jìn)行近鄰點(diǎn)搜索,找出所有數(shù)據(jù)對(duì)象的鄰域集,包含核心點(diǎn),邊界點(diǎn)以及噪聲點(diǎn),將找出的核心點(diǎn)用于后續(xù)的聚類步驟.雖然構(gòu)造KD 樹需要花費(fèi)一些時(shí)間且需要全局查詢,但是當(dāng)數(shù)據(jù)量增大時(shí),可以明顯減少近鄰節(jié)點(diǎn)查找次數(shù),因此是非常值得的.

(1)KD 樹的構(gòu)造

將數(shù)據(jù)點(diǎn)在K維空間中進(jìn)行分割并構(gòu)造KD 樹的節(jié)點(diǎn),先在一個(gè)維度上對(duì)數(shù)據(jù)點(diǎn)的某一屬性值進(jìn)行排序,選取中間值點(diǎn)作為根節(jié)點(diǎn),再構(gòu)造其左右子樹,其左子樹節(jié)點(diǎn)在此維度上的數(shù)值均小于根節(jié)點(diǎn)在此維度上的值,右子樹則相反;在子樹的構(gòu)造過程中,在第2 個(gè)維度上對(duì)數(shù)據(jù)點(diǎn)的第2 個(gè)屬性值進(jìn)行排序,選取中間值的數(shù)據(jù)點(diǎn)為子樹的根節(jié)點(diǎn),反復(fù)執(zhí)行,直至構(gòu)造完畢.利用KD 樹對(duì)DBSCAN 算法改進(jìn)可將算法的時(shí)間復(fù)雜度由O (n2)降至O (nlog2n).

(2)查找鄰近節(jié)點(diǎn)集合

利用KD 樹進(jìn)行近鄰節(jié)點(diǎn)的查詢,此步驟將遍歷數(shù)據(jù)集中的每一個(gè)節(jié)點(diǎn),讓每一個(gè)節(jié)點(diǎn)根據(jù)輸入的Eps參數(shù)計(jì)算出其正方形邊界范圍,再?gòu)腒D 樹的根節(jié)點(diǎn)開始查找其近鄰點(diǎn),比較樹中的每一層對(duì)應(yīng)維度上的值是否在其邊界范圍內(nèi),如果不滿足條件則去子樹中查找,如果在其邊界范圍內(nèi)還要繼續(xù)計(jì)算其兩點(diǎn)之間的距離是否滿足dist(X,Y)≤Eps,因?yàn)闃?gòu)造的正方形邊界范圍會(huì)略大于Eps為半徑的圓形范圍,兩者對(duì)應(yīng)關(guān)系如圖3所示.將滿足上述條件的數(shù)據(jù)對(duì)象添加到該點(diǎn)的neighbors 鄰域集合中,每個(gè)數(shù)據(jù)點(diǎn)都有一個(gè)屬性Key用于唯一標(biāo)識(shí)該點(diǎn),構(gòu)造后的neighbors(Keyn)集合形式如{Key1,Key2,···,Keyn},其含義是Key1點(diǎn)在Eps鄰域內(nèi)包含的數(shù)據(jù)點(diǎn)有Key2,···,Keyn.算法中采用的是haversine 距離[14],具體公式如下:

圖3 正方形邊界與Eps 半徑圓范圍

兩點(diǎn)的距離為:

其中,R為地球半徑,lat1,lon1和lat2,lon2 分別對(duì)應(yīng)P1,P2兩點(diǎn)的經(jīng)緯度,d ist(P1,P2)為P1,P2兩點(diǎn)之間的距離.

(3)KD-DBSCAN 聚類

將上一步中查找到的鄰近節(jié)點(diǎn)集合中長(zhǎng)度大于等于MinPts的數(shù)據(jù)點(diǎn)用于聚類,即len(neighbors(Keyn)) ≥MinPts的數(shù)據(jù)點(diǎn),通過過濾噪聲點(diǎn)來進(jìn)一步減少聚類時(shí)間.

算法的部分偽代碼如算法2和算法3.

算法2.構(gòu)建KD 樹CreateKDTree(points,tree_depth):1) //根據(jù)樹的深度來選擇維度2) axis=tree_depth mod K 3) //選擇第axis 維度的中間值為根節(jié)點(diǎn)進(jìn)行KD 樹的構(gòu)造4) select median by axis from points 5) //構(gòu)造節(jié)點(diǎn)和子樹6) node=median 7) node.left=KDTree(points in subList(0,median),axis,tree_depth+1)8) node.right=KDTree(points in subList(median+1,points.size()),axis,tree_depth+1)9) Return node算法3.找出鄰近節(jié)點(diǎn)集合find_neighbors(kdtree,node,eps)1) //遍歷節(jié)點(diǎn)node,根據(jù)Eps 大小計(jì)算邊界范圍2) bounding=getbounding(node,Eps)3) Set bounding_max as the max value of bounding 4) Set bounding_min as the min value of bounding 5) q=deque(kdtree)6) while size of q >0 7) current_node=q.popleft()8) if is_inbounding(current_node,bounding)9) if haversine(node,current_node) <=eps and current_node.key!=node.key 10) Put current_node into neighbors 11) endif 12) endif 13) Set axis as current_node’s axis 14) if bounding_max[axis] >current_node[axis] and bounding_min[axis] >current_node[axis]15) and current_node has rightTree:16) q.add(current_node.rightTree)17) elif bounding_max[axis] =current_node[axis] >=bounding_min[axis]:21) if current_node has rightTree 22) q.add(current_node.rightTree)23) endif 24) if current_node has leftTree 25) q.add(current_node.leftTree)26) endif 27) endif 28) Return neighbors

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集

本實(shí)驗(yàn)以成都市網(wǎng)約車GPS 數(shù)據(jù)為實(shí)驗(yàn)數(shù)據(jù),在Intel Core i7-9750H CPU 2.60 GHz,16 GB 內(nèi)存的筆記本電腦上運(yùn)行傳統(tǒng)DBSCAN 算法與改進(jìn)的KD-DBSCAN算法,統(tǒng)計(jì)兩種算法的運(yùn)行時(shí)間以及聚類的數(shù)目并用聚類評(píng)價(jià)指標(biāo)對(duì)兩種算法進(jìn)行評(píng)估.

3.2 實(shí)驗(yàn)結(jié)果與分析

設(shè)置參數(shù)Eps=100 m,MinPts=60,數(shù)據(jù)集從9 300 行依次增加到58 000 行,運(yùn)行結(jié)果如表1所示.

表1 不同數(shù)據(jù)行數(shù)的測(cè)試結(jié)果

圖4和圖5分別為耗時(shí)以及聚類簇個(gè)數(shù)的對(duì)比情況.

圖4 算法耗時(shí)對(duì)比圖

圖5 聚類簇個(gè)數(shù)

為比較兩種算法的聚類質(zhì)量,文中引入聚類效果評(píng)價(jià)指標(biāo)Calinski-Harabasz (CH)[15,16],其定義為:

其中,n為數(shù)據(jù)集樣本數(shù),k為類別數(shù).

CH 指標(biāo)可以用于評(píng)估DBSCAN 這類事先無(wú)法得知聚類個(gè)數(shù)的算法,即在真實(shí)的分類標(biāo)簽label 不知道的情況下用于評(píng)估聚類結(jié)果的性能,其指標(biāo)值越大說明簇內(nèi)數(shù)據(jù)對(duì)象之間的間距越小而簇間距離越大,聚類結(jié)果的CH 指標(biāo)如圖6所示.

圖6 聚類結(jié)果的CH 指標(biāo)

實(shí)驗(yàn)結(jié)果分析:

(1)聚類時(shí)間

從圖4中可以看出,隨著數(shù)據(jù)量的增加,傳統(tǒng)DBSCAN算法耗時(shí)是急劇增加的,而改進(jìn)的KD-DBSCAN 算法耗時(shí)依舊平穩(wěn),且二者耗時(shí)的差距越來越大.KD-DBSCAN算法體現(xiàn)出了KD 樹對(duì)于減少鄰近節(jié)點(diǎn)查詢時(shí)間的優(yōu)勢(shì).

(2)聚類數(shù)量

兩種算法在相同數(shù)據(jù)量的情況下,聚類產(chǎn)生的簇個(gè)數(shù)基本一致,在數(shù)據(jù)量較少和較大時(shí),KD-DBSCAN 算法產(chǎn)生的簇個(gè)數(shù)略微少于傳統(tǒng)DBSCAN 算法,這可能是由于KD-DBSCAN 算法對(duì)于數(shù)據(jù)的劃分更嚴(yán)格導(dǎo)致的.

(3)聚類質(zhì)量

從圖6中可以看出兩種算法在相應(yīng)的數(shù)據(jù)量下的聚類質(zhì)量基本相同,且隨著數(shù)據(jù)量的增大,KD-DBSCAN算法的CH 值總是略大于傳統(tǒng)DBSCAN 算法的.

綜上所述,改進(jìn)后的KD-DBSCAN 算法在保證了聚類的數(shù)量和質(zhì)量與傳統(tǒng)DBSCAN 算法保持基本一致的前提下,對(duì)聚類的效率有了大幅度的提升,因此利用KD 樹改進(jìn)的KD-DBSCAN 算法是切實(shí)可行的.

4 結(jié)束語(yǔ)

本文通過KD 樹對(duì)傳統(tǒng)DBSCAN 算法進(jìn)行改進(jìn),在保證了兩種算法的聚類個(gè)數(shù)以及質(zhì)量基本一致的前提下,極大地提高了算法的運(yùn)行效率.但是,當(dāng)數(shù)據(jù)量進(jìn)一步增大時(shí)兩種算法都會(huì)出現(xiàn)內(nèi)存不足的情況,因此下一步的研究工作會(huì)聚集于如何利用分布式計(jì)算框架來解決這類問題,以提升算法的性能.