DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

DBSCAN(노이즈가 있는 응용 분야의 밀도 기반 공간 군집화)은 서로 가까이 밀집한 점들을 클러스터로 묶고 성긴 영역의 점들을 노이즈로 분류하는 비지도 학습 알고리즘입니다. Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu가 1996년 KDD 학회에서 이 알고리즘을 소개했습니다. 클러스터 수를 미리 지정할 필요가 없고 고리, 초승달, 구불구불한 도로와 같은 임의 형태의 클러스터를 찾아내며, 노이즈 레이블은 간단한 이상 탐지 기능도 합니다. 알고리즘 전체는 두 가지 매개변수로 제어합니다. 이웃 반경과 이웃을 밀집한 것으로 간주하는 데 필요한 점의 개수입니다.

핵심점, 경계점, 노이즈#

DBSCAN은 모든 점의 이웃을 살펴봅니다. 즉, 거리 eps 이내에 있는 점들의 집합을 확인하고 그 구성원 수를 셉니다.

• 핵심점: 이웃에 min_samples개 이상의 점이 있습니다. scikit-learn 구현에서는 해당 점 자신도 개수에 포함합니다. 핵심점은 클러스터의 밀집된 내부를 형성합니다.
• 경계점: 핵심점이 되기에는 이웃이 부족하지만 핵심점 하나에서 eps 이내에 있습니다. 경계점은 클러스터의 가장자리를 형성합니다.
• 노이즈 점: 핵심점도 경계점도 아니므로 어떤 클러스터에도 속하지 않으며 레이블 -1을 받습니다.

방문하지 않은 핵심점에서 클러스터가 확장됩니다. DBSCAN은 해당 점의 이웃에 있는 모든 점을 추가한 다음, 새로 추가한 각 핵심점을 기준으로 더 이상 도달할 수 있는 점이 없을 때까지 반복합니다. 따라서 밀집된 이웃들이 겹쳐 이어지는 사슬은 어떤 형태로 구부러지든 하나의 클러스터가 됩니다. 경계점은 클러스터에 포함되지만 클러스터를 확장하지는 않습니다. 입력 순서가 주어지면 결과는 결정적이지만, 두 클러스터에 모두 도달할 수 있는 경계점은 먼저 도달한 클러스터에 포함되므로 데이터를 섞으면 경계점이 다른 클러스터로 이동할 수 있습니다.

eps와 min_samples 선택하기#

반경 eps이 가장 중요하며 데이터의 스케일에 따라 달라집니다. 따라서 보통 특징을 먼저 표준화합니다. 반경이 너무 작으면 대부분의 점이 노이즈로 남고, 너무 크면 인접한 클러스터가 하나로 합쳐집니다. 일반적인 휴리스틱에서는 각 점과 k번째 최근접 이웃 사이의 거리를 정렬합니다. k는 min_samples으로 설정하고, 거리가 급격히 증가하기 시작하는 곡선의 무릎 지점에서 eps를 선택합니다. min_samples 값을 크게 설정하면 클러스터링이 노이즈에 더 관대해지므로 대규모 또는 노이즈가 많은 데이터셋에서 흔히 사용합니다. 이미지 임베딩과 같은 고차원 공간에서는 점 사이의 거리가 서로 비슷해집니다. 따라서 실무에서는 DBSCAN을 실행하기 전에 차원 축소, 예를 들어 주성분 분석(PCA)을 적용하는 경우가 많습니다.

DBSCAN과 K-평균 및 HDBSCAN 비교#

K-평균 군집화는 클러스터 수를 미리 지정해야 하고 모든 점을 가장 가까운 중심점에 할당하므로, 작고 둥근 클러스터에 유리하며 이상치를 어떤 그룹에든 포함시킵니다. DBSCAN은 밀도를 기준으로 클러스터 수를 찾아내고 이상치는 제외합니다. DBSCAN의 약점은 전역 eps 값 하나만 사용한다는 점입니다. 클러스터의 밀도가 크게 다르면 희소 클러스터와 노이즈, 밀집 클러스터를 구분할 단일 반경을 정하기 어렵습니다. HDBSCAN은 모든 eps 값에 대해 DBSCAN을 사실상 실행한 뒤 가장 안정적인 클러스터를 유지해 이 문제를 해결합니다. 두 알고리즘과 관련 알고리즘 OPTICS는 scikit-learn 군집화 모듈에 포함되어 있습니다.

이 예제는 서로 맞물린 두 개의 초승달 모양에 무작위 이상치 20개를 추가해 군집화하고, 조정 랜드 지수를 사용해 각 결과를 실제 그룹과 비교합니다. 조정 랜드 지수에서 1.0은 완벽한 일치를 의미합니다.

import numpy as np
from sklearn.cluster import DBSCAN, KMeans
from sklearn.datasets import make_moons
from sklearn.metrics import adjusted_rand_score

# Two interleaving crescents plus 20 scattered outliers (true label -1)
X, y = make_moons(n_samples=300, noise=0.05, random_state=0)
rng = np.random.default_rng(0)
X = np.vstack([X, rng.uniform(-1.5, 2.5, size=(20, 2))])
y = np.concatenate([y, np.full(20, -1)])

# DBSCAN infers clusters from density; k-means is told there are 2
db_labels = DBSCAN(eps=0.2, min_samples=5).fit_predict(X)
km_labels = KMeans(n_clusters=2, random_state=0).fit_predict(X)

print(f"DBSCAN: {db_labels.max() + 1} clusters, {(db_labels == -1).sum()} noise points")
print(f"ARI: DBSCAN {adjusted_rand_score(y, db_labels):.2f}, k-means {adjusted_rand_score(y, km_labels):.2f}")

스크립트는 DBSCAN에서 클러스터 2개와 노이즈 점 15개를 출력하고, 조정 랜드 지수는 DBSCAN에서 0.97, K-평균에서 0.20을 출력합니다. DBSCAN은 두 초승달 모양을 따라 클러스터를 만들고 멀리 떨어진 이상치를 제외하지만, K-평균은 올바른 클러스터 수를 지정받았음에도 초승달 모양을 직선 경계로 가로질러 나눕니다.

실제 적용 사례#

• LiDAR 인지: 자율주행 차량 및 로보틱스 파이프라인은 LiDAR 스캔에서 지면 점을 제거한 다음 남은 3D 점을 클러스터링해 개별 장애물로 구분합니다. 객체 수를 알 수 없으므로 밀도 기반 클러스터링을 흔히 사용합니다.
• 탐지 후처리: result.boxes.xywh로 가져올 수 있는 YOLO26 탐지 박스의 중심점을 DBSCAN으로 군집화하면 군중 속 사람들의 무리나 생산 라인에서 반복되는 결함 위치를 찾을 수 있으며, 고립된 탐지는 노이즈로 제외됩니다.
• 사기 및 센서 모니터링: -1로 표시된 트랜잭션이나 측정값은 정상 동작의 모든 밀집 그룹에서 멀리 떨어져 있어 검토 대상이 됩니다.
• 공간정보 분석: 배송 및 차량 호출 서비스 회사는 GPS 지점을 클러스터링하여 자주 정차하는 장소와 승차 핫스팟을 찾습니다. Scikit-learn의 DBSCAN은 위도와 경도를 라디안으로 나타낸 경우 metric="haversine"을 입력으로 받으며, 이때 eps은 단위 구면의 각도이므로 지구 평균 반지름 6,371km를 사용하면 100미터 반경은 eps = 0.1 / 6371가 됩니다.