HDBSCAN¶

논문 정보¶

항목	내용
제목	Density-Based Clustering Based on Hierarchical Density Estimates
저자	Ricardo J. G. B. Campello, Davoud Moulavi, Jörg Sander
연도	2013
학회	PAKDD (Pacific-Asia Conference on Knowledge Discovery and Data Mining)
링크	Springer

핵심 아이디어¶

DBSCAN의 한계: - 단일 ε 값으로 전체 데이터를 처리 - 밀도가 다른 클러스터들을 함께 찾기 어려움 - ε가 너무 작으면 밀도 높은 클러스터만, 너무 크면 병합됨

HDBSCAN의 해결책: - 계층적 밀도 추정: 여러 ε 값에서 DBSCAN 실행한 것과 유사 - 클러스터 트리: 다양한 밀도 수준의 클러스터 계층 - 안정성 기반 추출: 가장 "지속성 있는" 클러스터 자동 선택 - 파라미터 최소화: ε 선택 불필요, min_cluster_size만 지정

알고리즘¶

핵심 개념¶

Core Distance $$\text{core}_k(x) = d(x, N_k(x))$$ 점 x에서 k번째 최근접 이웃까지의 거리

Mutual Reachability Distance $$d_{mreach-k}(a, b) = \max\{\text{core}_k(a), \text{core}_k(b), d(a, b)\}$$ 두 점이 모두 충분히 밀집된 영역에 있어야 가깝다고 판단

단계별 절차¶

입력: 데이터 X, min_cluster_size, min_samples (optional)
출력: 클러스터 라벨, 확률, 이상치 점수

1. Core Distance 계산
   - 각 점의 k-최근접 이웃 거리 계산 (k = min_samples)

2. Mutual Reachability Graph 구축
   - 모든 점 쌍의 mutual reachability distance 계산
   - 완전 그래프 또는 근사 그래프

3. Minimum Spanning Tree (MST) 구축
   - Prim's 또는 Borůvka 알고리즘

4. Cluster Hierarchy 구축
   - MST의 엣지를 거리 순으로 정렬
   - 엣지를 순차적으로 제거하며 계층 생성
   - min_cluster_size보다 작은 클러스터는 노이즈로 표시

5. Condensed Tree 생성
   - min_cluster_size 미만의 분기는 압축

6. 클러스터 추출 (Excess of Mass)
   - 각 클러스터의 "안정성(stability)" 계산
   - 가장 안정적인 클러스터들 선택

클러스터 안정성 (Stability)¶

\[\text{stability}(C) = \sum_{p \in C} (\lambda_p - \lambda_{birth})\]

$\lambda = 1/\epsilon$: 밀도 레벨
$\lambda_{birth}$: 클러스터가 생성된 밀도
$\lambda_p$: 점 p가 클러스터를 떠난 밀도

안정성이 높을수록 넓은 밀도 범위에서 지속되는 클러스터

시간 복잡도¶

단계	복잡도
Core distance	O(n log n) with KD-Tree
MST	O(n²) naive, O(n log n) with spatial index
전체	O(n log n) ~ O(n²)

장단점¶

장점¶

장점	설명
가변 밀도	다양한 밀도의 클러스터 동시 발견
파라미터 단순	ε 선택 불필요
소프트 클러스터링	확률, 이상치 점수 제공
노이즈 처리	자연스러운 이상치 탐지
이론적 배경	안정성 기반 추출

단점¶

단점	설명
계산 비용	DBSCAN보다 느림
메모리	계층 저장에 메모리 필요
고차원	여전히 차원의 저주 영향

DBSCAN vs HDBSCAN¶

항목	DBSCAN	HDBSCAN
파라미터	ε, MinPts	min_cluster_size
밀도 처리	단일 밀도	가변 밀도
클러스터 수	ε에 의존	자동 결정
출력	Hard labels	Soft (확률, 점수)
속도	빠름	느림
계층 정보	없음	Condensed tree

언제 쓰는가¶

적합한 경우¶

클러스터의 밀도가 다양할 때
클러스터 수를 모를 때
이상치 점수가 필요할 때
DBSCAN의 ε 튜닝이 어려울 때
클러스터 계층 구조를 탐색하고 싶을 때

부적합한 경우¶

실시간 처리 (DBSCAN이 더 빠름)
매우 대규모 데이터 (> 100만)
고차원 데이터 (> 50차원)
클러스터 수가 이미 정해진 경우

Python 코드¶

import numpy as np
import hdbscan  # pip install hdbscan
from sklearn.datasets import make_blobs, make_moons
import matplotlib.pyplot as plt

