Elamur Research⌕
☰
home / papers / 2016 / Unsupervised Deep Embedding for Clustering Analysis

Unsupervised Deep Embedding for Clustering Analysis

Paper · 2016 · Junyuan Xie, Ross Girshick and Ali Farhadi

Summary

Classic clustering methods such as k-means or GMM measure distances in a fixed, hand-chosen feature space. That space often fails for high-dimensional data like raw image pixels. Xie, Girshick and Farhadi propose Deep Embedded Clustering (DEC), which learns the representation and the cluster assignments together, without labels.

DEC first pretrains a stacked autoencoder to obtain a nonlinear mapping into a low-dimensional space, then initializes centroids there with k-means. It then alternates between two steps:

  • computing soft assignments of points to centroids with a Student's t kernel;
  • building a sharpened auxiliary target distribution that favours confident assignments and normalizes cluster frequency.

The encoder and the centroids are updated by SGD to minimize the KL divergence to that target, a form of unsupervised self-training.

On MNIST, STL (HOG features) and REUTERS, DEC beats k-means, LDMGI and SEC in accuracy and runs faster. It is also less sensitive to hyperparameters, which matters because unsupervised settings offer no labels for tuning. Its cost grows linearly with dataset size.

Key points

  • Accuracy with autoencoder features (Table 3): DEC reaches 84.30% on MNIST, 35.90% on STL-HOG, 72.17% on REUTERS-10k and 75.63% on full REUTERS. AE+k-means scores 81.84%, 33.92%, 66.59% and 71.97% on the same sets.
  • Complexity is O(nk) for n points and k centroids. Spectral methods, by contrast, need quadratic memory for the full graph Laplacian.
  • On imbalanced MNIST subsets with r_min = 0.1, DEC scores 70.10%, versus 66.82% for AE+k-means and 47.14% for plain k-means.
  • Unknown k can be chosen with a "generalizability" ratio (training loss divided by validation loss). On MNIST it drops sharply between 9 and 10 clusters, and NMI also peaks at 9 because DEC merges the similar-looking digits 4 and 9.
  • The Student's t degrees of freedom α is fixed at 1. The Caffe implementation is public at github.com/piiswrong/dec.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of WashingtonSeattle · United States402 works · 212,763 citations🏢MetaMenlo Park · United States214 works · 241,492 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 worksComputer Vision and Pattern Recognition · 3,486 works

Cite

Cite as Junyuan Xie, Ross Girshick and Ali Farhadi. 2016. Unsupervised Deep Embedding for Clustering Analysis. ICML 2016.

The paper itself, not this page. BibTeX from the library's record of the work. arXiv 1511.06335

@inproceedings{xie2016unsupervised,
  title = {{Unsupervised Deep Embedding for Clustering Analysis}},
  author = {Junyuan Xie, Ross Girshick and Ali Farhadi},
  booktitle = {ICML 2016},
  year = {2016},
  eprint = {1511.06335},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1511.06335}
}

References

