Clustering Part2
[Gaussian Mixture Model(GMM)]
What
Mixture Model 이란?
단순한 분포를 결합하여 복잡한 확률 분포를 체계적으로 구성할 수 있는 방법을 제공하는 모델이다.
GMM이란?
가우시안 분포를 사용하는 Mixture 모델이다.
K means, 특히 K center와 유사한 모델이다.
GMM에서는 3개의 파라미터(pi, 평균, 분산)를 찾는 것을 목표로 한다.
K means에서와의 차이: K means에서는 평균(뮤) 값만 찾는 것을 목표로 했었다. 여기서는 3개의 파라미터를 찾는 것을 목표로 한다.
Formula
평균과 분산, 그리고 파이 값(cluster에 얼마나 있는 지에 대한 값)은 다음과 같은 수식을 통해서 업데이트 한다.
이 때 평균을 구할 때 가중치(gamma)를 주어서 구한다 정도만 알아두자..
이 값을 합해서 확률을 구한다. (어떤 클러스터에 속할지..) ⇒ 답이 확률 값으로 나온다!!
Problem
우리는 이 확률 값을 maximize하는 것이 목표이다. 하지만 이는 불가능하다. 따라서 EM 알고리즘을 이용한다.
EM 알고리즘: K means에서와 매우 유사하다.
vs K means
K means와 GMM 사이의 차이점이다.
K means는 hard assignment(어느 클러스터에 속하는 지 확답 해준다)하지만, GMM probablities에 기반한다.
K means에 비해 다음과 같은 한계점들이 존재한다.
- K means보다 많은 iteration을 돌아야 한다.
- 매 cycle마다 비교를 해야 한다.
→ 이를 해결하기 위해 GMM을 써야하는 상황(확률로 된 결과를 얻고 싶을 때)에는 K means를 쓰고, GMM을 사용하기도 한다.
[Spectral Clustering]
What
데이터를 다른(해석하기 쉬운) feature space로 옮겨서 문제를 해결하는 방법이다.
구현은 쉬우나, 결과에 대한 이해가 어렵다.
Analysis by Graph
Spectral Clustering을 그래프로 해결해 보자.
- Min Cut
min cut으로 cluster를 구분할 수 있다.
그러나 min cut으로 자르면, 위처럼 outlier에 의존하게 될 가능성이 커진다.
- Norm cut
이를 해결하기 위해서 Normalize cut을 이용하기도 한다.
Norm cut에서는 다음과 같은 수식으로 자를 지점을 찾는다. (이 때 Vol은 cluseter의 모든 weight를 합한 값이다)
Norm cut을 이용하면 밑과 같이 outlier 문제를 해결할 수 있다. outlier의 Norm cut은 1.067인 반면, 잘라야 할 지점의 Norm cut은 1.038이 되게 된다.
(우리는 이해를 돕기 위해서 이 그래프를 이미 ‘단순화’된 형태로 보고 있는 것이다. 즉 우리는 이미 데이터를 해석하기 쉬운 차원으로 옮긴 그래프를 본 것이다. 실제 수학적으로 할 때는 ‘단순화’하는 과정을 추가로 진행해야 할 것이다)
Analysis by Math
Spectral Clustering을 수학적으로 해석해 보자.
이건 나중에 흥미 생기면 찾아보기,,