基于兩階段搜索的密度聚類算法

汪 勇，李巧娜，艾學(xué)軼

(武漢科技大學(xué) 恒大管理學(xué)院，湖北 武漢 430081)

0 引 言

密度聚類是應(yīng)用廣泛的一類機(jī)器學(xué)習(xí)方法。典型的密度聚類算法有DBSCAN[1]和DPC[2]。DBSCAN算法兩個(gè)參數(shù)憑經(jīng)驗(yàn)確定，易形成過(guò)度聚類或噪聲增多問(wèn)題。另外，核心對(duì)象的隨機(jī)選擇影響聚類的穩(wěn)定性。為此，Ankerst提出基于任何半徑和閥值的聚類方法OPTICS[3]，該方法生成一個(gè)簇排序可達(dá)圖，將參數(shù)隱含在圖形中，由應(yīng)用者根據(jù)需要選擇聚類結(jié)果，這給應(yīng)用者帶來(lái)極大不便。于是，一些改進(jìn)的算法如基于動(dòng)態(tài)近鄰的DN-DBSCAN算法[4]、高效處理簇密度的RNN-DBSCAN算法[5]、自適應(yīng)鄰域的AA-DBSCAN算法[6]以及解決離群數(shù)據(jù)點(diǎn)聚類問(wèn)題的VDBSCAN算法[7]等相繼被提出，在一定程度上提高了DBSCAN的聚類性能?；趯?duì)密度聚類方法思想的延伸，Rodriguez等在Science上發(fā)表論文提出密度峰聚類算法(DPC)。雖然DPC算法只有一個(gè)計(jì)算局部密度的截?cái)嗑嚯x參數(shù)，但該參數(shù)值確定依然無(wú)據(jù)可依，基于距離的最近鄰劃分聚類策略易產(chǎn)生錯(cuò)誤聚類。為此，研究者提出一些改進(jìn)的密度計(jì)算方法，提高密度峰值的差異性，如采用鄰域數(shù)據(jù)點(diǎn)殘差計(jì)算局部密度的REDPC算法[8]。計(jì)算相對(duì)密度的RDCA聚類算法[9]、基于邏輯分布和引力的密度計(jì)算方法DPC-LG[10]和自適應(yīng)密度峰聚類算法[11]等。針對(duì)連帶錯(cuò)誤聚類問(wèn)題，研究者提出一些改進(jìn)的聚類策略，如模糊加權(quán)k近鄰算法[12]、指數(shù)樣條k近鄰算法[13]以及相互鄰近度劃分聚類算法[14]等，較好地解決了連帶錯(cuò)誤聚類問(wèn)題。

在上述密度聚類算法研究基礎(chǔ)上，本文提出一種基于兩階段搜索的密度聚類算法(density clustering algorithm based on two-stage search，DCATS)，進(jìn)一步提高其聚類精度。

1 DCATS聚類思想

1.1 基本概念定義

給定數(shù)據(jù)集DS={x1,x2,…,xn}， 其中xi={xi1,xi2,xim}，i=1,2,…,n，n為數(shù)據(jù)數(shù)量，m為數(shù)據(jù)維度。設(shè)ε是一個(gè)正數(shù)，則開(kāi)區(qū)間 (xi-ε,xi+ε) 為數(shù)據(jù)點(diǎn)xi的ε鄰域。

定義1 數(shù)據(jù)點(diǎn)xi的密度ρ(xi)是xi鄰域ε內(nèi)的數(shù)據(jù)點(diǎn)數(shù)量，即

(1)

定義2 所有數(shù)據(jù)點(diǎn)按照密度由高到低排列，按式(2)計(jì)算相對(duì)密度差d(xi)，令具有最小相對(duì)密度差絕對(duì)值之和的密度為δ，則稱δ為密度閾值。當(dāng)ρ(xi)≥δ時(shí)，xi為高密度數(shù)據(jù)點(diǎn)。否則，xi為低密度數(shù)據(jù)點(diǎn)

(2)

定義3 設(shè)xj在xi的ε鄰域內(nèi)，且xi是高密度數(shù)據(jù)點(diǎn)，則稱xj是xi的直接密度可達(dá)點(diǎn)。設(shè)xj為高密度數(shù)據(jù)點(diǎn)，xk是xj的直接密度可達(dá)點(diǎn)，若xk是高密度數(shù)據(jù)點(diǎn)，則稱xk是xi關(guān)于鄰域ε和δ的密度可達(dá)點(diǎn)。否則，稱xk是xi的密度相連點(diǎn)。

