Model-based Clustering

2021-1학기, 대학에서 ‘통계적 데이터마이닝’ 수업을 듣고 공부한 바를 정리한 글입니다. 지적은 언제나 환영입니다 :)

June 2, 2021 7 minute read

2021-1학기, 대학에서 ‘통계적 데이터마이닝’ 수업을 듣고 공부한 바를 정리한 글입니다. 지적은 언제나 환영입니다 :)

앞에서 살펴본 <K-means>와 <hierarchical> clustering은 휴리스틱 기법에 속한다. 어떤 모델이 있는 것이 아니기 때문에, statistical inference 역시 불가능하다. 또한, 실전에서는 categorical variable 때문에 “dissimilarity measure”를 정의하는 것도 쉽지 않다.

<Model-based cluastering>은 데이터셋의 모델, 즉 PDF $Pr (x)$ 을 estimation 하는 기법이다!

2차원 데이터에서 non-parameteric method로 $Pr (x)$ 를 추정하는 것은 어렵지 않다!

Mixture ModelPermalink

2차원 데이터에서 PDF $Pr (x)$ 를 추정하는 것은 어렵지 않다. 그러나 3차원부터는 PDF를 추정하기 쉽지 않으며, 이것을 visualize 하는 것도 clustering 하는 것도 힘든 일이다.

이런 고차원에서의 문제를 해결하기 위해 쓰는 기법이 바로 <Mixture Model>이다! 참고로 <Mixture Model>은 “parameteric” 기법이다.

Let $P = {f_{ϕ} (\cdot) : ϕ \in P}$ be a parameteric model. 이때, $f_{ϕ} (x)$ 는 어떤 pdf로 예를 들면, 이런 형태다:

f_{ϕ} (x) = N (x ∣ μ, σ^{2})

$f_{ϕ} (x)$ 에서 $ϕ$ 는 parameter이며, 집합 $P$ 는 가능한 모든 $ϕ$ 에 대한 PDF의 모음인 것이다.

이번에는 $K$ -cluster를 표현하는 parameteric PDF를 $f_{ϕ_{k}} (x)$ 라고 할 때, 아래와 같은 PDF의 모음; collection of densities를 정의해보자. 별건 아니고, 그냥 cluster PDF의 가중합의 조합이다.

{\sum_{k = 1}^{K} π_{k} f_{ϕ_{k}} (\cdot) : ϕ_{k} \in P, π_{k} > 0, \sum_{k = 1}^{K} π_{k} = 1}

이것을 <K-component mixture model>이라고 한다! 이때, $π_{k}$ 를 “mixing proportion”이라고 한다.

💥 NOTE: 위에서 정의한 <K-component mixture model> 역시 PDF가 된다. 증명은 확률合이 1이 되는지 확인해보면 되는데, 쉽다.

component를 몇개 쓰는지에 따라 분포에서 나타나는 mode의 최대 갯수가 달라진다.

Let $X_{1}, \dots, X_{n}$ be iid from a <K-component mixture>; Data point $X_{i}$ 가 mixture model에서 샘플링 되었다고 가정한다.

우리는 Data points ${X_{1}, \dots, X_{n}}$ 로부터 parameter $θ$ 를 추정해야 한다. 현재 우리는 $θ$ 를 모르는(unknown) 상태며, 그 형태는 아래와 같다.

θ = (π_{1}, \dots, π_{K}, ϕ_{1}, \dots, ϕ_{K})^{T}

우리는 이 unknown parameter $ϕ$ 를 추정하기 위해 MLE를 사용할 것이다.

Algorithm. MLE

Find $θ$ such that maximize $ℓ (θ)$ .

ℓ (θ) = \sum_{i = 1}^{n} \log (\sum_{k = 1}^{K} π_{k} f_{ϕ_{k}} (X_{i}))

아마 보통의 MLE 문제는 위의 log-likelihood function에 편미분 해서, optimal solution을 찾는다. 하지만, 이 문제의 경우, 찾아야 하는 변수가 $2 K$ 정도 되기 때문에, 편미분으로는 쉽게 풀 수 없다. 심지어 Gradient Descent 같은 numerical method를 쓰는 것 역시 어렵다고 한다.

그러나 방법은 있다!! 이런 문제를 풀기 위해 우리는 <EMAlgorithm; Expectation-Maximization>을 사용할 것이다!! 😎

EM AlgorithmPermalink

먼저 <EM Algorithm>이 뭔지 그 정의부터 살펴보자.

EM is a general algorithm to find the MLE when a part of data is missing.

EM에서는 이런 missing data를 잠재변수, “latent variable” $Z$ 라고 한다. 그래서 EM에서 쓰는 데이터 $Y$ 는 아래와 같이 표현된다.

