특징
여러 features 을 가진 instances 들이 있을 때, 각 features 의 similarity 를 계산함.
similarity 가 좋은 애들끼리 그룹을 만듦.
이때 similarity 는 Euclidean Space 와 Non Euclidean Space 에서 구하는 방식이 다름.
$d=\sqrt[n]{\sum _{\ }^{\ }\left(x_i-y_i\right)^n}$
전자는 평범히 거리구하는 공식을 사용함.
Numeric Value 에서 많이 사용함.
n 을 크게할수록 평균과 거리가 먼 데이터의 비중이 높아짐.
$d=1-\cos \left(\theta \right)\ =1-\frac{dot\left(x,\ y\right)}{\left|\combi{x}\right|\left|\combi{y}\right|}$
후자는 벡터간 각도를 구함.
Categorical Value 에서 One hot encoding 을 해서 많이 사용함.
예를들어 문서 검색에서 단어의 조합이 중요하지 그 조합의 갯수는 관계없는 경우 많이 쓰임.
K-Means
k 는 clustering 되어서 묶일 그룹의 갯수임. 이를 미리 지정해야함.
k 개의 점을 feature space 에 랜덤하게 뿌림.
모든 instance 를 가장 가까운 랜덤하게 뿌린 점과 연결함.
각 k 개의 점과 연결된 instances 의 거리(Euclidean)의 평균을 구함
=> 이게 각 k 개의 점의 새로운 위치.
각 k 개의 점과 연결된 instances 의 집합의 평균이 변하지 않을 때 까지 반복.
=> cluster center 와 instances 의 거리가 local minimum 이 됨.
local minimum 이 global minimum 일 가능성을 높히기 위해 위 과정을 여러번 수행.
=> k 개의 점과 instances 간의 평균이 가장 낮은걸 선택
Euclidean Means 을 사용하므로 Categorical Value 에는 작동하기 힘듦.
또한 모든 feature 가 동등하게 고려받기 위해 정규화가 필수로 필요함.
클러스터에 중요한 feature 나 결과값에 대해서 해석하기 힘름.
=> 하지만 supervised 의 결과와 비교해볼 순 있다.
각 클러스터가 비슷한 크기일 때 성능이 제일 높다고함.
Agglomerative Clustering(Hierarchical)
먼저 구하고자 하는 Cluster 의 갯수를 지정해야함.
모든 데이터들이 처음엔 하나의 cluster 임.
가장 비슷한 두 cluster 를 찾아내서 합치는 것을 계속 반복함.
=> Ward(분산), Average, Complete(cluster 멤버 중 최대의 거리), Single(;; 최소거리) 중 택 1
우리가 원하는 Cluster 의 갯수가 나오면 멈춤.
=> 계층적으로 쌓아올린 데이터는 그대로 있어서 등고점같은 그래프도 만들 수 있음
Expectation Maximum(EM) Algorithms
bayes 와 gaussian distribution 를 이용한 clustering 이다.
각 cluster 는 gaussian distribution 을 나타내는 u(평균), std(표준편차) 로 이루어진다.
우리의 목적은 u, std 를 구하는 것.
악순환
instance 인 X 가 cluster A 에 속한 확률은 gaussian distribution 을 통해 구할 수 있다.
하지만 우리는 그 분포를 나타내는 u, std 를 알지 못한다.
만약 instance 가 어떤 cluster 에 속하는지를 알면 u, std 를 구할 수 있다.
하지만 이건 unsupervised 라 이것도 알지 못한다.
이처럼 계란과 닭의 악순환에 빠지지만 우리는 초기값으로 u, std 를 랜덤하게 배정하고 반복해서 업데이트함으로써 여기서 탈출할 수 있다.
Maximum Likelihood Estimation(MLE)
$\log P\left(D\right)=\sum _{\ }^{\ }\log \combi{P\left(x_i\right)}=\sum _{i=0}^{i=numX\ }\log \left(\sum _{j=0\ }^{i=numClass}\log \combi{\left(P\left(x_i\right)\cdot P\left(x_i\ /\ C_j\right)\right)}\right)$
$\log P\left(D\right)=\sum _{i\ in\ numX}^{\ }\log \combi{P\left(x_i\right)}=\sum _{\ }^{\ }\log \left(\sum _{j\ in\ numClass}^{\ }\log \combi{\left(P\left(x_i\right)\cdot P\left(x_i\ /\ C_j\right)\right)}\right)$$\log P\left(D\right)=\sum _{i\ in\ numX}^{\ }\log \combi{P\left(x_i\right)}=\sum _{\ }^{\ }\log \left(\sum _{j\ in\ numClass}^{\ }P\left(x_i\right)\cdot P\left(x_i\ /\ C_j\right)\right)$
$\theta =\arg \max _{\theta }^{ }\left(P\left(X\ /\ \theta \right)\right)$θ=ArgMaxθ(P(X / θ))
MLE 는 Bayes 의 응용인 likelihood 를 최대로 하는 조건을 찾자는 것이다.
위에서 θ 는 우리의 cluster 를 나타내는 u, std 의 값을 말한다.
만약 우리가 class A 에 대한 u, std 를 제대로 찾았다면 P(x) 의 합이 매우 클것이다.
왜냐하면 종모양 그래프의 중앙 부분에 x 들이 분포해 있을 것이기 때문이다.
$\log P\left(X\ /\ \theta \right)=\sum _{i\ in\ numX\ }^{\ }\log P\left(x_i\ /\ \ \theta \right)=\sum _{\ }^{\ }\log \left(\sum _{j\ in\ numClass}^{\ }P\left(\theta _j\right)\cdot P\left(x_i\ /\theta \ _j\right)\right)$
$ArgMax_{\theta }\left(\log P\left(X\ /\ \theta \right)\right)=\sum _{i\ in\ numX\ }^{\ }\log P\left(x_i\ /\ \ \theta \right)=\sum _{\ }^{\ }\log \left(\sum _{j\ in\ numClass}^{\ }P\left(\theta _j\right)\cdot P\left(x_i\ /\theta \ _j\right)\right)$
$ArgMax_{\theta }\left(\log P\left(X\ /\ \theta \right)\right)=\sum _{\ }^{\ }\log P\left(x_i\ /\ \ \theta \right)=\sum _{\ }^{\ }\log \left(\sum _{j\ in\ numClass}^{\ }P\left(A_j\right)\cdot P\left(x_i\ /A\ _j\right)\right)$
확률의 특성상 곱하면 점점 작아져서 이를 막기 위해 log 를 씌운다.
이때 가장 안쪽의 시그마는 P(A_j) 라는 확률분포함수로 기댓값을 구한 것이다.
애초에 여러 cluster 의 묶음을 나타낸 θ 를 쓴 시점부터 기댓값을 쓴다는 말이니 놀라지 말도록 하자.
문제는 위의 식의 최댓값을 찾기가 힘들다는 것이다.
P( x_i | A_j ) 는 A_j 가 Gaussian Distribution 이라 Concave (종모양) 그래프이다.
Concave 는 특성상 Global Maximum 지점이 Local Maximum 이라 간단하다.
하지만 sum( P(A_j) * P( x_i | A_j) ) 는 local maximum 이 매우 많기도 하고 Global Maximum 을 찾기가 매우 힘들다.
Expected Likelihood Estimation
$Log\left(P\left(X\ \ /\ \theta _1\right)\right)=Log\left(P\left(X,\ \ \theta _2\ \ /\ \theta _1\right)\right)-Log\left(P\left(\theta _2\ /\ \ X,\ \theta _1\right)\right)\ \ \ \ -\ trivial$
우리가 최댓값을 찾으려는 식을 다시풀면 위와 같다.
θ_1 은 cluster 에 대한 정보로 지금까지 썼던 θ 와 같은 의미이다.
θ_2 Latent Variable 이라고 불리는데, θ_1 과 데이터인 X 로부터 u, std 를 예측한 값이다.
일단 위 식은 trivial 하므로 θ_2 의 의미는 위에선 중요하지 않다.
Log(P( X/ θ1))= ∑j in numθ2(p(θ2 j / X, θ t1)Log(P( X, θ2j / θ1)))− ∑j in numθ2 (p(θ2j / X, θ t1)Log(P(θ2j / X, θ1)))
위의 식에서 P( θ_2 | X, θ_1t ) 를 곱해서 합친값으로 바꿨다.
이때 θ_1t 의 의미는 업데이트가 진행중인 θ_1 을 의미하며 가능한 θ_1 의 값중 하나다.
아까도 말했듯이 여러 cluster 의 모음인 θ_1, θ_2 를 썼다는건 기댓값을 계산한다는 말이다.
θ_2 는 추정한 값이다. 그래서 확률분포함수는 P( θ_2 | X, θ_1t ) 가 된다.
추정을 위해서 현재 θ_1 의 값을 θ_1t 로 나타냈음을 이해하자.
위 식에서 한 것은 θ_2 의 확률분포함수로 기댓값을 계산한 것이다.
Log(P(X / θ1))∝ ∑j in numθ2(p(θ2j / X, θ t1)Log(P(X, θ2 / θ1)))
https://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm
그리고 위키의 Proof 부분에 나와있듯이 위와 같은 비례식이 성립한다.
위의 등식에서 -시그마 부분이 떨어져 나오고 비례식이 된 것이다.
$\theta _1"\ =\ ArgMax_{\theta _1}\left(\sum _{i\ in\ numX}^{\ }E_{\theta _2}\left(\log P\left(x_i\ ,\ \theta _2\ ;\ \theta _1\right)\right)\right)$
위 비례식을 근거로 우리는 위와같은 식을 세울 수 있다.
식이 조금 달라보여도 위 비례식의 우변과 위 식의 우변 괄호 속은 같은 내용이다.
위 식은 계산하기가 쉬운데, MLE 와 달리 확률분포함수에 우리가 구하고자 하는 θ_1 가 없기 때문이다.
게다가 위 식은 Concave 하다. => 왜?
그래서 우리는 MLE 가 아닌 Expected Likelihood Estimation 을 쓰는 것이다.
$ArgMax_{\theta }\left(\log P\left(X\ /\ \theta \right)\right)=\sum _{\ }^{\ }\log P\left(x_i\ /\ \ \theta \right)$
Gaussian Mixture Model (GMM)
E-Step - θ_2 의 기댓값 계산.
$P\left(\theta _2\ /\ X,\ \theta _1\right)=\frac{1}{\sigma \sqrt{2\pi }}e^{-\left(x-\mu \right)^2\ /\ 2\sigma ^2}$
$P\left(\theta _2\ /\ X,\ \theta _1\right)=\sum _{i\ in\ numX\ }^{\ }\frac{1}{\sigma \sqrt{2\pi }}e^{-\left(x_i-\mu \right)^2\ /\ 2\sigma ^2}$ dfd