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는 
- 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에 적용했다는 점이 인상깊었다.