[ML] 비지도 학습 - (K-means, 가우시안 혼합 모델)

비지도 학습(unsupervised learning)

비지도 학습이란 알고 있는 출력값이나 정보 없이 학습 알고리즘을 가르쳐야 하는 모든 종류의 머신러닝을 의미

• 학습 알고리즘은 입력 데이터만으로 데이터에서 지식을 추출할 수 있어야 함

비지도 학습 문제

• 클러스터링(clustering)
• 차원 압축(dimensionality reduction)
• 이상 감지(anomaly detection)

비지도 학습 과제

• 알고리즘이 뭔가 유용한 것을 학습했는지 평가하는 것
• 보통 레이블이 없는 데이터에 적용하기 때문에 무엇이 올바른 출력인지 모름
• 모델이 어떤 일을 잘하고 있는지 이야기하기가 어려움
• 따라서 비지도 학습은 데이터를 더 잘 이해하고 싶을 때 탐석잭 분석 단계에서 많이 사용
• 지도 학습의 전처리 단계에서 사용
• 새롭게 표현된 데이터를 사용해 학습하면 지도 학습의 정확도가 좋아짐

군집(clustering)

• 군집 알고리즘은 데이터를 비슷한 것끼리 그룹으로 묶는 것입니다.
• 데이터셋을 클러스터(cluster)라는 그룹으로 나누는 작업

알고리즘

1. 데이터 포인트를 가장 가까운 클러스터 중심에 할당
2. 클러스터에 할당된 데이터 포인트의 평균으로 클러스터 중심을 다시 지정

• 클러스터에 할당되는 데이터 포인트에 변화가 없을 때 알고리즘 종료

9-1. 2차원 입력 데이터

• $\boldsymbol X$ : 입력 데이터 → 사용
• $\boldsymbol T$: 클래스 데이터 → 사용하지 않음

클러스터
데이터 분포의 모양

클러스터링
데이터 분포에서 클러스터를 찾아, 동일한 클러스터에 속하는 데이터 점에는 같은 클래스(label)을 붙이고, 다른 클러스터에 속하는 데이터 점에는 다른 클래스를 할당하는 것

<예시>

비지도 학습 문제: 클러스터링

• 클래스가 없는 데이터 $\boldsymbol X$
• 데이터는 3개의 덩어리(클러스터)로 나눌 수 있다.

클러스터링의 목적

• 클러스터에 대응하는 클래스(라벨)를 각 데이터 점에 할당하는 것

지도학습과 차이

• 지도 학습 문제는 클래스가 있는 데이터였다.
• 미지의 $x$에 대한 클래스를 예측하는 것이 목적

클래스와 클러스터 차이

• 클래스: 단순한 라벨을 의미
• 클러스터: 분포의 특징을 나타냄

클러스터링 알고리즘

• K-means 기법
• 가우시안 혼합 모델 사용한 클러스터링

9-2. K-means 기법

K-means 기법

• ▲($\mu$): 클러스터의 중심 벡터
• ●($R$): 각 데이터의 클래스 지시 변수

Steps

1. $\mu$에 초깃값을 부여한다.

2. $\mu$로 $R$을 갱신

   각 데이터 점을 가장 중심이 가까운 클러스터에 소속시킨다.

3. $R$로 $\mu$를 갱신

   각 클러스터에 속하는 데이터 점의 중심을 새로운 $\mu$로 한다.

   → 값이 변하지 않을 때까지 2, 3을 반복한다.

K-means 기법과 가우시안 혼합 모델 두 경우 모두 미리 분할할 클러스터의 수 K를 결정해야 합니다. 위 그림은 $K=3$개의 클러스터로 분류합니다.

• 분할할 클러스터의 수 지정: $K$

K-means 기법에서는 두 변수를 사용합니다.

• $\mu$: 클러스터의 중심 벡터로 클러스터의 중심 위치를 나타냄
• $R$: 클래스 지시 변수로 각 데이터 점이 어떤 클러스터에 속하는지를 나타냄

