Hierarchical Clustering (계층적 클러스터링)¶

개요¶

문제 정의¶

데이터를 계층적 트리 구조(덴드로그램)로 클러스터링:

클러스터 수를 미리 지정할 필요 없음
다양한 수준에서 클러스터 구조 파악 가능
클러스터 간 관계 시각화

핵심 아이디어¶

두 가지 접근법:

병합적 (Agglomerative): Bottom-up - 각 포인트가 하나의 클러스터로 시작 - 가장 가까운 클러스터 쌍을 반복적으로 병합 - 하나의 클러스터가 될 때까지 진행

분할적 (Divisive): Top-down - 전체 데이터가 하나의 클러스터로 시작 - 가장 이질적인 클러스터를 반복적으로 분할 - 각 포인트가 개별 클러스터가 될 때까지 진행

실제로는 병합적 방법이 주로 사용됨 (계산 효율성).

알고리즘/수식¶

병합적 클러스터링 (Agglomerative)¶

Algorithm: Agglomerative Clustering

Input: 데이터 X, 연결 방식 linkage
Output: 덴드로그램 (계층 구조)

1. 초기화: 각 포인트를 개별 클러스터로
   clusters = {{x_1}, {x_2}, ..., {x_n}}

2. 거리 행렬 계산
   D[i,j] = distance(cluster_i, cluster_j)

3. while |clusters| > 1:
     # 가장 가까운 클러스터 쌍 찾기
     (i, j) = argmin D[i,j]

     # 병합
     new_cluster = cluster_i union cluster_j

     # 거리 행렬 업데이트
     update D using linkage method

     # 병합 기록 (덴드로그램용)
     record merge(cluster_i, cluster_j, distance)

4. return dendrogram

연결 방식 (Linkage Methods)¶

클러스터 간 거리 정의:

방식	수식	특징
Single	min{d(a,b) : a in A, b in B}	체인 효과 위험, 긴 클러스터
Complete	max{d(a,b) : a in A, b in B}	조밀한 클러스터
Average (UPGMA)	mean{d(a,b) : a in A, b in B}	균형 잡힌 방법
Ward	argmin 병합 후 분산 증가량	최소 분산, 구형 클러스터
Centroid	d(centroid(A), centroid(B))	역전 가능

Ward's Method 상세¶

병합으로 인한 분산 증가량 최소화:

Delta(A, B) = (n_A * n_B) / (n_A + n_B) * ||c_A - c_B||^2

여기서: - n_A, n_B: 클러스터 크기 - c_A, c_B: 클러스터 중심

Ward's method는 k-means와 유사한 목적 함수를 계층적으로 최적화.

Lance-Williams 업데이트 공식¶

새 클러스터 (A union B)와 C 간 거리:

d(A union B, C) = alpha_A * d(A, C) + alpha_B * d(B, C) 
                 + beta * d(A, B) + gamma * |d(A, C) - d(B, C)|

Linkage	alpha_A	alpha_B	beta	gamma
Single	0.5	0.5	0	-0.5
Complete	0.5	0.5	0	0.5
Average	n_A/(n_A+n_B)	n_B/(n_A+n_B)	0	0
Ward	(n_A+n_C)/(n_A+n_B+n_C)	(n_B+n_C)/(n_A+n_B+n_C)	-n_C/(n_A+n_B+n_C)	0

시간 복잡도¶

알고리즘	시간	공간
기본	O(n^3)	O(n^2)
Single linkage (MST)	O(n^2)	O(n^2)
최적화 (sklearn)	O(n^2) ~ O(n^2 log n)	O(n^2)

하이퍼파라미터 가이드¶

파라미터	설명	옵션
linkage	연결 방식	'ward', 'complete', 'average', 'single'
metric	거리 측정	'euclidean', 'manhattan', 'cosine'
n_clusters	최종 클러스터 수	None (덴드로그램만) 또는 정수
distance_threshold	클러스터 병합 임계값	None 또는 float

Linkage 선택 가이드¶

Ward (기본 권장):
- 구형 클러스터에 적합
- euclidean 거리만 사용
- k-means와 유사한 결과

Complete:
- 조밀한 클러스터 원할 때
- 이상치에 민감

