지난 시간에 k-means 알고리즘에 관해 발표했는데, 당시에는 내용이 너무 쉬워 따로 준비할 필요가 없다고 생각했었지만 막상 발표를 마치고 보니 다루지 못한 부분이 많았던 것 같아 따로 포스팅하게 되었습니다. k-means 알고리즘의 과정을 말로 표현하면 다음과 같습니다.
(1) 랜덤으로 각 클러스터의 중심들을 정한다.
(2) 샘플들로부터 각 클러스터의 중심들까지의 거리를 계산해 가장 가까운 중심이 속한 클러스터에 샘플을 배정한다.
(3) 각 클러스터에 속한 샘플들의 평균을 계산해 그 지점을 클러스터의 중심으로 정한다.
(4) 클러스터의 중심에 변화가 없을 때까지 2 ~ 3을 반복한다.
이후로 https://www.youtube.com/watch?v=8zB-_LrAraw&t=1979s 영상을 보며 알게 된 내용을 적어보겠습니다.
1. 수식
전체 데이터 X를 K개의 군집으로 나누고, 이때의 분할들을 각각 $C_i, i \in {1, 2, … , K}$라 하며, 이 군집들 내부의 데이터를 $x_j \in C_i$, 각 군집의 중심을 $c_i$라 할 때 k-means 알고리즘을 수식으로 표현해보면 다음과 같습니다.
\[argmin\sum_{i=1}^{K}\sum_{x_j \in C_i}\left|\left| x_j-c_i\right|\right|^2\]위 수식을 최소로 하는 $c_i$들을 찾는 것이 k-means 알고리즘의 목표입니다. 이 수식은 k-means 알고리즘의 과정 (2)에서 이야기했던 샘플들로부터 각 클러스터 중심들까지의 유클리드 거리를 모두 더한 것입니다. 여기까지의 이해는 굉장히 쉬웠지만, 동시에 한 가지 의문이 들었습니다.
‘이 알고리즘은 각 클러스터에 속한 샘플들의 평균 = 클러스터의 중심이 될 때까지 반복을 수행한다는 것인데, 그것이 유클리드 거리의 합을 최소로 만든다는 것과 같은 의미가 되는가?’
직관적으로는 그럴 것 같다는 생각이 들었지만, 확실한 해답을 얻고 싶어 직접 증명해 보았습니다.
2. 각 클러스터에 속한 샘플들의 평균 = 클러스터의 중심이 된다는 것의 의미
임의의 클러스터 $C_i$에 속한 샘플들이 n개 있다고 합시다. 이 샘플들은 $x_j \in C_i, j \in {1, 2, … , n}$이라 쓰겠습니다. 또한, 이 군집의 중심은 $c_i$일 때, 각 샘플들로부터 클러스터 중심까지의 거리는 다음과 같이 표현할 수 있습니다.
\[(c_i-x_1)^2+(c_i-x_2)^2+ ... +(c_i-x_n)^2\]이들 제곱을 풀어 식을 전개하고, $c_i$에 관한 내림차순으로 다시 묶어 살펴봅시다.
\[nc_i^2+2((x_1+x_2+... +x_n)/n)c_i-((x_1+x_2+... +x_n)/n)^2+(x_1^2+x_2^2+...+x_n^2)\]이 2차함수는 $c_i=(x_1+x_2+… +x_n)/n$에서 최솟값을 가지며, 이것은 각 클러스터에 속한 샘플들의 평균이 됩니다.
따라서, 각클러스터에 속한 샘플들의 평균이 클러스터의 중심이 될 때에 k-means의 목표인 유클리드 거리의 합을 최소로 만드는 것을 달성할 수 있게 됩니다.
3. k-means 알고리즘의 한계
k-means 알고리즘은 샘플들이 중심으로부터 얼마나 떨어져 있느냐를 따질 뿐, 해당 클러스터의 샘플들이 얼마나 밀집되어 있는지, 클러스터가 얼마나 큰지 같은 부분은 판별하지 못합니다. 이처럼, k-means 알고리즘이 중심으로부터 각 샘플 사이의 유클리드 거리 합을 최소화하는 것을 목표로 하기 때문에 갖게 되는 한계점들이 있습니다.
(1) 군집들 사이의 크기 또는 밀도가 크게 차이날 때 잘 동작하지 못한다.
(2) 단순히 뭉쳐있는 것이 아니라 패턴이 존재하는 군집을 판별하기 어렵다.
이너셔를 줄이기 위한 방향으로 알고리즘을 진행해 나가다 보면, 크기가 큰 군집을 그대로 두면 당연히 중심에서부터의 거리가 멀어질 것이고, 자연스럽게 이 군집을 여러 개로 쪼개 버릴 것입니다. 또한, 어떤 모양을 이루고 있는 경우에는 그 모양을 전혀 알아내지 못하고 중심에서의 거리에 따라 군집을 나누어 버릴 것입니다.