AI/논문

[논문] DEC 리뷰 : Unsupervised Deep Embedding for Clustering Analysis

슈퍼짱짱 2018. 9. 19. 22:25
반응형



Unsupervised Deep Embedding for Clustering Analysis(DEC)
arXiv : 24 May 2016

논문 링크 : https://arxiv.org/pdf/1511.06335.pdf
깃 링크 : https://github.com/piiswrong/dec




1. Introduction

- 데이터 분석과 visualization에서 핵심인 Clustering은 각기 다른 관점에서 unsupervised machine learning으로 널리 연구되어 왔다.
  * What defines a cluster?
  * What is the right distance metric?
  * How to efficiently group instances into cluster?
  * How to validate clusters?

- 클러스터링 알고리즘에서 distance와 dissimilarity는 중요하다.
- Distance는 데이터를 feature space에 표현하는데 중요한 역할을 한다.
  * 예를 들어 k-means 클러스터링 알고리즘에서는 feature space에서 두 포인트 사이의 거리를 Euclidean distance로 측정한다.

- feature space를 고르는 것은 중요하다.
- 아주 간단한 이미지 데이터셋을 제외하고는, raw pixels에서 Euclidean distance를 사용하는 것은 완전히 비효율적이다.

- 본 논문에서는 데이터 기반 접근 방식으로 feature space와 cluster memberships을 동시에 해결할 방법을 제안한다.

- data space X에서 feature space Z(cluster에 최적화된)로 parameterized non-linear mapping을 정의한다.
- clustering에 최적화된 mapping을 학습하기 위해 backpropagation을 통한 SGD(stochastic gradient descent)를 사용한다. 

- cluster assignment와 feature representation(X->Z mapping)을 동시에 해결하길 원한다.
- 하지만, supervised learning이 아니므로, labeled data로 network를 train할 수 없다.
- 대신, 현재 soft cluster assignment로부터 파생된 auxiliary(보조) target 분포로 cluster를 반복적으로 재정의한다.
- 이 process는 점차 clustering뿐 아니라 feature representation도 향상시킨다.

- 이 실험은 image와 text data에서 정확도와, running time면에서 최신의 clustering 기법들 보다 충분히 향상된 성능을 보였다.
- 게다가, DEC는 hyperparameters 선택에 있어서도 훨씬 덜 민감하다.




contribution

(a) deep embedding과 clustering의 공동 최적화
(b) soft assignment를 통한 반복적 재정의

(c) clustering 정확도와 speed에 있어서 최첨단적인 결과




3. Deep embedded clustering


다음과 같은 문제를 정의한다.

중심이 µj , j = 1, . . . , k인 k개의 clusters에 n points의 데이터 존재


- 클러스터링을 data space X 에 바로 하는 것이 아니라, non-linear mapping fθ : X → Z한 feature space Z에서 한다. 

이때, θ는 learnable한 parameter이며, Z는 latent feature space이다.

- θ는 DNN으로 train한다.


- Z의 차원은 일반적으로 X의 차원보다 작다. 그 이유는 "curse of dimensionality(차원의 저주)"를 피하기 위해서이다.

* 차원의 저주에 대한 설명 https://leedakyeong.tistory.com/2?category=799282


- DEC는 feature space Z에서(즉, data space X에서가 아닌 임베딩된 feature space인 Z에서) k 개의 cluster centroids를 train함과 동시에 X->Z로 mapping하는 θ를 train하면서 data를 cluster한다.


- DEC has two phases

(1) parameter initialization with a deep autoencoder.

(2) parameter optimization, where we iterate between computing an auxiliary target distribution and minimizing the Kullback-Leibler(KL) divergence to it.

: 파라미터는 계산된 보조의 타켓 분포와의 KL divergence Loss를 줄이면서 최적화한다. 즉, 계산된 보조의 타겟 분포가 마치 label인 것처럼 supervised learning을 한다. 이때, loss는 두 분포의 차이를 줄여야 하므로 KL divergence를 사용한다.

* KL divergence에 대한 설명 https://leedakyeong.tistory.com/3?category=799282


3.1 Clustering with KL divergence

 X-> Z로 mapping하는 fθ와 초기 cluster centroids가 주어졌다고 가정하고 parameter optimization을 먼저 알아보자.


- unsupervised clustering을 두 step을 번갈아 수행하면서 진행한다.

(1) embedded points(feature space에 뿌려진 points. 즉, X->Z에서 Z)와 cluster centroids사이의 soft assignment 계산

