K-means++ 초기화

30번 K-means 는 초기 centroid를 무작위 로 골랐죠. 이게 문제가 됩니다 — 재수 없으면 centroid 두 개가 같은 클러스터에 몰리고, 한 클러스터는 비어버려 최종 해가 나쁘게 수렴.

K-means++ 는 초기 centroid를 서로 멀리 퍼뜨리는 방식으로 개선합니다:

알고리즘

1. 데이터에서 첫 centroid 를 무작위 로 하나 고름.
2. 각 점 $x$ 에 대해 가장 가까운 centroid 까지의 거리 제곱 $D(x)^2$ 계산.
3. 확률 $\propto D(x)^2$ 로 다음 centroid 샘플링 (멀리 있는 점이 뽑힐 확률 ↑).
4. k 개가 될 때까지 2-3 반복.

이론적으로 $O(\log k)$ 근사 보장 — 순진한 랜덤보다 훨씬 좋음. sklearn.cluster.KMeans 의 기본값도 init='k-means++'.

과제

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

• 반환: (k, D) centroid 배열.
• rng.choice(N, p=prob) 로 확률적 샘플링.
• 모든 centroid 는 X 안의 점이어야 함.

테스트 케이스