K-means Simulator (2D)

K-means — 이론적 설명

목표 (Objective)

K-means는 주어진 데이터를 K개의 군집(cluster)으로 나누어 각 군집의 중심(centroid)과 데이터 사이의 제곱거리 합(즉 inertia)을 최소화하는 것을 목표로 합니다.

\[ \text{inertia} = \sum_{i=1}^{N} \min_{1 \leq j \leq K} \|x_i - \mu_j\|^2 \] 여기서 \(x_i\)는 데이터 포인트, \(\mu_j\)는 j번째 군집의 중심입니다.

알고리즘 (Lloyd's algorithm, 한 반복)

1. 할당 단계 (Assignment) — 각 데이터 포인트를 가장 가까운 중심에 할당합니다 (유클리드 거리 기준).
2. 갱신 단계 (Update) — 각 군집의 중심을 그 군집에 할당된 점들의 평균으로 재계산합니다.
3. 위 두 단계를 반복하여 중심의 변화가 충분히 작아지거나 최대 반복에 도달하면 종료합니다.

초기화 (Initialization)

초기 중심 값에 따라 결과가 달라지므로 좋은 초기화가 중요합니다. kmeans++는 널리 쓰이는 방법으로, 첫 중심을 랜덤으로 고르고 이후 중심은 기존 중심에서 멀리 떨어진 점들을 확률적으로 선택하여 초기 분산을 크게 만드는 방식입니다. 이 방법은 수렴 속도와 품질을 개선합니다.

수렴성과 복잡도

• 알고리즘은 항상 국소 최적(local minimum)에 수렴하지만 전역 최적(global minimum)을 보장하지 않습니다.
• 계산 복잡도는 반복 횟수 \(T\), 점 개수 \(N\), 군집 수 \(K\), 차원수 \(D\)에 대해 일반적으로 \(O(T \cdot N \cdot K \cdot D)\) 입니다.

실무 팁

• 스케일링: 각 특성(feature)은 스케일이 다르면 한 특성이 좌우하므로 표준화(예: z-score) 또는 정규화를 고려하세요.
• 빈 군집 처리: 어떤 중심이 할당된 점이 없어지면(빈 군집) 중심을 랜덤 재초기화하거나 가장 먼 포인트로 재설정하는 전략을 씁니다. (위 코드에선 무작위 재초기화 처리)
• k 선택: 엘보우(elbow) 방식(반복해 inertia 변화를 보고 급격히 줄어드는 지점을 찾음)이나 실루엣(silhouette) 점수로 적절한 K를 추정합니다.
• 여러 시드 실행: 초기화 민감도를 줄이려면 서로 다른 초기화로 여러 번 실행한 뒤 inertia가 가장 작은 결과를 선택하세요.

왜 시뮬레이터로 실험해야 하나요?

K-means는 직관적이고 빠르지만 초기화, 스케일, 이상치(outlier)에 민감합니다. 시뮬레이터에서 서로 다른 데이터 분포와 초기화 전략을 시도해보면 어떤 상황에서 잘 동작하고 어떤 상황에서 문제를 일으키는지 직관적으로 이해할 수 있습니다.