7-2. EM algorithm for K-means clustering

---

< 목차 >

1. 용어정의
2. EM algorithm for K-means clustering

---

1. 용어정의

• 피드백 후 작성예정입니다.

---

2. EM algorithm for K-means clustering

D 크기의 차원을 가진 N개의 데이터가 있다고 가정하면, K-means Clustering은 이 데이터들의 분포를 K개의 집단으로 나누는 것이다.

 

K개의 집단으로 구분하기 위해, 데이터셋에 대한 "Distortion measure" 를 구하고 이를 최소화하는데 여기서 "Distortion measure"는 아래의 수식으로 계산된다.

 

여기서 μ_k 는 K번째 Cluster에 관한 평균이고, r_nk는 n번째 데이터가 K 번째 Cluster에 존재하면 '1'의 값을 갖고 아닐 경우 '0'의 값을 갖는다.

 

결국, EM 알고리즘을 적용한 K-means clustering은 J를 최소화하는 r_nk 와  μ_k 값을 찾아내는 것이다.

방법은 Two-step 으로, (1) Expectation step 과 (2) Maximization step으로 크게 구성되며 Distortion measure 의 값이 지정한 특정임계치 아래로 수렴할때 까지 반복(Repeat) 한다.

 

(1) Expectation step

• 모든 K개의 Cluster에 대해서 임의의 초기평균값을 설정하고, J 값을 최소화하는 아래의 r_nk 를 각 데이터마다 할당한다.

 

(2) Maximization step

• 각각의 데이터에 대해 할당된 r_nk 를 고정한 채로 J 값을 최소화하는 μ_k 값을 찾는데, Likelihood method을 이용한다.

 

(3) Repeat E-M

• 마지막으로 모든 데이터에 대한 Clustering이 변화가 없을 때까지 Expectation 과 Maximization(EM) 과정을 반복한다.

 

아래는 소개된 EM algorithm 을 이용해서 특정이미지를 K-means clustering 시킨 결과이다.

 

 

---