K-means 클러스터링

레이블 없이 데이터를 k개 그룹으로 나누는 대표적 비지도 알고리즘. Lloyd 알고리즘:

반복 구조

1. 초기화: 데이터에서 k개를 무작위 선택해 초기 중심점(centroid).
2. 할당(Assign): 각 점을 가장 가까운 centroid의 클러스터로.
3. 갱신(Update): 각 클러스터의 평균으로 centroid 업데이트.
4. 수렴할 때까지 (또는 max_iter 회) 2~3 반복.

결과: 각 점의 클러스터 레이블 + 최종 centroid 위치.

주의

• 초기 centroid에 민감 — 결과가 seed에 따라 달라짐 (실제로는 k-means++ 초기화가 표준).
• 이 문제에서는 단순 랜덤 초기화만 구현.

과제

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

• X shape (N, D), k 정수, max_iter 정수.
• 반환: (labels, centroids) — labels shape (N,) int, centroids shape (k, D).
• 초기화: rng.choice(N, k, replace=False) 로 k개 점을 centroid로 복사.
• 할당: 각 점에서 모든 centroid와 거리 계산 → argmin.
• 갱신: 각 라벨별 평균. 빈 클러스터는 기존 centroid 유지.

테스트 케이스