Source-linked AI summary
Unsupervised Deep Embedding for Clustering Analysis
Junyuan Xie, Ross Girshick, Ali Farhadi
TL;DR
Clustering has focused relatively little on learning the feature space in which clustering is performed. DEC jointly learns a lower-dimensional representation and cluster assignments, and experiments report improved performance, robustness, and scalability over prior methods.
Problem
Relatively little work has focused on unsupervised learning of the feature space used for clustering.
Method
DEC jointly learns a lower-dimensional nonlinear representation and cluster assignments by iteratively optimizing a KL divergence clustering objective with a self-training target distribution.
Results
DEC improves clustering accuracy and running time on image and textual datasets, while also showing greater hyperparameter robustness and linear complexity in the number of data points.
Takeaways & Limitations
DEC provides an unsupervised framework for learning representations specialized for clustering without ground-truth cluster-membership labels.
Takeaways & Limitations
DEC assumes that the initial classifier’s high-confidence predictions are mostly correct.
Abstract
from arXiv · showhide
Clustering is central to many data-driven application domains and has been studied extensively in terms of distance functions and grouping algorithms. Relatively little work has focused on learning representations for clustering. In this paper, we propose Deep Embedded Clustering (DEC), a method that simultaneously learns feature representations and cluster assignments using deep neural networks. DEC learns a mapping from the data space to a lower-dimensional feature space in which it iteratively optimizes a clustering objective. Our experimental evaluations on image and text corpora show significant improvement over state-of-the-art methods.
1. Introduction
The paper addresses the limited focus on learning feature spaces for clustering by jointly learning deep representations and cluster assignments. DEC iteratively refines clustering and reports improved accuracy, speed, and hyperparameter robustness on image and textual datasets.
- Motivation: Clustering depends critically on the feature space, yet unsupervised learning of that space has received relatively little attention.The paper notes that raw-pixel Euclidean clustering is ineffective for all but the simplest image datasets.
- Method: DEC defines a parameterized nonlinear mapping from data space X to a lower-dimensional feature space Z while jointly optimizing cluster assignments.This approach adapts deep feature learning to unsupervised clustering rather than supervised benchmark tasks.
- Method: DEC iteratively refines clusters using an auxiliary target distribution derived from current soft assignments, improving both clustering and feature representation.The iterative refinement addresses the absence of labeled data for training the deep network.
- Results: Experiments on MNIST, STL, and REUTERS show significant improvements over standard and state-of-the-art clustering methods in accuracy and running time.The evaluation covers both image and textual datasets.
- Results: DEC is significantly less sensitive to hyperparameter choices than state-of-the-art methods, supporting clustering when supervision is unavailable for cross-validation.The paper identifies this robustness as important for applying clustering to real data.
2. Related work
Prior clustering methods rely on original-space metrics, linear embeddings, or costly graph computations, limiting performance or scalability in high-dimensional and large datasets. DEC instead uses a centroid-based KL-divergence objective to jointly improve cluster assignments and feature representations with O(nk) complexity.
- Distance-based clustering: k-means and GMM are fast and broadly applicable, but their original-space distance metrics tend to fail as input dimensionality increases.These methods are established branches of clustering approaches.
- Embedding-based clustering: Joint dimensionality-reduction and clustering variants use EM-style iterations but remain limited to linear embeddings.They first cluster with k-means, then project into a lower-dimensional space maximizing inter-cluster variance.
- Spectral clustering: Spectral clustering offers more flexible distance metrics and generally outperforms k-means, but graph-based methods are expensive in memory and computation.Deep-autoencoder spectral methods improve performance while further increasing memory consumption.
- KL-divergence embeddings: t-SNE-related methods minimize KL divergence for embedding, with t-SNE complexity O(n^2) and approximations achieving O(n log n).Parametric t-SNE uses a deep neural network to parameterize the embedding.
- DEC: DEC minimizes KL divergence between a centroid-based distribution and an auxiliary target to jointly improve cluster assignments and feature representations.The centroid-based formulation reduces complexity to O(nk), where k is the number of centroids.
3. Deep embedded clustering
DEC jointly learns a nonlinear low-dimensional embedding and cluster assignments by optimizing cluster centers and neural-network parameters in the latent feature space. It initializes the model with a stacked denoising autoencoder and iteratively refines assignments using an auxiliary target distribution.
- Model formulation: DEC maps data into a typically lower-dimensional latent space while jointly learning the embedding parameters θ and k cluster centers.The nonlinear mapping fθ: X → Z is parameterized by a deep neural network to avoid the curse of dimensionality.
- Optimization: DEC alternates between soft assignment of embedded points to centroids and updates driven by high-confidence assignments until convergence.The procedure computes soft assignments, refines fθ and the centroids using an auxiliary target distribution, and repeats until a convergence criterion is met.
- Soft assignment: DEC computes soft assignments with a Student’s t-distribution kernel and fixes its degrees of freedom at α = 1 in all experiments.The resulting qij values represent the probability of assigning sample i to cluster j.
- Target distribution: The clustering objective minimizes KL divergence between soft assignments qi and an auxiliary target distribution pi.The target distribution is designed to strengthen predictions, emphasize high-confidence points, and normalize each centroid’s loss contribution.
- Optimization: The model jointly optimizes centroids and DNN parameters using stochastic gradient descent with momentum, stopping when fewer than tol% of assignments change.Gradients are propagated from the feature-space embeddings through the DNN by standard backpropagation.
- Initialization: DEC initializes its mapping with a stacked denoising autoencoder, discards the decoder after fine-tuning, and obtains initial centroids with k-means in the feature space.The encoder layers provide the initial mapping from the data space to the feature space.
4. Experiments
Experiments evaluate DEC on two image datasets and one text dataset against k-means, LDGMI, and SEC using unsupervised clustering accuracy. DEC outperforms competing methods, is comparatively robust to hyperparameter choices, and benefits from end-to-end training.
- Datasets and baselines: DEC is evaluated on MNIST, STL-10, REUTERS, and a 10,000-example REUTERS subset against k-means, LDGMI, and SEC.MNIST contains 70,000 handwritten digits; STL-10 includes labeled and unlabeled images; REUTERS uses 685,071 pruned documents and tf-idf features from 2,000 word stems.
- Evaluation protocol: Performance is measured with unsupervised clustering accuracy, using the ground-truth category count as the number of clusters.Accuracy finds the best one-to-one mapping between cluster assignments and ground-truth labels.
- Experimental setup: DEC uses a common d–500–500–2000–10 fully connected architecture without dataset-specific cross-validation tuning.The shared architecture is motivated by prior work, with d varying according to each dataset.
- Quantitative results: DEC outperforms all other methods, sometimes by a significant margin, across the best results from 9 hyperparameter settings.Freezing the nonlinear mapping during clustering generally performs worse than DEC, indicating the value of end-to-end training.
- Robustness and efficiency: DEC is more consistent across hyperparameter ranges, with λ = 40 near-optimal on all datasets, and processes the full REUTERS dataset in half an hour with GPU acceleration.The competing methods’ optimal hyperparameters vary widely.
- Qualitative results: DEC’s assignments align well with natural MNIST clusters, while STL-10 assignments are mostly correct for vehicles but partly reflect animal poses instead of categories.MNIST mainly confuses digits 4 and 9.
5. Discussion
DEC’s assumptions are supported by confidence-weighted gradients and increasingly separated MNIST embeddings during KL-divergence minimization. The method benefits from deep embedding and remains fairly robust to imbalance, while generalizability and NMI identify the optimal cluster count.
- Assumption validation: High-confidence points near cluster centers contribute more to the gradient and appear as canonical examples, whereas low-confidence points become ambiguous or mislabeled.On MNIST, examples transition from canonical “5” instances toward ambiguous and eventually mislabeled “8” instances as qij decreases.
- Training dynamics: KL-divergence minimization progressively separates embedded MNIST clusters and correspondingly improves clustering accuracy over training epochs.The progression is visualized with t-SNE applied to embedded points zi.
- Component contribution: Using autoencoder features, SEC and LD-MGI change little while k-means improves but remains below DEC, demonstrating benefits from deep embedding and KL-divergence fine-tuning.The comparison isolates the contribution of DEC’s representation learning and optimization objective.
- Imbalanced data: DEC is fairly robust to cluster-size variation in imbalanced MNIST subsets.The largest cluster is constructed to be 1/rmin times as large as the smallest, and Table 4 evaluates performance under varying retention rates.
- Selecting cluster count: Generalizability and NMI indicate that 9 is the optimal number of clusters, with generalizability dropping sharply from 9 to 10 and NMI highest at 9.The authors attribute the preference for 9 clusters partly to DEC merging visually similar handwritten 9s and 4s.
6. Conclusion
DEC jointly learns clustering assignments and representations through iterative self-training optimization, while providing improved, robust, and scalable unsupervised clustering performance.
- 6. Conclusion: DEC clusters data points in a jointly optimized feature space by iteratively minimizing a KL divergence objective with a self-training target distribution.The method is an unsupervised extension of semisupervised self-training and learns clustering-specialized representations without groundtruth membership labels.
- 6. Conclusion: DEC improves performance and robustness to hyperparameter settings, addressing the difficulty of cross-validation in unsupervised tasks.Its robustness is particularly important because cross-validation is not possible for unsupervised tasks.
- 6. Conclusion: DEC has linear complexity in the number of data points, enabling it to scale to large datasets.The scalability follows from the algorithm’s linear dependence on the number of data points.