Let $Y = (X, Z)$ be a random vector following a density $p_{θ} (\cdot)$ where $X$ is the “obsesrved data” and $Z$ is the “missing data”.

missing data $Z$ 가 도입되었지만, 여전히 우리의 목표는 observed data $X$ 로 likelihood를 최대값으로 만드는 $θ$ 를 찾는 것이다!

Let $ℓ (θ; X, Z) = \log p_{θ} (Y)$ be the “complete log-likelihood”; 먼저 $X$ 와 $Z$ 를 모두 사용하는 log-likelihood function을 정의한다.

여기서 잠깐 Insight를 얻고 가자. ‘Lee-jaejoon’님의 포스트의 포스트를 많이 참고했다.

1. 만약 모든 확률변수가 관측 가능했다면, 즉, $Z = \emptyset$ .

우리는 $θ$ 의 값을 추정하는 $\hat{θ}$ 를 얻을 수 있었을 것이다.

그러나 우리는 관측하지 못한 $Z$ 가 존재하므로, $θ$ 의 값을 추정할 수 없다.

2. 만약 $θ$ 의 값을 알고 있었다면,

우리는 이걸로 확률분포를 완전히 특정할 수 있기 때문에, 관측되지 않은 $Z$ 의 분포도 알 수 있다.

그러나 parameter $θ$ 는 unknown이기 때문에 $Z$ 의 분포 역시 알 수 없다.

즉, 현재의 상황은 $Z$ 를 모르니 $θ$ 를 모르고, 반대로 $θ$ 를 모르니 $Z$ 를 모르는 상황이다.

<EM Algorithm>은 “만약 $θ$ 를 안다면?”라는 아이디어로 이 상황을 해결한다.

Algorithm. EM Algorithm

1. Initialize Parameter

θ \leftarrow θ^{(0)}

2. Expectation Step; E-Step

만약 우리가 $θ$ 의 값이 $θ^{(0)}$ 라는 것을 알고 있다면, 또 관측한 데이터 $X$ 가 있다면, 우리는 이를 통해 관측하지 못한 missing data $Z$ 의 ‘조건부 분포‘을 구할 수 있다.

Pr (Z ∣ X = x, θ = θ^{(0)})

is a conditional distribution of $Z$ given $X = x$ and $θ = θ^{(0)}$ .

우리는 이 $Z$ 의 조건부 분포를 활용해 log-likelihood에서 $Z$ 를 marginalize 시킬 것이다. 이것은 우리가 모르는 $Z$ 를 없애주기 때문에 충분히 그럴듯한 접근이다! 이것을 표현하면 아래와 같다.

E_{Z ∣ X, θ^{(0)}} ℓ (θ; X, Z) = \sum_{Z} ℓ (θ^{(0)}; X = x, z) \cdot p_{θ^{(0)}} (z ∣ X = x)

이것은 missing data $Z$ 에 가능한 값들에 대한 평균적인 log-likelihood이다. 즉, $Z$ 가 정확히 어떤 값을 갖는지는 모르지만, $Z$ 가 가질 수 있는 값들에 대해 log-likelihood가 평균적으로 어떤 양상인지를 나타내주는 ‘함수’다.

우리는 이것을 ‘log-likelihood의 대타’라는 의미에서 “surrogate function” $Q (θ ∣ θ^{(0)}$ 라고 부른다.

Q (θ ∣ θ^{(0)}) = E_{Z ∣ X, θ^{(0)}} ℓ (θ; X, Z)

3. Maximization Step; M-Step

이제 우리는 $Z$ 를 marginalize out한, missing data에서 자유로운 surrogate function $Q (θ ∣ θ^{(0)})$ 를 가지고 있다. 우리를 이 $Q (θ ∣ θ^{(0)})$ 를 마치 우리가 본래 목표로 했던 likelihood 함수로 취급에 이것에 대해 maximize 하는 $θ$ 를 찾아줄 것이다. 그리고 그런 $θ$ 를 찾았다면, 그것을 새로운 $θ$ 값으로 사용한다!!

θ^{(1)} = \underset{θ}{argmax} Q (θ ∣ θ^{(0)})

4. Repeat Until Converge!

지금은 바쁘니, 추후에 마무리 하겠습니다!

referencesPermalink

‘Lee-jaejoon’님의 포스트

Seokyun Ha (aka. bluehorn07)

Model-based Clustering

Mixture ModelPermalink

EM AlgorithmPermalink

referencesPermalink

You may also enjoy

Interpolation for Uniformly Spaced Nodes, Runge Phenomenon

Interpolation Error

Newton’s Divided Differences

Lotteries