1단계에서 클러스터의 중심 벡터 $\mu$에 적절한 값을 제공하여 잠정적으로 중심을 결정합니다. 2단계에서는 현 시점에서의 클러스터 중심 벡터 $\mu$를 바탕으로 클래스 지시 변수 $R$을 결정합니다. 마지막 단계에서 현 시점에서의 클래스 지시 변수 $R$로 $\mu$를 갱신합니다.

이후 2, 3단계를 번갈아 반복하여, $\mu$와 $R$로 갱신을 계속합니다. 그리고 값이 더이상 변하지 않으면 절차를 종료합니다.

여기서 설명한 1~3단계를 더 상세히 다루도록 하겠습니다.

1. 변수의 준비와 초기화

$k$번째 클러스터의 중심 벡터는

$\boldsymbol \mu_k = [\mu_{k0}, \mu_{k1}] \ (k=0,1,2)$으

의 식으로 나타냅니다.

입력 차원이 2차원이어서 클러스터 중심도 2차원 벡터로 이뤄집니다.

중심 벡터에는 알고리즘의 최초에 적당한 초깃값을 제공합니다.

이 예에는 K=3이므로 3개의 중심 벡터를 일단 $\boldsymbol \mu_0 = [-2, 1], \boldsymbol \mu_1 = [-2, 0],\boldsymbol \mu_2 = [-2, -1]$으로 정합니다.

클래스 지시 변수 $\boldsymbol R$은 각 데이터가 어느 클래스에 속해 있는지를 $1-of-K$ 부호화법으로 나타난 행렬입니다.

$r_{nk} = \begin{cases} 1 & 데이터 \ n이 \ k에 \ 속하는 \ 경우 \\0 & 데이터 \ n이 \ k에 \ 속하지 \ 않는 \ 경우\end{cases}$

데이터 $n$에 대한 클래스 지시 변수를 벡터로 나타내면, 클래스 0에 속하는 경우는 다음과 같습니다.

$\boldsymbol r_n = [r_{n0}, r_{n1}, r_{n2}] = [1,0,0]$

모든 데이터를 정리하여 행렬로 나타낸 $R$은

$R = \begin{bmatrix} R_{00} & R_{01} & R_{02} \\ R_{10} & R_{11} & R_{12} \\ \vdots & \vdots & \vdots \\ R_{n-1, 0} & R_{n-1, 2} & R_{n-1, 2} \end{bmatrix} =$$\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ \vdots & \vdots & \vdots \\ 1 & 0 & 0 \end{bmatrix}$

입니다.

• $\boldsymbol \mu$: 클러스터의 중심 벡터 (초기화)
• $\boldsymbol X$: 입력 데이터
• $\boldsymbol R$: 클래스 (초기화)

2. $R$의 갱신

$\boldsymbol R$을 갱신하는 방법은 각 데이터 점을 가장 중심이 가까운 클러스트에 넣는 것입니다.

첫 번째 데이터(n=0)의 $r_n$을 갱신

$\boldsymbol \mu_n$로 $\boldsymbol r_{nk}$를 갱신

1. 데이터 $\boldsymbol X_n = (x_{n0}, x_{n1})$과 각 클러스터의 중심 $\boldsymbol \mu_k$까지의 제곱 거리를 $k=1,2,3$에 대해 계산합니다.

2. 거리가 가장 가까운 클래스를 그 데이터의 소속 클래스로 합니다.

클러스터 0과 제곱 거리가 가장 작으므로

$\boldsymbol r_{n=0} = [1,0,0]$

으로 한다.

첫 번째 데이터 점에서 클러스터 중심까지의 제곱 거리를 각 클러스터에 대해 계산하면

두 점 $\boldsymbol X_n$과 $\boldsymbol u_k$의 거리는 제곱근을 취한 것입니다.

그리고 거리 자체를 아는 것보단 데이터 점에서 가장 가까운 클러스터를 아는 것이 목표이므로, 제곱근의 계산을 생략한 제곱 거리를 비교하여 가장 가까운 클러스터를 결정합니다.

해당 과정이 $\boldsymbol u$로 모든 데이터 점에 대해 $\boldsymbol R$을 갱신하는 방법입니다.

