DBSCAN (Density-Based Spatial Clustering of Applications with Noise)¶
논문 정보¶
| 항목 | 내용 |
|---|---|
| 제목 | A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise |
| 저자 | Martin Ester, Hans-Peter Kriegel, Jorg Sander, Xiaowei Xu |
| 학회/저널 | KDD |
| 연도 | 1996 |
| 링크 | https://www.aaai.org/Papers/KDD/1996/KDD96-037.pdf |
개요¶
문제 정의¶
기존 클러스터링 (k-means 등)의 한계:
- 클러스터 수를 미리 지정해야 함
- 구형 클러스터만 탐지
- 이상치(노이즈)에 민감
- 밀도가 다른 클러스터 탐지 어려움
핵심 아이디어¶
밀도 기반 클러스터 정의:
- 밀도가 높은 영역 = 클러스터
- 밀도가 낮은 영역 = 노이즈/경계
- 임의의 형태 클러스터 탐지 가능
핵심 개념:
eps (epsilon): 이웃 탐색 반경
min_samples: 코어 포인트가 되기 위한 최소 이웃 수
Core Point: eps 반경 내에 min_samples 이상의 포인트
Border Point: 코어 포인트의 이웃이지만 자신은 코어가 아님
Noise Point: 코어도 아니고 코어의 이웃도 아님
알고리즘/수식¶
정의¶
eps-이웃 (eps-neighborhood):
밀도 직접 도달 가능 (Directly Density-Reachable):
q가 p로부터 직접 도달 가능: 1. q in N_eps(p) 2. |N_eps(p)| >= min_samples (p는 코어 포인트)
밀도 도달 가능 (Density-Reachable):
p에서 q로 밀도 도달 가능: p_1, p_2, ..., p_n 체인 존재 - p_1 = p, p_n = q - p_{i+1}이 p_i로부터 직접 도달 가능
밀도 연결 (Density-Connected):
p와 q가 밀도 연결: 어떤 o에서 p와 q 모두 밀도 도달 가능
클러스터 정의:
밀도 연결된 포인트들의 최대 집합
알고리즘¶
Algorithm: DBSCAN
Input: 데이터셋 D, eps, min_samples
Output: 클러스터 할당
1. 모든 포인트를 "unvisited"로 표시
2. for each unvisited point p:
mark p as visited
# eps-이웃 계산
N = get_neighbors(p, eps)
if |N| < min_samples:
mark p as NOISE (일단 노이즈로, 나중에 변경 가능)
else:
# 새 클러스터 시작
C = new cluster
expand_cluster(p, N, C, eps, min_samples)
3. return cluster assignments
function expand_cluster(p, N, C, eps, min_samples):
add p to C
for each point q in N:
if q is unvisited:
mark q as visited
N' = get_neighbors(q, eps)
if |N'| >= min_samples:
N = N union N' # 이웃 확장
if q is not yet member of any cluster:
add q to C
시간 복잡도¶
| 구현 | 복잡도 |
|---|---|
| 기본 (brute-force) | O(n^2) |
| 공간 인덱스 (KD-tree, Ball-tree) | O(n * log(n)) 평균 |
하이퍼파라미터 가이드¶
| 파라미터 | 설명 | 권장 값 |
|---|---|---|
| eps | 이웃 탐색 반경 | k-distance plot으로 결정 |
| min_samples | 코어 포인트 최소 이웃 | 2*d 이상 (d=차원) |
| metric | 거리 측정 | 'euclidean', 'manhattan', 'cosine' |
| algorithm | 이웃 탐색 알고리즘 | 'auto', 'ball_tree', 'kd_tree', 'brute' |
| leaf_size | 트리 리프 크기 | 30 |
eps 선택: k-distance plot¶
min_samples 선택¶
Python 코드 예시¶
기본 사용법¶
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons, make_blobs
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score
# 비구형 데이터 생성
X_moons, y_moons = make_moons(n_samples=500, noise=0.1, random_state=42)
# 스케일링
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X_moons)
# DBSCAN 적용
dbscan = DBSCAN(eps=0.3, min_samples=5)
labels = dbscan.fit_predict(X_scaled)
# 결과 분석
n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_noise = list(labels).count(-1)
print("=== DBSCAN Results ===")
print(f"Number of clusters: {n_clusters}")
print(f"Number of noise points: {n_noise} ({100*n_noise/len(labels):.1f}%)")
# 코어 샘플 수
core_samples_mask = np.zeros_like(labels, dtype=bool)
core_samples_mask[dbscan.core_sample_indices_] = True
print(f"Number of core samples: {sum(core_samples_mask)}")
# 시각화
plt.figure(figsize=(12, 5))
plt.subplot(1, 2, 1)
plt.scatter(X_scaled[:, 0], X_scaled[:, 1], c=y_moons, cmap='viridis', alpha=0.6)
plt.title('True Labels')
plt.subplot(1, 2, 2)
unique_labels = set(labels)
colors = plt.cm.Spectral(np.linspace(0, 1, len(unique_labels)))
for k, col in zip(unique_labels, colors):
if k == -1:
col = 'black' # 노이즈는 검정색
class_mask = (labels == k)
core_mask = core_samples_mask & class_mask
border_mask = ~core_samples_mask & class_mask
# 코어 포인트
plt.scatter(X_scaled[core_mask, 0], X_scaled[core_mask, 1],
c=[col], marker='o', s=50, alpha=0.8)
# 보더 포인트
plt.scatter(X_scaled[border_mask, 0], X_scaled[border_mask, 1],
c=[col], marker='o', s=20, alpha=0.4)
plt.title('DBSCAN Clustering')
plt.tight_layout()
plt.savefig('dbscan_result.png', dpi=150)
plt.show()
eps 선택: k-distance plot¶
from sklearn.neighbors import NearestNeighbors
# k-distance 계산
k = 5 # min_samples와 동일하게
neighbors = NearestNeighbors(n_neighbors=k)
neighbors.fit(X_scaled)
distances, indices = neighbors.kneighbors(X_scaled)
# k번째 이웃까지 거리 정렬
k_distances = np.sort(distances[:, k-1])
# 플롯
plt.figure(figsize=(10, 6))
plt.plot(range(len(k_distances)), k_distances)
plt.xlabel('Points (sorted)')
plt.ylabel(f'{k}-th Nearest Neighbor Distance')
plt.title('k-Distance Plot for eps Selection')
plt.axhline(y=0.3, color='r', linestyle='--', label='eps=0.3')
plt.legend()
plt.savefig('k_distance_plot.png', dpi=150)
plt.show()
# 엘보우 자동 탐지 (간단한 방법)
from kneed import KneeLocator
kneedle = KneeLocator(range(len(k_distances)), k_distances, curve='convex', direction='increasing')
eps_optimal = k_distances[kneedle.knee] if kneedle.knee else 0.3
print(f"Suggested eps: {eps_optimal:.4f}")
여러 파라미터 탐색¶
# eps와 min_samples 그리드 탐색
eps_values = np.arange(0.1, 1.0, 0.1)
min_samples_values = [3, 5, 7, 10]
results = []
for eps in eps_values:
for min_samples in min_samples_values:
dbscan = DBSCAN(eps=eps, min_samples=min_samples)
labels = dbscan.fit_predict(X_scaled)
n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_noise = list(labels).count(-1)
# 노이즈 제외하고 실루엣 점수 계산
if n_clusters > 1 and n_noise < len(labels) - 1:
mask = labels != -1
if len(set(labels[mask])) > 1:
score = silhouette_score(X_scaled[mask], labels[mask])
else:
score = -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
results_df = pd.DataFrame(results)
print("\nParameter Search Results:")
print(results_df.sort_values('silhouette', ascending=False).head(10).to_string(index=False))
HDBSCAN (계층적 DBSCAN)¶
# HDBSCAN: eps 자동 선택
# pip install hdbscan
import hdbscan
clusterer = hdbscan.HDBSCAN(
min_cluster_size=10,
min_samples=5,
metric='euclidean',
cluster_selection_epsilon=0.0
)
labels_hdb = clusterer.fit_predict(X_scaled)
n_clusters_hdb = len(set(labels_hdb)) - (1 if -1 in labels_hdb else 0)
n_noise_hdb = list(labels_hdb).count(-1)
print(f"\nHDBSCAN Results:")
print(f"Number of clusters: {n_clusters_hdb}")
print(f"Number of noise: {n_noise_hdb}")
# 클러스터 확률
print(f"Probability range: {clusterer.probabilities_.min():.2f} - {clusterer.probabilities_.max():.2f}")
DBSCAN vs K-means 비교¶
from sklearn.cluster import KMeans
fig, axes = plt.subplots(1, 3, figsize=(15, 5))
# 원본 데이터
axes[0].scatter(X_scaled[:, 0], X_scaled[:, 1], alpha=0.6)
axes[0].set_title('Original Data')
# K-means (k=2)
kmeans = KMeans(n_clusters=2, random_state=42)
labels_km = kmeans.fit_predict(X_scaled)
axes[1].scatter(X_scaled[:, 0], X_scaled[:, 1], c=labels_km, cmap='viridis', alpha=0.6)
axes[1].set_title('K-means (k=2)')
# DBSCAN
dbscan = DBSCAN(eps=0.3, min_samples=5)
labels_db = dbscan.fit_predict(X_scaled)
axes[2].scatter(X_scaled[:, 0], X_scaled[:, 1], c=labels_db, cmap='viridis', alpha=0.6)
axes[2].set_title('DBSCAN')
plt.tight_layout()
plt.savefig('dbscan_vs_kmeans.png', dpi=150)
plt.show()
언제 쓰나?¶
적합한 상황: - 클러스터 수를 모를 때 - 비구형/불규칙한 모양의 클러스터 - 이상치/노이즈가 있는 데이터 - 공간 데이터 (GPS, 지리) - 밀도가 유사한 클러스터들
부적합한 상황: - 클러스터 간 밀도가 크게 다를 때 (HDBSCAN 고려) - 고차원 데이터 (차원의 저주) - 매우 큰 데이터셋 (확장성) - 전역적으로 밀도가 균일하지 않을 때
장단점¶
| 장점 | 단점 |
|---|---|
| 클러스터 수 자동 결정 | eps, min_samples 민감 |
| 임의 형태 클러스터 탐지 | 밀도가 다른 클러스터 어려움 |
| 이상치 자동 탐지 | 고차원에서 성능 저하 |
| 특정 형태 가정 없음 | 파라미터 선택 어려움 |
| 결정적 알고리즘 (초기화 불변) | 메모리 사용량 높음 (거리 계산) |
관련 논문/참고¶
- Ester, M., et al. (1996). "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise". KDD.
- Campello, R.J.G.B., et al. (2013). "Density-Based Clustering Based on Hierarchical Density Estimates". PAKDD (HDBSCAN).
- scikit-learn documentation: https://scikit-learn.org/stable/modules/clustering.html#dbscan