Calinski-Harabasz Index (분산 비율 기준)

논문 정보

항목	내용
제목	A Dendrite Method for Cluster Analysis
저자	Tadeusz Calinski, Jerzy Harabasz
연도	1974
학회	Communications in Statistics - Theory and Methods
링크	Taylor & Francis

핵심 아이디어

클러스터링의 품질을 분산 비율로 측정: - Between-cluster variance (SSB): 클러스터 중심들 간의 분산 (높을수록 좋음) - Within-cluster variance (SSW): 클러스터 내부 분산 (낮을수록 좋음)

Variance Ratio Criterion (VRC)이라고도 불린다.

좋은 클러스터링 = 클러스터 간 분산 최대화 + 클러스터 내 분산 최소화

수식

Calinski-Harabasz Index

\[CH = \frac{SS_B / (k - 1)}{SS_W / (n - k)} = \frac{SS_B}{SS_W} \times \frac{n - k}{k - 1}\]

• \(n\): 총 데이터 포인트 수
• \(k\): 클러스터 수
• \(SS_B\): Between-cluster sum of squares (클러스터 간)
• \(SS_W\): Within-cluster sum of squares (클러스터 내)

Between-cluster Sum of Squares

\[SS_B = \sum_{i=1}^{k} n_i \|\mu_i - \mu\|^2\]

• \(n_i\): 클러스터 \(i\)의 포인트 수
• \(\mu_i\): 클러스터 \(i\)의 중심
• \(\mu\): 전체 데이터의 중심

Within-cluster Sum of Squares

\[SS_W = \sum_{i=1}^{k} \sum_{x \in C_i} \|x - \mu_i\|^2\]

해석

• 범위: [0, ∞)
• 높을수록 좋음: 클러스터가 밀집되고 잘 분리됨
• 최적 K: CH 값이 최대인 K 선택

시간 복잡도

• \(O(nk)\): 실루엣 (\(O(n^2)\))보다 빠름

장단점

장점

장점	설명
빠른 계산	O(nk), 대규모 데이터에 적합
레이블 불필요	내부 평가 지표
직관적	분산 비율로 해석 쉬움
ANOVA와 유사	통계적 기반

단점

단점	설명
볼록 클러스터 편향	구형/컴팩트 클러스터에 유리
밀도 무시	다양한 밀도의 클러스터 비교 어려움
노이즈 민감	이상치에 영향받음
상한 없음	절대적 기준 없음

언제 쓰는가

적합한 경우

• 최적 K 선택 (빠르게)
• 대규모 데이터 (실루엣보다 효율적)
• 볼록/구형 클러스터
• K-Means, GMM 평가

부적합한 경우

• 비볼록 클러스터
• 밀도가 다양한 클러스터
• DBSCAN 결과 평가

Python 코드

import numpy as np
from sklearn.cluster import KMeans
from sklearn.metrics import calinski_harabasz_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에 대해 CH Index 계산
K_range = range(2, 10)
ch_scores = []

for k in K_range:
    kmeans = KMeans(n_clusters=k, random_state=42)
    labels = kmeans.fit_predict(X)
    score = calinski_harabasz_score(X, labels)
    ch_scores.append(score)

# 시각화
plt.figure(figsize=(10, 5))
plt.plot(K_range, ch_scores, 'go-', linewidth=2)
plt.axvline(x=K_range[np.argmax(ch_scores)], color='r', linestyle='--',
            label=f'Optimal K = {K_range[np.argmax(ch_scores)]}')
plt.xlabel('Number of Clusters (K)')
plt.ylabel('Calinski-Harabasz Index')
plt.title('Calinski-Harabasz Index for Optimal K')
plt.legend()
plt.show()

print(f"Optimal K: {K_range[np.argmax(ch_scores)]}")
print(f"Best CH Score: {max(ch_scores):.2f}")

수동 계산

def calinski_harabasz_manual(X, labels):
    """CH Index 수동 계산"""
    n_samples, n_features = X.shape
    n_clusters = len(np.unique(labels))

    # 전체 중심
    overall_mean = X.mean(axis=0)

    ss_between = 0
    ss_within = 0

    for k in range(n_clusters):
        cluster_points = X[labels == k]
        n_k = len(cluster_points)
        cluster_mean = cluster_points.mean(axis=0)

        # Between-cluster: 클러스터 중심과 전체 중심 간 거리
        ss_between += n_k * np.sum((cluster_mean - overall_mean) ** 2)

        # Within-cluster: 클러스터 내 점들과 클러스터 중심 간 거리
        ss_within += np.sum((cluster_points - cluster_mean) ** 2)

    # CH Index
    ch_index = (ss_between / (n_clusters - 1)) / (ss_within / (n_samples - n_clusters))

    return ch_index, ss_between, ss_within