3. $\mu$의 갱신

$\mu$를 갱신하는 방법은 각 클러스터에 속하는 데이터 점의 중심을 새로운 $\mu$로 하면 됩니다.

$k=(0,1,2)$이기 때문에, 각 $k$에 속하는 데이터, 즉 $r_n=[\dots]$ 의 라벨을 가진 데이터 점에 주목해 각 평균을 구합니다.

시그마의 조건은 n is cluster 0입니다. 클러스터 0에 속하는 데이터 n의 합을 취하는 의미입니다.

식이 잘 이해가 안 갈 수도 있는데, 각 클래스 k의 따른 데이터 점의 각 평균을 구하는 식입니다.

이 과정은 $R$을 통해 $\mu$를 갱신하는 방법이며, 클래스 $k$에 속하는 데이터의 중심(좌표의 평균)을 새로운 $\mu_k$로 합니다.

( $N_k$: 클래스 k에 속하는 데이터의 수)

여기까지가 K-means 알고리즘의 계산을 모두 설명했습니다.

그 이후에는 2와 3의 절차를 반복해서 최적의 값을 찾아내면 됩니다. 앞에서도 반복해 설명했지만, 변수의 값이 변화하지 않으면 프로그램은 종료됩니다.

4. 왜곡 척도(distortion measure)

현재까지 K-means 기법의 알고리즘을 설명했습니다.

비지도 학습의 오차 함수처럼 학습이 진행함에 따라 감소하는 목적함수가 있을까요?

K-means 기법의 경우, 데이터 점이 속한 클러스터의 중심까지의 제곱 거리를 전체 데이터로 합한 것이 목적 함수에 대응합니다.

이를 왜곡 척도(distortion measure)이라 하며, 아래 식으로 표현할 수 있습니다.

왜곡 척도(distortion measure)

데이터 점부터 소속하는 클러스터 중심까지의 제곱 거리의 합

이를 더 깔끔하게 표현한다면

K-means 기법으로 얻을 수 있는 해는 초기값에 의존하는 경향이 있습니다. 처음 $\mu$에 어떤 값을 할당하느냐에 따라 결과가 달라집니다.

실제로는 다양한 $\mu$에서 시작하여 얻은 결과 중에 가장 왜곡 척도가 작은 결과를 사용합니다.

또한, 위의 예시에서는 $\mu$를 먼저 정했지만 $R$을 먼저 결정해도 상관없다고 합니다.

이 경우엔 반대로 $R$을 임의로 정해 거기서 $\mu$를 찾아가는 절차입니다.

9-3. 가우시안 혼합 모델

가우시안 혼합 모델(Gaussian Mixture Model: GMM)은 이름 그대로 Gaussian 분포가 여러 개 혼합된 클러스터링(clustering) 알고리즘입니다.

9.3.1 확률적 클러스터링

K-means 기법은 데이터 점을 반드시 클러스터에 할당합니다. 예를 들어 클러스터 0의 중심에 있는 데이터 점 A도, 클러스터 0의 끝에 있는 점 B에도 동일한 r=[1,0,0]이 할당됩니다.

K-means 기법은 각 데이터를 어느 하나의 클래스에 속하도록 $R$로 라벨을 붙였습니다. 여기서 개념을 확장합니다. 이 $R$을 확장하여 ‘각 클래스에 속할 확률’을 나타내는 클래스 확률 $\gamma$를 생각합니다.

만약 ‘데이터 점 A는 확실히 클러스터 0에 속하지만, 데이터 점 B는 클러스터 0와 클러스터 1에 모두 속해 있다’고 한다면, 이를 어떻게 수치화 할 수 있을까요?

데이터 점 A가 클러스터 0에 속할 확률을 0.9라면, 클러스터 1과 2에 속할 확률은 각각 0.1과 0.0이라 생각해보겠습니다.

이를 $\gamma_A$를 사용하여 나타냅니다.

당연히 어떤 쪽의 클러스터에는 반드시 속하게 되므로 3개의 확률을 더하면 1이 됩니다.

