Source-linked AI summary
Deep $k$-Means: Jointly clustering with $k$-Means and learning representations
Maziar Moradi Fard, Thibaut Thonet, Eric Gaussier
TL;DR
The paper asks how to jointly learn data representations and k-Means clustering rather than relying on representations or optimization steps that are separated. It introduces a continuous reparametrization with differentiable soft assignments, enabling joint stochastic-gradient optimization; across the evaluated collections, Deep k-Means outperforms DCN, while a potential shrinking degeneracy was not observed in practice.
Problem
Traditional clustering can be ineffective on high-dimensional data, motivating representations that are both faithful to the data and adapted to clustering.
Method
Deep k-Means continuously reparametrizes the k-Means objective with a differentiable softmax assignment, jointly optimizing auto-encoder representations and cluster representatives by SGD.
Results
Deep k-Means outperforms DCN on all collections considered under controlled comparisons.
Takeaways & Limitations
The approach provides a truly joint and scalable deep k-Means method that is competitive with deep-clustering state of the art.
Takeaways & Limitations
The loss might theoretically induce embedding-space shrinking, although the authors observed no experimental difference with L2 regularization and omitted it.
Abstract
from arXiv · showhide
We study in this paper the problem of jointly clustering and learning representations. As several previous studies have shown, learning representations that are both faithful to the data to be clustered and adapted to the clustering algorithm can lead to better clustering performance, all the more so that the two tasks are performed jointly. We propose here such an approach for $k$-Means clustering based on a continuous reparametrization of the objective function that leads to a truly joint solution. The behavior of our approach is illustrated on various datasets showing its efficacy in learning representations for objects while clustering them.
1 Introduction
Deep k-Means addresses clustering when original high-dimensional representations are ineffective by jointly learning representations and clustering parameters through gradient updates. The study also emphasizes controlled comparisons across methods.
- Motivation: High-dimensional data representations can make traditional clustering methods ineffective, motivating learned low-dimensional representations.Auto-encoders learn such representations unsupervised through a bottleneck and reconstruction objective.
- Contribution: Deep k-Means jointly learns representations and clustering parameters using only gradient updates rather than alternating continuous and discrete steps.This enables the method to benefit from stochastic gradient descent efficiency.
- Evaluation: The evaluation compares methods using the same auto-encoders, tuned hyperparameters, and, when possible, shared initialization and SGD minibatches.These controls address the effects of architecture choice, hyperparameter selection, initialization, and minibatch order.
2 Related work
Related work spans image-specific and general-purpose deep clustering, including generative and subspace-based approaches. Among k-Means-oriented methods, Deep k-Means is designed to avoid decoupled representation learning and discrete assignment updates.
- Image-specific approaches: Image-clustering methods commonly use convolutional neural networks to learn representations for image data.The cited approaches include recurrent cluster merging and pairwise-clustering formulations.
- General-purpose approaches: General-purpose deep clustering includes variational autoencoder–GMM models and DNN-learned subspace clustering methods.These approaches target clustering beyond image-specific settings.
- k-Means-related approaches: DEN decouples representation learning from k-Means, whereas DCN alternates representation, centroid, and discrete assignment updates.Deep k-Means addresses these differences by targeting joint learning with k-Means and gradient-based optimization.
3 Deep k-Means
Deep k-Means combines auto-encoder reconstruction with a k-Means loss in a learned embedding space, then replaces the hard nearest-representative operation with a differentiable continuous formulation. A softmax assignment and optional deterministic annealing enable joint SGD optimization, while the authors discuss uniqueness and potential shrinking behavior as scope conditions.
- 3 Deep k-Means: The formulation defines objects, K cluster representatives in Rp, differentiable distance functions, and a closest-representative operator for embeddings.For any vector y, cf(y; R) returns the representative closest according to f.
- 3 Deep k-Means: Deep k-Means represents each object with an auto-encoder encoder and jointly optimizes reconstruction and distance to the nearest cluster representative.The balancing parameter λ controls the trade-off between faithful reconstruction and clustering-useful representations.
- 3.1 Continuous generalization of Deep k-Means: The hard k-Means objective is continuously generalized with Gk,f, chosen so the resulting functions are differentiable with respect to representation and representative parameters.The method therefore permits joint optimization for a fixed α using stochastic gradient descent.
- 3.2 Choice of Gk,f: The adopted Gk,f is a parameterized softmax surrogate that is differentiable with respect to θ, R, and α.Its parameter α ranges over [0, +∞).
- 3.3 Choice of α: When the closest representative is unique, increasing α changes assignments from soft toward hard, with the hard limit corresponding to k-Means in the learned embedding space.Deterministic annealing gradually increases α so representatives evolve smoothly from low-temperature initialization toward hard assignments.
- 3.4 Shrinking phenomenon: The authors note that the loss might theoretically shrink the embedding subspace, but L2 regularization made no difference in experiments and was omitted.This potential degeneracy is therefore treated as unimportant in practice within the reported experiments.
4 Experiments
Experiments evaluate DKM on image and text benchmarks against standard, k-Means-related deep, and general-purpose deep clustering baselines. Results support joint representation learning and clustering, while annealing provides a pretraining alternative and DKM variants perform strongly across comparisons.
- Datasets: Experiments cover MNIST, USPS, 20NEWS, and RCV1 image and text clustering benchmarks.MNIST and USPS contain handwritten digits; 20NEWS uses 18,846 documents, while RCV1 uses a 10,000-document subset.
- Baselines and protocol: DKM, DCN, IDEC, AE-KM, and standard k-Means are compared using shared auto-encoders and controlled training settings.The study also aligns initialization and SGD minibatch sequences whenever possible, because run-to-run variance is non-negligible.
- Experimental setup: Hyperparameters controlling reconstruction–clustering trade-offs are selected by line search using validation labels, so the procedure may affect the unsupervised nature of clustering.The reported performance is evaluated on held-out test data, and the authors prefer this transparent procedure to vague or hidden selection.
- Results: DKMa markedly outperforms DCNnp without pretraining on all datasets and achieves performance similar to pretraining-based methods.The authors interpret annealing as an alternative to pretraining.
- Results: AE-KM overall obtains the worst results among pretraining-based representation-learning approaches, reinforcing the importance of jointly learning representations and clustering.Pretraining-based deep clustering methods generally outperform their non-pretrained counterparts, except that DKMa performs strongly without pretraining.
- Results: DKMp significantly improves over DCNp on every collection except RCV1 and is reported as the best deep k-Means clustering method.DCNp performs on par with AE-KM across the reported comparisons.
- Results: Against IDEC, DKMp is significantly better or statistically indistinguishable except for MNIST NMI, making DKM competitive with deep-clustering state of the art.DKMa also significantly outperforms IDECnp except on RCV1.
5 Conclusion
The paper introduces a jointly optimized Deep k-Means approach and reports favorable comparisons across several datasets under controlled experimental conditions.
- The approach jointly optimizes representation and k-Means clustering losses through stochastic gradient descent updates.
- Deterministic annealing provides an alternative initialization strategy alongside pretraining.
- Controlled comparisons use the same architecture, initialization, and minibatches across previous approaches.
- Experiments on several datasets show Deep k-Means outperforming DCN on all collections considered.
A Proof of Property 1
The proof establishes that the differentiable closeness function converges to a hard cluster-membership assignment under a unique closest representative, while fuzzy C-Means membership is a possible alternative with an additional caveat.
- Property A.1 assumes that each object has a unique closest representative according to the distance function.
- As inverse temperature α tends to infinity, the closeness function becomes 1 for the closest representative and 0 for all others.
- Fuzzy C-Means membership functions are identified as valid candidates for the differentiable closeness function.
- The fuzzy C-Means formulation may be undefined when a representative coincides with an object, requiring an additional assumption.
- The deterministic annealing scheme uses α_n+1 = 2^(1/log(n)^2) × α_n with α_1 = 0.1 in DKMa.
D Evaluation measures
The evaluation uses NMI and clustering accuracy as standard measures, with ARI additionally reported in the supplementary material.
- NMI measures normalized mutual information between ground-truth classes and obtained clusters.
- Figure 3 specifies an annealing schedule for inverse temperature α, beginning at α_1 = 0.1.
- NMI is computed from the mutual information of the class and cluster partitions, normalized by their entropies.
- ACC measures the proportion of data points whose clusters can be correctly mapped to ground-truth classes using the Hungarian algorithm.
- ARI counts pairwise agreement or disagreement between classes and clusters and corrects the result for chance.
E Dataset statistics and optimal hyperparameters
Dataset statistics and method-specific trade-off hyperparameters are summarized, with hyperparameter values selected on validation data and ARI results reported separately.
- Table 3 summarizes dataset statistics and optimal trade-off hyperparameters for DKM-, DCN-, and IDEC-based methods.
- The optimal hyperparameter is selected using a validation set disjoint from the test set used for reported results.
- Table 4 reports k-Means-related clustering performance as ARI percentages, averaged with standard deviations over 10 runs.
- Table 4 marks results statistically indistinguishable from the best pretrained or non-pretrained approach for each dataset and metric pair.
F Additional results
Additional results use 10 seeded runs whenever possible and apply Student’s t-test across those samples.
- 10 seeded runs provide the basis for additional results whenever possible.
- Student’s t-test is performed from the 10 samples.
- The reported statistical comparisons therefore draw on repeated seeded evaluations.
F.1 ARI results
The additional experiments report ARI comparisons for k-Means-related methods and compare DKM distance choices on 20NEWS. Cosine distance is tested for clustering while retaining euclidean distance for reconstruction, with lambda selected on validation data.
- ARI comparisons: Table 4 reports k-Means-related methods using the ARI measure across the paper’s datasets.
- ARI comparisons: Table 5 compares DKM and IDEC approaches in terms of ARI.
- Distance choices: The cosine variant uses cosine distance for f and euclidean distance for g, unlike the paper’s euclidean choice for both.
- Distance choices: The cosine-distance results use the optimal lambda determined on the validation set.
F.3 k-Means-friendliness of learned representations
The experiments assess how suitable learned embeddings are for subsequent k-Means clustering. Deep k-Means representations generally improve over autoencoder embeddings, with DKMp performing best overall despite nonsignificant differences on some datasets and metrics.
- Evaluation setup: Table 7 applies k-Means to learned embedding spaces to measure each method’s k-Means-friendliness.
- Evaluation setup: The comparison uses NMI and clustering accuracy, averaged over 10 runs with standard deviation.
- Results: On most datasets, embeddings learned by deep k-Means approaches significantly improve clustering over autoencoder-based representations.
- Results: DKMp representations are overall the most appropriate for k-Means, although differences are not statistically significant for every dataset or metric.
- Interpretation: These findings confirm that deep clustering methods bias their learned representations toward their clustering objectives.