[ML / Andrew Ng] Unsupervised Learning - Clustring

이번 챕터에서 알아볼 것은 Unsupervised learning 이다. 이는 앞의 classification 문제와 달리 input만 주어지고 output이 따로 없는 training 인데 이를 어떻게 분류하고 분석할 것인지 알아보자.

위와 같이 데이터가 주어졌을때 우리가 2개의 무리로 분류하고 싶을때 우리는 clustering 이라는 것을 한다. 이를 위해 cluster centroids 라는 것을 정해줘야 하는데 이는 무리의 중심을 설정한다고 보면 된다. 여기서는 cluster centroid를 2개 설정했으며 훈련을 통해 이를 각 cluster의 중심에 위치시킬 것이다.

훈련을 시키기 위해 우선 각 데이터들이 어느 cluster centroid에 가까운지 정해줘야 한다. 빨간색에 가까운 데이터는 다 빨간색으로 파란색에 가까우면 파란색으로 정해주는 식이다. 그리고 이 점들의 평균을 구해 centroid를 그 위치로 옮겨주며 반복해 준다.

여러번 반복하고 나면 더 이상 변하지 않는 것처럼 보이며 cluster centroids의 위치가 수렴될 것이다. 우리는 이와 같은 알고리즘을 K-means 알고리즘이라 하며 여기서 centroid의 개수가 K개이다. 아래에서 이 알고리즘에 대해서 자세히 다뤄보자.

우선 random 하게 cluster centroid K개의 값을 초기화해준다. 그리고 2가지 과정을 반복해야 한다.

 

첫번째로 index of cluster centroid인 c를 갱신해줘야 하는데 이 값은 x(i)에서 가장 가까운 centroid의 index 값이다. 모든 x에 대해 1 부터 K 까지의 cluster centroid 의 거리를 계산하고 이 중 가장 가까운 centroid 를 저장한다. 이 과정을 Cluster assignment step 이라 하며 각 input data에 cluster를 할당하는 과정이다.

 

두번째로 모든 centroid의 위치를 갱신해준다. 이 과정을 Move centroid step 이라 하며 간단하게 각 cluster에 속한 data 들의 위치를 평균내 그 cluster의 centroid 값을 갱신해준다. 위 두 과정을 centroids 가 수렴할 때까지 반복해준다.

K-means 알고리즘이 어떤 식으로 작동하는지 보았으니 이제 최적화를 해보자. c는 각 x의 가장 가까운 centroid의 index 값이고 mu_k 는 k번째 cluster centroid, 그리고 mu_c(i) 는 x(i)가 속한 cluster의 centroid 값이다. 이 값들을 최적의 값으로 만들기 위해 cost function을 이용하는데 오른쪽 아래의 식과 같고 저 함수를 Distortion function이라고 부른다.