K-means 기법으로 다룬 $R$의 확장입니다.

만약 클러스터 0의 가장 자리에 있던 데이터 점 B가 있다면, 이는

로 표현할 수 있습니다.

여기까지 ‘클러스터 k에 속할 확률’이라 설명했습니다.

예를 들어, 곤충의 질량과 크기를 나타내는 2차원 입력 데이터가 있고 3개의 클러스터가 존재한다는 것을 알아냈습니다. 클러스터에 속할 확률을 생각해보겠습니다.

즉, 모든 곤충은 클러스터의 배후에 있는 0, 1, 2 중 하나의 변종에 속하고 그 클래스에 따라 질량과 크기가 대략 정해집니다.

따라서 각 데이터에 대해 어떤 변종인지 확률(사후 확률)을 $\gamma$로 생각합니다. 이것이 ‘클러스터에 속해 있을 가능성’을 의미합니다.

잠재 변수(latent variable)

여기서 새로 나오는 개념은 잠재 변수(latent variable) 또는 숨은 변수(hidden variable)입니다.

아까 위에서 예로 들었던 곤충 변종 분류 문제를 다시 가져오겠습니다.

같은 종류의 곤충 200마리를 채취하여 질량과 크기를 기록하고 플롯하였더니, 3개의 클러스터가 나왔습니다.

이는 무엇을 의미할까요?

이 경우는 외형이 같은 곤충이 사실은 세 가지의 변종이었다라고 볼 수 있습니다. 3개의 클러스터가 나왔기 때문에 3개의 클래스의 존재가 암시되었습니다.

이렇게 관찰은 못했지만 데이터에 영향을 준 변수를 잠재 변수(latent variable)라고 합니다.

잠재 변수를 3차원 벡터를 사용해 1-of-K 부호화법으로 표현할 수 있습니다.

데이터 n이 클래스 k에 속한다면 $z_{nk}$만 1을 취하고, 다른 요소는 0으로 합니다.

이는 K-means 기법의 $R$과 거의 같습니다.

이 관점에서 데이터 $n$이 ‘클러스터 k에 속할 확률 $\gamma_{nk}$’란 데이터 $x_n$인 곤충이 ‘클래스 k의 변종일 확률’을 의미합니다.

관찰할 수 없는 $Z$의 추정치가 $\gamma$라고 볼 수 있습니다.

$Z$는 어떤 클래스에 속하고 있는지를 의미하므로 0 or 1의 값을 갖지만, $\gamma$는 확률적인 추정값이므로 0에서 1의 실수 값을 취합니다.

$\gamma$는 어떤 클러스터에 얼마나 기여하고 있는가를 의미하므로 부담률(responsibility)라고 합니다.

• $Z$: 어떤 클래스에 속하느냐
• $\gamma$: 어떤 클러스터에 얼마나 기여하고 있는가

정리하면,

확률적 클러스터링은 데이터의 배후에 숨어 있는 잠재 변수 $Z$를 확률적으로 $\gamma$를 추정하는 것입니다.

9.3.2 가우시안 혼합 모델

앞에서 설명한 부담률 $\gamma$을 구하기 위해 가우시안 혼합 모델이란 확률 모델을 배웁니다.

해당 식을 이해하기 위해 입력 $x$가 2차원인 경우 분포의 모양을 결정하는 매개 변수가 어떻게 되는지 살펴보겠습니다.

• 중심 벡터: 각 가우스 분포 k의 중심 $\mu_k = (\mu_{k0}, \mu_{k1})$
  
• 공분산 행렬: 각 가우스 분포 $k$의 퍼짐 $\Sigma_k = \begin{bmatrix} \sigma_{k00} & \sigma_{k01} \\ \\ \sigma_{k10} & \sigma_{k11} \end{bmatrix}$ , $\sigma_{k00} > 0, \sigma_{k11} > 0, \sigma_{k01} = \sigma_{k10}$
  
• 혼합 계수: 각각의 가우스 분포의 크기의 비율 $\pi_k$, $0 \le \pi_k \le 1,$ $\Sigma_{k=0}^{K-1} \pi_k = 1$
  

