基于最小生成樹的密度聚類算法研究

王 誠 ，高興東

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

0 引 言

數(shù)據(jù)挖掘伴隨著互聯(lián)網(wǎng)數(shù)據(jù)產(chǎn)生速度的大幅提升，已經(jīng)在越來越多的領(lǐng)域發(fā)揮作用。同時互聯(lián)網(wǎng)中的數(shù)據(jù)大多為無標(biāo)簽數(shù)據(jù)，聚類算法的優(yōu)勢得以體現(xiàn)。聚類分析作為數(shù)據(jù)挖掘中至關(guān)重要的技術(shù)之一，目前已經(jīng)在醫(yī)療、交通、電力、品質(zhì)育種等領(lǐng)域得到了廣泛應(yīng)用?；诿芏鹊木垲愃惴ㄊ悄壳皯?yīng)用較為廣泛的聚類分析算法之一。其中典型的算法有DBSCAN算法、OPTICS算法等。文獻(xiàn)[6]提出的DBSCAN算法對于Eps和MinPts敏感，同時二者為全局參數(shù)，雖然可以發(fā)現(xiàn)任何形狀的簇，但在運(yùn)算過程中參數(shù)無法更改，所以無法正確處理密度分布不均勻的樣本。文獻(xiàn)[7]提出了OPTICS算法，該算法并不直接得出結(jié)果簇，而是得出一個增廣的簇排序，即得到基于任何參數(shù)Eps和MinPts組合的DBSCAN算法的聚類結(jié)果，在結(jié)果中選擇聚類效果好的參數(shù)組合，該算法并沒有在本質(zhì)上解決如何選擇參數(shù)的問題，且過程產(chǎn)生了不必要的運(yùn)算量；同時這種排序?qū)е碌兔芏赛c(diǎn)與高密度點(diǎn)的相鄰關(guān)系在映射時被分離。另外，文獻(xiàn)[9]提出首先使用K-Means算法對數(shù)據(jù)集進(jìn)行分析以確認(rèn)輸入?yún)?shù)再進(jìn)行數(shù)據(jù)集的聚類；文獻(xiàn)[10]提出可以利用繪制k-dist圖的方式確認(rèn)Eps的值進(jìn)而確認(rèn)MinPts的值；文獻(xiàn)[11]通過分析數(shù)據(jù)集平均數(shù)等統(tǒng)計(jì)特性，運(yùn)用多組數(shù)據(jù)之間的比較得以確定Eps參數(shù)；文獻(xiàn)[12]提出KANN-DBSCAN算法利用

k

-近鄰確定Eps候選集合，通過

k

的數(shù)學(xué)期望確定MinPts參數(shù)。文獻(xiàn)[13]提出了一種基于局部特征的層次聚類算法，對不同密度樣本分別處理，解決樣本密度分布不均的聚類的問題。受上述研究啟發(fā)，可以使用對于算法結(jié)果影響較小的參數(shù)降低原算法中對于參數(shù)的敏感程度。該文提出一種基于最小生成樹的密度聚類算法。首先通過計(jì)算樣本點(diǎn)之間的相互可達(dá)距離構(gòu)建無向有權(quán)圖并求解其最小生成樹；再通過預(yù)設(shè)的最小簇對象數(shù)

n

對最小生成樹進(jìn)行剪枝，將最小生成樹中的節(jié)點(diǎn)中，子孫節(jié)點(diǎn)數(shù)不大于最小簇對象數(shù)的節(jié)點(diǎn)及其子孫節(jié)點(diǎn)標(biāo)記為噪聲；最后，根據(jù)預(yù)設(shè)的簇的個數(shù)

k

分割最小生成樹并對分割結(jié)果進(jìn)行聚類，解決了傳統(tǒng)算法對于參數(shù)敏感的問題(將該算法命名為MST-DBSCAN)。

1 DBSCAN算法

DBSCAN算法是一種經(jīng)典的空間密度聚類算法，該算法可以聚類任何形狀的簇并能夠自動確定簇的數(shù)量，不需要人為設(shè)定具體的簇?cái)?shù)。與其他聚類算法不同，該算法通過從隨機(jī)的數(shù)據(jù)對象開始向外擴(kuò)散的方式在數(shù)據(jù)集中進(jìn)行對象的聚類。該算法在眾多聚類算法中應(yīng)用較為廣泛且效果較好，其中主要定義如下：

定義1(Eps鄰域)：在數(shù)據(jù)集樣本中隨機(jī)選擇1個數(shù)據(jù)對象

p

，其鄰域

N

(

p

)定義為以

p

為核心，Eps的值為半徑的多維區(qū)域，即：

