DBSCAN

DBSCAN; Density-Based Spatial Clustering of Applications with Noise; 밀도 기반 군집화
점이 빽빽하게 모인 영역을 하나의 군집으로 보고, 밀도가 낮은 곳의 점은 잡음으로 분리하는 군집화 알고리즘

Ester, Kriegel, Sander, Xu가 1996년 KDD 학회에서 발표했다. 군집 수를 미리 정하지 않아도 되고, 원형이 아닌 임의 모양의 군집도 찾는다.

매개변수

eps(ε) : 이웃으로 볼 반경. 한 점에서 거리 eps 이내의 영역을 그 점의 ε-이웃이라 한다
MinPts : 핵심점이 되기 위해 ε-이웃 안에 있어야 하는 최소 점 수. 원 논문과 scikit-learn(min_samples) 모두 자기 자신을 포함해 센다

점의 종류

종류	조건	역할
핵심점(Core Point)	ε-이웃 안의 점 수 ≥ MinPts	군집을 만들고 확장한다
경계점(Border Point)	핵심점은 아니지만 어떤 핵심점의 ε-이웃 안에 있음	군집에 속하지만 군집을 더 넓히지는 않는다
잡음점(Noise Point)	핵심점도 경계점도 아님	어느 군집에도 속하지 않는다(이상치 후보)

동작 과정

방문하지 않은 점 하나를 고르고 ε-이웃을 구한다
이웃 수가 MinPts 미만이면 일단 잡음으로 표시한다(나중에 다른 핵심점의 이웃이면 경계점이 된다)
핵심점이면 새 군집을 만들고, 이웃 중 핵심점을 따라 연쇄적으로 도달 가능한 점을 모두 같은 군집에 넣는다
모든 점을 방문할 때까지 반복한다

핵심점 p의 ε-이웃에 있는 점 q는 p에서 직접 밀도 도달 가능(directly density-reachable)하다. 이런 연결을 이어 가면 밀도 도달 가능, 두 점이 같은 점에서 밀도 도달 가능하면 밀도 연결(density-connected)이라 하며, 하나의 군집은 서로 밀도 연결된 점들의 최대 집합이다.

매개변수 정하는 요령

MinPts는 데이터 차원 수 + 1 이상으로 잡고, 흔히 차원 수의 2배 정도를 쓴다. 잡음이 많을수록 크게 한다
eps는 각 점에서 k번째 가까운 이웃까지의 거리(k ≈ MinPts)를 정렬해 그린 k-거리 그래프에서 곡선이 급히 꺾이는 지점으로 정한다
거리 기반이므로 변수 척도를 먼저 맞춘다(변수 변환 참고)

장단점

장점	단점
군집 수 K를 미리 정할 필요가 없다	eps·MinPts 값에 결과가 민감하다
초승달·고리 등 임의 모양 군집을 찾는다	밀도가 서로 크게 다른 군집이 섞여 있으면 한 쌍의 eps·MinPts로 잘 나누지 못한다
잡음점을 따로 분리해 이상치 탐지에도 쓴다	고차원에서는 거리의 의미가 약해져 성능이 떨어진다
결과가 초기값에 좌우되지 않는다(경계점 소속만 처리 순서에 따라 달라질 수 있음)	공간 색인이 없으면 계산량이 O(n²)이다

K-평균과 비교

구분	K-평균	DBSCAN
기준	중심점까지의 거리	점의 밀도
군집 수	미리 K를 지정	자동으로 결정
군집 모양	볼록한 구형에 적합	임의 모양 가능
잡음·이상치	모든 점을 어느 군집에 배정, 이상치에 민감	잡음점으로 분리
초기값 영향	초기 중심에 따라 결과가 달라짐	거의 없음
주요 매개변수	K	eps, MinPts

scikit-learn 예제

import numpy as np
from sklearn.datasets import make_moons
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import DBSCAN, KMeans

X, _ = make_moons(n_samples=300, noise=0.05, random_state=42)
X = StandardScaler().fit_transform(X)

db = DBSCAN(eps=0.3, min_samples=5).fit(X)
labels = db.labels_                     # 잡음점은 -1
n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
print("군집 수:", n_clusters, "잡음 수:", np.sum(labels == -1))
print("핵심점 수:", len(db.core_sample_indices_))

km = KMeans(n_clusters=2, n_init=10, random_state=42).fit(X)  # 초승달을 직선으로 가른다

기본값은 eps=0.5, min_samples=5, 유클리드 거리다.

시험 포인트

핵심점·경계점·잡음점의 정의와 eps·MinPts의 역할
K-평균과의 차이(군집 수 사전 지정 불필요, 임의 모양, 잡음 분리)
실기에서 labels_의 -1이 잡음이라는 점, 척도 표준화 후 적용

같이 보기

참고 문헌