DBSCAN

DBSCAN

---

• DBSCAN(Density-Based Spatial Clustering of Applications with Noise) : 밀도 기반 배타적 분리형 군집화 알고리즘

  

• 군집 : 사전에 주어진 $\varepsilon, \text{MinPts}$ 에 기초했을 때 Maximality, Connectivity 조건을 만족하는 Non-Empty Subset

  

  • Maximality

    표본 $D$ 에 속하는 관측치 벡터 $\overrightarrow{p}, \overrightarrow{q}$ 에 대하여, $\overrightarrow{p} \in C \subseteq D$ 이고, $\overrightarrow{q}$ 가 $\overrightarrow{p}$ 로부터 밀도 기준 도달 가능한(Directly Density-Reachable) 벡터이면, $\overrightarrow{q} \in C$ 임

  • Connectivity

    군집 $C$ 에 속하는 관측치 벡터 $\overrightarrow{p}, \overrightarrow{q}$ 간에는 밀도 기준 연결되어 있음(Density-Connected)

Concept

---

$\varepsilon$-neighborhood of a point

표본 $D$ 에 속하는 관측치 벡터 $\overrightarrow{p}$ 에 대하여, $\overrightarrow{p}$ 의 이웃 집합 $N_{\varepsilon}(\overrightarrow{p})$ 은 $\overrightarrow{p}$ 와의 거리가 $\varepsilon$ 이하인 관측치 벡터 $\overrightarrow{q}$ 의 집합임

\[N_{\varepsilon}(\overrightarrow{p}) =\{\overrightarrow{q} \in D \mid d(\overrightarrow{p},\overrightarrow{q}) \le \varepsilon\}\]

Directly Density-Reachable

Core Point Condition 을 만족하는 관측치 벡터 $\overrightarrow{p} \in D$ 에 대하여, 그 이웃 관측치 벡터($\varepsilon$-neighborhood of a point) $\overrightarrow{q}$ 는 $\overrightarrow{p}$ 로부터 밀도 기준 직접 도달 가능한(Directly Density-Reachable) 관측치 벡터임

• Core Point Condition

  \[\vert N_{\varepsilon}(\overrightarrow{p}) \vert \ge \text{MinPts}\]

• Reachability

  \[\overrightarrow{q} \in N_{\varepsilon}(\overrightarrow{p})\]

Density-Reachable

Core Point Condition 을 만족하는 관측치 벡터 \(\overrightarrow{p} \in D\) 에 대하여, \(\overrightarrow{p}\) 와 \(\overrightarrow{q}\) 사이에 \(\overrightarrow{p}\) 로부터 밀도 기준 직접 도달 가능한 관측치 벡터 \(\overrightarrow{x}_{1},\overrightarrow{x}_{2},\cdots,\overrightarrow{x}_{n}\) 이 연쇄적으로 존재한다면, \(\overrightarrow{q}\) 는 \(\overrightarrow{p}\) 로부터 밀도 기준 도달 가능한(Density-Reachable) 관측치 벡터임

• \(\vert N_{\varepsilon}(\overrightarrow{p})\vert \ge \text{MinPts}\) : Core Point Condition
• \(\overrightarrow{x}_{1} \in N_{\varepsilon}(\overrightarrow{p})\) : Reachability
• \(\vert N_{\varepsilon}(\overrightarrow{x}_{\forall})\vert \ge \text{MinPts}\) : \(\overrightarrow{x}_{\forall}\) 의 이웃 벡터 갯수가 하한선 $\text{MinPts}$ 이상임
• \(\overrightarrow{x}_{i+1} \in N_{\varepsilon}(\overrightarrow{x}_{i})\) : \(\overrightarrow{x}_{i+1}\) 는 \(\overrightarrow{x}_{i}\) 의 이웃 벡터임
• \(\overrightarrow{q} \in N_{\varepsilon}(\overrightarrow{x}_{n})\) : $\overrightarrow{q}$ 는 $\overrightarrow{x}_{n}$ 의 이웃 벡터임

Density-Connected

Core Point Condition 을 만족하는 관측치 벡터 \(\overrightarrow{p},\overrightarrow{q} \in D\) 에 대하여, \(\overrightarrow{p}\) 로부터 밀도 기준 도달 가능한(Density-Connected) 동시에 \(\overrightarrow{q}\) 로부터 밀도 기준 도달 가능한(Density-Connected) 관측치 벡터 \(\overrightarrow{x} \in D\) 가 적어도 하나 존재한다면, \(\overrightarrow{p},\overrightarrow{q}\) 는 밀도 기준 연결되어 있음(Density-Connected)

• $\vert N_{\varepsilon}(\overrightarrow{p})\vert \ge \text{MinPts}$
• $\overrightarrow{x} \in N_{\varepsilon}(\overrightarrow{p})$
• $\vert N_{\varepsilon}(\overrightarrow{q})\vert \ge \text{MinPts}$
• $\overrightarrow{x} \in N_{\varepsilon}(\overrightarrow{q})$

---

이미지 출처

• https://ai.plainenglish.io/dbscan-density-based-clustering-aaebd76e2c8c
• https://journals.sagepub.com/doi/10.1177/1748301817735665