K-Means Clustering

K-평균은 K개의 클러스터로 데이터를 나누며, 클러스터 내 제곱거리(관성)를 최소화합니다.

$$ J = \sum_{i=1}^{N} \min_{1 \leq j \leq K} \left\lVert x_i - \mu_j \right\rVert^2 $$

각 샘플을 가장 가까운 중심에 할당한 뒤, 할당된 샘플의 평균으로 중심을 갱신합니다.

알고리즘은 두 단계 사이를 번갈아 수행합니다:

$$ c_i \leftarrow \arg\min_j \lVert x_i - \mu_j \rVert^2 $$

$$ \mu_j \leftarrow \frac{1}{|C_j|}\sum_{x_i \in C_j} x_i $$

관성은 수렴할 때까지 단조 감소합니다.

랜덤 초기화는 간단하지만 나쁜 시드에서 시작할 수 있습니다.

k-means++는 초기 중심을 퍼뜨려 더 빠른 수렴과 낮은 관성을 주는 경우가 많습니다.

실무에서는 여러 시드로 여러 번 실행해 지역 최소 민감도를 줄입니다.