개요
클러스터링은, 라벨이 없는 데이터에서 패턴을 찾는 것을 말한다. 예를 들자면, 이메일을 비슷한 내용끼리 그룹핑하는 것이나, 손님들의 분류를 찾는것과 같이 주어진 데이터를 패턴에 따라서 분류하는 것을 말한다. 클러스터링 알고리즘은 데이터를 요구하나 라벨을 요구하지는 않는다.
Clustering은 수학적으로 similar instances들을 grouping하는 것을 말한다.
K-Means Clustering
K는 클러스터링 할 숫자를 말한다. 알고리즘은 반복을 수행하면서 클러스터링을 수행한다. 사실 이 알고리즘은 Voronoi Graph를 생성하는 것과 매우 비슷한 알고리즘을 가진다. 매우 휴리스틱한 방법이지만, 매우 효과적으로 잘 작동한다.
K means알고리즘은 수렴을 보장하지만, 최적의 해를 구한다는 보장은 하지 못한다. 또한 데이터의 구조가 명확한 패턴이 있으면 이러한 패턴을 잘 잡아내지만 복잡한 구조를 가지고 있으면 잘 잡아내지 못한다. K-Means 알고리즘은 매우 다양한 분야에서 매우 많이 사용된다. 단순하고 간단하지만 매우 효과적인 알고리즘이다.
알고리즘
- K개의 랜덤한 클러스터링 센터를 구한다.
- 각각의 포인트 x에 대해서 K개의 랜덤한 클러스터링 센터중에서 가장 가까운 곳에 클러스터링 한다.
- K개의 클러스터링 센터를 분류된 포인트들의 평균으로 다시 설정한다.
- 새로 클러스터링 되는 포인트가 없을때까지 2부터의 단계를 반복한다.