dik-dij>0

(3)

1.2 兩階段搜索

DCATS由鄰域遞歸搜索和簇最近鄰搜索兩個(gè)階段組成。第一階段，鄰域遞歸搜索(recursive search in neighborhood，RSN)采用遞歸搜索方法，在高密度數(shù)據(jù)點(diǎn)鄰域內(nèi)搜索未聚類的直接密度可達(dá)點(diǎn)、密度可達(dá)點(diǎn)和密度相連點(diǎn)，并將這些數(shù)據(jù)點(diǎn)歸為該高密度數(shù)據(jù)點(diǎn)所在的簇。直到搜索到的數(shù)據(jù)點(diǎn)均已聚類或均為低密度數(shù)據(jù)點(diǎn)為止。RSN搜索流程如圖1所示。

圖1 鄰域逆歸搜索階段

圖1中，條件1判斷密度排序數(shù)據(jù)集是否含有未聚類的高密度數(shù)據(jù)點(diǎn)。條件2判斷每次搜索的數(shù)據(jù)點(diǎn)中是否含有高密度數(shù)據(jù)點(diǎn)。

第一階段聚類完成時(shí)可能存在未聚類的低密度數(shù)據(jù)點(diǎn)，此時(shí)，啟動(dòng)第二階段的簇最近鄰搜索算法(search the nearest neighbor in cluster，SNNC)，實(shí)現(xiàn)低密度數(shù)據(jù)點(diǎn)或離群數(shù)據(jù)點(diǎn)聚類。在已聚類數(shù)據(jù)簇中搜索距離未聚類的低密度數(shù)據(jù)點(diǎn)最近的數(shù)據(jù)點(diǎn)，即簇最近鄰點(diǎn)，根據(jù)簇最近鄰距離與鄰域關(guān)系以及當(dāng)前已聚類簇?cái)?shù)，確定該低密度數(shù)據(jù)點(diǎn)的歸屬。簇最近鄰搜索流程如圖2所示。

圖2 簇最近鄰搜索階段

圖2中，條件1判斷所有低密度數(shù)據(jù)點(diǎn)是否均已聚類。條件2判斷簇最近鄰距離是否小于等于鄰域。條件3判斷當(dāng)前聚類是否只有一個(gè)簇。

2 DCATS算法設(shè)計(jì)

2.1 聚類策略

DCATS運(yùn)用密度排序、簇最近鄰分配和自適應(yīng)搜索方法設(shè)計(jì)算法的聚類策略。

(1)密度排序

對(duì)于DBSCAN，假設(shè)xi和xj為隨機(jī)排列的兩個(gè)核心點(diǎn)，且xi和xj分屬于不同簇，dij>ε。數(shù)據(jù)點(diǎn)xk為非核心點(diǎn)，dik≤ε，djk≤ε。若xi排列在xj之前，則xk屬于xi所在的簇，否則，xk屬于xj所在的簇。故xk的歸屬具有隨機(jī)性。DCATS將所有數(shù)據(jù)點(diǎn)按密度由高到低排序，構(gòu)成密度序列，RSN從第一個(gè)高密度數(shù)據(jù)點(diǎn)創(chuàng)建類簇進(jìn)行聚類，SNNC從第一個(gè)低密度數(shù)據(jù)點(diǎn)搜索簇最近鄰點(diǎn)。密度排序策略解決DBSCAN聚類的穩(wěn)定性問(wèn)題。

(2)簇最近鄰分配

對(duì)于給定的未聚類數(shù)據(jù)點(diǎn)，其簇最近鄰與最近鄰的區(qū)別是，簇最近鄰為已聚類數(shù)據(jù)點(diǎn)，而最近鄰可能是已聚類數(shù)據(jù)點(diǎn)，也可能是未聚類數(shù)據(jù)點(diǎn)。SNNC根據(jù)低密度數(shù)據(jù)點(diǎn)與其簇最近鄰點(diǎn)的距離以及鄰域關(guān)系確定該低密度數(shù)據(jù)點(diǎn)的歸屬。當(dāng)?shù)兔芏葦?shù)據(jù)點(diǎn)與簇最近鄰之間距離小于等于鄰域時(shí)，將該低密度數(shù)據(jù)點(diǎn)歸類到其簇最近鄰所在的簇。當(dāng)其距離大于鄰域時(shí)，分為兩種情形，若當(dāng)前聚類簇?cái)?shù)為空或只有一簇時(shí)，則以該數(shù)據(jù)點(diǎn)創(chuàng)建一個(gè)新的簇。否則將該數(shù)據(jù)點(diǎn)歸類到其簇最近鄰所在的簇。

