PaperlayerView exact revision on arXiv

Source-linked AI summary

N2D: (Not Too) Deep Clustering via Clustering the Local Manifold of an Autoencoded Embedding

Ryan McConville, Raul Santos-Rodriguez, Robert J Piechocki, Ian Craddock

arXiv:1908.05968v6cs.LGstat.ML

TL;DR

Conventional clustering typically requires hand-engineered features, while deep clustering commonly uses a neural clustering network alongside learned representations. N2D applies manifold learning to an autoencoded embedding and then uses shallow clustering; it reports competitive results across datasets and finds UMAP particularly effective on the embedding.

  • Problem

    Conventional clustering typically requires hand-engineered features that are time-consuming, brittle, and influential on clustering performance.

    Source: §I · p. 1

  • Method

    N2D applies manifold learning to an autoencoded representation and clusters the resulting embedding with a shallow algorithm.

    Source: §I · pp. 1–2

  • Results

    N2D is reported as competitive with state-of-the-art deep clustering across datasets and outperforms those methods on several; on autoencoded embeddings, UMAP outperforms Isomap and t-SNE on all datasets.

    Source: §I · p. 2, E. Role of Each Component of N2D · p. 5

  • Takeaways & Limitations

    The results support learning a local manifold of an autoencoded embedding, while preserving some global structure as UMAP does, to discover a clusterable manifold across image and time-series datasets.

    Source: E. Role of Each Component of N2D · p. 6, §V · p. 7

Abstract

from arXiv · show

Deep clustering has increasingly been demonstrating superiority over conventional shallow clustering algorithms. Deep clustering algorithms usually combine representation learning with deep neural networks to achieve this performance, typically optimizing a clustering and non-clustering loss. In such cases, an autoencoder is typically connected with a clustering network, and the final clustering is jointly learned by both the autoencoder and clustering network. Instead, we propose to learn an autoencoded embedding and then search this further for the underlying manifold. For simplicity, we then cluster this with a shallow clustering algorithm, rather than a deeper network. We study a number of local and global manifold learning methods on both the raw data and autoencoded embedding, concluding that UMAP in our framework is best able to find the most clusterable manifold in the embedding, suggesting local manifold learning on an autoencoded embedding is effective for discovering higher quality discovering clusters. We quantitatively show across a range of image and time-series datasets that our method has competitive performance against the latest deep clustering algorithms, including out-performing current state-of-the-art on several. We postulate that these results show a promising research direction for deep clustering. The code can be found at https://github.com/rymc/n2d

I. INTRODUCTION

Conventional clustering often depends on hand-engineered features, while deep clustering learns representations and clusters them with neural networks. N2D instead applies manifold learning to an autoencoded embedding before shallow clustering, and reports competitive results across datasets.

  • Conventional clustering methods such as k-means, GMMs, DBSCAN, and hierarchical algorithms [12] typically require hand-engineered features that are time-consuming, brittle, and influential on performance.Feature selection may also be needed to eliminate redundant or poor-quality features, a task made more challenging in unsupervised settings.Source: §I · p. 1
  • Autoencoders learn representations from raw data by reconstructing the input, providing features without manual extraction and selection.A bottleneck can regularize the reconstruction by inducing a compressed representation.Source: §I · p. 1
  • Deep clustering typically combines automatically learned features with a neural clustering network, sometimes jointly learning the representation and clustering.Guo et al., for example, pre-train an autoencoder, initialize a deep clustering network with k-means, and then train the two jointly.Source: §I · p. 1
  • N2D replaces the clustering network with manifold learning on an autoencoded representation, then applies a conventional shallow clustering algorithm.The study compares local and global manifold methods on both raw data and autoencoded embeddings.Source: §I · pp. 1–2
  • N2D is reported as top-3 among state-of-the-art deep clustering methods across datasets and outperforms state-of-the-art methods on several.The framework shallow-clusters the manifold-reembedded space.Source: §I · p. 2

II. RELATED WORK

