본문 바로가기
Research/Machine Learning

Clustering, GMM, K-means, EM, DBSCAN

by IMCOMKING 2014. 6. 11.

케이민즈 - 케이니얼니스트의 클러스터링 버젼

k means랑 gmm이랑 거의 비슷함. 차이는 가우시안분포에대한 가정이 있는가 없는가 / 둘다 클러스터의 개수를 지정하고, EM 식으로 둘다 이터레이티브하게 클러스터링을 함. 

 

Centroid : 무게 중심, 질량 중심 (정확히는 질량 중심인데 해석하는데 큰차이는 없어 보임.)

 

 

K-means : K개의 클러스터를 묶어내는 것
(K-means가 EM(Expectation Maximization)의 전형적인 예라고 함.)

Step 1) K개 만큼의 랜덤한 점을 정한다.
Step 2) 각 클러스터의 점들을 계산해서 각각의 Centroid 를 구한다.
Step 3) 입력받은 X1에대해 가장 가까운 Centroid 쪽의 클러스터에 할당한다.
-> 다시 Step 2)로 돌아가서 Centroid를 갱신함.

(사실 이건 휴리스틱임. 원래는 각 클러스터의 분산이 최소가 되게 점을 할당함.)

 

 

DataMiningLectureNote2-3,4 latter.pdf
다운로드

 

 

http://unicone.blog.me/60067189849

http://blog.naver.com/hero1014/20198084057

 

 

 

 

 

GMM과 K-means clustering의 EM알고리즘적인 측면에서의 비교

E-step

E-step은 주어진 learning parameter하에서 최적의 scheme을 업데이트한다.(Bound가 갱신된다.)
 

- GMM에서는 현재 가지고 있는 파라미터(민과 베리언스)의 가우시안 분포에서 데이터 x의 점들이 어떤 portion으로 소속되는지, 그 파이 값을 업데이트한다.

 

- K-means clustering에서는 각 데이터 점 x들이 여러 개의 centroid중에서 어떤 점과 가장 가까운지 계산하여, 그 group(cluster)를 업데이트한다.

 

M-step

M-step에서는 현재의 scheme하에서 최적의 learning parameter를 업데이트한다.(현재의 bound를 최적화한다.)
 

- GMM에서는 현재 정해진 각 가우시안 분포들이 자신이 담당하는 데이터를 최적으로 표현할 수 있도록 그 mean과 variance들을 업데이트한다.

 

- K-means clustering에서는 cluster를 대표하는 centroid들을 갱신하여, group(cluster)내의 점들의 최적의 중앙지점이 되도록 업데이트한다.

 

 

 

 

 

 

DBSCAN

https://scikit-learn.org/stable/modules/clustering.html#dbscan

https://bcho.tistory.com/1205

https://en.wikipedia.org/wiki/DBSCAN

 

특징

- 일정 공간안에 점의 밀도가 threshold이상으로 높은 경우, cluster로 판단한다.

 

장점

- K-means와 달리 cluster 개수를 지정하지 않아도 된다.

- K-means와 달리 convex shape을 가정하지 않으므로, 임의의 cluster boundary가 생겨날 수 있다.

 

 

 

 

 

 

 

 

 

'Research > Machine Learning' 카테고리의 다른 글

Markov Chain, Markov Matrix  (0) 2014.06.24
Gaussian Distribution, Gaussian Mixture Model  (0) 2014.06.11
Nominal, Ordinal, Interval, Ratio  (0) 2014.06.11
거리, Distance  (0) 2014.06.11
ROC curve, ROC_AUC, PR_AUC, 민감도, 특이도  (14) 2014.06.11

댓글