k개의 가우스 분포를 모두 합해 다양한 분포를 표현할 수 있습니다. 가우시안 혼합 모델은 가수으 함수 여러 개를 합친 것입니다.

$N(x|\mu_k, \Sigma_k)$는 평균 $\mu_k$ 공분산 행렬 $\Sigma_k$의 2차원 가우스 함수를 나타냅니다.

서로 다른 평균과 공분산 행렬을 가진 2차원 가우스 함수가 $K$개 겹친 분포를 나타냅니다.

모델의 매개변수를 다시 정리해보면

• $\mu_k$: 각 가우스 분포의 중심을 나타냄
• $\Sigma_k$: 분포의 퍼짐을 나타내는 공분산 행렬
• $\pi_k$: 각 가우스 분포의 크기의 비율을 나타내는 혼합 계수, 이 혼합 계수는 0과 1 사이의 실수로 K로 합을 취했을 때 1임 $\Sigma_{k=0}^{K-1} \pi = 1$
  

9.3.3 EM 알고리즘의 개요

EM 알고리즘은 Expectation-Maximization의 약자입니다.

가우시안 혼합 모델을 사용하여 데이터의 클러스터링을 수행합니다.

여기선 EM 알고리즘을 사용하여 가우시안 혼합 모델을 데이터에 fitting 해보고, 부담률 $\gamma$를 구하는 방법을 설명합니다.

가우시안 혼합 모델의 EM 알고리즘: 개요

• $\pi_k$: 각 클러스터의 혼합 계수
• $\mu_k$: 중심 벡터
• $\Sigma_k$: 공분산 행렬
• $\gamma$: 각 데이터의 각 클러스터에 대한 부담률

Steps

1. $\pi, \mu, \Sigma$에 초깃값을 부여
2. (E Step) $\pi, \mu, \Sigma$로 $\gamma$를 갱신. 각 데이터 점은 각 클러스터에서 생성된 사후 확률로 $\gamma$를 계산
3. $\gamma$로 $\pi, \mu, \Sigma$를 갱신. 각 클러스터에 대한 부담률로 각 클러스터의 매개 변수를 계산

K-means 기법은 각 클러스터를 중심 벡터 $\mu$로 특정했습니다.

가우시안 혼합 모델은 중심 벡터 $\mu$뿐만 아니라 공분산 행렬 $\Sigma$에 의해 각 클러스터의 확산 정도를 기술합니다. 또한, 혼합 계수 $\pi$에 의해 각 클러스터의 크기 차이를 설명합니다.

그리고 클러스터링의 출력은 K-means 기법에서는 1-of-K 부호화에서의 $R$이었지만, 가우시안 혼합 모델은 각 클래스에 속할 확률에 대응하는 부담률 $\gamma$를 출력합니다.

알고리즘을 정리해보자면

$\pi, \mu, \Sigma$ 초기화로 시작하여 현시점의 $\pi, \mu, \Sigma$를 사용하여 $\gamma$를 구합니다. 해당 step은 EM 알고리즘으로 E Step이라고 합니다.

E Step을 더 쉽게 설명하면 E가 expectation으로 로그 가능도의 기댓값을 계산하는 과정이며, label을 찾는 과정이라 생각하면 됩니다.

다음에는 현시점 $\gamma$를 사용하여 $\pi, \mu, \Sigma$를 구합니다. 이 step은 EM 알고리즘으로 M Step이라고 불립니다.

M Step은 Maximization으로 maximum likelihood estimation을 수행하여 모수를 추정하는 과정입니다.

E Step: 변수의 정보(label)을 업데이트 → M Step: 변수들이 어떻게 분포되어 있는지에 대한 가설을 업데이트

E step과 M step을 매개 변수가 수렴할 때까지 반복합니다.

9.3.4 Step 0: 변수의 준비 및 초기화

• $\pi, \mu, \Sigma$에 초깃값을 할당

9.3.5 Step 1(E Step)

$\gamma$ 갱신

