UnSupervised Learning - K means Algorithm

* 첨부된 자료의 모든 저작권은 COURSERA에 있음을 미리 밝힙니다

Unsupervised Learning

- K means Algorithm

지금까지 살펴본 기계학습 방법들은, (크게는 Linear Regression과 Logistic Regression을 사용한 분류 방법부터

좀더 구체적으로는 Linear Regression, One vs One, One vs All 까지)

 모두 지도학습 (Supervised Learning) 을 통해 데이터를 훈련시켰다.

Supervised Learning 이란 데이터셋을 제공할 때 이 데이터 셋이 출력해야 하는 결과값(y)까지 제공하는 것으로

주어진 데이터를 훈련시켜 알고리즘이 어떤 결과를 가져와야 하는지를 알려주는 훈련 방법이다.

예를 들면 위 그림과 같다. x1, x2를 제공하면서 각각의 x1, x2를 가진 데이터가 O로 표현되어야 할지, X로 표현되어야 할지까지도 입력해준다. 반대로 비지도학습 (Unsupervised Learning)의 경우, 데이터 셋만 제공할 뿐, 이 데이터가 어떻게 그룹화되어야 할지, 어떤 결과를 출력해야 할 지에 대해서는 입력해주지 않는다. 예를 들면 아래 그림과 같다. 아래 그림의 경우 x1, x2의 좌표값을 가진 데이터만 제공할 뿐, 이 데이터가 어떻게 분류되어야 할 지는 알려주지 않는다.

이렇게 어떻게 그룹을 지어야 할지에 대한 명확한 가이드 라인이 제공되지 않는 학습 방법을 비지도학습 (Unsupervised Learning)이라 하고, 그룹을 지을때는 주로 Clustering Algorithm을 이용하여 그룹을 만들어 준다. (아래 그림의 파란색 원으로 묶은 부분이 그룹화 한 결과이다.)

K - means Algorithm

위에서 간단하게 비지도학습의 개념과 Clustering에 대해서 살펴보았다. Clustering이란 특정 영역에 모여있는 데이터들을 하나의 그룹으로 매핑해 주는 것이다. 위의 예제에서 10개의 데이터를 2개의 Cluster(그룹)으로 나눠준 것과 같다. 

이 Clustering Algorithm 중에서 가장 많이 쓰이는 것이 바로 K - means Algorithm이다.

K - means Algorithm의 핵심원리는 다음과 같다. (예제를 통해 살펴보자.)

1. K를 설정하고, 주어진 데이터셋에 K개의 Centroid를 지정한다. (K = 분류할 그룹의 개수)

2. Cluster Centroid를 기준으로 각 Centroid에 가까운 데이터들을 인덱싱한다.

예를들어 데이터 x1이 Centroid 1에 가장 가까운 경우 x1은 Centroid 1으로 (즉, 그룹 1로) 분류하는 것이다.

3. 특정 Centroid로 분류된 모든 데이터들의 Mean을 구해서 그 Mean을 새로운 Centroid 값으로 정한다. 

즉 Centroid 1을 기준으로 분류된 모든 데이터들의 평균을 다시 새로운 Centroid 1의 위치로 삼는것이다. 

그리고 이를 K - Means Algorithm의 Cost Function이 최솟값을 가질 때까지 반복한다. 

K - Means Algorithm의 Sudo Code는 다음과 같다.

Centroid를 정하고, 그 Centroid에 가까운 점들을 평균내서 그 값을 새로운 Centroid값으로 만들고, 이를 Cost Function이

최소가 될 때까지 반복하는 알고리즘이라고 할 수 있다.

K - Means optimization objective & Random initialization

K - Means Algorithm이 최적 Cluster들을 분류하기 위해서는 CostFunction을 최소화할 수 있는 Centroid들을 찾아내야 한다. 

CostFunction은 분류된 각각의 점들이 해당되는 각각의 Centroid들과 얼마나 멀리 떨어져 있는가에 대한 값으로 구성이 되며

이 값을 최소화하는 Centroid들을 찾아내면 된다.

K - Means Algorithm을 수행하기 전에 한 가지 짚고 넘어가야 할 부분은 바로 Random initialization이다.

Clustering Algorithm의 특성상 데이터를 그룹으로 분류할 수 있는 경우의 수가 굉장히 많기 때문에 처음에 initialization을 어떻게 해 주느냐에 따라 CostFunction의 최솟값이 Local Optima, 즉 국부적인 최솟값에 머물러 있을 가능성이 높다. 

즉, 처음에 initialize 된 Centroid들의 기준에서는 최솟값을 구하겠지만 애초에 다른 방식으로 initialize 되었더라면 훨씬 더 최적의 분류를 할 수 있었을 것이라는 이야기이다. 그래서 K - Means Algorithm을 Centroid들을 랜덤하게 initialize하여 수행하는 편이 좋다.