K-means 알고리즘
위키백과 ― 우리 모두의 백과사전.
K-means 알고리즘(영어: K-means algorithm)은 주어진 데이터를 특정 성질에 기초해서 k개의 묶음으로 나누는 방법중의 하나다. 데이터가 벡터 공간을 이룬다고 가정하고, 이 알고리즘은 각 묶음의 분산도를 최소화한다. 이것을 식으로 나타내면
여기서 k개의 묶음은 Si, i = 1,2,...,k으로 표시되고, μi 는 각 묶음에 솎한 점들 의 무게 중심이다
맨 처음, 각 점들을 k개의 집합으로 나눈다. 이 때 임의로 나누거나, 어떤 휴리스틱을 사용할 수도 있다. 그 다음 각 집합의 무게 중심을 구한다. 그 다음, 각각의 점들을 방금 구한 무게 중심들 중에 제일 가까운 것에 연결지음으로서 새로이 집합을 나눌 수 있다. 이 작업을 반복하면 점들이 소속된 집합을 바꾸지 않거나, 무게중심이 변하지 않는 상태로 수렴될 수 있다.
이 알고리즘은 실제 사용될 때 빠르게 수렴하기 때문에 널리 쓰인다. 보통 처음 주어진 데이터의 갯수보다 훨씬 적은 반복이 필요하다. 그러나 최근 Arthur 와 Vassilvitskii가 이 알고리즘이 superpolynomial 시간 - - 걸리는 경우가 있음을 보였다.
결과의 효용 측면에서는 이 알고리즘은 global 최적값을 보장해 주지 않는다. 맨 처음 나눈 방법에 상당히 의존적인 결과를 가지므로 전체 최적값에 비해 꽤 나쁜 값을 얻을 수도 있다. 그러나 이 알고리즘은 빠르기 때문에 다른 초기값으로 여러번 시도하여 좋은 묶음을 얻어 내곤 한다.
약점이 하나 더 있다면, 이 알고리즘을 시작할 때 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).
[편집] 바깥 고리
- Numerical Example of K means clustering
- Application example which uses K means clustering to reduce the number of colors in images
![]() |
이 문서는 암호학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다. |
분류: 암호학 토막글 | 통계학 | 알고리즘 | Machine learning