[군집]K-평균 알고리즘

 

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

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

 

  K-평균 알고리즘은 두 단계로 이루어져 있다. 첫 번째 단계는 각 센트로이드 위치에 근접한 점들을 찾아서 특정 군집에 할당하는 것이다. 두 번째 단계는 군집의 모든 점들을 좌표평균으로 계산해서 센트로이드 위치를 결정하는 것이다.

이 두 단계 알고리즘이 기대값 최대화(Expectation Maximization)의 전형적인 예라고 할 수 있다.

 EM 알고리즘은 두 단계를 수렴에 도달하기 전까지 반복한다. 첫 번째 단계는 기대(E) 단계로 군집의 기대점(expected point)을 찾는다. 두 번째 단계는 최대화(M) 단계에서 확보한 지식으로 군집 중심의 기대값을 높인다.

 

 머하웃에서 K-평균 알고리즘은 KmeansCluster  또는 KmeansDriver 클래스로 실행 할 수 있다.

KmeanCluster 클래스는 인메모리 형식으로 군집 처리를 한다. 반면에 KmeansDirver 클래스는 K-평균 알고리즘을 맵리듀스 작업으로 실행하는 진입점이다. 두 메소드 모두 일반 자바 프로그램처럼 실행 할 수 있으며, 디스크에서 읽거나 쓸 수 있다. 또한 아파치 하둡 클러스터에서도 두 메소드를 실행할 수 있기 떄문에 분산 파일시스템에서 데이터를 읽거나 쓸 수 있다.