[Machine Learning] Unsupervised Learning 비지도 학습

해당 내용은 Andrew Ng 교수님의 Machine Learning 강의(Coursera)를 정리한 내용입니다.

 

[Clusterning]

이전까지는 supervised learning 지도학습에 대해서 이야기를 했었고, supervised learning은 아래처럼 주어진 training set과 이에 해당하는 label이 존재했다. 따라서 그래프를 봐도 명확하게 구분이 된다.

하지만, unsupervised learning 비지도 학습은 아래처럼 label이 없고 단지 Training set만 존재한다.

그렇기 때문에, 우리는 이 data를 가지고 어떠한 구조를 가지는지 찾아야하고, 이것을 Unsupervised Learning이라고 한다. 우리는 Training Set을 비슷한 특성을 가진 data끼리 Cluster로 묶는 방법인 Clustering Algorithm을 먼저 알아볼 것이다. 다른 종류의 unsupervised learning도 있고, 나중에 알아볼 것이다.

 

- K-means Algorithm

이렇게 Clustering Algorithm 중 하나는 K-means Algorithm 이다.

위 그래프와 같이 training set으로 초록색 점들을 갖는 데이터가 있을 때, 우리는 Cluster Centroid라는 점을 random하게 정한다. 여기서는 Cluster Centroid로 2개를 사용했다. 우리는 매 순환(iteration)을 통해서 이 Centroid를 최종적으로 각 Cluster의 중간에 위치시킬 것이다.

우선 두 개의 Cluster Centroid를 랜덤하게 정했으면, 모든 training set에 대해서 어느 cluster centroid에 가까운 지 나타낼 수 있다. 여기서는 빨간색 cluster와 파란색 cluster로 나누어져 있다. 우리는 각 cluster에 해당하는 모든 점들의 평균을 구하고, 그 평균으로 Centroid를 옮긴다. 그렇게 옮기면 아래와 같이 될 것이다.

그리고 모든 Training Set에 대해서 변경된 Cluster Centroid 중에 어느 cluster가 가까운지 다시 정하면 아래와 같이 변경될 것이다.

이 방법을 반복하다 보면 결국 바뀌지 않는 Cluster Centroid로 수렴하게 될 것이고, 아래와 같이 Cluster가 결정된다.

 

K-means 알고리즘에서 입력은 K와 Training Set이다. K는 cluster의 개수이며, 우리가 결정해야되는 파라미터이다. 어떻게 선택해야 하는지는 조금 있다가 이야기를 할 것이다.

그리고 K-means algorithm은 다음과 같은 방법으로 진행된다.

우선 Random하게 K개의 Cluster Centroid의 값을 초기화한다. 이 값은 다음과 같이 표기한다.

\[\mu_1, \mu_2, \cdots, \mu_k \in \mathbb{R}^n\]

그리고 아래 과정을 반복한다.

1) 모든 training set에 대해서 어느 cluster(1 ~ K)에 가까운지 확인하고 해당 cluster의 index를 저장하는 \(c^{(i)}\)를 갱신한다. 이 과정이 Cluster assignment step, 각 training example에 cluster를 할당하는 과정이다.

가까운 cluster는 다음과 같은 식을 통해서 구한다.

\[\underset{k}{min} \left \| x^{(i)} - \mu_k \right \| ^2\]

2) 모든 Cluster 개수 K에 대해서 각 클러스터에 속해있는 training set에 대해서 평균을 구해서 각 \(\mu\)값을 갱신한다. 예를 들어서, \(x^{(1)}, x^{(5)}, x^{(6)}, x^{(10)}\)이 속하는 cluster가 \(c^{(1)} = 2, c^{(5)} = 2, c^{(6)} = 2, c^{(10)} = 2\) 일 때, 갱신되는 \(\nu_2\)의 값은 다음과 같다.

\[\mu_2 = \frac{1}{4}(x^{(1)}, x^{(5)}, x^{(6)}, x^{(10)}) \in \mathbb{R}^n\]

이 과정이 Move Centroid Step 이다.

 

우리는 위 두 step을 Centroid가 수렴할 때까지 반복하면 된다.

 

K-means 알고리즘은 명확히 분류하기 힘든 데이터에 대해서도 분류할 수 있다. 아래와 같은 데이터의 경우에도 잘 분류해준다. 아래 그래프는 키와 몸무게에 따른 T-Shirt 사이즈이다.

 

- Optimization objective

다음으로 K-means 알고리즘을 최적화하는 방법에 대해서 알아보자.

여기서 \(c^{(i)}\)는 각 training set \(x^{(i)}\)가 속하는 Cluster의 Index이고, \(\mu_k\)는 Cluster k의 Centroid 값이다.(\(\mu_k \in \mathbb{R}^n\))

그리고, \(\mu_{c^{(i)}}\)는 \(x^{(i)}\)가 속하는 Cluster의 Centroid 값이다.

즉, 어떤 i에 대해서 \(x^{(i)} = 5\)이고, \(c^{(i)} = 5\)이면 -> \(\mu_{c^{(i)}} = \mu_5\)가 된다.

 