Average:
- 균형 잡힌 방법
- 다양한 거리 측정 가능

Single:
- 긴/불규칙 형태 클러스터
- 체인 효과 주의

Python 코드 예시¶

기본 사용법¶

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import AgglomerativeClustering
from sklearn.datasets import make_blobs
from scipy.cluster.hierarchy import dendrogram, linkage, fcluster
from scipy.spatial.distance import pdist

# 데이터 생성
X, y_true = make_blobs(n_samples=150, centers=4, cluster_std=0.8, random_state=42)

# 병합적 클러스터링
agg_clustering = AgglomerativeClustering(
    n_clusters=4,
    linkage='ward'
)
labels = agg_clustering.fit_predict(X)

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

axes[0].scatter(X[:, 0], X[:, 1], c=y_true, cmap='viridis', alpha=0.6)
axes[0].set_title('True Labels')

axes[1].scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', alpha=0.6)
axes[1].set_title('Hierarchical Clustering')

plt.tight_layout()
plt.savefig('hierarchical_result.png', dpi=150)
plt.show()

덴드로그램 시각화¶

from scipy.cluster.hierarchy import dendrogram, linkage

# linkage 계산
Z = linkage(X, method='ward')

# 덴드로그램
plt.figure(figsize=(14, 7))
dendrogram(
    Z,
    truncate_mode='lastp',  # 마지막 p 병합만 표시
    p=30,
    leaf_rotation=90,
    leaf_font_size=10,
    show_contracted=True
)
plt.xlabel('Sample index')
plt.ylabel('Distance')
plt.title('Hierarchical Clustering Dendrogram (Ward)')
plt.axhline(y=15, color='r', linestyle='--', label='Cut threshold')
plt.legend()
plt.tight_layout()
plt.savefig('dendrogram.png', dpi=150)
plt.show()

덴드로그램에서 클러스터 수 결정¶

# 거리 임계값으로 클러스터 수 결정
from scipy.cluster.hierarchy import fcluster

# 다양한 임계값 테스트
thresholds = [5, 10, 15, 20, 25]

for t in thresholds:
    labels_t = fcluster(Z, t=t, criterion='distance')
    n_clusters = len(set(labels_t))
    print(f"Threshold {t}: {n_clusters} clusters")

# 최적 임계값으로 클러스터 할당
optimal_threshold = 15
final_labels = fcluster(Z, t=optimal_threshold, criterion='distance')

# 또는 클러스터 수로 직접 지정
labels_k = fcluster(Z, t=4, criterion='maxclust')

연결 방식 비교¶

from sklearn.cluster import AgglomerativeClustering
from sklearn.metrics import silhouette_score

linkages = ['ward', 'complete', 'average', 'single']

fig, axes = plt.subplots(2, 2, figsize=(12, 12))

for ax, linkage_type in zip(axes.flatten(), linkages):
    if linkage_type == 'ward':
        agg = AgglomerativeClustering(n_clusters=4, linkage=linkage_type)
    else:
        agg = AgglomerativeClustering(n_clusters=4, linkage=linkage_type, 
                                       metric='euclidean')

    labels = agg.fit_predict(X)
    score = silhouette_score(X, labels)

    ax.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', alpha=0.6)
    ax.set_title(f'{linkage_type.capitalize()} (Silhouette: {score:.3f})')

plt.tight_layout()
plt.savefig('linkage_comparison.png', dpi=150)
plt.show()

연결 행렬 활용¶

# AgglomerativeClustering의 연결 행렬 접근
agg = AgglomerativeClustering(n_clusters=4, linkage='ward')
agg.fit(X)

# children_: 각 병합 단계의 두 자식 인덱스
# n_leaves_: 리프 수
# distances_: 병합 거리 (compute_distances=True 필요)

agg_with_dist = AgglomerativeClustering(
    n_clusters=None,
    distance_threshold=0,  # 전체 트리 계산
    linkage='ward',
    compute_distances=True
)
agg_with_dist.fit(X)

print(f"Number of leaves: {agg_with_dist.n_leaves_}")
print(f"Number of merges: {len(agg_with_dist.children_)}")
print(f"Distance range: {agg_with_dist.distances_.min():.2f} - {agg_with_dist.distances_.max():.2f}")