Related work spans conventional clustering and feature learning, deep clustering architectures, and methods that apply manifold learning to existing embeddings. These approaches vary in how they learn representations, impose clustering objectives, and use local or global structure.

  • Conventional clustering includes hierarchical methods, which split or merge clusters, and partitional methods such as k-means and GMMs.K-means minimizes squared distances to cluster centroids; GMMs use covariance structure and latent Gaussian centers.Source: §II · p. 2
  • Feature-learning methods include autoencoders and non-deep techniques such as PCA, ICA, LLE, and Isomap, which preserve different data structures.PCA preserves important structure, while LLE and Isomap preserve geometric and neighbour properties.Source: §II · p. 2
  • Deep clustering separates or combines representation learning and clustering, using networks such as MLPs, CNNs, and GANs with reconstruction, generative, or clustering losses.Some methods combine losses through joint training, often weighting the clustering loss below the non-clustering loss.Source: §II · p. 2
  • IDEC and ASPC-DA initialize clustering networks from autoencoders and jointly train them, while DEC and JULE use a single combined loss.JULE integrates representation learning and clustering in a recurrent model, which the passage describes as inefficient.Source: §II · p. 2
  • Prior embedding work applied LLE to windows of word embeddings for word-similarity tasks, whereas N2D targets the manifold of an entire embedding for clusterability.Other work incorporated locality into autoencoder learning for document clustering and classification.Source: §II · p. 2

III. METHOD

N2D combines an autoencoder representation with a manifold learner that explicitly considers local structure. The method examines Isomap as a global alternative for finding structure in that embedding.

III. METHOD

  • N2D augments an autoencoder, which does not explicitly account for local structure, with a manifold learning technique that does.The method aims to improve representation quality in terms of clusterability.Source: §III · p. 2, A. Autoencoder · p. 3

A. Autoencoder

  • An autoencoder maps input x to a feature vector h and decodes h back to a reconstruction r, learning by minimizing a loss that penalizes dissimilarity from x.Mean Squared Error is one possible reconstruction loss; compression can regularize the network.Source: A. Autoencoder · pp. 2–3

B. Isomap

  • Isomap builds a k-nearest-neighbour graph, uses shortest-path geodesic distances to form a global pairwise similarity matrix, and applies classical scaling.Its key parameters here are the number of output components and the number of neighbours.Source: B. Isomap · p. 3

C. t-SNE

The methods differ in the structure they preserve: t-SNE optimizes local distances, while UMAP represents local structure and can also retain more global structure. UMAP uses a neighbourhood graph and a low-dimensional layout, with hyperparameters controlling locality and embedding geometry.

C. t-SNE

  • t-SNE constructs probabilities over data pairs and minimizes the KL divergence between those probabilities and a distribution over mapped points.Its perplexity is related to the number of neighbours and is typically not very sensitive.Source: C. t-SNE · p. 3

D. UMAP

  • UMAP [19] seeks to represent local structure while also better incorporating global structure, and computes a low-dimensional layout from a weighted k-neighbour graph.It optimizes the layout to approximate the original fuzzy topological structure using cross entropy.Source: D. UMAP · p. 3
  • UMAP assumes data are uniformly distributed on a Riemannian manifold with a locally constant metric and local connectivity.Its neighbour count trades local granularity against global structure; the target dimensionality is set to the sought number of clusters, and minimum distance affects point separation.Source: D. UMAP · p. 3

E. N2D

N2D learns an autoencoded representation, re-embeds it with a locality-focused manifold learner, then applies shallow clustering. The method studies manifold choices and defaults, reporting UMAP as superior on the embedding and competitive benchmark performance.