N

(

q

)={

q

∈

D

|dist(

p

,

q

)≤Eps}

(1)

其中，

D

為數(shù)據(jù)集中所有對象的集合，

q

為數(shù)據(jù)集中的對象，dist(

p

,

q

)表示

p

、

q

兩對象之間的距離。定義2(核心點(diǎn))：對于數(shù)據(jù)集中的對象

p

，如果在對象

p

的鄰域內(nèi)的對象數(shù)大于等于核心點(diǎn)閾值MinPts，則將對象

p

稱為核心點(diǎn)。定義3(直接密度可達(dá))：數(shù)據(jù)對象

p

、

q

關(guān)于Eps和MinPts直接密度可達(dá)當(dāng)且僅當(dāng)滿足公式2、公式3。

p

∈

N

(

q

)

(2)

|

N

(

q

)|≥MinPts

(3)

其中，

q

為核心點(diǎn)。定義4(密度可達(dá))：數(shù)據(jù)對象

p

、

q

，如果存在對象鏈路

p

,

p

,…,

p

,

q

，對于

p

+1和

p

關(guān)于Eps和MinPts直接密度可達(dá)，則稱

p

、

q

關(guān)于Eps和MinPts密度可達(dá)。定義5(密度相連)：類比定義4，當(dāng)對象鏈路上的所有對象關(guān)于Eps和MinPts密度可達(dá)，則稱

p

、

q

關(guān)于Eps和MinPts密度相連。

定義6(噪聲、簇)：從一個核心點(diǎn)出發(fā)，所有與當(dāng)前核心點(diǎn)密度可達(dá)的點(diǎn)的集合構(gòu)成一個簇；同理，所有核心點(diǎn)都密度不可達(dá)的對象稱為噪聲。

基于以上定義，DBSCAN算法核心思想為，將數(shù)據(jù)集中所有的對象按照密度是否可達(dá)劃分為不同的簇，對于密度不可達(dá)的對象標(biāo)記為噪聲對象。其過程為：

(1)隨機(jī)選取數(shù)據(jù)集中的一個對象，判斷該對象是否為核心點(diǎn)。如果為核心點(diǎn)，則將該對象標(biāo)記為核心點(diǎn)并作為簇的起點(diǎn)；如果不是核心點(diǎn)標(biāo)記為非核心點(diǎn)；

(2)從(1)中選取的核心點(diǎn)出發(fā)，尋找所有和該對象密度可達(dá)的所有對象，加入當(dāng)前核心點(diǎn)的簇中，并以核心點(diǎn)的簇中的對象為起始點(diǎn)繼續(xù)迭代尋找更多的核心點(diǎn)放入核心點(diǎn)簇中；直至當(dāng)前核心點(diǎn)簇中的所有核心點(diǎn)無法找到更多滿足條件的密度可達(dá)的對象為止；

(3)重復(fù)過程(1)(2)，直到所有的密度可達(dá)的對象都聚類成簇。

DBSCAN算法使用歐氏距離表示對象和對象之間的距離，同時使用從核心點(diǎn)向外拓展尋找簇的方式，可以發(fā)現(xiàn)任意形狀的簇。

2 MST-DBSCAN

傳統(tǒng)DBSCAN算法存在幾點(diǎn)弊端：第一，傳統(tǒng)算法無法使用同一組參數(shù)將密度分布不均勻的數(shù)據(jù)集中的兩種或多種密度的數(shù)據(jù)進(jìn)行準(zhǔn)確的聚類。第二，需要人為指定參數(shù)且參數(shù)對于算法結(jié)果的影響很大。在MinPts確定的情況下，選擇的Eps參數(shù)越小，簇中對象和對象之間的距離越小，簇的密度越高。但如果選擇了過小的Eps，使得對象的選擇過于苛刻，會導(dǎo)致大多數(shù)的對象被錯誤標(biāo)記為噪聲，增加了噪聲的數(shù)量導(dǎo)致算法準(zhǔn)確性降低，同時原本為一個簇的對象也會被拆分為多個簇，將相似的對象簇進(jìn)行了過度拆分；如果選擇了過大的Eps會導(dǎo)致對象的選擇條件降低，很多噪聲被錯誤地歸入簇，原本獨(dú)立的各個簇也會被歸為一類，降低了聚類的有效性。在Eps確定的情況下，選擇的MinPts越大，同一簇中的將包含更多的對象簇的密度越高。選擇了過小的MinPts會使得大量的對象被標(biāo)記為核心點(diǎn)，同一個簇中從核心點(diǎn)出發(fā)會包含更多的噪聲；過大的MinPts會導(dǎo)致核心點(diǎn)數(shù)量減少，使得一些邊緣對象被錯誤舍棄。