• $\pi, \mu, \Sigma$로 $\gamma$를 갱신

각 데이터 점의 부담률을 계산합니다.

계산 식은 아래와 같습니다.

부담률 $\gamma$는 모든 $n,k$에 대해 갱신합니다. 그리고 각 가우스 함수의 값을 계산하고 합이 1이 되도록 규격화합니다.

어떤 데이터 점 $n$에 착안했을 때, 그 데이터 점에서의 각 가우스 함수의 높이 $a_k = \pi_k N(x_n|\mu_k, \Sigma_k)$를 구합니다.

그리고 $k$에서의 합을 취해 1이 되도록 $a_k$의 총합 $\Sigma_k^k a_{k'}$로 나누어 규격화한 것을 $\gamma_{nk}$로 합니다.

가우스 함수의 값이 높을수록 부담률도 높아지는 직관적인 갱신 방법입니다.

9.3.6 Step 2(M Step)

$\pi, \mu, \Sigma$ 의 갱신

우선 각 클러스터에 대한 부담률의 합 $N_k$를 구합니다.

K-means 기법에서는 말하는 각 클러스터에 속할 데이터의 수에 해당합니다.

부담률 식을 바탕으로 혼합률 $\pi_k$를 갱신합니다.

N은 전체 데이터 수이므로 혼합률은 전체에 대한 클러스터 내 수의 비율이 됩니다. 그래서 비율에 맞는 적합한 갱신 방법이 되며,

중심 벡터 $\mu_k$를 다음 식에서 갱신합니다.

클러스터에 부담률의 가중치를 더한 데이터의 평균이 됩니다. 이것은 K-means 기법에서 말하는 ‘클러스터 데이터의 평균을 구한다’와 대응합니다.

마지막으로 가우스의 공분산 행렬을 갱신합니다.

갱신식에는 앞에서 구한 $\mu_k^{new}$가 사용됩니다.

클러스터에 부담률의 가중치를 더한 데이터의 공분산 행렬을 구합니다.

가우스 함수를 이터에 fitting 할 때의 공분산 행렬을 구하는 방법과 유사합니다.

9.3.7 가능도

가우시안 혼합 모델은 데이터의 분포 $p(x)$를 나타내는 모델입니다.

분류 문제에서 다룬 로지스틱 회귀 모델은 $p(t|x)$와 $x$에 대해 클래스의 확률을 나타내는 모델이었기 떄문에, 클러스터링에서 취급하는 모델은 분류 문제에서 다룬 모델과 다릅니다.

EM 알고리즘은 가우시안 혼합 모델이 입력 데이터 $X$의 분포에 맞게 매개 변수를 갱신하는 알고리즘이었습니다.

입력 데이터가 조밀한 구간에 가우스 함수를 배치하여, 입력 데이터가 띄엄띄엄한 부분은 분포의 값이 낮도록 매개 변수를 조정합니다. 결과적으로 각 가우스 분포가 다른 클러스터를 나타낸 것입니다.

그렇다면 EM 알고리즘은 무엇을 최적화 할까요? 목적 함수가 무엇인지 생각해볼 수 있습니다.

입력 데이터 $X$는 가우시안 혼합이 식에 로그를 취해 로그 가능도를 만듧니다.

EM 알고리즘의 매개 변수 갱신 규칙은 가능도 극대화의 원리를 따릅니다.

가능도는 모든 데이터 점 $X$가 모델에서 생성된 확률이므로 아래 식에 할당됩니다.

이 로그를 취한 로그 가능도는

가능도나 로그 가능도를 최적화 시킬 때는 똑같이 극대화를 하기 때문에, -1을 곱한 음의 로그 가능도를 오차 함수 $E(\pi, \mu, \Sigma)$ 로 정의합니다.

그러면 매개 변수를 다시 기본값으로 초기화하여 오차 함수 $E(\pi, \mu, \Sigma)$ 가 알고리즘의 갱신 단계에서 단조롭게 감소하는지를 살펴보면 됩니다.

EM 알고리즘이 진행됨에 따라 음의 로그 가능도는 단조롭게 감소합니다.