K-Medoids (PAM)

논문 정보

항목	내용
제목	Finding Groups in Data: An Introduction to Cluster Analysis
저자	Leonard Kaufman, Peter J. Rousseeuw
연도	1987 (PAM), 1990 (책 출판)
출판	Wiley Series in Probability and Statistics
링크	Wiley

핵심 아이디어

K-Means의 문제점: - 중심점(centroid)이 가상의 점 (실제 데이터가 아님) - 평균을 사용하므로 이상치에 민감

K-Medoids의 해결책: - Medoid: 클러스터 내 다른 모든 점과의 거리 합이 최소인 실제 데이터 포인트 - 평균 대신 중앙값처럼 작동하여 이상치에 강건

PAM (Partitioning Around Medoids)은 가장 유명한 K-Medoids 알고리즘.

알고리즘

목적 함수

\[J = \sum_{i=1}^{K} \sum_{x \in C_i} d(x, m_i)\]

• \(m_i\): i번째 클러스터의 medoid (실제 데이터 포인트)
• \(d(x, m_i)\): x와 medoid 간의 거리 (유클리드, 맨해튼 등)

PAM 알고리즘

입력: 데이터 X = {x₁, ..., xₙ}, 클러스터 수 K
출력: Medoids M = {m₁, ..., mₖ}, 클러스터 할당

BUILD 단계 (초기화):
1. 첫 번째 medoid: 다른 모든 점과의 거리 합이 최소인 점 선택
2. j = 2, ..., K:
   - 기존 medoid들과의 거리 감소량이 최대인 점을 추가

SWAP 단계 (최적화):
1. 반복:
   a. 각 medoid mᵢ에 대해:
      - 각 비-medoid o에 대해:
        - mᵢ를 o로 교체했을 때 총 비용 변화 ΔT 계산
   b. ΔT가 음수인 (비용이 감소하는) 교체가 있으면:
      - 가장 큰 감소를 주는 교체 수행
   c. 종료 조건: 더 이상 비용 감소 없음

시간 복잡도

단계	복잡도
BUILD	O(n²K)
SWAP (한 반복)	O(K(n-K)²)
전체	O(n²K + tK(n-K)²) ≈ O(n²K)

K-Means의 O(nKd)보다 훨씬 느림.

장단점

장점

장점	설명
이상치 강건성	중앙값처럼 극단값에 덜 민감
해석 용이	Medoid가 실제 데이터 (대표 샘플)
임의 거리 함수	유클리드 외에도 사용 가능
범주형 데이터	Gower 거리 등으로 혼합 데이터 처리

단점

단점	설명
계산 비용	O(n²)로 대규모 데이터에 부적합
K 지정 필요	클러스터 수 사전 결정
지역 최적해	전역 최적 보장 없음

K-Means vs K-Medoids

항목	K-Means	K-Medoids
대표점	Centroid (가상)	Medoid (실제 데이터)
목적 함수	WCSS (제곱 거리)	거리 합
이상치	민감	강건
거리 함수	유클리드만	임의 거리
복잡도	O(nKd)	O(n²K)
적합 데이터	수치형, 대규모	혼합형, 소규모

언제 쓰는가

적합한 경우

• 이상치가 많은 데이터
• 클러스터의 대표 샘플이 필요할 때
• 범주형/혼합형 데이터
• 유클리드 거리가 부적합한 경우 (문자열, 시퀀스 등)
• 데이터 크기가 작을 때 (< 10K)

부적합한 경우

• 대규모 데이터 (너무 느림)
• 이상치가 없는 깨끗한 데이터 (K-Means로 충분)
• 실시간 처리가 필요한 경우

Python 코드

import numpy as np
from sklearn_extra.cluster import KMedoids  # pip install scikit-learn-extra
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt

# 이상치가 있는 데이터 생성
np.random.seed(42)
X, y_true = make_blobs(n_samples=200, centers=3, cluster_std=0.5)
# 이상치 추가
outliers = np.array([[10, 10], [-8, 8], [8, -8]])
X = np.vstack([X, outliers])

