[Data Mining] K-Mean Clustering

k-mean clustering algorithm을 공부해보자. 이것도 그다지 복잡하고 그런 clustering은 아니다. 그러니까 한번 재밌게 공부를 해보자.

당연히 이것도 clustering이니까 앞서 공부했던 Hierarchical Agglomerative Algorithm처럼 cluster로 나누는 것이다. 어떻게 하는 것인지 아래의 예제를 통해 알아보자.

k mean clustering은 data를 k개의 cluster로 나눈다. 우리는 2개로 나눠보자. k=2이다. k mean clustering은 각 cluster의 centre를 각각의 data와 비교하여 가까운 cluster에 넣는 방식으로 clustering을 한다. 우리는 k=2로 두었으니 위의 data에서 아무거나 random으로 두개 만 짚어보자. A와 C를 각각 C1, C2로 놓고 각 data들과의 거리를 측정해보자.(Euclidean distance 사용)

이렇게 측정을 완료했으면 cluster와의 거리를 비교하여 각각의 data를 가까운 cluster에 포함시킨다.

그렇게 모여진 것들의 x1, x2의 평균을 구해서 새로운 centre를 구한다. A와 B가 C1으로 모이므로 A과 B의 x1은 각각 1, 1이고 x2는 1과 0이므로 평균은 각각 1, 0.5가 된다.같은 방법으로 C2에 대해서도 C, D, E전부 모아서 평균을 내보면 1.6777, 3.6777이 나온다.

이렇게 구한 새로운 centre를 가지고 또 각각의 data와의 거리를 구한다.(여기서부터 같은 과정이 계속 반복될 것이다.)

측정을 완료했으니, cluster와의 거리를 비교하여 각각의 data를 가까운 cluster에 포함시킨다.

그렇게 모여진 것들의 x1, x2의 평균을 구해서 새로운 centre를 구한다.

새로운 centre를 가지고 또 각각의 data와의 거리를 구한다.

측정을 완료했으니, cluster와의 거리를 비교하여 각각의 data를 가까운 cluster에 포함시킨다.

그렇게 모여진 것들의 x1, x2의 평균을 구해서 새로운 centre를 구한다.

어라? 업데이트를 했는데 변화가 없다. 그러면 지금부터는 하나마나 작업이 되어버리므로 그만 끝낸다. 위의 centre가 우리의 마지막 centre이다. 그러면 그래프를 통해 보자.

어느정도 우리의 permanent centre에 평균적으로 가까워져있는 것을 볼 수 있겠다.