K-Means 클러스터링 마스터하기

K-means는 partitioning method 클러스터링의 대표적인 예다.

클러스터의 centroid와 클러스터 내 점들 간의 거리(정확히는 거리 제곱 합)가 최소가 되도록 k개의 클러스터를 만드는 기법이다.

 

즉, 아래가 최소가 되도록 하는 클러스터 k를 만드는 것이 k-means라고 정리할 수 있겠다.

$$\sum_{m=1}^{K}\sum_{i=1}^{Nm}(C_{m}-t_{i}^{m})^{2}$$

* C_m은 m 번째 cluter의 centroid, t는 m번째 cluter에 속한, i번째 datapoint를 가리킨다.

 

사실 위 식이 최소가 되도록 하는 partition을 찾기 위해서는, 모든 가능한 partition을 시도해보아야 한다.

현실적으로 불가능한 방식이다.

따라서, 클러스터를 centroid로 대표하는 방식을 대신 사용하는데, 이것이 k-means이다.

---

 

Steps

어떻게 k-means가 작동하는지 아래 단계를 살펴보며 이해해보자.

1. k 개의 random한 좌표를 centroid로 지정하고, centroid를 중심으로 k개의 cluster를 partition한다.

2. 나눈 현재 partition의 클러스터 centroid를, seed point로서 새로 계산한다. (Compute)

3. seed point에서 가까운 점을 같은 클러스터로 할당한다. (Assign)

4. 클러스터 assign이 바뀌지 않을 때까지 2, 3을 반복한다.

 

그림으로 설명하면 아래와 같은 과정으로 이루어질 것이다.

centroid 계산과 할당이 반복되는 것을 확인할 수 있다.

---

 

Optimization 관점에서의 K-means

이러한 k-means의 작동방식을, 모델 파라미터 최적화의 관점에서도 해석해보자.

아래는 k-means 알고리즘의 Loss Function이다.

$$L = \sum_{i=1}^{N}\sum_{m=1}^{k}z_{i}^{m}*||t_{i}-c_{m}||^{2}$$

즉, loss를 최소화하는 z를 할당하기 위해 c와 z를 반복해서 설정, 변경하는 것이 k-means라고 이해할 수 있겠다.

---

 

강점과 약점

partitioning method의 대표적인 방식인 만큼, 비교적 시간복잡도가 낮다는 장점이 있다. (O(nkt))

하지만, k(클러스터의 수)를 미리 정해야 한다는 점,

noise와 outlier를 다루는 것이 불가능하다는 점,

다양한 형태의 데이터 (특히 non-convex shape)의 클러스터에 맞지 않다는 점,

centroid를 활용한 heuristic한 partitioning이라는 점 등이 한계점으로 꼽힐 수 있겠다.