# 密度聚類(lèi)DBSCAN、HDBSCAN

DBSCAN

DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪聲的基于密度的聚類(lèi)方法）是一種基于密度的空間聚類(lèi)算法。該算法將具有足夠密度的區(qū)域劃分為簇，并在具有噪聲的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的簇，它將簇定義為密度相連的點(diǎn)的最大集合。 在DBSCAN算法中將數(shù)據(jù)點(diǎn)分為三類(lèi)：

• 核心點(diǎn)（Core point）。若樣本 的 鄰域內(nèi)至少包含了MinPts個(gè)樣本，即 ( )≥ ，則稱樣本點(diǎn) 為核心點(diǎn)。
• 邊界點(diǎn)（Border point）。若樣本 的 鄰域內(nèi)包含的樣本數(shù)目小于MinPts，但是它在其他核心點(diǎn)的鄰域內(nèi)，則稱樣本點(diǎn) 為邊界點(diǎn)。
• 噪音點(diǎn)（Noise）。既不是核心點(diǎn)也不是邊界點(diǎn)的點(diǎn)

1、算法的流程

• 根據(jù)給定的鄰域參數(shù)Eps和MinPts確定所有的核心對(duì)象
• 對(duì)每一個(gè)核心對(duì)象
• 選擇一個(gè)未處理過(guò)的核心對(duì)象，找到由其密度可達(dá)的的樣本生成聚類(lèi)“簇”
• 重復(fù)以上過(guò)程

偽代碼：

(1) 首先將數(shù)據(jù)集D中的所有對(duì)象標(biāo)記為未處理狀態(tài) (2) for（數(shù)據(jù)集D中每個(gè)對(duì)象p） do (3) if （p已經(jīng)歸入某個(gè)簇或標(biāo)記為噪聲） then (4) continue; (5) else (6) 檢查對(duì)象p的Eps鄰域 NEps(p) ； (7) if (NEps(p)包含的對(duì)象數(shù)小于MinPts) then (8) 標(biāo)記對(duì)象p為邊界點(diǎn)或噪聲點(diǎn)； (9) else (10) 標(biāo)記對(duì)象p為核心點(diǎn)，并建立新簇C, 并將p鄰域內(nèi)所有點(diǎn)加入C (11) for (NEps(p)中所有尚未被處理的對(duì)象q) do (12) 檢查其Eps鄰域NEps(q)，若NEps(q)包含至少M(fèi)inPts個(gè)對(duì)象，則將NEps(q)中未歸入任何一個(gè)簇的對(duì)象加入C； (13) end for (14) end if (15) end if (16) end for

2、優(yōu)點(diǎn)

• 相比K-Means，DBSCAN 不需要預(yù)先聲明聚類(lèi)數(shù)量。
• 可以對(duì)任意形狀的稠密數(shù)據(jù)集進(jìn)行聚類(lèi)，相對(duì)的，K-Means之類(lèi)的聚類(lèi)算法一般只適用于凸數(shù)據(jù)集。
• 可以在聚類(lèi)的同時(shí)發(fā)現(xiàn)異常點(diǎn)，對(duì)數(shù)據(jù)集中的異常點(diǎn)不敏感。
• 聚類(lèi)結(jié)果沒(méi)有偏倚，相對(duì)的，K-Means之類(lèi)的聚類(lèi)算法初始值對(duì)聚類(lèi)結(jié)果有很大影響。

3、缺點(diǎn)

• 當(dāng)空間聚類(lèi)的密度不均勻、聚類(lèi)間距差相差很大時(shí)，聚類(lèi)質(zhì)量較差，因?yàn)檫@種情況下參數(shù)MinPts和Eps選取困難。
• 如果樣本集較大時(shí)，聚類(lèi)收斂時(shí)間較長(zhǎng)，此時(shí)可以對(duì)搜索最近鄰時(shí)建立的KD樹(shù)或者球樹(shù)進(jìn)行規(guī)模限制來(lái)改進(jìn)。
• 在兩個(gè)聚類(lèi)交界邊緣的點(diǎn)會(huì)視乎它在數(shù)據(jù)庫(kù)的次序決定加入哪個(gè)聚類(lèi)，幸運(yùn)地，這種情況并不常見(jiàn)，而且對(duì)整體的聚類(lèi)結(jié)果影響不大（DBSCAN*變種算法，把交界點(diǎn)視為噪音，達(dá)到完全決定性的結(jié)果。）
• 調(diào)參相對(duì)于傳統(tǒng)的K-Means之類(lèi)的聚類(lèi)算法稍復(fù)雜，主要需要對(duì)距離閾值eps，鄰域樣本數(shù)閾值MinPts聯(lián)合調(diào)參，不同的參數(shù)組合對(duì)最后的聚類(lèi)效果有較大影響。

HDBSCAN聚類(lèi)

1、空間變換

所謂的空間變換，就是我們用互達(dá)距離來(lái)表示兩個(gè)樣本點(diǎn)之間的距離。這樣會(huì)使得，密集區(qū)域的樣本距離不受影響，而稀疏區(qū)域的樣本點(diǎn)與其他樣本點(diǎn)的距離被放大。這增加了聚類(lèi)算法對(duì)散點(diǎn)的魯棒性?？臻g變換的效果顯然取決于K的選擇，當(dāng)K較大時(shí)，會(huì)使得核心距離變大，所以互達(dá)距離也變大，這樣會(huì)有更多樣本點(diǎn)被分配到稀疏區(qū)域。即更多點(diǎn)將被視為散點(diǎn)。

