Week 8.2 K-Means Algorithm 2

EM 알고리즘

Latent variable에 대해서 iteratively optimization 해서 목적함수를 최소화 시키는것을 EM 알고리즘이라 한다.

Expectation // Maximization 의 step을 반복수행하는것.

1. Expecation 

- rnk를 Optimization 해주는 과정.

2. Maximization 

- Parameter ( rnk, centroid)를 maximization 해주는 과정. 즉 centroid를 optimize 해주는 과정.

 

처음에는 μk가 랜던값으로 세팅되어 있는데 , 이 랜덤한 μk에 대응하여  rnk , centroid 셋팅을해보는것이다.

이렇게 엉터리 μk에 대해 optimize 된상태의 rnk, centroid를 이용하여 또다시 μk를 업데이트 한다. 이러한 과정을 반복하는 과정을 EM 이라한다.

 

3. rnk

- 1이면 assign 된것, 0 이면 assign 되지 않은것이다.

- discrete variable이라 하지만 현실은 discrete 하지 않다. 이것이 나중에 문제가 될수 있다.

 

4. μk

assign 된 data point 들의 평균값이다. 처음값은 random 값으로 세팅한다.

 

1) μk를 random으로 설정.

2) rnk 를 assign

3) 다시 assign된 point를 모아서, μk를 업데이트

4) rnk를 업데이트

 

위의 1)~4)의과정을 반복 !!

Sum Distance (J)는 반복하다보면 특정값으로 수렴한다.

지금하는것은 Euclidean distance만 생각하고있다.  이것은 모든 clustering 이 원의 형태로 만들어 지고 있다.