# 가변 밀도 데이터 생성
np.random.seed(42)
# 밀도가 다른 3개의 클러스터
blob1, _ = make_blobs(n_samples=500, centers=[[0, 0]], cluster_std=0.5)
blob2, _ = make_blobs(n_samples=100, centers=[[5, 5]], cluster_std=0.2)  # 밀집
blob3, _ = make_blobs(n_samples=300, centers=[[-5, 5]], cluster_std=1.5)  # 희소
X = np.vstack([blob1, blob2, blob3])

# HDBSCAN 적용
clusterer = hdbscan.HDBSCAN(
    min_cluster_size=15,      # 클러스터 최소 크기
    min_samples=5,            # core point 기준 (optional)
    cluster_selection_epsilon=0.0,  # 최소 거리 임계값
    metric='euclidean',
    cluster_selection_method='eom',  # 'eom' 또는 'leaf'
    prediction_data=True       # soft clustering을 위해
)
labels = clusterer.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}%)")

# 시각화
fig, axes = plt.subplots(1, 2, figsize=(14, 5))

# 클러스터링 결과
scatter = axes[0].scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', s=10)
axes[0].scatter(X[labels == -1, 0], X[labels == -1, 1], c='red', marker='x', s=30, label='Noise')
axes[0].set_title('HDBSCAN Clustering')
axes[0].legend()
plt.colorbar(scatter, ax=axes[0])

# 확률 (membership probability)
scatter2 = axes[1].scatter(X[:, 0], X[:, 1], c=clusterer.probabilities_, cmap='RdYlGn', s=10)
axes[1].set_title('Cluster Membership Probability')
plt.colorbar(scatter2, ax=axes[1])

plt.tight_layout()
plt.show()

Condensed Tree 시각화¶

# Condensed Tree
clusterer.condensed_tree_.plot(select_clusters=True, 
                               selection_palette=['blue', 'green', 'orange'])
plt.title('HDBSCAN Condensed Tree')
plt.show()

# Single Linkage Tree
clusterer.single_linkage_tree_.plot(cmap='viridis', colorbar=True)
plt.title('Single Linkage Tree')
plt.show()

이상치 점수 활용¶

# Outlier Score (높을수록 이상치일 가능성 높음)
outlier_scores = clusterer.outlier_scores_

plt.figure(figsize=(10, 5))
plt.scatter(X[:, 0], X[:, 1], c=outlier_scores, cmap='Reds', s=10)
plt.colorbar(label='Outlier Score')
plt.title('HDBSCAN Outlier Scores')
plt.show()

# Top 10 이상치
top_outliers = np.argsort(outlier_scores)[-10:]
print("Top 10 outlier indices:", top_outliers)

Soft Clustering (확률 기반)¶

# 새 데이터에 대한 예측
X_new = np.array([[2, 2], [-3, 3], [10, 10]])

# 근사 예측 (prediction_data=True 필요)
labels_new, strengths = hdbscan.approximate_predict(clusterer, X_new)

for i, (x, label, strength) in enumerate(zip(X_new, labels_new, strengths)):
    print(f"Point {i}: {x} -> Cluster {label}, Strength {strength:.3f}")

DBSCAN과 비교¶

from sklearn.cluster import DBSCAN

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

# Ground truth (가정)
axes[0].scatter(X[:, 0], X[:, 1], c='gray', s=10)
axes[0].set_title('Original Data')

# DBSCAN (단일 eps)
dbscan = DBSCAN(eps=0.5, min_samples=5)
db_labels = dbscan.fit_predict(X)
axes[1].scatter(X[:, 0], X[:, 1], c=db_labels, cmap='viridis', s=10)
axes[1].scatter(X[db_labels == -1, 0], X[db_labels == -1, 1], c='red', marker='x', s=30)
axes[1].set_title(f'DBSCAN (eps=0.5): {len(set(db_labels))-1} clusters')

# HDBSCAN
axes[2].scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', s=10)
axes[2].scatter(X[labels == -1, 0], X[labels == -1, 1], c='red', marker='x', s=30)
axes[2].set_title(f'HDBSCAN: {n_clusters} clusters')

plt.tight_layout()
plt.show()

참고 문헌¶

Campello, R. J. G. B., Moulavi, D., & Sander, J. (2013). Density-Based Clustering Based on Hierarchical Density Estimates. PAKDD 2013, 160-172.
Campello, R. J. G. B., Moulavi, D., Zimek, A., & Sander, J. (2015). Hierarchical Density Estimates for Data Clustering, Visualization, and Outlier Detection. ACM TKDD, 10(1).
McInnes, L., Healy, J., & Astels, S. (2017). hdbscan: Hierarchical density based clustering. JOSS, 2(11), 205.