K-means Clustering Algorithm

K-means (MacQueen, 1967) 은 유명한 군집화 (Clustering) 문제를 해결하는 가장 간단한 자율학습 (Unsupervised Learning) 알고리즘중 하나이다. 사전에 정해진 어떤수의 클러스터를 통해서 주어진 데이터 집합을 분류하는 간단하고 쉬운 방법이다. k-means 는 partitional clustering 에 속한다.

data 이외에 cluster 의 수 를 input 으로 하며 이때 를 seed point 라고 한다. seed point 는 임의로 선택되며 바람직한 cluster 구조에 관한 어떤 지식들이 seed point를 선택하는데에 사용될 수 있다. Forgy' algorithm 과 다른점은 하나의 sample 이 하나의 cluster 에 합류하자마자 곧 cluster 의 centroid 가 다시 계산된다는 것이다. 또한 Forgy' algorithm 이 반복적(iterative) 한 반면에 -means algorithm 은 data set에서 단지 두 번만의 pass 가 이루어진다. 그 과정은 다음과 같다.

1. 처음에 cluster 로서 시작한다. 남아있는  sample들에 대해서는 가장 가까이 있는 centroid를 찾는다. 이것에 가장 가까이 있는 centroid를 가지는 것이 확인된 cluster 에 sample을 포함시킨다. 각각의 sample 들이 할당된 후에 할당된 cluster 의 centroid 가 다시 계산된다.

2. 그 data를 두 번 처리한다. 각 sample에 대하여 가장 가까이 있는 centroid를 찾는다. 가장 가까이 있는 centroid를 가진 것으로 확인된 cluster 에 sample을 위치시킨다. (이 step 에서는 어떤 centroid 도 다시 계산하지 않는다.)

site :

A Tutorial on Clustering Algorithms : K-means : Applet

• J. B. MacQueen (1967): "Some Methods for classification and Analysis of Multivariate Observations, Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability", Berkeley, University of California Press, 1:281-297
• Andrew Moore: “K-means and Hierarchical Clustering - Tutorial Slides”
• Brian T. Luke: “K-Means Clustering”
• Tariq Rashid: “Clustering”
• Hans-Joachim Mucha and Hizir Sofyan: “Nonhierarchical Clustering”

paper :

The k-means Algorithm : Earl Gose 외

K-평균군집화(K-Means Clustering) : 장남식

K-평균 군집 방법을 이용한 가중 커널분류기 (Kernel Pattern Recognition using K-means Clustering Method) : 심정욱, 백장선, 한국통계학회 응용통계연구 13권 2호, 2000

K-평균 군집화의 재현성 평가 및 응용 (Reproducibility Assessment of K-Means Clustering and Applications) : 허명희, 이용구, 한국통계학회 응용통계연구 17권 1호, 2004