[DEC] Unsupervised Deep Embedding for Clustering Analysis

1) Deep Cluster Pipeline:

Phase 1:

• Network architecture: “Denoising” stacked autoencoder

• Iterative training of successive layers using input-output MSE: ReLU, dropout

• Trained layers stacked into a deep autoencoder and fine-tuned (SGD)

• Resulting encoder (its latent representation) used as feature space

Phase 2:

• Run traditional k-means to obtain the initial locations of centroids μk (20 restarts, picking the best solution)

• Calculate P, Q and KL loss.

• Update the centroids.

• If more than tol% (tolerance) examples changed assignment, go to step 2

Notice: This phase does not introduce any extra parameters (except for 𝜈 ) 

2) Clustering Loss Function:

• Student’s t-distribution can be used as the kernel to measure the similarity (van der Maaten and Hinton, 2008) between points μj and centroids.

• The q_ij:

  1. are normalized,

  2. implement soft assignment of objects to clusters

• Note: q_ij define a probability distribution Q. If we had a reference distribution P, we could define our loss as KL divergence

• Naive option: define P as delta distribution (one-hot vector).

• However, because Q is soft, it’s better to define P also as a soft distribution.

• What do we want?

  1. Strengthen predictions (i.e., improve cluster purity),

  2. Put more emphasis on data points assigned with high confidence, and

  3. Normalize loss contribution

• By squaring the original distribution and then normalizing it, the auxiliary distribution P forces assignments to have stricter probabilities (closer to 0 and 1).

Other implementations of DEC:

• Original Caffe: https://github.com/piiswrong/dec

• PyTorch: https://github.com/CharlesNord/DEC-pytorch and https://github.com/eelxpeng/dec-pytorch

• Keras: https://github.com/XifengGuo/DEC-keras and https://github.com/fferroni/DEC-Keras

• MXNet: https://github.com/apache/incubator-mxnet/blob/master/example/deep-embedded-clustering/dec.py

• Chainer: https://github.com/ymym3412/DeepEmbeddedClustering

References:

• https://medium.com/@dptmn200/unsupervised-deep-embedding-for-clustering-analysis-a-summary-f6e5f2dce94f