Week 8.1 K-Means Algorithm 1

Unsupervised learning 인 K - Means 알고리즘에 대해 알아보겠습니다.

 

먼저 Supervised learning 과 Unsupervised learning 에 대해 알아보자. Supervised leaning은 training case를 제공받아 분석을 해서 미래에 올 testing case 대해 가장 likely한 hypothesis를 찾아 내는 training 된 결과물이다. (Supervision을 준다 혹은 가이드를 준다는 의미이다.)

 

Unsupervised learning 은 tag가 없는것이다. True value를 모르는 상황에서 , 패턴을 찾아보는 것이다.

스팸과 스팸 아닌 이메일 이 있다고한다면 스펨메일의 그룹 , 스펨이 아닌 메일의 그룹 , 두 군집을 찾고 스팸인지 스팸이 아닌지는 나중에 알아봐야되것이지 Training 된 case가 없기 때문에 군집만 찾아내고 이게 어떤 내용인지는 알기 어렵다.

 

제공된 Dataset에서 "초록 데이터 / 빨간 데이터 / 파란데이터 "다 라는것을 이미 받아놓고 있다 (트레이닝할 수 있는 true value가 있다)라고 하면 Supervised learning 이다. ( 위의 좌측 그림 )

 

실제 Unspervised learning은 점들이 많이 찍혀 있는 상황에서 점들에 대한 개별적인 태그가 없다.(기준을 잡을수 있는 true value가 없다) 이런 상황에서 내부의 어떤 동력에 의해 어떤 군집이 만들어지는가를 찾아내는것이 unsupervised learning이다. 우리가 hidden variable이 있어서 이것들을 찾아내는 과정이다. 즉 latent variable의 optimal assignment 를 찾는것이 주 목적이다. 

 

Clustering은 같은 군집내에서 latent factor를 공유하고 있다는 것을 짐작할 수 있다. 하지만 uncertain area 의 경우는 어떻게 판별해야할지가 Clustring 의 문제점이 된다.

 

 

K-means Algorithm

- 내부적인 동력이 K 개쯤이 있다. K개의 내부동력에 의해서 n개의 데이터 포인트가 발생하겠다고 생각하는것이다.

K-Means 와 K-Neareat Neighbor는 다른 개념이다. K - Means 는 군집을 찾는 목적이다.

K-Nearat Neighbor는 특정 범위내에 있는 K개의 이웃을 기준으로 판정을 내리는것이다. 근처 Value의 truth value를 알아야한다. 즉 Supervised learning을 위한 목적이다.

 

K-Neareat Neighbor

예를들면 위 동그라미 부분에 새로운 점이 관측되었다고 하자. 이것이 빨간점인지 파란점인지 구분을 해보자. 특정범위내에 있는 K개의 이웃을 찾는것이다. 6개의  이웃을 찾아봤더니 4개는 빨간색이고 2개는 파란색이였다. 즉 여기있는 검은색점은 아마도 빨간색이지 않을까라고 판정을 내리는것이다. 

 

K-means algorithm

K-means algorithm은 우리가 실제 보는것은 검은색점들 밖에 없다. 이것들을 optimal assign 하려고한다.

여기 군집의 Centroid(중심)는 주어지지 않지만 이것을 알아내야한다.

 

즉 K-means algorithm은 아래와 같이 2단계로 진행된다.

1) Centroid를 찾아야한다.

2) 개별 점들을 가까이 있는 Centroid에 assign해야한다.

 

이것을 수식적으로 표현해보자.

 

μk 는 Centroid 이고, Xn은 개별 데이터 point 이다. rnk는 assingment 에 대한 정보이다. 즉 개별데이터 포인트 곱하기 개별클러스터 Centroid 갯수로 되어있다. 하나의 개별데이터 포인트는 하나의 Centroid 에만 assing 할수 있다.

그래서 rnk 가 rij 라하면 i번째 관측된 x 포인트가 j번째 Centroid로 assign 되겠다는것만 표현하면 된다. 

즉 assign 된 1건의 case에 대해서는 1로 표현 하고 , assign 되지 않은  다른 centroid에 대해서는 0으로 만들어 주겠다는 것이다. 즉 rnk 에 대해서 1 혹은 0으로 만들어 주겠다는 것이다.

이 수식에서는 rnk와 μk 를 조절하면서 J를 줄여가는 과정이 K - means algorithm 이다. 이것을 어떻게 Optimize 할수 있을까? Iterativly optimize 해야한다.  rnk를 한번 optimize 해주고 ,  이 rnk 를 이용해 μk를 optimize 해주고 이것을 반복적으로 loop를 돌아서 전체를 optimize 해야한다.