📂머신러닝

DBSCAN: 밀도 기반 군집화

알고리즘 ¹

DBSCAN^{Density-Based Spatial Clustering of Applications with Noise}은 거리공간 $\left( X , d \right)$ 에서 점의 밀도에 기반하여 클러스터링을 수행하는 알고리즘이다. 두 개의 하이퍼파라미터인 반경^radius $\varepsilon > 0$ 와 밀도의 기준이 될 최소점수^{minimal number of points} $m$ 이 주어진다.

1. 유한집합 $D \subset X$ 를 데이터베이스^database라 한다.
2. $p \in D$ 에 대해 $N_{\varepsilon} \left( p \right) = \left\{ q \in X \mid d \left( p , q \right) \le \varepsilon \right\}$ 를 $p$ 의 이웃^neighborhood이라 한다.
3. $p \in D$ 가 $| N_{\varepsilon} \left( p \right) | \ge m$ 을 만족하면 $p$ 를 핵심점^{core point}이라 한다.
4. $p \in D$ 가 핵심점은 아니지만, $N_{\varepsilon} \left( p \right)$ 이 다른 핵심점을 포함하면 $p$ 를 경계점^{border point}이라 한다.
5. 핵심점 $q$ 에 대해 $p \in N_{\varepsilon} \left( q \right)$ 이면 $q$ 는 $p$ 에 직접 도달가능^{directly reachable}하다고 한다. $$ p = p_{1} , \cdots , p_{n} = q $$ 위와 같이 $p_{k}$ 가 $p_{k+1}$ 에 직접 도달가능하면서 $p = p_{1}$ 이고 $q = p_{n}$ 인 시퀀스가 존재하면 $p$ 는 $q$ 에 도달가능^reachable하다고 한다.
6. 두 $p , q \in D$ 에 도달가능한 핵심점 $o \in D$ 가 존재하면 $p$ 와 $q$ 는 연결^connected되었다고 한다.
7. 공집합이 아닌 $C \subseteq D$ 의 모든 $\forall p, q \in C$ 들이 다음 두 조건을 만족하면 클러스터^cluster라 한다.
   • (i) 최대성: 만약 $p$ 에서 $q$ 로 도달가능하면, $q \in C$ 이다.
   • (ii) 연결성: $p$ 와 $q$ 는 연결되었다.
8. 그 어떤 클러스터에도 속하지 못하는 점을 노이즈^noise라 한다.

설명 ²

도달가능성과 연결성의 차이는 핵심점에 한정되는지 아닌지가 다르다. 연결성은 대칭적인 관계인 것과 달리, 도달가능한 주체가 되려면 핵심점이라는 조건이 필요하기 때문에 $p$ 가 $q$ 에 도달가능할지라도 그 반대는 불가능할 수 있다.

인기

2025년 기준 클러스터링이라 하면 보통 DBSCAN이 종결 알고리즘이라고 할만큼 매우 준수한 성능을 보이며 오랫동안 널리 쓰여온 기법이다. $k$-평균 군집화가 단순함을 무기로 삼고 계층적 군집화가 직관성을 무기로 삼는다면 DBSCAN은 상대적으로 복잡한 데이터셋에서도 높은 일관성을 가지고 있다.

DBSCAN 이후로 군집화 알고리즘의 발전이 없었던 것은 아니지만, $k$-평균 군집화와 계층적 군집화가 그러하듯 자잘한 변형들이 시도되었을 뿐 굳건한 입지를 흔들 수는 없었다. 이렇게 세 알고리즘은 클러스터링계의 삼신기로 통하며, EM 알고리즘 등의 기법들은 교과서에서 조금씩 다루어지는 정도에 그친다.

특히나 인공지능의 시대가 열린 뒤로는 지도학습이 초강세를 보이며 클러스터링 기법의 혁신은 거의 멈춘 것으로 보인다. 반대로 말하면, 클러스터링 자체를 연구할 생각이 없다면 DBSCAN을 마지막으로 공부를 끝내도 된다는 뜻이기도 하다.