38 references, 7 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Aggarwal, Charu C and Reddy, Chandan K. Data clustering: algorithms and applications. CRC Press, 2013. find
  2. Alelyani, Salem, Tang, Jiliang, and Liu, Huan. Feature selection for clustering: A review. Data Clustering: Algorithms and Applications, 2013. find
  3. Bellman, R. Adaptive Control Processes: A Guided Tour. Princeton University Press, Princeton, New Jersey, 1961. find
  4. Bengio, Yoshua, Courville, Aaron, and Vincent, Pascal. Representation learning: A review and new perspectives. 2013.
  5. Bishop, Christopher M. Pattern recognition and machine learning. springer New York, 2006. find
  6. Boutsidis, Christos, Drineas, Petros, and Mahoney, Michael W. Unsupervised feature selection for the kmeans clustering problem. In NIPS, 2009. find
  7. Coates, Adam, Ng, Andrew Y, and Lee, Honglak. An analysis of single-layer networks in unsupervised feature learning. In International Conference on Artificial Intelligence and Statistics, pp. 215–223, 2011. find
  8. De la Torre, Fernando and Kanade, Takeo. Discriminative cluster analysis. In ICML, 2006. find
  9. Doersch, Carl, Singh, Saurabh, Gupta, Abhinav, Sivic, Josef, and Efros, Alexei. What makes paris look like paris? ACM Transactions on Graphics, 2012. find
  10. Girshick, Ross, Donahue, Jeff, Darrell, Trevor, and Malik, Jitendra. Rich feature hierarchies for accurate object detection and semantic segmentation. In CVPR, 2014.
  11. Halkidi, Maria, Batistakis, Yannis, and Vazirgiannis, Michalis. On clustering validation techniques. Journal of Intelligent Information Systems, 2001. find
  12. Hinton, Geoffrey E and Salakhutdinov, Ruslan R. Reducing the dimensionality of data with neural networks. Science, 313(5786):504–507, 2006. find
  13. Hornik, Kurt. Approximation capabilities of multilayer feedforward networks. Neural networks, 4(2):251–257, 1991. find
  14. Jia, Yangqing, Shelhamer, Evan, Donahue, Jeff, Karayev, Sergey, Long, Jonathan, Girshick, Ross, Guadarrama, Sergio, and Darrell, Trevor. Caffe: Convolutional architecture for fast feature embedding. arXiv preprint arXiv:1408.5093, 2014.
  15. Krizhevsky, Alex, Sutskever, Ilya, and Hinton, Geoffrey E. Imagenet classification with deep convolutional neural networks. In NIPS, 2012.
  16. Kuhn, Harold W. The hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83– 97, 1955. find
  17. Le, Quoc V. Building high-level features using large scale unsupervised learning. In Acoustics, Speech and Signal Processing (ICASSP), 2013 IEEE International Conference on, pp. 8595–8598. find
  18. LeCun, Yann, Bottou, Léon, Bengio, Yoshua, and Haffner, Patrick. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278– 2324, 1998. find
  19. Lewis, David D, Yang, Yiming, Rose, Tony G, and Li, Fan. Rcv1: A new benchmark collection for text categorization research. JMLR, 2004.
  20. Li, Tao, Ma, Sheng, and Ogihara, Mitsunori. Entropy-based criterion in categorical clustering. In ICML, 2004. find
  21. Liu, Huan and Yu, Lei. Toward integrating feature selection algorithms for classification and clustering. IEEE Transactions on Knowledge and Data Engineering, 2005. find
  22. Long, Jonathan, Shelhamer, Evan, and Darrell, Trevor. Fully convolutional networks for semantic segmentation. arXiv preprint arXiv:1411.4038, 2014. find
  23. MacQueen, James et al. Some methods for classification and analysis of multivariate observations. In Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, pp. 281–297, 1967. find
  24. Nair, Vinod and Hinton, Geoffrey E. Rectified linear units improve restricted boltzmann machines. In ICML, 2010. find
  25. Nie, Feiping, Zeng, Zinan, Tsang, Ivor W, Xu, Dong, and Zhang, Changshui. Spectral embedded clustering: A framework for in-sample and out-of-sample spectral clustering. IEEE Transactions on Neural Networks, 2011. find
  26. Nigam, Kamal and Ghani, Rayid. Analyzing the effectiveness and applicability of co-training. In Proc. of the ninth international conference on Information and knowledge management, 2000. find
  27. Srivastava, Nitish, Hinton, Geoffrey, Krizhevsky, Alex, Sutskever, Ilya, and Salakhutdinov, Ruslan. Dropout: A simple way to prevent neural networks from overfitting. JMLR, 2014.
  28. Steinbach, Michael, Ertöz, Levent, and Kumar, Vipin. The challenges of clustering high dimensional data. In New Directions in Statistical Physics, pp. 273–309. Springer, 2004. find
  29. Tian, Fei, Gao, Bin, Cui, Qing, Chen, Enhong, and Liu, Tie-Yan. Learning deep representations for graph clustering. In AAAI Conference on Artificial Intelligence, 2014. van der Maaten, Laurens. Learning a parametric embedding by preserving local structure. In International Conference on Artificial I… find
  30. JMLR, 2014. van der Maaten, Laurens and Hinton, Geoffrey. Visualizing data using t-SNE. find
  31. Vincent, Pascal, Larochelle, Hugo, Lajoie, Isabelle, Bengio, Yoshua, and Manzagol, Pierre-Antoine. Stacked denoising autoencoders: Learning useful representations in a deep network with a local denoising criterion. JMLR, 2010. find
  32. Von Luxburg, Ulrike. A tutorial on spectral clustering. Statistics and computing, 2007. find
  33. Xiang, Shiming, Nie, Feiping, and Zhang, Changshui. Learning a mahalanobis distance metric for data clustering and classification. Pattern Recognition, 2008. find
  34. Xing, Eric P, Jordan, Michael I, Russell, Stuart, and Ng, Andrew Y. Distance metric learning with application to clustering with side-information. In NIPS, 2002. find
  35. Yan, Donghui, Huang, Ling, and Jordan, Michael I. Fast approximate spectral clustering. In ACM SIGKDD, 2009. find
  36. Yang, Yi, Xu, Dong, Nie, Feiping, Yan, Shuicheng, and Zhuang, Yueting. Image clustering using local discriminant models and global integration. IEEE Transactions on Image Processing, 2010. find
  37. Ye, Jieping, Zhao, Zheng, and Wu, Mingrui. Discriminative k-means for clustering. In NIPS, 2008. find
  38. Zeiler, Matthew D and Fergus, Rob. Visualizing and understanding convolutional networks. In ECCV. 2014.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/xie-2016-unsupervised-deep-embedding-clustering-analysis/