k-평균 산책

1. 무엇을 푸는 알고리즘인가

k-평균은 n개의 점을 k개의 무리(cluster)로 나눕니다. 각 점은 자기와 가장 가까운 중심점(centroid)에 속합니다. 그 결과 평면이 centroid를 기준으로 한 영역들로 잘립니다(보로노이 다이어그램). ¹

한 줄로: "비슷한 점끼리 묶고, 그 가운데 점을 평균으로 잡는 일을 반복" 합니다.

"할당"과 "평균 갱신" 두 단계는 모두 SSE(Sum of Squared Errors)를 줄이는 방향으로만 움직입니다. 그래서 SSE는 매 단계 단조 감소합니다. 가능한 클러스터 배치 경우의 수는 유한하므로, 알고리즘은 결국 멈춥니다. ²

한국어 한 줄 요약: "항상 줄어드는 값이 있는데 경우의 수가 유한하면, 반드시 끝난다".

k-평균은 비슷한 크기·둥근 모양의 무리를 잘 찾습니다. 반대로 위 옆의 스마일처럼 곡선/얼굴/링 같은 비선형 모양에서는 알고리즘이 "원하는 부분"을 제대로 묶지 못합니다.²

이런 경우엔 DBSCAN, 가우시안 혼합 모형(EM), 스펙트럴 클러스터링 같은 다른 도구가 필요합니다.