실습 · 연습문제 1개

k-means는 군집 내 제곱합(inertia)

$$J = \sum_{i=1}^{N} \lVert \mathbf{x}_i - \boldsymbol{\mu}_{c_i} \rVert^2$$

을 줄이는 두 단계를 번갈아 반복한다(Lloyd 알고리즘).

1. 배정: 각 점 $\mathbf{x}_i$를 가장 가까운 중심 $\boldsymbol{\mu}_j$에 배정한다. 거리가 같으면 번호가 작은 중심을 고른다(np.argmin의 동작).
2. 갱신: 각 중심을 배정된 점들의 평균으로 옮긴다. 배정된 점이 하나도 없는 중심은 그대로 둔다.

함수 kmeans(X, init_centers, n_iter=100)를 완성한다.

인자·반환	shape	의미
X	(N, D)	데이터
init_centers	(K, D)	초기 중심 (이 값을 고치지 않는다)
반환 centers	(K, D)	마지막 중심
반환 labels	(N,)	마지막 중심에 대한 배정 (정수)
반환 history	길이 ≤ n_iter인 리스트	반복마다 배정 직후의 inertia $J$

배정이 더 이상 바뀌지 않으면 반복을 멈춘다. 테스트는 다음을 확인한다.

• 손으로 풀 수 있는 1차원 예에서 중심과 배정이 정확한가
• history가 증가하지 않는가(Lloyd 반복은 $J$를 늘리지 않는다)
• 반환된 labels가 반환된 centers에 대한 최근접 배정인가
• 초기 중심이 나쁘면 다른 국소해에 멈출 수 있는가(그래서 실제로는 여러 초기값을 시도한다)

힌트: 점과 중심 사이의 제곱 거리 행렬 (N, K)는 broadcasting으로 ((X[:, None, :] - C[None, :, :]) ** 2).sum(-1)이다.