K-means++ 초기화가 random initialization보다 줄이는 것과 보장하지 않는 것은 무엇인가요?

결론부터 말하면 k-means++는 첫 중심들이 한 곳에 몰리는 확률을 낮춰 나쁜 초기화의 위험을 줄이지만, global optimum이나 한 번의 실행에서의 안정성을 보장하지 않습니다. 첫 중심을 0으로 정하고 나머지 후보의 현재 최소 제곱거리가 [1,4,9]라면 다음 중심의 확률은 D²/ΣD²이므로 [1/14,4/14,9/14], 약 [0.071,0.286,0.643]입니다. 멀리 있는 후보를 선호한다는 설명은 이 표의 숫자로 확인할 수 있습니다. 이미 선택된 중심과 같은 점은 D²가 0이라 다시 뽑힐 확률이 없습니다.

예를 들어 1차원 점 [0,1,9,10], K=2에서 초기 중심 [1,9]를 쓰면 {0,1}, {9,10}으로 나뉘고 갱신 중심은 [0.5,9.5], inertia는 1.0입니다. 반면 두 중심이 [0,1]처럼 왼쪽에 몰리면 첫 할당에서 오른쪽 점들이 한 중심에 쏠리고, 이후 Lloyd 반복이 다른 지역해로 갈 수 있습니다. 실제 비교에서는 seed별 최종 inertia뿐 아니라 counts, 중심 좌표, 경계 표본을 함께 기록합니다. 낮은 inertia 하나를 global optimum이라고 부르지 않고 여러 seed 또는 명시한 초기화 횟수의 분포로 안정성을 판단합니다. 모든 후보의 D²가 0이 되는 중복 데이터에서는 분모가 0이므로 균등 선택·종료 같은 정책을 따로 정해야 합니다.

실험 결과를 해석할 때는 초기 중심의 좌표만 저장하지 말고 각 단계의 D² weight와 난수 seed를 남깁니다. 같은 데이터에서 seed 7은 inertia 1.0, seed 11은 3.5가 나왔다면 1.0을 채택할 수는 있어도 “항상 1.0”이라고 말할 수는 없습니다. 또한 k-means++가 초기화를 좋게 만들어도 Lloyd 갱신은 여전히 선택된 초기 상태에서 출발하므로, 여러 실행의 최솟값과 분산을 함께 봐야 합니다.