# 검증
kmeans = KMeans(n_clusters=4, random_state=42)
labels = kmeans.fit_predict(X)

ch_sklearn = calinski_harabasz_score(X, labels)
ch_manual, ssb, ssw = calinski_harabasz_manual(X, labels)

print(f"sklearn CH: {ch_sklearn:.4f}")
print(f"Manual CH:  {ch_manual:.4f}")
print(f"SS_Between: {ssb:.2f}")
print(f"SS_Within:  {ssw:.2f}")

실루엣과 비교

from sklearn.metrics import silhouette_score

K_range = range(2, 10)
ch_scores = []
silhouette_scores = []

for k in K_range:
    kmeans = KMeans(n_clusters=k, random_state=42)
    labels = kmeans.fit_predict(X)
    ch_scores.append(calinski_harabasz_score(X, labels))
    silhouette_scores.append(silhouette_score(X, labels))

fig, axes = plt.subplots(1, 2, figsize=(14, 5))

axes[0].plot(K_range, ch_scores, 'go-')
axes[0].axvline(x=K_range[np.argmax(ch_scores)], color='r', linestyle='--')
axes[0].set_xlabel('K')
axes[0].set_ylabel('CH Index')
axes[0].set_title(f'Calinski-Harabasz (Optimal K={K_range[np.argmax(ch_scores)]})')

axes[1].plot(K_range, silhouette_scores, 'bo-')
axes[1].axvline(x=K_range[np.argmax(silhouette_scores)], color='r', linestyle='--')
axes[1].set_xlabel('K')
axes[1].set_ylabel('Silhouette Score')
axes[1].set_title(f'Silhouette (Optimal K={K_range[np.argmax(silhouette_scores)]})')

plt.tight_layout()
plt.show()

대규모 데이터 성능 비교

import time

# 대규모 데이터
X_large, _ = make_blobs(n_samples=50000, centers=5, random_state=42)
kmeans = KMeans(n_clusters=5, random_state=42)
labels_large = kmeans.fit_predict(X_large)

# CH Index 시간
start = time.time()
ch = calinski_harabasz_score(X_large, labels_large)
ch_time = time.time() - start

# Silhouette 시간
start = time.time()
sil = silhouette_score(X_large, labels_large)
sil_time = time.time() - start

print(f"데이터 크기: {len(X_large):,}")
print(f"Calinski-Harabasz: {ch:.2f} (Time: {ch_time:.3f}s)")
print(f"Silhouette:        {sil:.4f} (Time: {sil_time:.3f}s)")
print(f"속도 비율: {sil_time / ch_time:.1f}x 빠름 (CH)")

분산 분해 시각화

def visualize_variance_decomposition(X, labels):
    """SSB와 SSW 시각화"""
    n_clusters = len(np.unique(labels))
    overall_mean = X.mean(axis=0)

    fig, ax = plt.subplots(figsize=(10, 8))

    colors = plt.cm.tab10(np.linspace(0, 1, n_clusters))

    for k in range(n_clusters):
        cluster_points = X[labels == k]
        cluster_mean = cluster_points.mean(axis=0)

        # 클러스터 포인트
        ax.scatter(cluster_points[:, 0], cluster_points[:, 1], 
                   c=[colors[k]], s=20, alpha=0.5, label=f'Cluster {k}')

        # 클러스터 중심
        ax.scatter(cluster_mean[0], cluster_mean[1], 
                   c=[colors[k]], s=200, marker='X', edgecolors='black')

        # Within: 중심에서 포인트로 (일부만)
        for point in cluster_points[::10]:  # 10개마다
            ax.plot([cluster_mean[0], point[0]], [cluster_mean[1], point[1]], 
                    c=colors[k], alpha=0.2, linewidth=0.5)

        # Between: 전체 중심에서 클러스터 중심으로
        ax.plot([overall_mean[0], cluster_mean[0]], [overall_mean[1], cluster_mean[1]],
                c='red', linewidth=2, linestyle='--')

    # 전체 중심
    ax.scatter(overall_mean[0], overall_mean[1], 
               c='red', s=300, marker='*', edgecolors='black', label='Overall mean')

    ax.set_title('Variance Decomposition: SS_Between (red) vs SS_Within (colored)')
    ax.legend()
    plt.show()

visualize_variance_decomposition(X, labels)

관련 기법

• Silhouette Score - 응집도/분리도 기반
• Davies-Bouldin Index - 클러스터 유사도 기반
• Elbow Method - WCSS만 사용

참고 문헌

1. Calinski, T., & Harabasz, J. (1974). A Dendrite Method for Cluster Analysis. Communications in Statistics - Theory and Methods, 3(1), 1-27.
2. Milligan, G. W., & Cooper, M. C. (1985). An Examination of Procedures for Determining the Number of Clusters in a Data Set. Psychometrika, 50(2), 159-179.