K-means Clustering

클러스터링 기법 중에 대표되는 것으로 다차원 입력 데이터를 어떻게 어떤 그룹에 속하게 할지에 대한 문제를 다룬다. 

데이터의 집합을 정의하자.

N개로 이루어져 있는 데이터를 K개의 클러스터로 분류하려고 한다(물론 K는 미리 지정한다). K개의 클러스터 정 중앙에 놓여 있는 값을 μk라고 표기 한다.

K-means 클러스터링의 아이디어는 K개의 mean(중앙 값)을 이용해 클러스터링 하는 것이다. μk와 이에 속하는 클러스터 데이터 사이의 거리의 총합은 클러스터에 속하지 않는 데이터 사이의 거리의 총합보다 작다. 그러므로 우리의 목표는 주어진 데이터 집합으로부터 이러한 중심 μk의 값을 결정하는 것이다. 

N개의 데이터를 K개의 클러스터로 구분지어 Sk = {S1, S2, ... SK}의 데이터 집합으로 구분한다면, μk가 Sk의 중심이므로 

각 데이터 집합별 중심과 집합 내 데이터간의 거리(유클리디안 거리, Euclidean Distance)의 제곱합을 최소화하는 데이터 집합 S를 찾는 것이 목표이다. 

다른 식으로 함수를 정의하기 위해 바이너리 변수 rnk를 도입하자.

rnk는 n번째 데이터 xn이 k번째 클러스터에 속할 경우는 1, 속하지 않을 경우는 0로 정의되는 변수이다. 의미적으로는 위의 argmin 식과 같은데, 함수 J를 왜곡 측정(distortion measure) 함수라고 한다. 마찬가지로 이 J를 최소화하기 위해서 rnk와 μk를 구해야 한다.

이를 위해 반복적인 절차의 계산을 게 된다.

1. 먼저 임의의 값으로 μk를 초기화한다.
2. μk가 정해졌으므로 J를 최소화하는 rnk를 구한다.
3. 새롭게 얻어진 rnk를 고정하고 μk를 구한다.
4. J가 적당한 값으로 수렴하거나 적당한 반복 횟수에 도달할 때까지 2~3의 과정을 반복한다.

rnk가 구해지는 과정을 먼저 살펴보면, N개의 데이터는 각각에 대해 서로 독립이므로 rnk도 각각의 n에 대해 따로 최적화하면 된다. 즉, 다른 샘플과의 연관을 고려할 필요 없이 현재 샘플에 대한 가장 타당한 값을 선택하면 된다.

복잡하게 생각할 필요없이 n번 째 샘플은 K개의 클러스터 중심과의 거리를 계산하여 가장 가까운 것을 선택하면 된다.

다음으로 μk에 대해 알보자. 앞에서 rnk를 구했으므로 이를 고정하고, 목적함수 J가 이차함수이므로 이를 미분하여 0이 되는 지점이 죄소값이므로 이를 통해 구할 수 있다.

이를 μk에 대해 정리하면,

결국 클러스터 k에 속한 x에 대한 평균을 구하는 것이 된다. 

위의 그림을 보면 이해가 쉬울 것이다.

• (a)는 라벨링 되지 않은 데이타가 존재할 때 임의의 두 개의 클러스터 중심을 초기화 하는 것다.
• 그 다음 μk를 고정해 두고 rnk를 구해 1차적으로 데이터를 클러스터링 한다. (b)
• 나뉘어진 데이터를 기준으로 다시 μk를 구하면 (c)와 같이 중심점이 이동을 하게된다.
• 다시 μk를 고정해 두고 rnk를 구해 데이터를 (d)와 같이 다시 라벨링하여 구분한다.
• 이와 같은 과정을 반복하여 μk가 어느 정도 수렴하거나 정해진 반복횟수만큼 수행할 때까지 계속 업데이트 한다.

클러스터링 과정을 애니메이션화 하면 아래 그림과 같다.

왜곡 측정함수 J는 업데이트가 반복해서 수행될 수록 값이 작아지면서 일정 값으로 수렴을 하게 될 것이다.

K-means Clustering을 비교적 간단한 수식을 통해 기준값이 주어지지 않은 데이터를 분류하는 Unsupervised Learning의 한 방법이다. 이보다 더 개념적으로 확장한 알고리즘으로 GMM, Gaussian Mixture Model이 있으며 다음의 포스팅을 참고하기 바란다.

>> GMM, Gaussian Mixture Model