[ML개론] (24) K-Mean Algorithm

이제 Regression을 활용한 Classification 말고 non-labeled data에 대한 Clustering을 진행해보자.

가령 좌측그림과 같이 서로 세가지의 다른 label을 지닌 data가 x1, x2에 대해 다음과 같이 산포되어있다고 가정하자. 

이들은 서로 다른 label을 지닌 다른 타입의 data지만 우리가 지닌 sample dataset에는 이들의 label이 없다. 즉 이전까지 살펴본 지도학습의 경우 정답에 해당하는 label이 있었기 때문에 그 정답과 예측치의 오차를 줄이는 방식으로 classification을 진행했지만 clustering은 label이 없기 때문에 조금 다른 방향으로 학습을 진행한다. 이를 비지도학습이라 부른다.

 

그 중 K-Means Clustering과 Gaussain Mixture Model에 대해 배워보자. 

우선 직관적인 학습 알고리즘을 소개하자면 다음과 같다. 우선 K개의 중점을 지정한다. 그리고 data를 가까운 중점을 기준으로 군집화한다. 이러한 알고리즘을 수차례 반복하면서 적절한 중점과 적절한 군집화를 학습해나가는 것이 K-Means Algorithm이라 할 수 있겠다 .

mu_k가 k번째 centroid의 vector값, x_n이 특정 input data x의 vector값, r_nk는 n번째 data가 k번째 cluster에 속하는지 여부를 나타낸다고 가정하면, 우리의 목적은 J(=r_nk*||x_n - mu_k||^2)의 합을 최소화해주는 것이 되겠다. 이는 앞서 살펴봤듯이 centroid의 위치를 조정하는 작업과 할당여부를 결정하는 작업을 통해 최소화된다. 

 

비슷한 알고리즘 중 K-nearest Algorithm이 존재한다. 가령 근방 6개의 neighbor 중 4개가 red, 2개가 blue면 해당 지점을 red로 판단하는 것이다. 그러나 이는 K-means와 근본적 차이가 존재하는데 해당 지점이 red, blue인지에 대한 명확한 정보가 필요하니 labeling이 동반되어야하기에 이는 지도학습의 일종인 것이다. 

 

 

다시 K-means로 돌아와서, 그 optimization algorithm을 살펴보자.

우선 Expectation phase를 거친다. 이는 주어진 parameter에 의한 log-likelihood의 기대값을 구하는 과정이다. 즉, mu_k에 대한 값이 주어지면 실제 data와의 L2 norm을 구하고, 그들의 합을 minimize해주는 방향으로 r_nk를 할당한다.

그러고나선 Maximization phase로 들어선다. log-likelihood를 극대화할 수 있는 parameter를 할당하는 과정이다. 이 땐 mu_k를 업데이트해나가면서 확률을 극대화한다.

맨 처음에는 mu_k가 random하게 setting되어있을테니 r_nk를 이에 optimize하고, 그 r_nk를 기반으로 mu_k를 멀쩡한 방향으로 optimize하는 것을 반복한다. 이 때 J를 mu_k로 편미분하여 optimized mu_k에 대한 식을 구할 수 있다. 이는 assigned x_n에 대한 평균값과도 같다. 

 

우선 mu_k를 random값으로 initialize하고, r_nk를 이 mu_k에 대해 assign한다. 그리고 E(r_nk*X_n)을 극대화하며 EM 알고리즘을 반복한다. K-means의 단점은 다음과 같다. 

첫째, cluster의 갯수 K는 어떻게 구할 것인가? (A. Bayesian parameter)

둘째, mu_k의 initial location은 어떻게 정할것인가? (A. random number, try multiple time)

셋째, mu_k와 x_n의 거리는 어떻게 측정할것인가? 유클리드 거리에만 의존하는 것은 문제가 있다. 가령 음수에서 1도 움직이는 것보다 양수에서 1도 움직이는 것이 더욱 중요한 것일 수 있기 때문.

넷째, Hard clustering이 아닌 soft clustering이 필요하다. 

 

GMM은 세번째, 네번째 문제를 해결할 수 있다.