針對以上弊端對算法進(jìn)行改進(jìn)，改進(jìn)后的MST-DBSCAN算法定義如下參數(shù)：

定義7(簇的個數(shù)

k

)：對數(shù)據(jù)集聚類后期望得到簇的個數(shù)。定義8(最小簇對象數(shù)

n

)：數(shù)據(jù)集聚類期望得到簇中對象數(shù)的最小值。

改進(jìn)算法的步驟如下：

Step1：距離計(jì)算。

傳統(tǒng)算法中常使用歐氏距離表示對象與對象之間的距離，但考慮到數(shù)據(jù)集中對象的密度分布不均勻，而歐氏距離反映的是空間內(nèi)的真實(shí)距離，對于分布不均的數(shù)據(jù)集的對象之間的距離無法歸一化，密度大的區(qū)域的對象之間的距離和密度小的區(qū)域的對象之間的距離沒有可比性，所以使用相互可達(dá)距離，如公式4，代替樣本點(diǎn)之間的真實(shí)距離。經(jīng)過距離替換后大密度區(qū)域的對象之間距離不受影響，小密度區(qū)域的對象之間的距離被放大，起到了歸一化的作用，使得大密度區(qū)域和小密度區(qū)域的對象之間的距離可以進(jìn)行比較，增加了聚類算法對散點(diǎn)的魯棒性；同時使用相互可達(dá)距離代替歐氏距離可以使單鏈路聚類算法更加貼合地去擬合數(shù)據(jù)集中的密度分布。

d

(

p

,

q

)=max{core(

p

),core(

q

),

d

(

p

,

q

)}

(4)

其中，

k

表示距離當(dāng)前對象第

k

近的對象，該參數(shù)對聚類結(jié)果影響不大，通常設(shè)置為

N

*0

.

02(

N

為數(shù)據(jù)集對象總數(shù))；

d

(

p

,

q

)表示對象

p

、

q

之間的相互可達(dá)距離；

d

(

p

,

q

)表示二者之間的歐氏距離；core(

p

)表示對象

p

的核心距離，即與對象

p

與第

k

近的對象的距離，具體計(jì)算方法如下；core(

x

)=

d

(

x

,

N

(

x

))

(5)

其中，

N

(

x

)表示數(shù)據(jù)集中以

x

為中心第

k

近的對象。

Step2：構(gòu)建最小生成樹。

利用Step1中求解的相互可達(dá)距離構(gòu)建距離加權(quán)無向圖。構(gòu)建該無向圖的鄰接矩陣：

(6)

其中，

d

表示數(shù)據(jù)集中對象

p

、

q

之間的相互可達(dá)距離。使用Prim算法計(jì)算當(dāng)前鄰接矩陣的最小生成樹，建立數(shù)據(jù)集中所有對象之間的聯(lián)系。該算法是圖論中一種常用的求解最小生成樹的算法，以權(quán)值最小的邊為主導(dǎo)，再加權(quán)有向圖中搜尋最小生成樹，使得生成樹的權(quán)最小，即：

(7)

其中，

W

(

T

)表示樹

T

的權(quán)，

A

表示樹

T

的邊的集合，

d

表示有向圖中點(diǎn)(

p

,

q

)之間的權(quán)。

算法步驟如下：

(1)初始化：定義圖中的所有頂點(diǎn)集合為

V

，全部邊的集合為

E

，選中的頂點(diǎn)的集合為

V

，選中的邊的集合為

E

，將

V

及

E

初始化為

V

={}，

E

={}。隨機(jī)在

V

中放入集合

V

中的任意節(jié)點(diǎn)

p

作為算法的起始節(jié)點(diǎn)，即

V

={

p

}；(2)構(gòu)建樹：在所有

p

∈

V

，

q

∈

V

-

V

的邊(

q

,

p

)∈

E

中找到權(quán)值最小的邊

e

=(

p

,

q

)放入集合

E

中，同時將

q

放入

V

中；(3)遞歸：重復(fù)步驟(2)中構(gòu)建樹的過程，直到所有的頂點(diǎn)都放入到

V

中為止，即

V

=

V

。此時

E

中存在

N

-1條邊及

N

個點(diǎn)。將

E

中的所有邊，按照起點(diǎn)-終點(diǎn)-權(quán)重的方式封裝，并將封裝后的結(jié)果放入列表PTList中。

Step3：簇的聚類。

通過Step2后生成的最小生成樹，將數(shù)據(jù)集中的所有對象連接起來。通過切斷節(jié)點(diǎn)和節(jié)點(diǎn)之間的邊，將最小生成樹切斷成為多個獨(dú)立的子樹。具體步驟如下：

