K-평균 알고리즘

위키백과 ― 우리 모두의 백과사전.

K-평균 알고리즘(영어: K-means algorithm)은 주어진 데이터를 특정 성질에 기초해서 k 묶음으로 나누는 방법 중 하나다. 데이터가 벡터 공간을 이룬다고 가정하고, 이 알고리즘은 각 묶음의 분산도를 최소화한다. 이것을 식으로 나타내면 다음과 갈다.

$V = \sum_{i=1}^{k} \sum_{j \in S_i} |x_j - \mu_i |^2$

여기서 $k$ 개의 묶음은 $S i$ , $i = 1,2,..., k$ 으로 표시되고, $μ i$ 는 각 묶음에 속한 점들 $x_j \in S_i$ 의 무게중심이다

맨 처음, 각 점들을 k개 집합으로 나눈다. 이 때 임의로 나누거나, 어떤 휴리스틱을 사용할 수도 있다. 그 다음 각 집합의 무게 중심을 구한다. 그 다음, 각각의 점들을 방금 구한 무게중심 가운데 제일 가까운 것에 연결지음으로써 새로이 집합을 나눌 수 있다. 이 작업을 반복하면 점들이 소속된 집합을 바꾸지 않거나, 무게중심이 변하지 않는 상태로 수렴될 수 있다.

이 알고리즘은 실제 사용될 때 빠르게 수렴하기 때문에 널리 쓰인다. 보통 처음 주어진 데이터의 개수보다 훨씬 적은 반복만 필요하다. 그러나 최근 아서(Arthur)와 러시아어: Vassilvitskii가 이 알고리즘이 다항을 넘는(superpolynomial) 시간 - $2^{\Omega(\sqrt{n})}$ - 걸리는 경우가 있음을 보였다.

결과의 효용 측면에서는 이 알고리즘은 전역 최적값을 보장해 주지 않는다. 맨 처음 나눈 방법에 상당히 의존한 결과가 나오므로 전체 최적값에 비해 꽤 나쁜 값을 얻을 수도 있다. 그러나 이 알고리즘은 빠르기 때문에 다른 초기값으로 여러번 시도하여 좋은 묶음을 얻어 내곤 한다.

약점이 하나 더 있다면, 이 알고리즘을 시작할 때 k값을 정해 주어야 하는 점인데, 데이터가 자연스럽게 분포되어 있지 않으면 이상한 결과를 얻을 수도 있다.

[편집] 참고

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

D. Arthur, S. Vassilvitskii (2006): "How Slow is the k-means Method?," Proceedings of the 2006 Symposium on Computational Geometry (SoCG).