(3)自適應(yīng)搜索

自適應(yīng)搜索是指DCATS根據(jù)鄰域和數(shù)據(jù)分布情形而自動(dòng)選擇執(zhí)行RSN和SNNC實(shí)現(xiàn)聚類。當(dāng)數(shù)據(jù)點(diǎn)均勻分布時(shí)，根據(jù)設(shè)置的鄰域，所有數(shù)據(jù)點(diǎn)均為高密度數(shù)據(jù)點(diǎn)或低密度數(shù)據(jù)點(diǎn)，DCATS只啟動(dòng)RSN或SNNC即可完成聚類。對(duì)于連續(xù)變密度數(shù)據(jù)，則同時(shí)啟動(dòng)RSN和SNNC進(jìn)行兩階段搜索聚類。

2.2 符號(hào)說(shuō)明

DCATS算法涉及的符號(hào)見(jiàn)表1。

表1 符號(hào)說(shuō)明

2.3 算法描述

2.3.1 RSN算法

采用密度排序和自適應(yīng)搜索策略設(shè)計(jì)RSN算法，算法描述如下。

(1)給定數(shù)據(jù)集DS，設(shè)置鄰域eps。

(2)按式(4)計(jì)算DS兩數(shù)據(jù)點(diǎn)之間的距離d并按距離升序排列

(4)

(3)按式(1)計(jì)算數(shù)據(jù)點(diǎn)xi的密度DP(xi)，并按密度降序排列。

(4)按式(2)計(jì)算數(shù)據(jù)點(diǎn)xi的相對(duì)密度差絕對(duì)值之和，選擇最小值的數(shù)據(jù)點(diǎn)密度作為密度閾值DenThd。

(5)設(shè)置數(shù)據(jù)點(diǎn)編號(hào)SN、聚類輸出矩陣C和各簇?cái)?shù)據(jù)點(diǎn)數(shù)累積值Q。SN為按密度排序的數(shù)據(jù)點(diǎn)編號(hào)。

(6)判斷SN的狀態(tài)，若SN不為空且DP(1)≥DenThd， 轉(zhuǎn)下一步，否則轉(zhuǎn)SNNC算法。

(7)以數(shù)據(jù)點(diǎn)SN(1)創(chuàng)建一個(gè)簇并將其存入C。令高密度數(shù)據(jù)點(diǎn)HDP初始值為SN(1)，刪除SN(1)。

(8)若HDP不為空，轉(zhuǎn)下一步，否則轉(zhuǎn)步驟(6)。

(9)查找HDP鄰域內(nèi)不重復(fù)且未聚類的數(shù)據(jù)點(diǎn)Pts并將其存入C，刪除SN中數(shù)據(jù)點(diǎn)Pts。

(10)累積已聚類數(shù)據(jù)點(diǎn)數(shù)量并存入Q。

(11)按定義4查找Pts中的高密度數(shù)據(jù)點(diǎn)，生成新的HDP，轉(zhuǎn)步驟(8)。

2.3.2 SNNC算法

采用密度排序、簇最近鄰分配和自適應(yīng)搜索策略設(shè)計(jì)SNNC算法，算法描述如下。

(1)判斷所有數(shù)據(jù)點(diǎn)是否為低密度數(shù)據(jù)點(diǎn)。若C為空，表示所有數(shù)據(jù)點(diǎn)為低密度數(shù)據(jù)點(diǎn)，即DenThd>DP(1,2)， 轉(zhuǎn)下一步。否則轉(zhuǎn)步驟(3)。

(2)將SN(1)添加至C，創(chuàng)建一個(gè)簇，刪除SN(1)。

(3)統(tǒng)計(jì)SN中余下的低密度數(shù)據(jù)點(diǎn)數(shù)量L，令i=1。

(4)若i≤L，轉(zhuǎn)下一步。否則聚類結(jié)束，輸出聚類數(shù)據(jù)C。

(5)從dist中提取與數(shù)據(jù)點(diǎn)SN(i)構(gòu)成的點(diǎn)對(duì)A，統(tǒng)計(jì)A的點(diǎn)對(duì)數(shù)量S，令j=1。

(6)若j≤S，轉(zhuǎn)下一步。否則i=i+1，轉(zhuǎn)步驟(4)。

(7)在A中查找距離SN(i)最近的點(diǎn)對(duì)A(j,2)。

