K-means++ Initialization [medium]

v1 K-means 의 문제: 초기화 가 무작위라 local minimum 에 자주 빠짐. 같은 데이터에 seed 만 바꿔도 전혀 다른 클러스터링 — 그리고 운이 나쁘면 두 centroid 가 바로 옆에 배치됨.

K-means++ (Arthur & Vassilvitskii 2007): centroid 를 서로 멀리 흩어지게 확률적으로 선택.

알고리즘

1. 첫 centroid $c_1$ 은 X 에서 균등 무작위.
2. 이미 뽑은 centroid 들이 $\{c_1, ..., c_m\}$ 일 때:
   • 각 점 $x$ 의 현재 가장 가까운 centroid 와의 거리 제곱 $D(x)^2$ 계산.
   • 다음 centroid 를 $P(x) = \frac{D(x)^2}{\sum_i D(x_i)^2}$ 확률로 샘플.
3. $k$ 개 모일 때까지 반복.
4. 이 초기값으로 Lloyd 알고리즘 (할당 + 갱신) 실행.

Inertia (WCSS)

클러스터 품질 스칼라:

$\text{inertia} = \sum_i \lVert x_i - c_{\ell(i)} \rVert^2$

K-means 의 목적함수. 같은 $k$ 에 대해 inertia 가 낮을수록 좋은 클러스터링.

과제

함수 kmeans_pp(X, k, max_iter, seed) 를 완성하세요.

• 반환: (labels, centroids, inertia) — 이전 반환값 + Python float.
• 초기화는 K-means++ (위 알고리즘).
• 한 번의 rng = np.random.default_rng(seed) 로 전 과정 사용.
• 빈 클러스터가 생기면 해당 centroid 는 갱신 없이 유지.

테스트 케이스