(1)將生成的PTList按照距離降序排序；

(2)依次選取步驟(1)排序后距離最大的邊的兩個節(jié)點(diǎn)

i

、

j

，將這兩個節(jié)點(diǎn)之間的邊斷開，并計(jì)算節(jié)點(diǎn)

i

、

j

的所有子孫節(jié)點(diǎn)的個數(shù)，記為

N

、

N

，不妨設(shè)

N

≤

N

。如果某一個節(jié)點(diǎn)的子孫節(jié)點(diǎn)個數(shù)不小于最小簇對象數(shù)，即min(

N

,

N

)≥

n

，則將節(jié)點(diǎn)

N

及其所有子孫節(jié)點(diǎn)歸為聚類的一個簇，放入隊(duì)列

C

List中；否則將上述子孫節(jié)點(diǎn)全部標(biāo)記為噪聲節(jié)點(diǎn)；(3)重復(fù)步驟(2)，直到有

k

-1個簇被放入了

C

List中；(4)將沒有被標(biāo)記的節(jié)點(diǎn)組成標(biāo)記為一個簇放入

C

List中。

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

為了對改進(jìn)后算法的聚類有效性進(jìn)行評估，進(jìn)行以下對比實(shí)驗(yàn)。將該算法與DBSCAN算法、文獻(xiàn)[12]提出的KANN-DBSCAN算法以及OPTICS算法在公開數(shù)據(jù)集上進(jìn)行對比。

實(shí)驗(yàn)環(huán)境：Intel(R) Core(TM) i7-8565U CPU @1.80 GHz 1.99 GHz，軟件環(huán)境：JDK1.8、IDEA。

該文使用的聚類算法的評價指標(biāo)選擇調(diào)整蘭德指數(shù)(ARI)、歸一化互信息(NMI)、完整性指標(biāo)及同質(zhì)性指標(biāo)。

調(diào)整蘭德指數(shù)(ARI)是一種衡量兩個數(shù)據(jù)分布的吻合程度的指標(biāo)。蘭德指數(shù)(RI)對兩個隨機(jī)的劃分上存在缺陷，使得RI結(jié)果不是一個接近0的常數(shù)。ARI解決了該問題，其指標(biāo)的取值范圍為[-1,1]，值越大表示其聚類結(jié)果越接近真實(shí)結(jié)果，且對于隨機(jī)聚類的ARI都非常接近0，其計(jì)算方法如下：

(8)

其中，RI為蘭德指數(shù)，計(jì)算方法如下：

(9)

歸一化互信息(NMI)指標(biāo)是對互信息的歸一化，是信息論中的一種信息度量的方式，可以理解為一個隨機(jī)事件中包含另外一個隨機(jī)事件的信息量?？梢酝ㄟ^隨機(jī)時間發(fā)生的概率計(jì)算得到。

(10)

其中，

I

(

X

;

Y

)表示兩隨機(jī)事件的互信息，

p

(

x

,

y

)表示二者的聯(lián)合分布概率，

p

(

x

)及

p

(

y

)分別表示兩事件單獨(dú)發(fā)生的概率。

NMI將互信息的取值歸一化在[0,1]之間，其取值越接近0表示聚類結(jié)果越差，越接近1表示聚類結(jié)果越接近真實(shí)結(jié)果，計(jì)算公式如下：

(11)

完整性及同質(zhì)性是一種基于條件熵的聚類評估方法。二者往往存在一定的負(fù)相關(guān)關(guān)系。其中，完整性(completeness)表示在真實(shí)結(jié)果中某一簇的所有成員，經(jīng)過聚類后被分配到單一簇的程度；同質(zhì)性(homogeneity)表示聚類結(jié)果中每一個簇包含單一類別的成員的程度。兩個指標(biāo)的取值范圍為[0,1]，越接近0表示聚類后的結(jié)果分布松散，對數(shù)據(jù)集的錯誤聚類情況越多，越接近1表示聚類結(jié)果越準(zhǔn)確。計(jì)算方法如公式12和公式13：

(12)

(13)

其中，

h

表示同質(zhì)性，

c

表示完整性，

h

、

c

的取值范圍為[0,1]；

H

(

C

|

K

)及

H

(

K

|

C

)是給定簇

C

和

K

的條件熵，

H

(

C

)及

H

(

K

)是簇的熵。

選用以上4個參數(shù)作為聚類結(jié)果的評價指標(biāo)，可以從聚類結(jié)果與真實(shí)結(jié)果的吻合度、聚類結(jié)果的準(zhǔn)確性及聚類程度等多方面衡量聚類算法的聚類效果。