위 강의자료에서 보면 알 수 있듯이, K-means 알고리즘도 Cost J 함수를 최소화하는 \(c^{(i)}, \mu_k\)를 찾는 것이다. 

Cost는 아래와 같이 나타내고, Distortion function이라고 불린다.

\[\begin{align*} &J(c^{(1)}, \cdots, c^{(m)}, \mu_1, \cdots, \mu_K) = \frac{1}{m}\sum_{i = 1}^{m} \left \| x^{(i)} - \mu_{c^{(i)}} \right \| ^2 \\ &\underset{\underset{c^{(1)}, \cdots, c^{(m)}}{\mu_1, \cdots, \mu_K}}{min} J(c^{(1)}, \cdots, c^{(m)}, \mu_1, \cdots, \mu_K) \end{align*} \]

 

다시 K-means 알고리즘에서 살펴보면, Cluster assignment step에서는 Cluster Centroid \(mu_k\)가 고정된 상황에서 각 training example \(x^{(i)}\)의 cluster index 값인 \(c^{(i)}\)의 값을 사용해서 cost를 최소화 하는 것이다(각 example이 최적의 cluster에 배정되는 것). Move centroid step에서는 \(c^{(i)}\)가 고정된 상태에서 \(\mu_k\)의 값을 사용해 cost를 최소화 하는 것이다(각 cluster의 최적 centroid를 구하는 것).

 

- Random initialization

이번에는 K개의 Cluster의 centroid를 선택하는 방법에 대해서 알아보자.

먼저 Cluster의 개수 K는 데이터의 수 m보다 작아야 한다. 

우리가 사용할 수 있는 방법 중 한 가지는 K개의 centoird 값을 K개의 example과 동일하게 두는 것이다. (\(\mu_1 = x^{(1)}, \mu_2 = x^{(2)}, ...\))

초기값이 잘 선택되었다면 위 그래프와 같이 고르게 초기화되지만, 제대로 초기값이 설정되지 않아 제대로된 Clustering을 못하는 경우도 생긴다.

이렇듯, K-means 알고리즘은 초기화에 따라서 다른 결과가 나타날 수 있고, 최악의 경우에는 Local Optima에 도달한다.

 

초기화가 잘 되었다면 위의 그래프처럼 Clustering될 수 있지만, 운이 나쁘다면 아래 두 그래프처럼 제대로 Clustering이 되지 않을 수 있다.

 

그렇다면 이 문제를 어떻게 해결해야 할까?

우리가 사용할 수 있는 한 가지 방법을 랜덤 초기화를 여러번 반복하여 알고리즘을 학습해서, 가장 좋은 모델을 선택하는 것이다.

랜덤 초기화를 50 ~ 1000번 정도 수행해서 각각의 랜덤 초기화 값에서 K-means 알고리즘을 수행해서 학습하고 Distortion Function으로 Cost를 계산한다. 그리고 cost가 제일 낮은 모델을 찾아서 선택한다.

Cluster의 개수가 적을수록 Local Optima에 빠질 확률이 높기 때문에, 이 방법은 K가 2 ~ 10개로 적을 때 효과가 좋다.

 

- Choosing the Number of Clusters

K-means 알고리즘을 처음 설명하면서 우리는 Cluster의 개수 K를 설정해주어야 한다고 했고, 어떻게 설정하면 되는지 알아보자. 

사실 자동으로 K값을 선택하는 좋은 방법은 없으며, K의 값을 선택하는 가장 일반적인 방법은 데이터를 보거나 다른 Clustering Algorithm의 결과를 보고 수동으로 선택하는 것이다. 

위의 데이터 분포를 보면, 누군가는 K = 2로 누군가는 K = 4로 설정할 수도 있다.

 

[Elbow Method]

클러스터의 개수 K를 정하는데 사용할 수 있는 방법 중 하나는 Elbow Method이다. 이 방법은 K의 개수는 1에서 점차 늘려가면서 Distortion Function(Cost Function)을 계산한다. 그래서 그래프를 그려보면서 특정 K이후의 Cost가 거의 변하지 않는 지점 elbow point가 있다면, 그 K를 선택하는 것이 좋을 것이다. (아래 그래프에서 K = 3 지점)

하지만 이 방법이 항상 통하는 것은 아니고, 아래와 같이 Cost가 급격하게 변하는 부분이 없다면 elbow로 지정할 만한 point가 없다. 이 경우에는 이 방법을 쓸 수 없다.

[K-means for a Later Purpose]

만약 K-means 알고리즘을 어떠한 목적을 위해서 사용한다면, 그 목적에 잘 맞는지 평가해서 가장 잘 동작하는 모델을 선택해서 K를 결정할 수 있다.

즉, 분류하는 목적에 따라서 직관으로 선택하는 것이다.

예를 들어 위처럼 T-shirt 사이즈를 결정할 때, 이익이 극대화되는 종류의 수를 선택하면 된다.