34. 자율적으로 학습하기 (Unsupervised Learning) : K means optimization

이번에는 기존의 다른 알고리즘에서 optimization objective를 했던것과 같이 K means 알고리즘에 대한 optimization에 대해서 알아보겠습니다.

c(i)는 각각의 x(i)의 데이터가 갖게되는 cluster의 번호를 의미하며 이 값은 cluster의 k 만큼의 존재하는 수 중에서 하나가 됩니다.

uk는 cluster의 centroid(중심점)가 되는 정보로 k 갯수 만큼 존재합니다.

uc(i)는 x(i)의 데이터가 속하는 cluster에 대한 cluster 중심점을 의미하게 됩니다.

이렇게 구성된 정보를 바탕으로 J 함수가 아래의 그림과 같이 생성이 됩니다. 이 J함수는 cost 함수이면서 또 Distortion 이라고 불리웁니다. 이 함수는 x(i)와 uc(i) 간에 거리의 제곱으로 나타내며 이 두개의 점과 거리를 아래 그림에서 빨간색과 같이 표현을 할 수 있습니다.

그리고 이 J 함수를 minimize 하는 것이 우리의 목표입니다. -> min J ( c(1)...c(m), u1....uk)

K means 알고리즘이 동작하는 기본적인 단계는 아래의 그림과 같습니다.

우선 K 개의 cluster centroids를 임의의 위치에 배치를 합니다.

그리고 cluster centroids 들을 고정시킨 상태에서 거리가 가까운 x data들을 해당 cluster에 속하도록 지정을 합니다.(cluster assignment step)

그런후에 할당된 x 들의 평균값을 가지는 위치로 cluster centroids들을 이동시켜줍니다. (move centroids)

이 두가지 단계를 반복적으로 수행함으로서 최적의 cluster 위치를 찾게 되는 것입니다.

Random Initialization

초기에 cluster centroids의 위치를 random하게 잡는것이 좋다고 했는데 이것에 대해서 좀더 알아보겠습니다.

아래 그림의 경우와 같이 두 분류의 data가 존재하고 K=2인 즉, cluster가 2개로 구성이 된다고 하겠습니다. 임의의 x data를 선정하여 중심점으로 사용하는데 위의 그래프와 같이 아래와 위쪽에 고루 선택이 되었다면 좋은 결과가 있겠습니다만,

아래쪽의 그래프와 같이 한쪽으로 쏠려 위치가 되었다면 어떻게 될까요? 아마도 위쪽의 그래프 보다 좋치 않은 결과를 보여주게 될 것입니다.(local optima)

또 아래와 같은 경우의 데이터를 생각해보겠습니다. 이번에는 3개의 clusters를 구성하려고 합니다.

위쪽의 그래프와 같이 위치가 잡혔다면 아주 운이 좋게 시작될 수 있을겁니다만 아래쪽에 두개의 그래프와 같이 몰려있게 되면 조금 이상하게 결과가 나타나게 될 것입니다. 아마도 오른쪽의 그림과 같이 크게 두 분류가 하나로 묶이고 나머지 한 분류의 데이터가 두개로 쪼개질 것입니다.

그래서 이를 위한 좋은 해결방법이 바로 multiple random initialization 입니다.

아래 그림에서와 같이 반복적으로 100번을 수행하는 것입니다. 임의의 중심점을 잡고 K-means 알고리즘을 돌려서 나오는 cost 함수의 값이 100번 모두 다르게 나오게 될 것인데 이중에서 cost가 가장 작은 값을 가지는 것을 취하는 것입니다.

반복 수행하는 횟수는 약 50회~1000회 정도면 적당한데 이 방법은 cluster의 수가 10개 이하의 경우에 잘 적용이 됩니다. 만약 10개 이상의 cluster를 사용하는 경우에는 위와 같이 local optima가 발생할 가능성이 상대적으로 높기 때문에 많이 수행한다고 더 좋은 결과가 나오지 않을 수도 있기 때문입니다.

Choosing the Number of Clusters

Cluster의 수는 어떻게 선택하는 것이 좋을까요?

아래와 같은 데이터가 있다고 해보겠습니다. 어떤사람은 4개로 분류를 하는게 좋다고 할 수도 있고 또 어떤 사람은 크게 2개로 분류를 하는 것이 좋다고 할 수도 있을 것입니다. 둘가지 방법 모두 나쁘지 않기에 몇개의 cluster가 좋은지 여부에 대한 정확한 하나의 정답이 있다고 보기 어렵다는 것을 알수 있습니다.

이를 위해서 많이 사용되는 방법이 바로 Elbow method 입니다. 간단하게 K를 1개부터 늘려가면서 cost를 비교해 보는 것입니다. 그리고 아래 그림과 같이 그림을 그렸을때 마치 팔의 모양과 같은 그래프가 왼쪽의 그림처럼 나타나면 이때 팔꿈치의 elbow의 K 가 좋다라는 것입니다. 아래 에제에서는 K=3일때가 적절하다고 생각할 수 있겠습니다. 

그러나 오른쪽 그림과 같이 특별하게 보여지는 elbow가 없을 경우도 있기에 항상 좋은 해답을 주는 것은 아님을 알아야 하겠습니다.

또 다른 방법은 우리가 알고자 하는 목적에 맞게 조절을 해보는 것입니다.

아래 그림에서와 같이 티셔츠의 사이즈를 3개로 구분을 하거나 5개로 구분을 함으로서 경영자의 목적에 맞도록 어느 사이즈가 잘 팔리고 어느 사이즈가 인기가 없어서 재고를 줄여야 하는지 등등 보다 세밀하게 분석하기 위한 목적으로서 K의 갯수가 결정이 될 수도 있을 것입니다. 또는 이 두가지의 결과에 대하여 비교 분석도 가능하겠습니다.