E. N2D

  • Because unsupervised hyperparameters generally cannot be crossvalidated, dimensions equal the cluster count; Isomap uses 5 neighbors, UMAP 20, and UMAP minimum distance 0.The authors consider UMAP's zero minimum distance suitable because their goal is manifold representation rather than visualization.Source: E. N2D · pp. 3–4
  • N2D first autoencodes the raw data, then learns a more clusterable manifold that preserves local distances, and finally applies a shallow clustering algorithm.The method represents this sequence as an autoencoder, manifold learner, and clustering algorithm.Source: E. N2D · p. 4
  • Across three manifold-learning methods on raw data and autoencoded embeddings, UMAP performs best on the embedding, and N2D is competitive with state-of-the-art across image and time-series datasets.The authors also report state-of-the-art results on several datasets and say the manifold-learning step can significantly increase performance.Source: E. N2D · p. 4

IV. EXPERIMENTS

Experiments use diverse datasets, including standard deep-clustering benchmarks. The collection includes image datasets and time-series datasets spanning handwriting, activities, and other data types.

IV. EXPERIMENTS

  • The experiments use a range of diverse datasets, including standard datasets used to evaluate deep-clustering algorithms.Source: §IV · p. 4

A. Datasets

  • Image datasets include MNIST and its 10,000-image test subset, USPS, and Fashion, with 10 classes each.MNIST and Fashion contain 70,000 images; USPS contains 9,298 images and uses 16×16 images rather than MNIST's 28×28.Source: A. Datasets • · p. 4
  • Time-series datasets include pendigits, with 10,992 digit samples represented by stylus coordinates, and HAR, with smartphone sensor data from 30 people across six activities.Source: A. Datasets • · p. 4

B. Evaluation Metrics

The study evaluates unsupervised clustering with accuracy and normalized mutual information. Both metrics range from 0 to 1, with higher values indicating better clustering.

B. Evaluation Metrics

1) Accuracy:

  • Accuracy (ACC) is the best match between ground-truth labels and predicted clusters.Source: 1) Accuracy · p. 4
  • ACC maximizes the fraction of matching labels over mappings between cluster labels and ground-truth labels.Here, y denotes ground-truth labels, c cluster labels, and m mappings between clusters and labels.Source: 1) Accuracy · p. 4

2) Normalized Mutual Information:

This section defines normalized mutual information and describes experimental settings and results analyses. It also distinguishes low-dimensional visualization from the higher-dimensional clustering setup.

2) Normalized Mutual Information:

  • NMI normalizes mutual information to the 0–1 range, where 0 means no mutual information and 1 means perfect correlation.The notation uses H for entropy and I for mutual information between ground-truth and cluster labels.Source: 2) Normalized Mutual Information · p. 4

C. Experimental Settings

  • The autoencoder is a fully connected MLP trained for 1,000 epochs, while UMAP uses 20 neighbors, dimensions equal to the cluster count, and minimum distance 0.The encoder dimensions are d-500-500-2000-c; the decoder mirrors the encoder, and the final clustering uses a GMM with c components and general covariance matrices.Source: C. Experimental Settings · p. 4

D. Results

  • The results section evaluates individual N2D components with accuracy and NMI and compares the full method with other clustering algorithms.Source: D. Results · pp. 4–5
  • Figure 1 visualizes N2D on all six datasets using two dimensions and 5,000 plotted points; clustering instead uses dimensions equal to the cluster count and achieves higher performance.Source: Figure 1 · p. 5
  • Table I evaluates method components with GMM clustering after AE, UMAP, and N2D; some Isomap results are unavailable because it exhausted 64GB of memory.Source: Table I · p. 5

E. Role of Each Component of N2D

Component comparisons show that manifold learning improves clustering metrics and that UMAP on the autoencoded embedding performs best among the tested manifold methods. Across benchmarks, N2D is consistently competitive, while its largest reported gains and practical runtime vary by dataset.

