[ML] K-평균 군집화(K-means clustering)

---

K-평균 군집화 (K-Means Clustering)

 

지도학습에서는 주어진 레이블이 있어 정해진 클래스로 분류하는 문제를 머신러닝을 통해 해결하지만, 주어진 레이블이 없는 데이터에 대해서는 군집화(clustering)를 통해 클래스를 분류한다. 당연히 유사한 데이터끼리 같은 군집에 묶여야 하기 때문에 유사성을 어떻게 따지느냐가 클러스터링의 핵심이라 할 수 있다.

K-평균 군집화는 다음과 같은 절차로 이루어진다. 우선 데이터 샘플 중에서 무작위로 $ K $ 개의 중심 $ \mu^{(j)} $, $ ( j \in \{1, \cdots, k \} ) $ 를 선택한다. 그 다음 각 샘플 $ x^{(i)} $ 를 가장 가까운 중심 $ \mu^{(j)} $ 에 할당한다. 각 클러스터에 속한 샘플드르이 평균으로 중심을 이동시키고, 클러스터 할당 변화가 없거나 허용 오차(tolerance) 또는 최대 반복 횟수(iteration)에 도달할 때까지 위 과정을 반복한다.

가장 가까운 중심에 할당한다는 것은 데이터 포인트간 유사도(similarity)를 거리(distance)의 반대 개념으로 보는 것이다. 거리는 기본적으로 제곱 유클리드 거리(square Euclidean distance)로 정의되고, 이는 다음과 같다.

$$ d(x, y) = \sum_{j=1}^m (x_j - y_j)^2 = \| x - y \|^2_2 $$

이 거리(metric)를 기반으로 K-평균 알고리즘은 군집화를 군집 내 제곱오차합(SSE)을 최소화하는 최적화 문제로 바꿔 접근한다.

$$ SSE = \sum_{i=1}^n \sum_{j=1}^k w^{(i, j)} \| x^{(i)} - \mu^{(j)} \|^2_2 $$

$$ w^{(i, j)} = \begin{cases} 1 , & \quad x^{(i)} \text{is in cluster } j \\ 0, & \quad \text{otherwise} \end{cases} $$

중심은 다음과 같이 업데이트한다.

$$ \mu^{(j)} = \frac{1}{\lvert C_j \rvert} \sum_{i: c^{(i)} = j} x^{(i)} $$

간단하게 설명했던 절차를 풀어서 설명하면 다음과 같다.

1. $K$ 개의 초기 중심(centroid)을 데이터 공간에서 무작위로 선택한다.
2. 각 데이터 포인트 $ x^{(i)} $ 를 가장 가까운 중심 $ \mu^{(j)} $ 에 할당한다.
3. 각 클러스터에 할당된 데이터 포인트들의 평균을 계산하여 중심을 업데이트한다.
4. 업데이트된 중심을 기준으로 각 데이터 포인트를 다시 가장 가까운 중심으로 할당한다.
5. 할당 결과를 바탕으로 각 클러스터의 평균 위치를 다시 계산하여 중심을 업데이트한다.
6. 다시 한 번 각 데이터 포인트를 가장 가까운 중심으로 할당한다.
7. 할당된 데이터 포인트들의 평균으로 중심을 업데이트한다.
8. 클러스터 할당이 이전 단계와 동일하거나 허용 오차 또는 최대 반복 횟수에 도달하면 알고리즘을 종료한다. 아니라면 2단계로 돌아가서 수행한다.

 

---

K-평균++ (K-means++)

 

기본적인 K-평균은 무작위로 초기 중심을 선택하기 때문에 수렴 속도가 느릴 수 있고, 지역 최적값(local minima)에 빠질 위험이 있다. 이를 보완한 것이 K-평균++로 초기 중심을 보가 효율적으로 선택한다. 절차는 다음과 같다.

