寫在前面：健忘星人自學筆記，僅供參考。

通俗易懂的參考資料

正文：

在上一章我們簡單介紹了一下 K-Means演算法，其主要針對類圓形區域資料的聚類，對非凸資料集無計可施。而今天要介紹的 密度聚類 DBSCAN 演算法可以彌補這個缺點，它可用於任何形狀的聚類，既適用於凸樣本集，也適用於非凸樣本集。

1、DBSCAN 基礎概念

DBSCAN，Density-Based

Spatial Clustering of Applications

with Noise

，具有噪聲的基於密度的聚類方法。全稱中透露出兩個重要資訊，即 DBSCAN 聚類演算法是抗噪的，稍後我們會介紹詳細的機制。

另外就是，DBSCAN 聚類是

密度聚類

的代表性演算法。

密度聚類的思想，其實和人類的思維十分相似，透過判斷“是否緊密相連“來確定樣本點是否屬於一個簇。

如果一個點周圍環繞很多其他點，並且比他密度大的點離他距離還很遠，則認為這個點是一個聚類中心。在DBSCAN中，我們將其稱之為

“核心物件”

。

為了清楚得定義核心物件，我們需要明確兩個判斷條件：

（1）核心物件“周圍”的距離如何度量？

（2）圍繞了“很多”點，“很多”該如何界定？

上面兩個問題，正好對應了 DBSCAN 演算法中兩個重要的引數 （ε，MinPts）

鄰域ε，指定的每個核心物件搜尋的半徑值。

MinPts，每個核心物件周圍最少應該包含的點的數量。

由此我們引申出核心點的定義：

若以某個點為中心，指定半徑ε範圍內包含點的個數超過MinPts，則這個點是一個核心點。

舉例，

如上所示，指定MinPts=5，考察藍點q 和綠點p

若假設半徑為5，分別以p和q為中心畫圓，圈定“周圍“的搜尋半徑

以 q 為中心的圓內有7個點（包含自己），超過MinPts（=5），滿足核心點定義

所以 q 是一個核心點；

以 p 為中心的圓內有3個點，少於MinPts 的要求，不滿足核心點的定義

但同時 p 還有一個特性，它落在了核心點q 的圓內，

雖然 p 很遺憾沒達到核心點的資格，但是 p 是一個“邊界點”

下面給出邊界點的定義，

若以某個點為中心，指定半徑 ε 範圍內包含點的個數不足MinPts，但是其落在了某個或者多個核心點的鄰域內，則該點是一個“邊界點”。

最後，對於既不是核心點，也不是邊界點的點，我們也給它一個稱呼——“噪音點”

2、DBSCAN 原理

理解了“核心點”“邊界點”“噪音點”的基本概念，我們來看DBSCAN是如何工作的。

1。將所有點按照“核心點、邊界點或噪聲點“分類標記；

2。刪除噪聲點；

3。如果兩個核心點之間的距離小於 ε ，為其賦予一條邊，互相連通；檢查所有核心點

4。每組連通的核心點形成一個簇；

5。將每個邊界點指派到一個與之關聯的核心點的簇中（哪一個核心點的半徑範圍之內）。

上面的步驟看起來是不是很簡單呢~

官方給出的步驟專業性更強，比較難以讀懂，但是我們還是試著理解一下

密度直達：

p點與核心物件q的距離小於 ε，p密度直達q

（如之前的舉例）

密度可達：

p、q之間距離大於 ε，但是兩者ε半徑範圍內，有共同一點m

（顯然 m 密度直達p，且 m密度直達q）

核心點 p，q 透過點 m 連線了起來，因此 p、q 密度可達

密度相連：

p、o 密度可達，q，o 密度可達，則 p，q 密度相連

DBSCAN的演算法就是，

（1）先找到一個核心物件，從它出發，確定若干個

直接密度可達

的物件

（2）再從這若干個物件出發，尋找它們

直接密度可達

的點，

（3）直至最後沒有可新增的物件了，那麼一個簇的更新就完成了。

我們也可以說，簇其實就是所有密度可達的點的集合。

備註：

我們可能會遇到一些特殊的情況，某些樣本可能到兩個核心物件的距離都小於ε，但是這兩個核心物件由於不是密度直達，又不屬於同一個聚類簇，那麼如果界定這個樣本的類別呢？

一般來說，此時DBSCAN採用先來後到，先進行聚類的類別簇會標記這個樣本為它的類別。也就是說DBSCAN的演算法不是完全穩定的演算法。

3、優缺點

優點：

1、不需要指定簇的個數

2、對噪音不敏感，可以在聚類的同時發現異常點

3、初始值對演算法無影響

缺點：

1）如果樣本集的密度不均勻、聚類間距差相差很大時，聚類質量較差，這時用DBSCAN聚類一般不適合。

2） 如果樣本集較大時，聚類收斂時間較長，此時可以對搜尋最近鄰時建立的KD樹或者球樹進行規模限制來改進。

3） 調參相對於傳統的K-Means之類的聚類演算法稍複雜，主要需要對 （ε，MinPts） 聯合調參，不同的引數組合對最後的聚類效果有較大影響。

今天就到這裡，感謝觀看~~