# scipy 형식으로 변환하여 덴드로그램 생성
def create_linkage_matrix(model):
    counts = np.zeros(model.children_.shape[0])
    n_samples = len(model.labels_) if hasattr(model, 'labels_') else model.n_leaves_

    for i, merge in enumerate(model.children_):
        current_count = 0
        for child_idx in merge:
            if child_idx < n_samples:
                current_count += 1
            else:
                current_count += counts[child_idx - n_samples]
        counts[i] = current_count

    linkage_matrix = np.column_stack([
        model.children_,
        model.distances_,
        counts
    ]).astype(float)

    return linkage_matrix

Z_sklearn = create_linkage_matrix(agg_with_dist)

비구형 클러스터에서의 성능¶

from sklearn.datasets import make_moons

# 비구형 데이터
X_moons, y_moons = make_moons(n_samples=200, noise=0.05, random_state=42)

# 다양한 연결 방식 비교
fig, axes = plt.subplots(2, 3, figsize=(15, 10))

axes[0, 0].scatter(X_moons[:, 0], X_moons[:, 1], c=y_moons, cmap='viridis', alpha=0.6)
axes[0, 0].set_title('True Labels')

linkages = ['ward', 'complete', 'average', 'single']
for ax, linkage_type in zip(axes.flatten()[1:5], linkages):
    agg = AgglomerativeClustering(n_clusters=2, linkage=linkage_type)
    labels = agg.fit_predict(X_moons)

    ax.scatter(X_moons[:, 0], X_moons[:, 1], c=labels, cmap='viridis', alpha=0.6)
    ax.set_title(f'{linkage_type.capitalize()}')

# DBSCAN과 비교
from sklearn.cluster import DBSCAN
dbscan = DBSCAN(eps=0.2, min_samples=5)
labels_dbscan = dbscan.fit_predict(X_moons)
axes[1, 2].scatter(X_moons[:, 0], X_moons[:, 1], c=labels_dbscan, cmap='viridis', alpha=0.6)
axes[1, 2].set_title('DBSCAN')

plt.tight_layout()
plt.savefig('hierarchical_moons.png', dpi=150)
plt.show()

클러스터 안정성 분석¶

from sklearn.model_selection import train_test_split
from sklearn.metrics import adjusted_rand_score

# 부트스트랩으로 클러스터 안정성 평가
n_bootstraps = 100
stability_scores = []

for i in range(n_bootstraps):
    # 부트스트랩 샘플
    indices = np.random.choice(len(X), size=len(X), replace=True)
    X_boot = X[indices]
    y_boot = y_true[indices]

    # 클러스터링
    agg = AgglomerativeClustering(n_clusters=4, linkage='ward')
    labels_boot = agg.fit_predict(X_boot)

    # ARI 계산
    ari = adjusted_rand_score(y_boot, labels_boot)
    stability_scores.append(ari)

print(f"Clustering Stability (ARI):")
print(f"  Mean: {np.mean(stability_scores):.4f}")
print(f"  Std: {np.std(stability_scores):.4f}")
print(f"  Min-Max: {np.min(stability_scores):.4f} - {np.max(stability_scores):.4f}")

언제 쓰나?¶

적합한 상황: - 클러스터 수를 모를 때 (덴드로그램 분석) - 계층적 구조 파악이 필요할 때 (분류 체계) - 시각화가 중요할 때 - 중소규모 데이터셋 (n < 10,000) - 생물학적 분류, 문서 분류

부적합한 상황: - 대규모 데이터셋 (O(n^2) 메모리) - 실시간 클러스터링 - 새 데이터 추가 시 재계산 필요 - 노이즈가 많은 데이터 (single linkage 특히)

장단점¶

장점	단점
클러스터 수 미리 지정 불필요	O(n^2) 시간/공간 복잡도
덴드로그램으로 구조 파악	대규모 데이터에 부적합
다양한 연결 방식 선택	병합 후 취소 불가
재현 가능 (결정적)	체인 효과 (single linkage)
다양한 거리 측정 가능	이상치에 민감할 수 있음