K-Means¶

논문 정보¶

항목	내용
제목	Least squares quantization in PCM
저자	Stuart P. Lloyd
연도	1957 (내부 기술 노트), 1982 (공식 출판)
학회	IEEE Transactions on Information Theory
링크	IEEE Xplore

핵심 아이디어¶

Lloyd는 원래 펄스 코드 변조(PCM)에서 신호를 최적으로 양자화하는 문제를 해결하기 위해 이 알고리즘을 개발했다. 핵심 아이디어는 단순하다:

K개의 중심점(centroid)을 임의로 배치
각 데이터 포인트를 가장 가까운 중심점에 할당
각 클러스터의 평균으로 중심점 업데이트
수렴할 때까지 2-3 반복

이 반복 과정이 Within-Cluster Sum of Squares (WCSS)를 최소화함.

알고리즘¶

목적 함수¶

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

\(K\): 클러스터 수
\(C_i\): i번째 클러스터
\(\mu_i\): i번째 클러스터의 중심점
\(\|x - \mu_i\|^2\): 유클리드 거리의 제곱

단계별 절차¶

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

1. 초기화: K개의 중심점 μ₁, μ₂, ..., μₖ를 무작위로 선택
2. 반복:
   a. 할당 단계 (E-step):
      각 xᵢ에 대해: cᵢ = argmin_j ‖xᵢ - μⱼ‖²
   b. 업데이트 단계 (M-step):
      각 j에 대해: μⱼ = (1/|Cⱼ|) Σ_{x∈Cⱼ} x
3. 종료 조건: 중심점이 변하지 않거나 최대 반복 횟수 도달

시간 복잡도¶

한 번의 반복: \(O(nKd)\)
전체: \(O(tnKd)\) (t = 반복 횟수)

장단점¶

장점¶

장점	설명
단순함	구현이 쉽고 직관적
확장성	대규모 데이터에 적용 가능
수렴 보장	항상 지역 최적해에 수렴
해석 용이	중심점으로 클러스터 특성 파악

단점¶

단점	설명
K 지정 필요	클러스터 수를 사전에 알아야 함
초기화 민감	초기 중심점에 따라 결과가 달라짐
구형 가정	비구형 클러스터에 부적합
이상치 민감	평균 기반이라 이상치에 취약
지역 최적해	전역 최적해 보장 안 됨

언제 쓰는가¶

적합한 경우¶

클러스터가 대략 구형이고 크기가 비슷할 때
클러스터 수를 사전에 알거나 추정 가능할 때
대규모 데이터에서 빠른 클러스터링이 필요할 때
이미지 압축, 색상 양자화
고객 세분화 (초기 탐색)

부적합한 경우¶

클러스터가 비정형(초승달, 동심원 등)일 때
클러스터 크기/밀도가 크게 다를 때
이상치가 많을 때
클러스터 수를 전혀 모를 때

Python 코드¶

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

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

# K-Means 적용
kmeans = KMeans(
    n_clusters=4,
    init='random',      # 기본 초기화 (k-means++이 아님)
    n_init=10,          # 서로 다른 초기화로 10번 실행
    max_iter=300,       # 최대 반복 횟수
    tol=1e-4,           # 수렴 허용 오차
    random_state=42
)
kmeans.fit(X)

# 결과
labels = kmeans.labels_           # 클러스터 할당
centers = kmeans.cluster_centers_ # 중심점
inertia = kmeans.inertia_         # WCSS (목적 함수 값)

print(f"WCSS (Inertia): {inertia:.2f}")
print(f"반복 횟수: {kmeans.n_iter_}")

# 시각화
plt.figure(figsize=(8, 6))
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', s=50, alpha=0.6)
plt.scatter(centers[:, 0], centers[:, 1], c='red', marker='X', s=200, edgecolors='black')
plt.title('K-Means Clustering')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()

Elbow Method로 최적 K 찾기¶

wcss = []
K_range = range(1, 11)

for k in K_range:
    kmeans = KMeans(n_clusters=k, init='k-means++', random_state=42)
    kmeans.fit(X)
    wcss.append(kmeans.inertia_)

plt.figure(figsize=(8, 5))
plt.plot(K_range, wcss, 'bo-')
plt.xlabel('Number of Clusters (K)')
plt.ylabel('WCSS')
plt.title('Elbow Method')
plt.xticks(K_range)
plt.show()

참고 문헌¶

Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129-137.
MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability.

K-Means¶

논문 정보¶

핵심 아이디어¶

알고리즘¶

목적 함수¶

단계별 절차¶

시간 복잡도¶

장단점¶

장점¶

단점¶

언제 쓰는가¶

적합한 경우¶

부적합한 경우¶

Python 코드¶

Elbow Method로 최적 K 찾기¶

관련 기법¶

참고 문헌¶