K-Means++

논문 정보

항목	내용
제목	k-means++: The Advantages of Careful Seeding
저자	David Arthur, Sergei Vassilvitskii
연도	2007
학회	SODA (ACM-SIAM Symposium on Discrete Algorithms)
링크	Stanford

핵심 아이디어

K-Means의 가장 큰 문제점은 초기 중심점 선택에 민감하다는 것. 잘못된 초기화는: - 수렴이 느리거나 - 지역 최적해에 빠지거나 - 빈 클러스터가 발생

Arthur & Vassilvitskii는 "멀리 떨어진 점을 중심점으로 선택"하는 확률적 초기화를 제안했다.

핵심 통찰: 이미 선택된 중심점들로부터 멀리 떨어진 점일수록 다음 중심점으로 선택될 확률이 높아야 함.

알고리즘

초기화 절차 (D² Weighting)

입력: 데이터 X = {x₁, x₂, ..., xₙ}, 클러스터 수 K
출력: 초기 중심점 μ₁, μ₂, ..., μₖ

1. 첫 번째 중심점 μ₁을 X에서 균등 무작위 선택

2. j = 2, 3, ..., K에 대해:
   a. 각 점 xᵢ에 대해 가장 가까운 기존 중심점과의 거리 계산:
      D(xᵢ) = min_{1≤t<j} ‖xᵢ - μₜ‖²

   b. 확률 분포 계산:
      P(xᵢ) = D(xᵢ)² / Σₘ D(xₘ)²

   c. 확률 P에 따라 다음 중심점 μⱼ 선택

3. 이후 표준 K-Means 반복 수행

이론적 보장

K-Means++는 다음을 보장함:

\[E[\phi] \leq 8(\ln k + 2) \cdot \phi_{OPT}\]

• \(\phi\): K-Means++ 결과의 WCSS
• \(\phi_{OPT}\): 최적 해의 WCSS

즉, 기대값이 최적해의 O(log k) 배 이내로 보장됨.

시간 복잡도

• 초기화: \(O(nKd)\)
• 전체: \(O(nKd) + O(tnKd)\) = \(O(tnKd)\) (초기화 오버헤드 무시 가능)

장단점

장점

장점	설명
이론적 보장	O(log k) 근사 보장
빠른 수렴	평균 반복 횟수 크게 감소
안정적 결과	실행마다 결과 편차 감소
쉬운 적용	초기화만 바꾸면 됨

단점

단점	설명
초기화 비용	랜덤 초기화보다 느림 (K번의 전체 순회)
이상치 민감	이상치가 초기 중심으로 선택될 수 있음
K 지정 필요	여전히 K를 사전에 알아야 함

K-Means vs K-Means++ 비교

항목	K-Means (random)	K-Means++
초기화 비용	O(K)	O(nKd)
수렴 속도	느림, 불안정	빠름, 안정적
결과 품질	편차 큼	O(log k) 보장
이론적 보장	없음	있음

언제 쓰는가

적합한 경우

• 항상 K-Means 대신 K-Means++ 사용 (scikit-learn 기본값)
• 수렴 속도와 결과 품질 모두 중요할 때
• 여러 번 실행해서 비교할 여유가 없을 때

부적합한 경우

• 초기화 시간도 아껴야 하는 실시간 시스템
• 이상치가 매우 많은 데이터 (이상치가 초기 중심이 됨)

Python 코드

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
import time

# 데이터 생성
X, y_true = make_blobs(n_samples=1000, centers=5, cluster_std=1.0, random_state=42)

# Random 초기화 vs K-Means++ 비교
results = {}

for init_method in ['random', 'k-means++']:
    start = time.time()
    kmeans = KMeans(
        n_clusters=5,
        init=init_method,
        n_init=1,           # 공정한 비교를 위해 1회만 실행
        max_iter=300,
        random_state=42
    )
    kmeans.fit(X)
    elapsed = time.time() - start

    results[init_method] = {
        'inertia': kmeans.inertia_,
        'n_iter': kmeans.n_iter_,
        'time': elapsed
    }

# 결과 출력
print("=" * 50)
print(f"{'Method':<12} {'WCSS':<12} {'Iterations':<12} {'Time (s)':<10}")
print("=" * 50)
for method, res in results.items():
    print(f"{method:<12} {res['inertia']:<12.2f} {res['n_iter']:<12} {res['time']:<10.4f}")

수렴 비교 시각화

# 여러 번 실행하여 편차 비교
n_runs = 20
random_inertias = []
plusplus_inertias = []

for seed in range(n_runs):
    km_random = KMeans(n_clusters=5, init='random', n_init=1, random_state=seed).fit(X)
    km_plusplus = KMeans(n_clusters=5, init='k-means++', n_init=1, random_state=seed).fit(X)
    random_inertias.append(km_random.inertia_)
    plusplus_inertias.append(km_plusplus.inertia_)

# Box plot
fig, ax = plt.subplots(figsize=(8, 5))
ax.boxplot([random_inertias, plusplus_inertias], labels=['Random', 'K-Means++'])
ax.set_ylabel('WCSS (Inertia)')
ax.set_title('Initialization Method Comparison (20 runs)')
plt.show()

print(f"Random:    mean={np.mean(random_inertias):.2f}, std={np.std(random_inertias):.2f}")
print(f"K-Means++: mean={np.mean(plusplus_inertias):.2f}, std={np.std(plusplus_inertias):.2f}")

직접 구현

def kmeans_plusplus_init(X, k, random_state=None):
    """K-Means++ 초기화 구현"""
    rng = np.random.RandomState(random_state)
    n_samples, n_features = X.shape

    # 첫 번째 중심점: 균등 무작위 선택
    centers = [X[rng.randint(n_samples)]]

    for _ in range(1, k):
        # 각 점에서 가장 가까운 중심점까지의 거리 제곱
        dist_sq = np.array([
            min(np.sum((x - c) ** 2) for c in centers)
            for x in X
        ])

        # 확률 분포 (D² weighting)
        probs = dist_sq / dist_sq.sum()

        # 확률에 따라 다음 중심점 선택
        next_center_idx = rng.choice(n_samples, p=probs)
        centers.append(X[next_center_idx])

    return np.array(centers)

# 테스트
init_centers = kmeans_plusplus_init(X, k=5, random_state=42)
print(f"초기 중심점 shape: {init_centers.shape}")

관련 기법

• K-Means - 기본 알고리즘
• Mini-Batch K-Means - 대규모 데이터용
• K-Medoids - 이상치에 강함
• K-Means|| - 병렬화된 초기화 (Bahmani et al., 2012)

참고 문헌

1. Arthur, D., & Vassilvitskii, S. (2007). k-means++: The Advantages of Careful Seeding. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1027-1035.
2. Bahmani, B., Moseley, B., Vattani, A., Kumar, R., & Vassilvitskii, S. (2012). Scalable K-Means++. Proceedings of the VLDB Endowment, 5(7), 622-633.