1. 빈 집합 $ M $ 을 생성한다.
2. 첫번째 중심 $ \mu^{(i)} $ 를 무작위로 선택하여 $ M $ 에 추가한다.
3. 아직 $ M $ 에 포함되지 않은 각 데이터 $ x^{(i)} $ 에 대해 $ M $ 내 가장 가까운 중심까지의 제곱 거리 $ d(x^{(i)}, M)^2 $ 을 계산한다.
4. 이 거리의 비례 확률(proportional probability)에 따라 다음 중심 $ \mu^{(p)} $ 를 선택한다.
5. $ K $ 개의 중심이 선택될 때까지 3-4단계를 반복한다.

선택확률은 다음과 같다.

$$ p(\mu_p) = \frac{d(\mu^{(p)}, M)^2}{\sum_i d(x^{(i)}, M)^2} $$

K-평균보다 초기화 단계에서 더 고른(cover) 중심을 선택하기 때문에 수렴 속도가 빠르고 더 안정적인, 즉 글로벌 최적(global minima)에 가까운 결과를 얻는 것이 장점이다.

 

---

엘보우 기법 (Elbow Method)

 

앞선 K-평균 클러스터링을 생각해보면 결국 초기값으로 K를 넣어주어야 한다. 그렇다면 어떤 K가 가장 좋은 값인가를 생각해봐야 할 것이다. 여러가지 K값을 선택하는 방법이 있는데, 엘보우 기법은 대표적인 경험적 방법이다.

각 K에 대해 클러스터링을 진행하고, 왜곡(distortion)이 가장 급격히 증가하기 시작하는 K값을 찾아 최적의 K를 찾는다. 왜곡 척도인 속성 관성(inertia)은 SSE로 다음과 같다.

$$ SSE = \sum_{i=1}^n \sum_{j=1}^k w (i, j) \| x^{(i)} - \mu^{(j)} \|^2_2 $$

이를 활용하여 각 K값에 대한 SSE를 계산하고 이를 시각화해본다.

간단하게 위와 같이 시각화되었다면 4에서 더이상 개선되지 않으므로 최적의 K값으로 4를 선택한다. 더 이상 개선되지 않는 지점이 팔꿈치(elbow)와 같아서 엘보우 기법이다.

단 명확한 팔꿈치가 보이지 않을 경우 주관적 판단이 들어갈 수 밖에 없는 한계가 있다.

 

---

실루엣 분석 (Silhouette Analysis)

 

실루엣 지표를 이용하는 방법으로 엘보우 기법과 유사하게 클러스터링 품질을 평가하고 이를 기반으로 최적의 K를 선택한다. 이때 실루엣 계수는 내부적(intrinsic) 척도로 실루엣 계수를 계산하는 개별 실루엣 값은 다음과 같이 계산한다.

$$ s(i) = \frac{b(i) - a(i)}{\max \{ a(i), b(i) \}}, \quad (-1 \leq s(i) \leq 1) $$

여기서 $ a(i)$ 는 군집 응집도(cohesion)으로 샘플 $ x^{(i)} $ 와 동일 군집 내 다른 모든 점들 간의 평균 거리이다.

$$ a(i) = \frac{1}{\lvert C_{c^{(i)}}\rvert - 1} \sum_{j: c^{(j)} = c^{(i)},\, j \neq i} \|x^{(i)} - x^{(j)}\| $$

$ b(i) $ 는 군집 분리도(separation)로 샘플 $ x^{(i)} $ 와 다른 군집 내 가장 가까운 이웃 내 모든 점들 간의 평균 거리이다.

$$ b(i) = \min_{l \neq c^{(i)}} \frac{1}{\lvert C_l \rvert} \sum_{j: c^{(j)} = l} \| \| x^{(i)} - x^{(j)} \| $$

실루엣 값이 클수록, 즉 $ 1 $ 에 가까울수록 잘 분리된 샘플이고, $ 0 $ 에 가까우면 클러스터 경계 근처에 위치한 샘플이며, $ -1 $ 에 가까우면 잘못 할당된 샘플이다.

전체 군집화를 평가하기 위해 평균 실루엣 계수를 계산한다.

$$ S = \frac{1}{n} \sum_{i=1}^n s(i) $$

이 값이 클수록 군집화 구조가 뚜렷하다고 판단하며, 각 $ K $ 값을 확인하고, 가장 실루엣 계수가 큰 K값을 선택한다.