DBSCAN¶

논문 정보¶

항목	내용
제목	A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise
저자	Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu
연도	1996
학회	KDD (International Conference on Knowledge Discovery and Data Mining)
링크	AAAI

핵심 아이디어¶

기존 클러스터링(K-Means, Hierarchical)의 한계: - 클러스터 수 K를 미리 지정해야 함 - 구형 클러스터만 잘 찾음 - 노이즈/이상치를 클러스터에 강제 할당

DBSCAN의 접근: - 밀도(density)가 높은 영역을 클러스터로 정의 - 밀도가 낮은 영역은 노이즈로 분류 - 클러스터 수를 자동으로 결정 - 임의의 형태의 클러스터 발견 가능

알고리즘¶

핵심 정의¶

ε (eps): 이웃 반경 (neighborhood radius)
MinPts: 핵심점이 되기 위한 최소 이웃 수
ε-이웃: 점 p로부터 거리 ε 이내의 모든 점 $$N_\epsilon(p) = \{q \in D : d(p, q) \leq \epsilon\}$$

점의 분류¶

유형	조건	설명
Core point	$\\|N_\epsilon(p)\\| \geq MinPts$	밀집 영역의 내부
Border point	Core point의 ε-이웃이지만, 자신은 Core가 아님	클러스터 경계
Noise point	어떤 Core point의 이웃도 아님	이상치

밀도 연결성 (Density Connectivity)¶

직접 밀도 도달 (Directly density-reachable): p가 Core이고 q ∈ N_ε(p)
밀도 도달 (Density-reachable): 직접 밀도 도달의 체인
밀도 연결 (Density-connected): 공통 점 o를 통해 밀도 도달 가능

클러스터 = 밀도 연결된 점들의 최대 집합

알고리즘 절차¶

입력: 데이터 D, ε, MinPts
출력: 클러스터 집합 C, 노이즈 집합 N

1. 모든 점을 UNVISITED로 표시
2. 각 점 p ∈ D에 대해:
   a. p가 VISITED면 건너뜀
   b. p를 VISITED로 표시
   c. N_ε(p) 계산
   d. |N_ε(p)| < MinPts면:
      - p를 NOISE로 표시
   e. 아니면 (p는 Core point):
      - 새 클러스터 C 생성
      - p를 C에 추가
      - Seeds = N_ε(p) - {p}
      - Seeds의 각 점 q에 대해:
        * q가 NOISE면 C에 추가
        * q가 UNVISITED면:
          - VISITED로 표시
          - N_ε(q) 계산
          - |N_ε(q)| ≥ MinPts면:
            Seeds에 N_ε(q) 추가
          - q가 어느 클러스터에도 없으면 C에 추가

시간 복잡도¶

구현	복잡도
기본	O(n²)
공간 인덱스 (KD-Tree, Ball-Tree)	O(n log n)

장단점¶

장점¶

장점	설명
K 불필요	클러스터 수 자동 결정
임의 형태	비구형 클러스터 발견
노이즈 처리	이상치 자동 식별
강건성	클러스터 순서/초기화 무관

단점¶

단점	설명
파라미터 민감	ε, MinPts 선택이 중요
가변 밀도	밀도가 다른 클러스터 어려움
고차원	차원의 저주로 거리 무의미해짐
메모리	거리 계산 시 O(n²) 가능

파라미터 선택¶

ε 선택: k-distance graph¶

from sklearn.neighbors import NearestNeighbors
import numpy as np
import matplotlib.pyplot as plt

# k-최근접 이웃 거리 계산
k = 4  # MinPts와 동일하게 설정
nn = NearestNeighbors(n_neighbors=k)
nn.fit(X)
distances, _ = nn.kneighbors(X)

# k번째 이웃까지의 거리를 정렬
k_distances = np.sort(distances[:, k-1])[::-1]

plt.figure(figsize=(10, 5))
plt.plot(k_distances)
plt.xlabel('Points sorted by distance')
plt.ylabel(f'{k}-th nearest neighbor distance')
plt.title('k-Distance Graph (Elbow Method for ε)')
plt.axhline(y=0.5, color='r', linestyle='--', label='Suggested ε')
plt.legend()
plt.show()

팁: 그래프의 "엘보우" 지점을 ε로 선택

MinPts 선택¶

경험적 규칙: MinPts ≥ dim + 1 (dim = 차원)
2D 데이터: MinPts = 4가 일반적
노이즈가 많으면: MinPts 증가
작은 클러스터를 찾으려면: MinPts 감소