(2) 보조의 타겟 분포를 사용하여 현재의 high confidence assignments로부터 train하여 fθ update 및 cluster centroids 재정의.

즉, 보조의 타겟 분포가 label이 되어 마치 supervised learning인 것 처럼 train하여 parameter 최적화

이 process는 수렴 기준이 충족될 때 까지 반복.



3.1.1 SOFT ASSIGNMENT


embedded point zi 와 centroid µj를 계산하기 위해 t-분포 사용



where zi = fθ(xi) ∈ Z, xi ∈ X 즉, zi는 xi를 embedding한 것.

α는 t-분포의 자유도. 이때, cross-validation을 하지 않기 때문에 자유도는 1. 즉, α=1

qij는 i번째 데이터가 j번째 cluster에 속할 확률. 즉, soft assignment



3.1.2. KL DIVERGENCE MINIMIZATION


- cluster는 높은 신뢰도(unsupervised learning이 보조의 타겟 분포의 도움으로 supervised learning이 되었으므로)로 train하면서 반복적으로 재정의

- 특히, soft assignment를 target distribution에 matching하면서 train

- 즉, soft assignments qi 와 보조의 타겟 분포 pi의 KL divergence loss가 DEC network의 loss가 되는 것


* pi가 qi로 추정하고 싶은 target 분포


그럼 pi는 어떻게 정의?

- naive하게는 cluster의 centroid주변의 일정 threshold외에는 무시하는 delta 분포로 생각 할 수 있으나, qi가 soft assignment(진짜 label이 아닌 계산된 label이기 때문)이므로 pi역시 softer probabilistic target을 사용하는 것이 자연스러움


- 타겟 분포는 다음과 같은 특징이기를 원함

(1) 예측 강화

(2) 높은 신뢰도로 할당된 data point에 더 강조

(3) 클러스터 사이즈로 loss 값을 정규화. 클러스터 사이즈가 클수록 loss에 주는 기여도가 커서 전체 feature space를 왜곡시키는 것을 방지하기 위함


위에따라 pi는 다음과 같이 정의


- 이 training 전략은 마치 self-training처럼 unlabeled dataset에 초기 classifier를 사용하여 labeled data를 만든다.



3.1.3 OPTIMIZATION


- Stochastic Gradient Descent (SGD)로 cluster centers {µj} 와 DNN parameters θ를 동시에 최적화한다. 


3.2 Parameter initialization

3.1 과정은 θ와 초기 cluster centroids가 주어졌다고 가정하고 진행했다. 그럼 이제 DNN parameters θ 와 the cluster centroids {µj}를 초기화 하는 방법을 알아보자


- DEC network에 θ는 a stacked autoencoder (SAE)로 initialize한다.


- SAE network는 를 loss로 minimize하며 train하고, 여기에 encoder부분을 DEC network에 초기 parameter로 사용한다.


- cluster center는 initialize된 network에서 나온 embedded data(feature space Z에 있는)를 k-means로 clustering해서 initialize한다.




즉, 위 과정을 정리하면


SAE train 

-> encoder부분만 DEC의 network로 

-> 위 network로 data space X 에서 feature space Z로 embedding (3.1.1의 qij 구하는 식의 zi) 

-> 이 초기 z들로 k-means를 통해 cluster center(qij 구하는 식의 µj) 

-> 앞 에서 구한 zi 와 µj로 qij 계산 

-> pij(3.1.2)계산 

-> KL divergence Loss 계산 

-> SGD로 network update 

-> update된 network로 다시 zi, uj 계산 

-> ... 


수렴할 때 까지 반복




4. Experiments


- MNIST, STL-10, REUTERS data로 실험



DEC w/o backprop은 DEC에서 X->Z로 mapping하는 fθ를 멈추고 실험 한 것.

즉, feature space는 제일 처음 mapping된 Z이후 변경하지 않고 clustering만 진행.






y축은 각각의 cluster, x축은 왼쪽부터 cluster center에 가장 가까운 순서대로 나열




epoch에 따른 cluster 결과와 Accuracy






내 생각 :

- 이전 클러스터링 알고리즘들은 일단 좌표공간에 데이터를 뿌리고 나면 좌표공간은 고정된 채로 클러스터를 더 잘 나누기 위한 연구를 했다면,

DEC는 좌표공간에 데이터를 뿌리는 것 부터 고민했다는 점

- unsupervised learning을 target 분포를 추정함으로써 마치 supervised learning인 것 처럼 해서 network에 적용했다는 점이 인상깊었다. 




반응형