(8)若A(j,2)屬于C，由式(3)可知，A(j,2)是SN(i)的簇最近鄰，轉(zhuǎn)下一步。否則j=j+1， 轉(zhuǎn)步驟(6)。

(9)統(tǒng)計(jì)當(dāng)前已聚類的簇?cái)?shù)nc。

(10)若SN(i)與A(j,2)之間的距離A(j,3)≤eps， 轉(zhuǎn)下一步。否則，若nc=1，轉(zhuǎn)步驟(14)。否則轉(zhuǎn)下一步。

(11)查找A(j,2) 在類簇C中的位置并將SN(i) 插入到C的A(j,2) 之前的位置。

(12)查找A(j,2) 位置值在Q中的位置。

(13)更新C中各類簇?cái)?shù)據(jù)點(diǎn)累積數(shù)。i=i+1， 轉(zhuǎn)步驟(4)。

(14)將SN(i)添加到C的尾部，構(gòu)成新簇，轉(zhuǎn)步驟(13)。

2.4 時(shí)間復(fù)雜度

由RSN算法步驟可知，它由距離計(jì)算、密度計(jì)算和鄰域搜索過(guò)程組成。數(shù)據(jù)點(diǎn)距離計(jì)算次數(shù)為n(n-1)/2， 故時(shí)間復(fù)雜度為O(n2)。 顯然，密度計(jì)算的時(shí)間復(fù)雜度為O(n)。 鄰域搜索是一個(gè)遞歸過(guò)程，假設(shè)聚類為c簇，數(shù)據(jù)點(diǎn)數(shù)量分別為n1,n2,…,nc， 則時(shí)間復(fù)雜度為

O(logn1+logn2+…+lognc)

(5)

對(duì)于SNNC算法，最壞情況下，假設(shè)剩余的數(shù)據(jù)點(diǎn)有n個(gè)，因d是有序的，故只需n次搜索即可完成聚類，時(shí)間復(fù)雜度為O(n)。

由上述分析可知，距離計(jì)算是DCATS算法執(zhí)行最耗時(shí)的過(guò)程，與DBSCAN和DPC算法一樣，DCATS時(shí)間復(fù)雜度為O(n2)。

3 算法性能分析

3.1 數(shù)據(jù)集選擇

為驗(yàn)證DCATS聚類算法性能，選擇4個(gè)人工數(shù)據(jù)集和4個(gè)UCI真實(shí)數(shù)據(jù)集進(jìn)行測(cè)試[14]。數(shù)據(jù)集描述見(jiàn)表2。

表2 數(shù)據(jù)集描述

將DCATS與DBSCAN、AA-DBSCAN[6]、DPC和RDCA[9]進(jìn)行聚類效果對(duì)比。利用標(biāo)準(zhǔn)互信息(NMI)[15]、調(diào)整蘭德系數(shù)(ARI)[16]和Fowlkes-Mallows指數(shù)(FMI)[17]評(píng)價(jià)各算法的聚類效果。采用Matlab作為實(shí)驗(yàn)平臺(tái)，經(jīng)多次實(shí)驗(yàn)選擇最優(yōu)參數(shù)作為各算法的聚類參數(shù)。

3.2 人工數(shù)據(jù)集測(cè)試

5個(gè)算法在4個(gè)人工數(shù)據(jù)集上的聚類結(jié)果評(píng)價(jià)指標(biāo)見(jiàn)表3。粗體數(shù)值表示對(duì)應(yīng)的指標(biāo)最優(yōu)。

表3 人工數(shù)據(jù)集聚類評(píng)價(jià)

由表3可知，對(duì)于Flame、Jain和Square這3個(gè)數(shù)據(jù)集，DCATS這3個(gè)指標(biāo)保持最優(yōu)。對(duì)于Aggregation數(shù)據(jù)集，DCATS的NMI指標(biāo)最優(yōu)，AA-DBSCAN的ARI、FMI指標(biāo)略優(yōu)于DCATS?？偟膩?lái)看，AA-DBSCAN和DBSCAN聚類效果優(yōu)于DPC和RDCA，AA-DBSCAN優(yōu)于DBSCAN，RDCA優(yōu)于DPC，DCATS算法聚類效果優(yōu)于比較的4個(gè)算法。各算法在4個(gè)人工數(shù)據(jù)集上的聚類結(jié)果如圖3～圖7所示。

圖3 DCATS聚類結(jié)果

圖4 DBSCAN聚類結(jié)果

圖5 AA-DBSCAN聚類結(jié)果

圖6 DPC聚類結(jié)果