E. Role of Each Component of N2D

  • Adding manifold learning improves cluster accuracy and NMI over the individual components, while GMM typically performs poorest across datasets.Table I reports component-level accuracy and NMI comparisons.Source: E. Role of Each Component of N2D · p. 5
  • On raw data, Isomap beats t-SNE on 2 of 4 processable datasets but fails on 2 of 6 from 64GB memory exhaustion; on embeddings, it wins on 1 of 4.Thus, the raw-data comparison is limited to the datasets Isomap could process.Source: E. Role of Each Component of N2D · p. 5
  • On autoencoded embeddings, N2D with UMAP outperforms Isomap and t-SNE on all datasets; UMAP is also superior on 3 of 6 raw datasets.The authors identify a locally focused learner that also captures some global structure as best suited to finding a clusterable manifold.Source: E. Role of Each Component of N2D · pp. 5–6
  • N2D ranks in the top three on 5 of 6 datasets and has the best accuracy and NMI on Fashion, pendigits, and HAR.The comparison includes shallow and deep clustering algorithms; some dataset scores were unavailable because they were not tested or could not readily be computed.Source: Table II · p. 6
  • N2D gains 25 percentage points over AE and UMAP on HAR, and about 15 percentage points in accuracy on MNIST and USPS.The authors report the largest gains over subcomponents on HAR.Source: E. Role of Each Component of N2D · p. 6
  • N2D clusters MNIST and Fashion-MNIST in around 18 minutes and the remaining four datasets in two to four minutes.The reported stage timings use an AE trained for 1,000 epochs on an Nvidia RTX 2080 Ti, without early stopping; manifold learning uses UMAP.Source: E. Role of Each Component of N2D · p. 6, Table III · p. 6

F. Comparison with other methods

N2D replaces a jointly trained clustering network with UMAP and a GMM, retaining competitive or superior performance while reducing complexity. Results span image and non-image datasets, with ASPC-DA comparisons qualified by its use of data augmentation.

F. Comparison with other methods

  • Unlike IDEC and ASPC-DA, which jointly train a second network with clustering and reconstruction losses, N2D uses UMAP followed by a GMM and is reported as competitive or superior to other methods with less complexity.The comparison includes conventional clustering and recent deep-clustering methods.Source: F. Comparison with other methods · p. 6
  • N2D ranks in the top three on five of six datasets, leads Fashion accuracy by around 5 absolute percentage points over ClusterGAN, and exceeds ASPC-DA on pendigits and HAR accuracy by 11 and 15 percentage points.On MNIST-test, N2D accuracy is around 1 percentage point below JULE and DEPICT and 2 points below top-ranked ASPC-DA.Source: F. Comparison with other methods · pp. 6–7
  • On pendigits and HAR, N2D achieves the best performance among methods with available results and consistently exceeds DEC and IDEC in accuracy and NMI across the datasets.The authors note that results for several image-oriented deep-clustering methods were unavailable or difficult to obtain on these non-image datasets.Source: F. Comparison with other methods · pp. 6–7
  • ASPC-DA typically slightly outperforms N2D on several datasets, and the authors attribute this performance to data augmentation, which they propose to evaluate for N2D in future work.Without augmentation, ASPC-DA accuracy is reported as 0.924 vs 0.988 on MNIST, 0.785 vs 0.973 on MNIST-test, and 0.688 vs 0.982 on USPS.Source: F. Comparison with other methods · p. 7

V. CONCLUSION

The conclusion presents N2D as a less-deep clustering approach that applies manifold learning to an autoencoder embedding before shallow clustering. It reports competitive results across image and time-series datasets, with stronger performance on several datasets.

V. CONCLUSION

  • N2D replaces the clustering network with manifold learning within an autoencoder embedding, then clusters the re-embedded data with a shallow architecture.The conclusion describes this as reducing the deepness of typical deep-clustering algorithms.Source: §V · p. 7
  • The manifold-learning experiments support learning the local manifold of an autoencoded embedding while preserving global structure, as UMAP does, to find a more clusterable embedding.Source: §V · p. 7
  • N2D achieves top-three performance on five of six datasets and surpasses the next-best algorithm by around 5 absolute percentage points in Fashion-MNIST accuracy and 15 percentage points on HAR.The evaluation includes image and time-series datasets and compares N2D with conventional shallow and state-of-the-art deep-clustering approaches.Source: §V · p. 7
Loading 1908.05968v6…