개요
K는 클러스터링 할 숫자를 말한다. 알고리즘은 반복을 수행하면서 클러스터링을 수행한다. 사실 이 알고리즘은 Voronoi Graph를 생성하는 것과 매우 비슷한 알고리즘을 가진다. 매우 휴리스틱한 방법이지만, 매우 효과적으로 잘 작동한다.
K means알고리즘은 수렴을 보장하지만, 최적의 해를 구한다는 보장은 하지 못한다. 또한 데이터의 구조가 명확한 패턴이 있으면 이러한 패턴을 잘 잡아내지만 복잡한 구조를 가지고 있으면 잘 잡아내지 못한다. K-Means 알고리즘은 매우 다양한 분야에서 매우 많이 사용된다. 단순하고 간단하지만 매우 효과적인 알고리즘이다.
알고리즘
- K개의 랜덤한 클러스터링 센터를 구한다.
- 각각의 포인트 x에 대해서 K개의 랜덤한 클러스터링 센터중에서 가장 가까운 곳에 클러스터링 한다.
- K개의 클러스터링 센터를 분류된 포인트들의 평균으로 다시 설정한다.
- 새로 클러스터링 되는 포인트가 없을때까지 2부터의 단계를 반복한다.
Agglomerative Clustering
우선 가까운 요소들을 merging시키고 이러한 작업을 점점 넓혀간다.이러한 작업을 하면 tree와 같은 유사도를 가지는 구조가 얻어진다. 이러한 tree구조에서 level of clustering을 정하면 적절하게 clustering작업이 이루어지게된다. 즉 K-Means와 비슷하게 서로 비슷한 것끼리 묶는 작업이 있지만, K값에 대한 서술이 필요없다. 그렇다면 이러한 작업에서 closes를 어떻게 정의하는냐의 문제가 있다.