# K-Medoids (PAM)
kmedoids = KMedoids(
    n_clusters=3,
    metric='euclidean',     # 'manhattan', 'cosine' 등 사용 가능
    method='pam',           # 'pam' 또는 'alternate'
    init='k-medoids++',     # 초기화 방법
    max_iter=300,
    random_state=42
)
kmedoids.fit(X)

# K-Means (비교용)
kmeans = KMeans(n_clusters=3, random_state=42)
kmeans.fit(X)

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

# K-Medoids
axes[0].scatter(X[:, 0], X[:, 1], c=kmedoids.labels_, cmap='viridis', s=50, alpha=0.6)
medoids = X[kmedoids.medoid_indices_]
axes[0].scatter(medoids[:, 0], medoids[:, 1], c='red', marker='*', s=300, edgecolors='black', label='Medoids')
axes[0].scatter(outliers[:, 0], outliers[:, 1], c='orange', marker='x', s=100, label='Outliers')
axes[0].set_title(f'K-Medoids (Inertia: {kmedoids.inertia_:.2f})')
axes[0].legend()

# K-Means
axes[1].scatter(X[:, 0], X[:, 1], c=kmeans.labels_, cmap='viridis', s=50, alpha=0.6)
axes[1].scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], 
                c='red', marker='X', s=300, edgecolors='black', label='Centroids')
axes[1].scatter(outliers[:, 0], outliers[:, 1], c='orange', marker='x', s=100, label='Outliers')
axes[1].set_title(f'K-Means (Inertia: {kmeans.inertia_:.2f})')
axes[1].legend()

plt.tight_layout()
plt.show()

# Medoid 확인 (실제 데이터 포인트)
print("Medoid indices:", kmedoids.medoid_indices_)
print("Medoid coordinates:\n", medoids)

맨해튼 거리 사용

# 맨해튼 거리 (L1) - 이상치에 더 강건
kmedoids_l1 = KMedoids(
    n_clusters=3,
    metric='manhattan',
    random_state=42
)
kmedoids_l1.fit(X)
print(f"Manhattan distance inertia: {kmedoids_l1.inertia_:.2f}")

사용자 정의 거리 함수

from sklearn.metrics import pairwise_distances

# 코사인 거리
kmedoids_cosine = KMedoids(
    n_clusters=3,
    metric='cosine',
    random_state=42
)
kmedoids_cosine.fit(X)

# 사전 계산된 거리 행렬 사용
dist_matrix = pairwise_distances(X, metric='euclidean')
kmedoids_precomputed = KMedoids(
    n_clusters=3,
    metric='precomputed',
    random_state=42
)
kmedoids_precomputed.fit(dist_matrix)

CLARA - 대규모 데이터용 근사 알고리즘

# CLARA: Clustering Large Applications
# PAM을 샘플에서만 수행하고 전체 데이터에 적용
from sklearn_extra.cluster import KMedoids

# 대규모 데이터
X_large, _ = make_blobs(n_samples=10000, centers=5, random_state=42)

# KMedoids with 'alternate' method (CLARA-like, faster)
kmedoids_fast = KMedoids(
    n_clusters=5,
    method='alternate',  # PAM보다 빠름
    random_state=42
)
kmedoids_fast.fit(X_large)
print(f"Alternate method inertia: {kmedoids_fast.inertia_:.2f}")

관련 기법

• K-Means - 평균 기반 (빠르지만 이상치에 민감)
• CLARA - 대규모용 K-Medoids 근사 (Kaufman & Rousseeuw, 1990)
• CLARANS - 랜덤 샘플링 기반 (Ng & Han, 1994)
• DBSCAN - 밀도 기반 (이상치 자동 탐지)

참고 문헌

1. Kaufman, L., & Rousseeuw, P. J. (1990). Finding Groups in Data: An Introduction to Cluster Analysis. Wiley.
2. Park, H. S., & Jun, C. H. (2009). A simple and fast algorithm for K-medoids clustering. Expert Systems with Applications, 36(2), 3336-3341.
3. Schubert, E., & Rousseeuw, P. J. (2019). Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms. SISAP.