언제 쓰는가¶

적합한 경우¶

클러스터 수를 모를 때
비정형 클러스터 (초승달, 동심원 등)
이상치 탐지가 필요할 때
밀도가 비교적 균일할 때
공간 데이터 (지리, 이미지)

부적합한 경우¶

밀도가 매우 다른 클러스터들
고차원 데이터 (> 20차원)
클러스터 간 밀도 차이가 클 때 → HDBSCAN 사용

Python 코드¶

import numpy as np
from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons, make_blobs
from sklearn.preprocessing import StandardScaler
import matplotlib.pyplot as plt

# 초승달 데이터 (K-Means로는 어려움)
X, y = make_moons(n_samples=300, noise=0.05, random_state=42)
X = StandardScaler().fit_transform(X)

# DBSCAN 적용
dbscan = DBSCAN(
    eps=0.3,              # 이웃 반경
    min_samples=5,        # MinPts
    metric='euclidean',   # 거리 척도
    algorithm='auto',     # 'ball_tree', 'kd_tree', 'brute'
    n_jobs=-1             # 병렬 처리
)
labels = dbscan.fit_predict(X)

# 결과 분석
n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_noise = list(labels).count(-1)

print(f"클러스터 수: {n_clusters}")
print(f"노이즈 포인트: {n_noise} ({n_noise/len(X)*100:.1f}%)")

# 시각화
plt.figure(figsize=(10, 6))
unique_labels = set(labels)
colors = plt.cm.viridis(np.linspace(0, 1, len(unique_labels)))

for k, col in zip(unique_labels, colors):
    if k == -1:
        col = 'red'  # 노이즈는 빨간색
        marker = 'x'
        label = 'Noise'
    else:
        marker = 'o'
        label = f'Cluster {k}'

    class_member_mask = (labels == k)
    xy = X[class_member_mask]
    plt.scatter(xy[:, 0], xy[:, 1], c=[col], marker=marker, s=50, label=label, alpha=0.6)

plt.title('DBSCAN Clustering (Moon Dataset)')
plt.legend()
plt.show()

K-Means와 비교¶

from sklearn.cluster import KMeans

fig, axes = plt.subplots(1, 3, figsize=(15, 4))

# 원본 데이터
axes[0].scatter(X[:, 0], X[:, 1], c=y, cmap='viridis', s=30)
axes[0].set_title('Ground Truth')

# K-Means
kmeans = KMeans(n_clusters=2, random_state=42)
kmeans_labels = kmeans.fit_predict(X)
axes[1].scatter(X[:, 0], X[:, 1], c=kmeans_labels, cmap='viridis', s=30)
axes[1].set_title('K-Means (Fails!)')

# DBSCAN
axes[2].scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', s=30)
axes[2].scatter(X[labels == -1, 0], X[labels == -1, 1], c='red', marker='x', s=50)
axes[2].set_title('DBSCAN (Success!)')

plt.tight_layout()
plt.show()

파라미터 그리드 탐색¶

from sklearn.metrics import silhouette_score

eps_values = [0.1, 0.2, 0.3, 0.4, 0.5]
min_samples_values = [3, 5, 7, 10]

results = []
for eps in eps_values:
    for min_samples in min_samples_values:
        db = DBSCAN(eps=eps, min_samples=min_samples)
        labels = db.fit_predict(X)

        n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
        n_noise = list(labels).count(-1)

        # 클러스터가 2개 이상이고 노이즈가 전체가 아닐 때만 실루엣 계산
        if n_clusters >= 2 and n_noise < len(X):
            score = silhouette_score(X[labels != -1], labels[labels != -1])
        else:
            score = -1

        results.append({
            'eps': eps,
            'min_samples': min_samples,
            'n_clusters': n_clusters,
            'n_noise': n_noise,
            'silhouette': score
        })

import pandas as pd
df = pd.DataFrame(results)
print(df.sort_values('silhouette', ascending=False).head(10))

참고 문헌¶

Ester, M., Kriegel, H. P., Sander, J., & Xu, X. (1996). A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. KDD-96 Proceedings, 226-231.
Schubert, E., Sander, J., Ester, M., Kriegel, H. P., & Xu, X. (2017). DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN. ACM Transactions on Database Systems, 42(3).

유형	조건	설명
Core point	\(\\|N_\epsilon(p)\\| \geq MinPts\)	밀집 영역의 내부
Border point	Core point의 ε-이웃이지만, 자신은 Core가 아님	클러스터 경계
Noise point	어떤 Core point의 이웃도 아님	이상치