文章目錄

• 1. 密度聚類
• 2. DBSCAN
• • 2.1 算法原理
• 3. DBSCAN 優缺點
• • 3.1 優點
  • 3.2 缺點
  • 3.3 與 KMeans 比較
• 4. SKlearn 實現
• 5. 在線可視化 DBSCAN
• 參考文獻

相關文章：

機器學習 | 目錄

機器學習 | 聚類評估指標

機器學習 | 距離計算

無監督學習 | KMeans 與 KMeans++ 原理

無監督學習 | GMM 高斯混合聚類原理及Sklearn實現

1. 密度聚類

密度聚類亦稱“基于密度的聚類”（Density-Based Clustering），此類算法假設聚類結構能通過樣本分布的緊密程度確定。通常情況下，密度聚類算法從樣本密度的角度來考察樣本之間的可連接性，并基于可連接樣本不斷擴展聚類簇以獲得最終的聚類結果^[1]。這類算法可以克服 KMeans、BIRCH等只適用于凸樣本集的情況。

常用的密度聚類算法：DBSCAN、MDCA、OPTICS、DENCLUE等。^[2]

密度聚類的主要特點是：

（1）發現任意形狀的簇

（2）對噪聲數據不敏感

（3）一次掃描

（4）需要密度參數作為停止條件

（5）計算量大、復雜度高

2. DBSCAN

DBSCAN（具有噪聲的基于密度的空間聚類，Density-Based Spatial Clustering of Applications with Noise）是一種著名的密度聚類算法，它基于一組“鄰域”（neighborhood）參數（$\epsilon ,MinPts$）來刻畫樣本分布的緊密程度。

首先我們通過一個簡單的例子來介紹 DBSCAN，對于以下數據，我們任意選取一個點，定義一個以 $?$ 為半徑的鄰域，若鄰域內沒有其他點，則這個點定義為噪聲或異常點。

圖1 鄰域半徑及噪聲點

若這個點不是噪聲，則考慮第二個參數：鄰域內最少樣本個數 $MinPts$，若某點鄰域內最少樣本個數不少于 $MinPts$，則這個點定義為核心點。對于該鄰域內的非核心對象，定義為邊界點，假設 $MinPts$=5 ，則聚類過程如下圖所示：

圖2 鄰域內樣本個數少于最少個數 圖3 核心點與邊界點

同理，繼續掃描其余的點，可得其他簇：

圖4 兩個不同的聚類簇

下面，我們將通過嚴格的數學定義，來描述 DBSCAN 聚類算法。

2.1 算法原理

首先，給定數據集 $D=\{x_1,x_2,...,x_m\}$，我們定義下面幾個概念：

• $?$ 鄰域：對 $x_j\in D$，其 $?$ 鄰域包含數據集 $D$ 中與 $x_j$ 的距離不大于 $?$ 的樣本，即 $N_{?}=\{x_o\in D|dist(x_i,x_j\le ?)\}$；

• 核心對象（core object）：若 $x_j$ 的 $\epsilon$ 鄰域至少包含 $MinPts$ 個樣本，即 $|N_{?}(x_j)\ge MinPts|$，則 $x_j$ 是一個核心對象；

• 密度直達（directly density-reachable）：若 $x_j$ 位于 $x_i$ 的 $?$ 鄰域中，且 $x_i$ 是核心對象，則稱 $x_j$ 由 $x_i$ 密度直達；

• 密度可達（density-reachable）：對 $x_i$ 與 $x_j$，若存在樣本序列 $p_1,p_2,...,p_n$，其中 $p_1=x_i,p_n=x_j$ 且 $p_{i+1}$ 由 $p_i$ 密度直達，則稱 $x_i$ 由 $x_j$ 可達；

• 密度相連（density-connected）：對 $x_i$ 與 $x_j$，若存在 $x_k$ 使得 $x_i$ 與 $x_j$ 均由 $x_k$ 密度可達，則稱 $x_i$ 與 $x_j$ 密度相連。

對于鄰域中的距離函數 dist(?,?)，在默認情形下設為歐式距離。

下圖給出了上述概念的直觀顯示，假設 $MinPts=3$：虛線顯示出 $?$ 鄰域,$x_1$ 是核心對象， $x_2$ 由 $x_1$ 密度直達，$x_3$ 由 $x_1$ 密度可達，$x_3$ 與 $x_4$ 密度相連。

圖4 樣本點劃分示意圖

---

基于這些概念，DBSCAN 將“簇”定義為：密度可達關系導出的最大的密度相連樣本集合。形式化地說，給定鄰域參數（$?,MinPts$），簇 $C?D$ 是滿足以下性質的非空樣本子集：

$$連接性（connectivity）：x_i\in C,x_j\in C?x_i與x_j密度相連\text{\hspace{1em}(1)}$$

$$最大性（maximality）：x_i\in C,x_j由x_i密度可達?x_j\in C\text{\hspace{1em}(2)}$$

若 $x$ 為核心對象，則 $x$ 密度可達的所有樣本組成的集合記為 $X=\{x^{\prime }\in D|x^{\prime }由x密度可達\}$，其中 $X$ 為滿足連接性和最大性的簇。

于是，DBSCAN 算法先任選數據集中的一個核心對象為“種子”（seed），再由此出發確定相應的聚類簇。

算法描述如下圖所示，

• 在第 1-7 行中，算法先根據給定的鄰域參數（$?,MinPts$）找出所有核心對象；

• 在第 10-24 行中，以任一核心對象為出發點，找出由密度可達的樣本以生成聚類簇，知道所有核心對象均被訪問過為止。

圖5 DBSCAN 算法

3. DBSCAN 優缺點

3.1 優點

（1）不用指明類別數量；

（2）能靈活找到并分離各種形狀和大小的類；

（3）能很好地處理噪聲和離群點。

3.2 缺點

（1）對于從兩個類均可達的邊界點，由于各個點是被隨機訪問的，因此 DBSCAN 不能保證每次都返回相同聚類；

（2）在不同密度的類方面有一定難度。

3.3 與 KMeans 比較

從下面的圖中可以看出，DBSCAN 在不規則的數據上，能更好地分類。

圖6 DBCASAN 與 KMeans 聚類效果比較

4. SKlearn 實現

sklearn.cluster.DBSCAN(eps=0.5, min_samples=5, metric=’euclidean’, metric_params=None, algorithm=’auto’, leaf_size=30, p=None, n_jobs=None)

eps : float, optional 【$?$】

The maximum distance between two samples for one to be considered as in the neighborhood of the other. This is not a maximum bound on the distances of points within a cluster. This is the most important DBSCAN parameter to choose appropriately for your data set and distance function.

min_samples : int, optional 【$MinPts$】

The number of samples (or total weight) in a neighborhood for a point to be considered as a core point. This includes the point itself.

5. 在線可視化 DBSCAN

你可以通過這個網站選擇樣本分布和參數，并在線可視化 DBSCAN 聚類的過程。

參考文獻

[1] 周志華. 機器學習[M]. 北京: 清華大學出版社, 2016: 211.

[2] liuy9803.機器學習之密度聚類算法[EB/OL].https://blog.csdn.net/liuy9803/article/details/80812489, 2018-06-26 .

總結

以上是生活随笔為你收集整理的无监督学习 | DBSCAN 原理及Sklearn实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。