초기화

우선 알고리즘으로 모든 관측치에 클러스터를 할당하여 초기화해야 한다. 무작위 분할법(random partition method)은 데이터 세트의 중심을 향해 클러스터의 포인트를 배치한다. 또 다른 초기화 방법인 포지법(Forgy method)은 클러스터의 첫 번째 위치를 무작위로 흩뿌린다.

첫 번째 클러스터의 관측이 할당되면 클러스터 할당을 보고 알고리즘을 업데이트할 수 있다.

 

할당

관측된 각 개체를 클러스터에 할당한다. 개체를 어느 클러스터 센트로이드에 할당할지를 정하려면 알고리즘은 유클리디언 거리(Euclidean distance)를 사용해야 한다. 클러스터 센트로이드까지의 유클리디언 거리를 제곱하여 제곱의 합이 가장 작은 클러스터에 개체를 할당한다.

유클리디언 거리는 간단한 초급 수준의 수학으로 계산할 수 있다. 피타고라스의 정리(Pythagoras’ theorem)를 기억한다면 충분히 할 수 있다.

X축에 6개, Y축에 4개의 포지션으로 구성된 격자 또는 그리드가 있다고 가정하자. 그림 8-3과 같이 클러스터의 중심점은 현재 (1,6)에 있고, 개체는 (3,1)에 있다.

거리는 가로로 3 - 1 = 2, 세로로 6 - 1 = 5이다. 피타고라스의 정리를 사용하면 제곱 거리는 다음과 같다.

 

29의 제곱근은 5.38이다. 이런 작업이 데이터의 모든 개체를 대상으로 수행되어 클러스터에 할당된다.

▲ 그림 8-3 유클리디언 거리