Davies-Bouldin Index¶
논문 정보¶
| 항목 | 내용 |
|---|---|
| 제목 | A Cluster Separation Measure |
| 저자 | David L. Davies, Donald W. Bouldin |
| 연도 | 1979 |
| 학회 | IEEE Transactions on Pattern Analysis and Machine Intelligence |
| 링크 | IEEE |
핵심 아이디어¶
클러스터의 품질을 가장 비슷한 클러스터와의 비교로 측정: - 각 클러스터에 대해 "가장 헷갈리는" 다른 클러스터와의 유사도 계산 - 유사도 = (두 클러스터의 내부 분산 합) / (두 중심 간 거리)
낮을수록 좋음: 클러스터 내부는 밀집, 클러스터 간은 분리
수식¶
Davies-Bouldin Index¶
\[DB = \frac{1}{k} \sum_{i=1}^{k} \max_{j \neq i} R_{ij}\]
클러스터 유사도¶
\[R_{ij} = \frac{S_i + S_j}{d_{ij}}\]
- \(S_i\): 클러스터 \(i\)의 내부 분산 (scatter)
- \(d_{ij}\): 클러스터 \(i\)와 \(j\)의 중심 간 거리
내부 분산 (Scatter)¶
\[S_i = \frac{1}{n_i} \sum_{x \in C_i} \|x - \mu_i\|\]
또는 제곱 평균: $\(S_i = \sqrt{\frac{1}{n_i} \sum_{x \in C_i} \|x - \mu_i\|^2}\)$
해석¶
- 범위: [0, ∞)
- 0에 가까울수록 좋음: 클러스터가 작고 잘 분리됨
- 최적 K: DB 값이 최소인 K 선택
시간 복잡도¶
- \(O(nk + k^2)\)
장단점¶
장점¶
| 장점 | 설명 |
|---|---|
| 빠른 계산 | O(nk + k²) |
| 레이블 불필요 | 내부 평가 지표 |
| 직관적 | "가장 비슷한 클러스터" 개념 |
| 범위 해석 | 0에 가까울수록 좋음 |
단점¶
| 단점 | 설명 |
|---|---|
| 볼록 클러스터 편향 | 구형 클러스터에 유리 |
| 중심 기반 | 비중심 클러스터 부적합 |
| K에 민감 | K가 커지면 대체로 감소 |
다른 지표와 비교¶
| 지표 | 범위 | 최적 | 계산 | 특징 |
|---|---|---|---|---|
| Silhouette | [-1, 1] | 1 | O(n²) | 개별 점 분석 가능 |
| Calinski-Harabasz | [0, ∞) | 높음 | O(nk) | 분산 비율 |
| Davies-Bouldin | [0, ∞) | 0 | O(nk+k²) | 최악 쌍 기반 |
언제 쓰는가¶
적합한 경우¶
- 빠른 평가가 필요할 때
- 볼록/구형 클러스터
- K-Means, GMM 결과 평가
- 여러 클러스터링 결과 비교
부적합한 경우¶
- 비볼록 클러스터
- DBSCAN 결과 (노이즈 포인트 처리 문제)
- 개별 점 분석이 필요한 경우
Python 코드¶
import numpy as np
from sklearn.cluster import KMeans
from sklearn.metrics import davies_bouldin_score
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
# 데이터 생성
X, y_true = make_blobs(n_samples=500, centers=4, cluster_std=0.6, random_state=42)
# 다양한 K에 대해 DB Index 계산
K_range = range(2, 10)
db_scores = []
for k in K_range:
kmeans = KMeans(n_clusters=k, random_state=42)
labels = kmeans.fit_predict(X)
score = davies_bouldin_score(X, labels)
db_scores.append(score)
# 시각화
plt.figure(figsize=(10, 5))
plt.plot(K_range, db_scores, 'ro-', linewidth=2)
plt.axvline(x=K_range[np.argmin(db_scores)], color='g', linestyle='--',
label=f'Optimal K = {K_range[np.argmin(db_scores)]}')
plt.xlabel('Number of Clusters (K)')
plt.ylabel('Davies-Bouldin Index')
plt.title('Davies-Bouldin Index for Optimal K (Lower is Better)')
plt.legend()
plt.show()
print(f"Optimal K: {K_range[np.argmin(db_scores)]}")
print(f"Best DB Score: {min(db_scores):.4f}")
수동 계산¶
def davies_bouldin_manual(X, labels):
"""DB Index 수동 계산"""
n_clusters = len(np.unique(labels))
# 각 클러스터의 중심과 내부 분산 계산
centroids = []
scatters = []
for k in range(n_clusters):
cluster_points = X[labels == k]
centroid = cluster_points.mean(axis=0)
centroids.append(centroid)
# 내부 분산 (평균 거리)
scatter = np.mean(np.linalg.norm(cluster_points - centroid, axis=1))
scatters.append(scatter)
centroids = np.array(centroids)
scatters = np.array(scatters)
# R_ij 계산
R = np.zeros((n_clusters, n_clusters))
for i in range(n_clusters):
for j in range(n_clusters):
if i != j:
d_ij = np.linalg.norm(centroids[i] - centroids[j])
R[i, j] = (scatters[i] + scatters[j]) / d_ij
# DB Index = 각 클러스터의 max R_ij 평균
db_index = np.mean([np.max(R[i, :]) for i in range(n_clusters)])
return db_index, R, scatters, centroids
# 검증
kmeans = KMeans(n_clusters=4, random_state=42)
labels = kmeans.fit_predict(X)
db_sklearn = davies_bouldin_score(X, labels)
db_manual, R_matrix, scatters, centroids = davies_bouldin_manual(X, labels)
print(f"sklearn DB: {db_sklearn:.4f}")
print(f"Manual DB: {db_manual:.4f}")
print(f"\nScatters (내부 분산): {scatters}")
print(f"\nR matrix (클러스터 유사도):")
print(R_matrix)
클러스터 쌍 유사도 시각화¶
def visualize_db_components(X, labels, R_matrix, centroids):
"""DB 구성 요소 시각화"""
n_clusters = len(centroids)
fig, axes = plt.subplots(1, 2, figsize=(14, 5))
# 클러스터 시각화
for k in range(n_clusters):
cluster_points = X[labels == k]
axes[0].scatter(cluster_points[:, 0], cluster_points[:, 1], s=20, alpha=0.5, label=f'Cluster {k}')
axes[0].scatter(centroids[:, 0], centroids[:, 1], c='red', marker='X', s=200, edgecolors='black')
# 가장 유사한 클러스터 쌍 연결
for i in range(n_clusters):
j = np.argmax(R_matrix[i])
axes[0].plot([centroids[i, 0], centroids[j, 0]],
[centroids[i, 1], centroids[j, 1]],
'r--', alpha=0.5, linewidth=2)
axes[0].set_title('Clusters with Most Similar Pairs (red lines)')
axes[0].legend()
# R 행렬 히트맵
im = axes[1].imshow(R_matrix, cmap='Reds')
axes[1].set_title('R_ij Matrix (Cluster Similarity)')
axes[1].set_xlabel('Cluster j')
axes[1].set_ylabel('Cluster i')
plt.colorbar(im, ax=axes[1])
# 값 표시
for i in range(n_clusters):
for j in range(n_clusters):
if i != j:
axes[1].text(j, i, f'{R_matrix[i,j]:.2f}', ha='center', va='center')
plt.tight_layout()
plt.show()
visualize_db_components(X, labels, R_matrix, centroids)
세 지표 종합 비교¶
from sklearn.metrics import silhouette_score, calinski_harabasz_score, davies_bouldin_score
K_range = range(2, 10)
results = []
for k in K_range:
kmeans = KMeans(n_clusters=k, random_state=42)
labels = kmeans.fit_predict(X)
results.append({
'K': k,
'Silhouette': silhouette_score(X, labels),
'Calinski-Harabasz': calinski_harabasz_score(X, labels),
'Davies-Bouldin': davies_bouldin_score(X, labels)
})
import pandas as pd
df = pd.DataFrame(results)
fig, axes = plt.subplots(1, 3, figsize=(15, 4))
# Silhouette (높을수록 좋음)
axes[0].plot(df['K'], df['Silhouette'], 'bo-')
axes[0].axvline(x=df.loc[df['Silhouette'].idxmax(), 'K'], color='r', linestyle='--')
axes[0].set_xlabel('K')
axes[0].set_ylabel('Score')
axes[0].set_title(f"Silhouette (Best K={df.loc[df['Silhouette'].idxmax(), 'K']})")
# Calinski-Harabasz (높을수록 좋음)
axes[1].plot(df['K'], df['Calinski-Harabasz'], 'go-')
axes[1].axvline(x=df.loc[df['Calinski-Harabasz'].idxmax(), 'K'], color='r', linestyle='--')
axes[1].set_xlabel('K')
axes[1].set_ylabel('Score')
axes[1].set_title(f"Calinski-Harabasz (Best K={df.loc[df['Calinski-Harabasz'].idxmax(), 'K']})")
# Davies-Bouldin (낮을수록 좋음)
axes[2].plot(df['K'], df['Davies-Bouldin'], 'ro-')
axes[2].axvline(x=df.loc[df['Davies-Bouldin'].idxmin(), 'K'], color='g', linestyle='--')
axes[2].set_xlabel('K')
axes[2].set_ylabel('Score')
axes[2].set_title(f"Davies-Bouldin (Best K={df.loc[df['Davies-Bouldin'].idxmin(), 'K']})")
plt.tight_layout()
plt.show()
print(df.to_string(index=False))
관련 기법¶
- Silhouette Score - 개별 점 기반
- Calinski-Harabasz Index - 분산 비율
- Dunn Index - 최소 분리 / 최대 직경
참고 문헌¶
- Davies, D. L., & Bouldin, D. W. (1979). A Cluster Separation Measure. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-1(2), 224-227.
- Halkidi, M., Batistakis, Y., & Vazirgiannis, M. (2001). On Clustering Validation Techniques. Journal of Intelligent Information Systems, 17(2-3), 107-145.