圖7 RDCA聚類結(jié)果

圖3(a)～圖7(a)是Flame數(shù)據(jù)集的聚類結(jié)果。5個(gè)算法均聚為2簇，DBSCAN和AA-DBSCAN存在少數(shù)噪聲點(diǎn)，且AA-DBSCAN噪聲點(diǎn)少于DBSCAN。DPC和RDCA出現(xiàn)明顯的連帶錯(cuò)誤，聚類結(jié)果較差。只有DCATS聚類結(jié)果最理想。

圖3(b)～圖7(b)是Jain數(shù)據(jù)集的聚類結(jié)果。DCATS、DBSCAN和AA-DBSCAN聚為3簇，DBSCAN和AA-DBSCAN出現(xiàn)少量噪聲點(diǎn)。DPC和RDCA雖聚為2簇，但存在較多的錯(cuò)誤聚類?？偟膩?lái)看，DCATS在Jain數(shù)據(jù)集上的聚類結(jié)果最好。

圖3(c)～圖7(c)是Aggregation數(shù)據(jù)集的聚類結(jié)果。5個(gè)算法均聚為7簇。AA-DBSCAN噪聲點(diǎn)少于DBSCAN。DPC和RDCA均有3簇出現(xiàn)錯(cuò)誤聚類?？偟膩?lái)看，對(duì)于Aggregation數(shù)據(jù)集，前3個(gè)算法聚類結(jié)果相近，DCATS算法聚類結(jié)果更優(yōu)。

圖3(d)～圖7(d)是Square數(shù)據(jù)集的聚類結(jié)果。DBSCAN和AA-DBSCAN出現(xiàn)較多的噪聲點(diǎn)，DPC和RDCA均存在簇間錯(cuò)誤聚類。相對(duì)而言，DCATS在Square數(shù)據(jù)集上的聚類結(jié)果明顯優(yōu)于另外4個(gè)算法。

3.3 真實(shí)數(shù)據(jù)集測(cè)試

真實(shí)數(shù)據(jù)集均為多維度數(shù)據(jù)。5個(gè)算法在4個(gè)真實(shí)數(shù)據(jù)集上的聚類結(jié)果評(píng)價(jià)指標(biāo)見(jiàn)表4。粗體數(shù)值表示對(duì)應(yīng)的指標(biāo)最優(yōu)。

由表4可知，對(duì)于Seeds數(shù)據(jù)集，DCATS、DPC和RDCA這3個(gè)指標(biāo)相同，均為最優(yōu)。對(duì)于Heart數(shù)據(jù)集，DCATS、DPC和RDCA的ARI和FMI指標(biāo)相同，均為最優(yōu)，DBSCAN的NMI指標(biāo)最優(yōu)。對(duì)于Lonosphere數(shù)據(jù)集，DCATS的ARI和FMI指標(biāo)最優(yōu)，AA-DBSCAN的NMI指標(biāo)最優(yōu)。對(duì)于Libras數(shù)據(jù)集，DCATS的NMI和ARI指標(biāo)最優(yōu)，DPC的FMI指標(biāo)略優(yōu)于DCATS。綜合來(lái)看，DCATS算法的聚類精度優(yōu)于比較的密度聚類算法，表明其聚類策略是有效的。

表4 真實(shí)數(shù)據(jù)集聚類評(píng)價(jià)

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

DCATS對(duì)所有數(shù)據(jù)按密度進(jìn)行排序，第一階段的鄰域遞歸搜索算法代替DBSCANs基于核心對(duì)象的鄰域搜索機(jī)制，避免DBSCANs核心對(duì)象的選擇順序造成數(shù)據(jù)點(diǎn)隨機(jī)聚類問(wèn)題，實(shí)現(xiàn)數(shù)據(jù)的穩(wěn)定聚類。同時(shí)，鄰域遞歸搜索算法自動(dòng)確定類簇，避免DPCs聚類算法人工確定聚類中心帶來(lái)的主觀聚類問(wèn)題。DCATS的簇最近鄰搜索算法實(shí)現(xiàn)低密度離群數(shù)據(jù)點(diǎn)的正確聚類，消除DBSCANs聚類產(chǎn)生的噪聲數(shù)據(jù)點(diǎn)。同時(shí)，簇最近鄰搜索算法解決了DPCs的最近鄰劃分策略產(chǎn)生的聚類連帶錯(cuò)誤問(wèn)題，提高了聚類精度。如何合理確定DCATS的鄰域參數(shù)值得進(jìn)一步探討。