[1주차 K-mean clustering & Gaussian Mixture Model 신인섭]

00. Supervised vs Unsupervised Learning

 

Clustering에 대해 설명하기 전에, Clustering이 속해있는 unsupervised learning(비지도학습)과 그와 다른 Supervised learning(지도학습)에 대해 알아보자.

 

위 그림의 지도학습(Supervised learning)은 데이터에 정답(label)이 존재한다.

따라서 우리는 이러한 정답을 기준으로 데이터의 피쳐에 대해 분석하거나, 새로운 데이터에 대한 예측을 하곤한다.

 

그러나 비지도 학습(unsupervised learning)의 경우, 정답이 존재하지 않는다.

이러한 데이터를 기반으로,

1. Clustering

2. latent factor

3. gragh structure

에 대해 탐구한다.

 

01. Clustering cf w/ supervised learning

좌측의 그래프는 정답(색깔)이 존재하는 지도학습의 케이스이고, 오른쪽의 경우는 정답이 존재하지 않는 비지도 학습의 클러스터링 케이스이다.

 

클러스팅의 결과를 보면, 각각의 데이터들 간에 공유하는 잠재 특성을 기반으로 데이터를 군집화하여 구분했다.

하지만, 영역을 표시하는 범주를 보면, 겹치는 부분이 존재하는데, 

이러한 모호한 부분의 데이터를 어느 영역으로 군집화를 해야할 지에 대한 해결이 필요하다.

 

02. K-mean algorithm

- KNN vs K-mean

Clustering 알고리즘중에 대표적인 알고리즘으로 k-mean clustering이 존재한다. 

이는 KNN 알고리즘과 이름이 유사하여 헷갈릴 수 있는데, 다음과 같은 차이가 존재한다.

 

KNN 알고리즘의 경우, 일단 지도학습에 사용되는 알고리즘으로,

새로운 데이터에 대해 정답을 예측할 때, 예측하고자 하는 데이터 주변에 가장 가까운 데이터 K개를 골라,

K개 데이터의 label에 다수결에 의해 정답을 예측하는 방식이다.

 

K-mean 알고리즘은 그와 다르게, 비지도 학습으로,

데이터를 주변에 가장 가까운 Centroid의 군집으로 분류하게 된다.

- K-mean algorithm

k-mean 알고리즘으로 데이터를 군집화 하는 과정은 크게 두가지 스텝으로 나뉜다.

step 1. K개의 centroid 선정.

step 2. 가장 가까운 centroid로 데이터를 cluster 시킨다.

 

위 과정을 수식화 하면 다음과 같다.

r_nk는 n 번째 데이터 x가 k번째 군집 μ에 속할 지 안 속하지에 대한 0,1 확률 변수이다.

μ는 K개의 centroid를 나타낸다.

 

우리는 J를 최소화하는 것이 목표이다.

J 식에는 r과 μ, 두가지 변수가 존재하기에 우리는 Iterative optimization(EM 알고리즘)을 사용한다.

 

- K-mean Expectation and Maximization

* Expectation

-> data point를 가장 가까운 centroid에 assign 한다 => r_nk optimization

 

* Maximization

-> assign 된 r_nk로 centroid position update(MLE) => μ_k optimization

~> 다시 바뀐 μ_k 에 대해 Expectation(r_nk 최적화)를 진행할 수 있다.

 

- K-mean Algorithm Properties

K-mean 알고리즘의 한계이자 특성은 4가지가 존재한다.

1. K 를 정해야한다.

 - 얼마나 군집화를 진행할 지에 대한 정보가 없기에 K를 정해야한다는 한계가 존재한다.

2. 초기 centroid를 잡아야한다.

 - EM 알고리즘은 초기 centroid를 랜덤하게 설정하여 최적화하는 과정이므로 초기값에 따라 local minima에 빠질 가능성이 존재한다.

3. Euclidean distance의 한계가 존재한다.

- 2norm의 계산으로 data와 centroid의 거리를 측정했기에, 여기서 우리는 data의 각각의 feature에 대한 영향력을 동등하게 생각했다. 그러나 사전정보가 있었거나, 혹은 특정 데이터의 영향력이 매우 강력한 경우에 유클리드 거리는 한계가 존재한다.

4. Hard clustering이다.

위 그림을 보면, 군집화 영역이 겹치는 부분이 존재했는데, k-mean은 이 양쪽의 군집에 속할수 있다는 정보에 대해 무시하고, 가장 가까운 centroid에 군집화하는 결정을 내리게 된다. 

이러한 clustering 방식을 hard clustering이라고 한다.

 

위 한계중 3번과 4번의 한계 특징을 보완한 알고리즘이 존재한다.

바로 Gaussian Mixture Model (GMM) 이다.

 

03. Gaussian Mixture Model

- Mixture Model

왼쪽과 같이 관찰 된 데이터의 분포를 해석하는 하나의 측면으로 Mixure Model 이 제시 되었다.

