k-means 알고리즘

지난 글 : [알고리즘/알고리즘 도감] - 클러스터링

 

k-means 알고리즘은 클러스터링 알고리즘의 하나로, k-means 알고리즘에서는 클러스터의 수를 미리 지정해 그 수에 맞춰 그룹을 나눈다.

 

1

아래에서 데이터는 '점'으로 표현한다.

1. 먼저, 클러스터링을 하고픈 데이터를 준비하고 클러스터 수를 정한다(여기서는 3).
2. 클러스터의 중심점이 될 세 점을 임의의 위치에 설치한다.
3. 각 데이터는 세 개의 중심점 중 자신으로부터 가장 가까운 곳에 있는 것을 찾는다.
4. 각 데이터가 속하는 중심점의 색으로 데이터를 분류하고, 이 것으로 세 개의 클러스터가 만들어진다.
5. 각 클러스터의 중심을 재계산해 해당 위치로 클러스터의 중심점을 이동시킨다.
6. 가장 가까운 클러스터의 중심점을 재계산하고 각 데이터를 클러스터로 재분류한다.
7. '각 데이터의 클러스터 분류'와 '중심점을 클러스터 중심으로 이동'을 중심점이 수렴(움직일 수 없을 때까지)할
	때까지 반복한다.
8. 더 이상 중심점이 이동하지 않으므로 클러스터링이 완료된다.

 

k-means 알고리즘에서 작업을 반복하다 보면 중심점이 반드시 수렴하게 된다는 것은 수학적으로 증명된 사실이라 한다.

 

참고 서적 :