Unsupervised Deep Embedding for Clustering Analysis

Unsupervised Deep Embedding for Clustering Analysis (Paper)

J. Xie, R. Girshick, A. Farhadi (University of Washington, Facebook AI Reaserch), 2016

1. 서론

Clustering 은 우리가 데이터를 Unsupervised 로 분석하기 위해서 사용하는 방법으로, 이 논문에서는 딥러닝을 활용하여 Feature Representation과 Cluster Assignment 를 동시에하는 것을 목표로 합니다. 첫 번째 목표인, Feature Representation은 X 를 우리에게 주어진 데이터, U 를 우리가 분류하고자 하는 Cluster 라고 할 때, X 를 바로 U 로 맵핑하는 것보다. 어떤 Non Linear 한 Function 을 통해서 더 작은 Dimension Size 를 갖는 Z 로 맵핑하여, 차원의 저주를 회피하겠다는 것으로, X 를 Z 로 맵핑하는 Function 을 훈련하는 것에 있다고 볼 수 있겠습니다. 두 번째 목표인 Cluster Assignment 는 U 를 구하는 작업으로, Kmean Clustering 과 KL Divergence 를 활용하여 이루어집니다.

2. 기존연구

(1) Visualizing Data Using T-SNE (Post)

T-Stochastic Neighbor Embedding은 고차원 데이터를 2차원에 시각하기 위한 방법에 대한 연구인데, 이 내용중에 고차원 데이터에서 유클리시안 거리를 데이터 포인트의 유사성을 표현하는 조건부 확률로 표현하는 방법과, KL-Divergence 를 활용하여 LOSS Function 을 설계하고 이를 Gradient 를 적용하여 최적화하는 내용이 있는데, DEC 를 이해하는데 있어 필수적이라고 판단된다.

3. 핵심 Idea

DEC 는 크게 두 개의 Step 으로 진행되는데, 첫 번째는 일반적인 SAE(Stacked Auto Encoder)를 훈련하여 Encoder 부의 Weight 값을 초기화 하는 과정이고, 두 번째는 KL Divergence 를 최소화하는 방향으로 Clustering 을 최적화하는 것입니다. 아래의 그림에서 윗 부분의 SAE 를 훈련하는 부분이 첫 번째 Step, 그림의 아래 부분이 두 번째, 훈련된 Encoder 부를 KL Divergence 를 최소화 하는 형태로 최적화 하는 것이 되겠습니다.

(1) Step1 : Pretrain Encoder

유형별로 Compressed Vector 혹은 Latent Space 를 잘 축소하여 표현할 수 있는 Encoder 부를 확보하기 위하여 SAE 를 활용하여 훈련을 진행합니다. 논문에서 훈련시 사용한 Hyper Parameter 는 아래와 같습니다.

set network dimension to d-500-500-2000-10 for all datasets (d is data-space dimension)
iniitalize the weight to random numbers from zero-mean gaussian with std = 0.01
pretrain : epoch 50000, dropout rate = 20%, learning rate = 0.1 (which is divided by 10 every 20000 iterations, weight decay is set to 0.)
DEC train : epoch 100000 without dropout, a constant learning rate of 0.01. The convergence threshold is set to tol = 0.1%
batch size = 256

(2) Step2 : Optimization

이제 KL-Divergence 를 최소화하는 형태로 최적화를 하는 부분입니다. 처음으로 설명할 내용은 Soft Assignment 입니다. t-SNE 에서 봤던, 데이터 간의 거리를 확률로 표현하기 위한 Term 입니다. 다만 다른 점이 있다면, x(i) – x(j) 가 z-u 로 사용되었는데, z 는 위의 step1 의 결과인 Compressed Vector 가 되겠습니다. (X 는 Original Input, Z 는 Compressed Vector) 그리고 u는 Z 를 Kmean Clustering 을 통해 구한 Centroid 가 되겠습니다. 최종적으로 각 데이터 Set 에 대한 각 Cluster 에 속할 확률이 q 로 구해지게 될 것입니다.

T-SNE 에서는 q 가 X(고차원) 에 대한 발생 확률 분포이고, p 가 Y (저차원) 에 대한 발생 확률 분포였으며, KL-Divergence 는 P와 Q 간의 거리를 의미하고 있었다. 현재까지 AutoEncoder 를 통해 구해진 Z 와 Kmean 을 통해 구한 Centroid U 간의 발생 확률 분포를 q 로 구하였는데, 그럼 p (타겟이 되는) 분포는 어떻게 구할 것인가를 설명하도록 하겠습니다. p 를 구하는 것에는 다시 q를 사용하고 있는데, 자세한 식은 아래와 같으며, p 또한 각 Data Set 에 대해서 Cluster 별 발생 확률이 구해지게 될 것입니다.

p 를 구하는 것은 DEC 의 성능에 있어서 매우 중요한 요소로 아래와 같은 점을 감안되도록 수식을 구성하였습니다.

클러스터 내 순도(purity)가 높아지도록 합니다. strengthen predictions (improve cluster purity)
높은 신뢰도를 갖는 할당에 더 가중치를 줍니다. put more emphasis on data points assigned with high confidence
클러스터 사이즈로 손실함수 값을 정규화합니다. 클러스터 사이즈가 클수록 손실함수에 주는 기여도가 커서 전체 피쳐 공간을 왜곡시키는 것을 방지하기 위해서입니다. normalize loss contribution of each centroid to prevent large clusters from distorting the hidden feature space

T-SNE 에서 그랬던 것 처럼 P 와 Q 의 분포를 최소화 하는 것이 최적의 Cluster 를 찾는 DEC 의 목적이 될 것이고, P와 Q 의 분포의 차이가 LOSS Function 이 되며, 이는 아래와 같이 KL-Divergence 를 활용하여 표현이 가능하다.

4. 결론

Epoch 0 이 그냥 SAE 를 사용해서 Clustering 을 한 상태이고, Epoch 1 이상부터가 DEC 개념이 적용되었다고 볼 수 있는데, 결과를 보면, 시각적으로도 더 군집이 확실하게 이루어지며, Accuracy 도 상승하는 것을 볼 수 있다. 30 Epoch 에서 SAE 와 Kmean 을 사용한 Initial 상태 0.80 보다 개선된 0.84 를 보여주고 있다.

이러한 성능의 개선은 불균형한 데이터에서도 동일하게 적용되는데, MNIST 데이터를 일부러 불균형하게 만들어, 테스트한 결과에서도 DEC 를 적용한 것이 더 높은 성능을 보이고 있다.

적절한 클러스터의 수(N) 을 찾는데 아래와 같은 두 가지 지표를 사용하였는데, Normalized Mutual Information(상호정보량) (A와 B가 발생할 확률중에 A와 B가 동시에 발생할 확률) 과 Train Accuracy 와 Validation Accuracy 를 활용하여 모델의 일반화 정도를 측정하여, 3~20개의 Cluster 별로 테스트를 통해 적절한 그룹수를 도출하였다고 한다. 여기에서는 NMI와 G 가 Cross 되는 지점을 활용하였다고 함.