k-평균 군집화
알고리즘
Input
$p$차원의 데이터 $N$ 개와 자연수 $k$ 가 주어져있다고 하자.
Step 1. 초기화
$k$ 개의 점 $\mu_{1} , \cdots , \mu_{k}$ 을 랜덤하게 정한다. 각각의 $\mu_{j}$ 는 군집 $M_{j}$ 의 평균이 될 것이다.
Step 2. 거리 계산
$i$번째 데이터 $x_{i}$ 와 $j = 1 , \cdots , k$ 에 대해서 $\| x_{i} - \mu_{j} \|$ 를 계산한다. 그 중 가장 작은 것을 골라 $x_{i} \in M_{j}$ 이 되도록 한다. 이를 각각의 $i = 1 , \cdots , N$ 에 대해 반복한다.
Step 3. $\mu_{j}$ 업데이트
다음의 업데이트를 $j = 1 , \cdots , k$ 에 대해 반복한다. $$ \mu_{j} \gets \sum_{x \in M_{j}} {{ x } \over {| M_{j} |}} $$ 업데이트를 해도 $\mu_{j}$ 들이 더 이상 변하지 않으면 알고리즘을 끝내고, 제대로 업데이트가 되었다면 Step 2. 로 돌아간다.
Output
각 군집의 무게중심인 $\mu_{j}$ 과 각 데이터들이 어떤 군집에 속하는지 반환한다.
- 여기서 $\| \cdot \|$ 는 $l_{2}$-놈 혹은 유클리드 놈, 유쥬얼 놈 등으로 불리는 거리 개념이다.
설명
$k$-평균 군집화는 주어진 데이터를 $k$ 개의 부류로 군집화하는 비지도학습법이다. 위의 삽화들은 특히 $p=2$차원에서 주어진 $N=20$ 개의 데이터를 $k=2$ 개의 부류로 구분하는 것을 나타내고 있다.
평균은 제곱 에러를 최소화하는 대표값이며, $k$-평균 클러스터링은 이러한 수학적 사실을 기반으로 데이터를 잘 분류한다. 더욱 쉽게 설명하자면, 좌표를 더해서 평균을 낸다는 것은 기하학적인 센스에서 무게중심을 의미하므로 $\mu_{j}$ 들이 어떤 데이터의 중심으로 빨려들어가는 것이다. 물론 이를 보장하려면 더 강한 조건과 수식적인 설명이 필요하지만, 애초에 $k$-평균 클러스터링은 단순함이 매력인 알고리즘이므로 이에 대해서 굳이 깊게 파고들지 않겠다.
장단점
가장 큰 문제는 이러한 분류가 별로 정확하지가 않다는 것인데, 이를 보완하기 위한 수많은 알고리즘이 나왔음에도 단순함으로 이 알고리즘을 압도할 알고리즘은 없다. 데이터 사이언티스트의 입장에서 데이터를 받자마자 가장 먼저 시도하는 것은 바로 이 $k$-평균 군집화다. 군집화 한번으로 분석을 끝내려는 게 아니라, 분석을 시작하면서 감을 잡기 위해서 쓰는 알고리즘인 것이다.