Skip to content

What is DBSCAN ​

DBSCAN(Density-based spatial clustering of applications with noise)是一種基於密度的演算法。給定一個數量點的閾值,表示該群集要超過一定的密度程度。密度程度則會透過距離方式來做計算。

Concept ​

Parameters ​

  • Eps
    • 鄰域的最大半徑
  • MinPts
    • 點的 Eps-neighborhood 中的最少點數量

Density Definition ​

  • $\varepsilon$-Neighborhood
    • 距離對象半徑 $\varepsilon$ 以內的對象。
    • 距離 $\varepsilon$ 內的所有點的集合。

$N_{\varepsilon}(p):{q|d(p,q) \leq \varepsilon}$

  • High density
    • 一個對象的 $\varepsilon$-Neighborhood 至少包含 MinPts 個對象。

${\varepsilon}$-Neighborhood of $p$ ${\varepsilon}$-Neighborhood of $q$ Density of p is high (MinPts = 4) Density of q is low (MinPts = 4)

Core, Border & Outlier ​

給定 ${\varepsilon}$ 和 MinPts,將對象分為三個群集。

  • Core point
    • 如果點在 Eps 內具有超過指定數量的點(MinPts),則該點為 core point - 這些點位於群集的內部。
    • 在其 $N_{\varepsilon}$ 內至少具有 "minPoint"(包括自身)點的點。
  • Border point
    • border point 在 Eps 內少於 MinPts,但在 core point 附近。
    • 點是 DDR(Direct Density Reachable),但不是 core point。
  • Noise point
    • noise point 是不是 core point 也不是 border point 的任何點。
    • 不屬於任何點的 $N_{\varepsilon}$ 的點。

Density-reachability(directly and indirectly) ​

  • Directly density-reachable
    • 如果 $p$ 是 core point 且 $q \in N_{\varepsilon}$,則從點 $p$ 直接可以達到密度 $q$。如果有連接這兩個點的 DDR 點鏈,則兩個點是 DR。

  • $q$ 是直接從 $p$ 達到密度的。
  • $p$ 不能直接從 $q$ 到達密度。
  • 密度可達性是不對稱的。

  • 從 $p_2$ 直接可以達到密度點 $p$
  • $p_2$ 可直接從 $p_1$ 達到密度
  • $p_1$ 可從 $q$ 直接達到密度
  • $p$ <- $p_2$ <- $p_1$ <- q 形成鍊
  • $p$ 從 $q$ (間接)可達到密度。
  • $q$ 從 $p$ 不可達到密度。

Example ​

python
import matplotlib.pyplot as plt  
import numpy as np  
from sklearn import datasets 
from  sklearn.cluster import DBSCAN

iris = datasets.load_iris() 
X = iris.data[:, :4]
plt.scatter(X[:, 0], X[:, 1], c="red", marker='o', label='see')  
plt.xlabel('petal length')  
plt.ylabel('petal width')  
plt.legend(loc=2)  
plt.show()  

dbscan = DBSCAN(eps=0.4, min_samples=9)
dbscan.fit(X) 
label_pred = dbscan.labels_

x0 = X[label_pred == 0]
x1 = X[label_pred == 1]
x2 = X[label_pred == 2]
plt.scatter(x0[:, 0], x0[:, 1], c="red", marker='o', label='label0')  
plt.scatter(x1[:, 0], x1[:, 1], c="green", marker='*', label='label1')  
plt.scatter(x2[:, 0], x2[:, 1], c="blue", marker='+', label='label2')  
plt.xlabel('petal length')  
plt.ylabel('petal width')  
plt.legend(loc=2)  
plt.show()

Ref ​

Built with VitePress