K-평균 알고리즘

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

K-평균 알고리즘(K-means algorithm)은 주어진 데이터를 k개의 클러스터로 묶는 알고리즘으로, 각 클러스터와 거리 차이의 분산을 최소화하는 방식으로 동작한다.

이 알고리즘은 EM 알고리즘을 이용한 클러스터링과 비슷한 구조를 가지고 있다.

알고리즘[편집]

i번째 클러스터의 중심을 \mu_i, 클러스터에 속하는 점의 집합을 S_i라고 할 때, 전체 분산은 다음과 같이 계산된다.

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

이 값을 최소화하는 S_i을 찾는 것이 알고리즘의 목표가 된다.

알고리즘은 우선 초기의 \mu_i를 임의로 설정하는 것으로 시작한다. 그 다음에는 다음의 두 단계를 반복한다.

  • 클러스터 설정: 각 점에 대해, 그 점에서 가장 가까운 클러스터를 찾아 배당한다.
  • 클러스터 중심 재조정: \mu_i를 각 클러스터에 있는 점들의 평균값으로 재설정해준다.

만약 클러스터가 변하지 않는다면 반복을 중지한다.

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

성질[편집]

이 알고리즘은 간단한 구조를 가지고 있고 많은 환경에서 빠르게 수렴하기 때문에(보통은 처음 주어진 데이터의 개수보다 훨씬 적은 반복만 필요하다) 널리 사용된다. 하지만 이 알고리즘이 다항을 넘는(superpolynomial) 시간(2^{\Omega(\sqrt{n})})이 걸리는 경우도 존재한다. Smoothed analysis 경우의 복잡도는 다항 시간이다.

이 알고리즘은 전역 최적값을 보장해 주지 않는다. 맨 처음 나눈 방법에 상당히 의존한 결과가 나오므로 초기 클러스터 설정에 따라서는 실제 최적값보다 꽤 나쁜 값을 얻을 수도 있다. 이를 방지하기 위해서는, 서로 다른 초기값으로 여러 번 시도하여 가장 좋은 결과를 사용하는 기법 등을 사용할 수 있다.

또한, 이 알고리즘은 구하려는 클러스터의 갯수를 미리 정해 두어야 한다. 클러스터 갯수를 너무 많이 설정하면 큰 클러스터가 여러 개로 나뉘는 결과를 얻을 수도 있다.

참고 문헌[편집]

  • 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).

바깥 고리[편집]