2、建立最小生成樹(shù)

我們可將數(shù)據(jù)看作一個(gè)加權(quán)圖，其中數(shù)據(jù)點(diǎn)為頂點(diǎn)，任意兩點(diǎn)之間的邊的權(quán)重為這些點(diǎn)之間的互達(dá)距離。對(duì)圖像進(jìn)行分裂。最終圖的變化過(guò)程是：從完全圖到極小連通子圖。HDBSCAN使用最小生成樹(shù)算法：

3、層次聚類(lèi)結(jié)構(gòu)

• 第一步：將樹(shù)中的所有邊按照距離遞增排序
• 第二步：然后依次選取每條邊，將邊的鏈接的兩個(gè)子圖進(jìn)行合并。

這樣就構(gòu)建出了聚合樹(shù)：

可以理解，類(lèi)似于哈夫曼樹(shù)的構(gòu)造，這棵樹(shù)自上而下數(shù)據(jù)之間的距離是從大到小的。

4、剪枝

同時(shí)進(jìn)行剪枝，即最小子樹(shù)做了限制，主要是為了控制生成的類(lèi)簇不要過(guò)小：

• 第一步：確定最小族大小n
• 第二步：自上而下遍歷聚類(lèi)樹(shù)，并在每個(gè)節(jié)點(diǎn)分裂時(shí)：看分裂產(chǎn)生的兩個(gè)樣本子集的樣本數(shù)是否大于n
• 如果左右兒子中有一個(gè)子結(jié)點(diǎn)的樣本數(shù)< n，我們就直間將該節(jié)點(diǎn)刪除，并且另一個(gè)子節(jié)點(diǎn)保留父節(jié)點(diǎn)的身份
• 如果兩個(gè)子結(jié)點(diǎn)中的樣本數(shù)都<n，那么就將其兩個(gè)子節(jié)點(diǎn)都刪除，即當(dāng)前節(jié)點(diǎn)不再向下分裂
• 如果兩個(gè)子結(jié)點(diǎn)中的樣本數(shù)都>=n，那么我們進(jìn)行正常分裂，即保持原聚類(lèi)樹(shù)不變。

5、提取簇

經(jīng)過(guò)聚類(lèi)樹(shù)的壓縮操作，樹(shù)中已經(jīng)沒(méi)有了散點(diǎn)，我現(xiàn)在的任務(wù)只是將比較相近的節(jié)點(diǎn)合并到一族中去，我們最后選擇的簇能夠有更好的穩(wěn)定性。

我們可以這里理解，有一個(gè)閾值distance，如上圖的紅線。用它切割，面最近的節(jié)點(diǎn)作為聚類(lèi)的一個(gè)類(lèi)，而紅線上面的聚起來(lái)的都是散點(diǎn)。問(wèn)題是，我們?nèi)绾沃篱撝翟谀睦?#xff1f;能不能有更好的提取族的方式呢？HDBSCAN定義了一種基于穩(wěn)定度的提取族方式那么如何來(lái)定義樹(shù)中節(jié)點(diǎn)的穩(wěn)定度呢？ 我們先定義一個(gè)λ，它是距離的倒數(shù)：

對(duì)于樹(shù)中的某個(gè)節(jié)點(diǎn)定義兩個(gè)量：λbirth，λdeath λbirth表示：分裂產(chǎn)生當(dāng)前節(jié)點(diǎn)時(shí)，distance的倒數(shù)。 λdeath表示：當(dāng)前節(jié)點(diǎn)被分裂成兩個(gè)子結(jié)點(diǎn)時(shí)，distance的倒數(shù)。 λp表示：當(dāng)前節(jié)點(diǎn)（族）下各節(jié)點(diǎn)p從前節(jié)點(diǎn)（族）分離出去時(shí)，distance的倒數(shù)。 在這里對(duì)λp做下說(shuō)明，p從聚類(lèi)族分離出去有兩種情況：

• λp = λdeath時(shí)，即該節(jié)點(diǎn)（簇）被分裂成兩個(gè)子結(jié)點(diǎn)了
• λbirth <= λp < λdeath時(shí)，即在該之間距離變化中可能切割出散點(diǎn)。此時(shí)，原來(lái)的節(jié)點(diǎn)（簇）并沒(méi)有分裂成兩個(gè)子結(jié)點(diǎn)，而是直接把散點(diǎn)給移除了。

我們定義穩(wěn)定度為：

提取簇步驟：

• 第一步：初始化族

將壓縮聚類(lèi)樹(shù)的每個(gè)葉節(jié)點(diǎn)都選定為某個(gè)簇。

• 第二步：自下而上遍歷遍歷整棵樹(shù)，并且每一步進(jìn)行下面操作：

如果當(dāng)前節(jié)點(diǎn)的穩(wěn)定性小于兩個(gè)子結(jié)點(diǎn)的穩(wěn)定性總和，那么我們將該節(jié)點(diǎn)的穩(wěn)定性設(shè)置為其子節(jié)點(diǎn)的穩(wěn)定性之和。如果當(dāng)前節(jié)點(diǎn)的穩(wěn)定性大于兩個(gè)子結(jié)點(diǎn)的穩(wěn)定性總和，那么將當(dāng)前節(jié)點(diǎn)定為某個(gè)簇。

總結(jié)

以上是生活随笔為你收集整理的dbscan聚类算法matlab_密度聚类DBSCAN、HDBSCAN(转)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。