實(shí)驗(yàn)分別選擇UCI公開數(shù)據(jù)集中的5個常用數(shù)據(jù)集，數(shù)據(jù)集包含了不同維度、不同分類數(shù)的數(shù)據(jù)集，各個數(shù)據(jù)集中的具體參數(shù)如表1所示。

表1 UCI數(shù)據(jù)集

4種算法在UCI數(shù)據(jù)集上的評價指標(biāo)對比如表2所示。

表2 4種算法在UCI數(shù)據(jù)集上的評價指標(biāo)對比

將5個數(shù)據(jù)集在DBSACAN、OPTICS、KANN-DBSCAN、MST-DBSCAN算法中的各個性能指標(biāo)繪制成折線圖，如圖1所示。

圖1 改進(jìn)前后各指標(biāo)對比結(jié)果

通過以上對比結(jié)果可以看出，MST-DBSCAN算法在各個數(shù)據(jù)集中的評價指標(biāo)相比于傳統(tǒng)算法都有著不同程度的改進(jìn)，相比其他改進(jìn)算法，該算法在整體效果上優(yōu)于其他算法。雖然在Iris數(shù)據(jù)集中OPTICS算法的NMI及完整性指標(biāo)高于MST-DBSCAN；在Thyroid數(shù)據(jù)集中KANN-DBSCAN算法的ARI及完整性指標(biāo)優(yōu)于MST-DBSCAN算法等，但從整體效果對比來看，隨著數(shù)據(jù)集的特征數(shù)增加，MST-DBSCAN算法的ARI、同質(zhì)性等聚類評價指標(biāo)明顯高于其他聚類算法。

在密度分布不均勻的數(shù)據(jù)集及高維度數(shù)據(jù)集中，改進(jìn)的算法體現(xiàn)了優(yōu)越性。在處理密度分布不均勻的數(shù)據(jù)集時，如Glass及Wine數(shù)據(jù)集，其中Glass數(shù)據(jù)集的不平衡問題最為突出，通過對比圖1可以發(fā)現(xiàn)，MST-DBSCAN算法在4種評價指標(biāo)上的表現(xiàn)都優(yōu)于其他算法，其中NMI指標(biāo)最為明顯。在處理高維度數(shù)據(jù)集時，如Breast Cancer數(shù)據(jù)集，該數(shù)據(jù)集的數(shù)據(jù)維度為32，從評價指標(biāo)中可以看出，MST-DBSCAN算法的表現(xiàn)同樣優(yōu)于其他算法。尤其對于KANN-DBSCAN算法，在ARI及NMI指標(biāo)上有明顯優(yōu)勢。

通過上述比較發(fā)現(xiàn)，該文提出的MST-DBSCAN算法的聚類效果最好，在密度分布不均及高維度數(shù)據(jù)集上的表現(xiàn)較好，DBSCAN和OPTICS算法的效果一般，KANN-DBSCAN算法在數(shù)據(jù)維度高的數(shù)據(jù)集的聚類效果最不理想。

4 結(jié)束語

該文運(yùn)用最小生成樹思想，對數(shù)據(jù)集中的對象構(gòu)建最小生成樹，通過指定簇的個數(shù)及最小簇對象數(shù)進(jìn)行剪枝，因?yàn)橹付舜氐臄?shù)目，使聚類結(jié)果更加接近真實(shí)結(jié)果。進(jìn)一步優(yōu)化了DBSCAN對Eps及MinPts敏感的問題，選擇使用更加容易確定的參數(shù)代替較難確定的參數(shù)，省去了原算法中對于Eps及MinPts選擇的過程。同時通過在對象之間使用相互可達(dá)距離代替DBSCAN中使用的歐氏距離在一定程度上避免了維度災(zāi)難問題，解決了DBSCAN算法對于密度分布不均與數(shù)據(jù)集聚類效果不理想的問題。實(shí)驗(yàn)結(jié)果表明，MST-DBSCAN算法可以完成對于密度分布不均勻的數(shù)據(jù)集的聚類；同時，對高維數(shù)據(jù)集的聚類效果優(yōu)于原DBSCAN算法。但MST-DBSCAN算法在低維數(shù)據(jù)集聚類效果不穩(wěn)定，同時算法增加了聚類的復(fù)雜度，對于規(guī)模較大的數(shù)據(jù)集消耗時間較長。接下來的工作將繼續(xù)降低算法的時間復(fù)雜度及低維數(shù)據(jù)集的聚類穩(wěn)定性，將算法的聚類效果最優(yōu)化。