오른쪽의 정규분포들과 같이 서로 다른 근원을 가지는 normal distribution이 mixed 된 분포로 해석 할 수 있다.

이러한 각각의 정규 분포 단위 해석을 subpopulation 단위로 생각할 수 있으며, 이들이 결합이 되어

Mixture distribution을 표현한다.

π_k : Mixing Coefficient

K개의 옵션들에 대한 각각의 확률을 의미한다. 이는 k-mean clustering의 r_nk와 비슷하지만,확률의 범위가 0~1사이로 연속적으로 존재한다는 차이가 존재한다.

 

위 P로 표현한 분포에 대해, 특정 데이터가 특정 군집으로 분류될 확률은 다음과 같다.

r : 특정 data x_n가 주어졌을때 K번째 군집으로 분류될 확률

 

- GMM optimization 

*Expectation*

r에 대한 식을 보면 알 수 있는 것 중에, x, π, μ, Σ 주어지면 r을 구할 수 있다는 특징이 있다.

 

*Maximization*

E과정에서 구한 r을 이용해, 나머지 파라미터들을 미분을 통해 업데이트가 가능하다.

이렇게 업데이트 된 파라미터들을 기반으로 다시 Expectation과정을 거치는 최적화 방식으로 진행이 된다.

 

- GMM iterative result

K-mean에서 우리는 모호한 경계에 있는 데이터들에 대해 군집의 양립성을 무시하는 방식으로 진행한 반면

GMM에서는 iterate 초반에는 경계에 있는 데이터들이 양쪽 각 군집이 될 확률을 동시에 가지고 있음을 확인할 수 있다.

(itr 초반에 경계에 있는 데이터 색이 섞여 있는 것을 확인 할 수 있다.)

 

~> GMM은 확률적으로 assign하기에 Itr 초반에는 색이 섞여 있지만, 후반으로 갈 수록 점점 명확해지는 것을 확인할 수 있다.

==> Soft clustering

 

- GMM pros and cons

pros

- Soft clustering

- Subpopulation 간 관계에 대해 더 정보를 얻을 수 있다.

 

cons

- 아무래도 k-mean에 비해 연산량이 증가했기에 Long Computation time의 한계 존재

- Local Maxima 가능성 (EM 알고리즘 최적화의 한계)

- Relation GMM and K-mean

위 식은 GMM에서 확률 함수 r에 대한 식을 정규분포 수식화로 변형한 형태이다.

 

가장 우변 식에서 ε이 0으로 간다고 가정해보자.

그러면, -1/2ε 은 매우 작아지는 변화를 보일 것이다. 그렇다면 거기에 곱해진 데이터와 평균간의 거리식에 따라 작아지는 속도가 달라지게 될것이다.

즉, 데이터와 평균간의 거리가 가까울 수록 먼 데이터에 비해 지배적으로 r 값에 작용되는 것을 알 수 있다.

이말인 즉슨, 결국 k-mean의 hard assignment와 동일한 의미로 귀결이 된다.

 

GMM은 결국 k_mean을 표현할 수있는 조금더 포괄적인 알고리즘이며, soft assignment 와 Covariance matrix를 사용하는 특징이 존재한다.

 

04. EM algorithm

기존의 조건부 확률에서 Latent Variable Z를 도입하여 적용하게 된다.

첫줄에 조건부 확률에 대한 변형식을 거치고 부등식이 나오는데 이는 Jensen’s Inequality를 활용하여 적용했다.

결국 부등식이 존재하기에, 우리는 lower bound를 최대화하는 과정이 필요했다.

 

첫줄 맨 우변을 다르게 Q식과 L식으로 다르게 표현이 가능하다. L식을 보면 식 자체에 l(theta) 항이 존재하는데, 

결국 l에서 빼주는 항이 0으로 갈수록 부등식을 등식으로 근사시킬 수 있다.

 

그렇다면 빼주는 항이 중요해지는데, 해당 항의 형태를 잘 살펴보면, KL divergence 형태임을 알 수 있다.

KL divergence는 두 확률 분포의 유사성을 나타내는 지표인데, 동일한 확률 분포가 되면 최솟값 0을 가진다.

즉 Z에 대한 분포 q를 P(Z|X,theta) 분포와 일치시켜 최적화가 가능하다.

 

이렇게 분포 q 가 계산이 되면, 우리는 Q 식을 theta에 대해 최적화가 가능해진다.

새로이 최적화된 theta를 다시 KL 최소화 과정을 거치는 방식으로 반복이 되어 최적화가 진행이 된다.

 

위 그림을 보면 

 

초기 존재하는 KL 차이를 최소화하기 위해 q를 최적화 하고, 

새로운 q에 대해 theta를 다시 update가 가능하다.

그렇게 업데이트 된 theta를 다시 적용하게 되면 lnP(X|theta_t+1)가 다시 계산이 된다.