군집화

: 훈련집합이 주어지면 조건을 만족하는 군집집합을 찾아내는 작업

 

조건

 

1. 모든 군집이 하나 이상의 샘플을 가지도록 함

2,3. 모든 샘플이 단 하나의 군집에 속하도록 함

 

- 경성 군집화 hard clustering -> 한 샘플이 하나의 군집에 속하도록 강제하는 방식

- 연성 군집화 soft clustering -> 샘플마다 군집에 속하는 정도를 다르게 함

 

- 군집의 개수를 부류의 개수로 간주하는 경우 군집화를 class discovery부류발견 작업이라고 함

-> 부류 발견은 주관성 개입 가능

--> 응용 상황에 따라 k와 군집화 알고리즘이 지닌 하이퍼 매개변수를 적절히 조절해서 합리적인 결과 얻어야 함

 

1. k-means algorithm

(+) 단순하고 성능 좋은 인기 군집화 알고리즘

(-) 군집의 개수 k를 지정해야 하는 단점

 

k-medoids

k-medoids는 샘플 중 대표를 뽑고 뽑힌 대표로 군집 중심을 갱신함

k-means에 비해 잡음에 둔감

 

multi-start k-means 알고리즘

k-평균이 초기 군집 중심에 민감한 문제 해결 가능

서로 다른 초기 군집 중심을 가지고 k-평균을 여러 번 수행한 후 가장 좋은 품질의 해를 선택하는 전략

 

EM 알고리즘

k-means에서는 은닉변수 Z의 추정과 알고리즘의 해인 A의 추정을 번갈아 가며 수행하는 방식으로 동작함

Expectation maximization algorithm : 은닉변수의 추정과 매개변수 추정을 번갈아 수행하며 최적의 해를 찾는 과정

은닉변수 latent variable : 중간에 임시로 사용되다 사라지는 변수

혼합 가우시안을 추정하는 작업에서는 EM 알고리즘이 중요한 역할을 함

E단계 : 은닉변수를 추정하는 단계

M단계 : 매개변수를 추정하는 단계

 

2. 친밀도 전파 알고리즘

: 샘플 간의 similarity로부터 책임 responsibility 행렬R과 가용 availability 행렬 A라는 두 종류의 친밀도 affinity 행렬을 계산하고, 

친밀도 정보를 이용해서 군집을 찾는 알고리즘