ML-2-DBSCAN

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

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

• 1
• 2
• 3
• ai-academy-taiwan