[컴퓨터비전] Unsupervised Learning (2)

About K-means

좋은점

다양한 데이터셋에 적용이 가능하다. (데이터 간 distance가 정의 가능하다면)

데이터의 사전 분석이 필요하지 않다. (탐색적인 기법)

빠르고 구현하기 쉬움

나쁜점

직접 K값과 threshold를 지정해야 한다. (dataset에 적합한 hyperparameter를 찾아줘야 함)

느려질 수가 있음 (time complexity: O(KNd) *K=threshold, N=height, d=dimensions)

Local minimum에 빠질 확률이 높음

어떨 때 적용하면 좋을까?

Data mining에서 classification 알고리즘으로 활용

Design choices

Randomly하게 K point로 initial cluster를 활용함, Optimization 시 local minimum에 빠질 위험이 높아짐. (Global minimum이 있음에도 불구하고 local mininum에 빠지게 되는 현상)

이상적인 클러스터링과 현실 (K값 선택의 딜레마)

  개체가 K-means의 K값인 2만큼 clustering되어야 하는데, outlier를 포함해야 하므로 hyperparameter인 k값을 찾지 못하면 아래처럼 outlier까지 잘못 분류해내는 현상이 나타남.

Validation Set*

여러 수의 cluster 수로 돌려봄과 동시에 performance를 비교함

K-means의 K 값을 validation set으로 활용

hyperparameter를 도출하는 set

최종은 test set을 쓰는데, validation set으로 greedy search를 함.

Agglomerative clustering

이 clustering 방법은 K-means와는 다르게 initial K 를 주지 않아도 됨

procedure

1. 모든 point들을 each cluster로 취급한다.

2. 가장 비슷한 pair를 찾고 tree로 clustering한다.

3. parent cluster로 merge한다

4. 2-3과정을 반복해서 binary tree 구축

결과적으로 그림과 같은 tree가 구축되고, 원하는 distance level (depth)에서 짜름으로써 cluster 개수 결정 가능

Pros and cons

Pros

적용 범위가 넓고 구현하기 쉬움

클러스터들은 적응형의 모양을 가지게 됨

클러스터의 수직계층구조를 제공 (binary tree 형태 구성의 특징)

Cons

weighted될 수 있음

K-means처럼 cluster의 수와 threshold를 지정해줘야 함

ultrametric(hyperparameter와 유사한 의미)를 사용해여 의미있는 계층 생성 가능

Attraction basin

  모집단이 가우시안 분포를 따르고 있으면 데이터들이 중앙으로 모이도록 한다.

Mean shift (평균 이동)

Region에 대해 중심값의 boundary(k-means의 k같이)를 주고 mean shift vector만큼 이동한다.

mean shift vector은 kernel density estimation을 통해서 계산한다.

* cluster와 tracking에도 사용이 가능함

Spectral clustering

특징: 개느림 (N개에 대한 모든 distance를 계산하기 때문에)

Segmentation as a result

  segmentation의 결과는 영상에서 최대한 많은 부분을 차지하고 있을 때 가장 좋다.

위쪽 사진은 K값이 2이기 때문에 2개의 꽃을 찾아냈다.