Deep divergence-based approach to clustering

Michael Kampffmeyer, Sigurd Løkse, Filippo Maria Bianchi, Lorenzo Livi, Arnt-Børre Salberg, Robert Jenssen

TL;DR

The authors present Deep Divergence-based Clustering (DDC), a method that performs feature learning and clustering simultaneously in a single end-to-end pipeline. By optimizing a novel loss function based on Cauchy-Schwarz divergence and geometric constraints, DDC achieves state-of-the-art performance on image and text datasets without requiring the cumbersome pre-training steps (like autoencoders) common in other deep clustering methods.

What Problem Does This Paper Address?

Traditional clustering algorithms like k-means often struggle with high-dimensional data (like images) because they rely on simple distance metrics in the raw input space. Deep learning offers a solution by learning hierarchical representations, but most "deep clustering" methods are fragmented. For example, the popular Deep Embedded Clustering (DEC) requires a two-stage process: first, training an autoencoder to learn features, and then fine-tuning for clustering.

The authors identify a gap: the need for a principled, information-theoretic loss function that allows a neural network to discover cluster structures from scratch. They aim to move away from "hand-crafted" pipelines and toward a model that understands the geometry of the output space while maximizing the statistical divergence between clusters.

Methods

The core of the paper is the DDC loss function, which consists of three distinct terms designed to shape the network's hidden representations and cluster assignments:

  1. Cauchy-Schwarz (CS) Divergence ($l_1$): This term measures the dissimilarity between the probability density functions (PDFs) of the clusters. By maximizing this divergence, the network ensures that clusters are well-separated and internally compact. The authors use a Parzen window estimator to make this calculation data-driven and differentiable.
  2. Orthogonality Constraint ($l_2$): To prevent "degenerate solutions"—where the network might collapse all data into a single cluster—this term encourages the cluster assignment vectors to be orthogonal. This effectively acts as a regularizer that promotes a balanced distribution of data across classes.
  3. Simplex Corner Constraint ($l_3$): Since the final layer uses a softmax activation, the output space is a simplex. This term encourages the network to push data points toward the "corners" of the simplex, resulting in "crisp" assignments (where a point clearly belongs to one cluster) rather than ambiguous, soft assignments.

The architecture is flexible: the authors use a LeNet-inspired convolutional neural network (CNN) for image data and a fully connected MLP for vectorial/text data.

Datasets

The authors evaluated DDC on several benchmarks:

  • MNIST: The classic dataset of 70,000 handwritten digits.
  • SEALS-3 & SEALS-2: Real-world aerial RGB images used for detecting seal pups. This is a challenging "in-the-wild" dataset with high variance in the background (ice, water, etc.).
  • Reuters: A large-scale text dataset (800,000 news stories) represented via TF-IDF features.

Key Insights and Ideas

  • End-to-End is Possible: Unlike many competitors, DDC doesn't need a "warm start" from a pre-trained autoencoder. It can learn features and clusters simultaneously from random initialization.
  • Geometry Matters: The authors show that simply maximizing divergence isn't enough. By explicitly exploiting the geometry of the softmax output (the simplex), they force the network to make more confident and distinct clustering decisions.
  • Information Theory meets Deep Learning: The "aha moment" here is the successful adaptation of the Cauchy-Schwarz divergence—a staple of traditional "shallow" clustering—into a differentiable loss function suitable for backpropagation in deep networks.
  • Scalability: Because the method uses mini-batch training, it avoids the $O(n^2)$ memory complexity that plagues spectral clustering, making it viable for massive datasets like Reuters.

Key Results

DDC and its ensemble version (DDC-VOTE) consistently outperformed baselines like k-means, Spectral Embedded Clustering (SEC), and DEC:

  • MNIST: DDC-VOTE achieved an unsupervised accuracy of 88.49%, significantly higher than DEC (84.31%) and k-means (53.33%).
  • Reuters: DDC-VOTE reached 77.62% accuracy, outperforming DEC (63.79%).
  • Robustness: Qualitative results (using guided backpropagation) showed that the network successfully ignores background noise and focuses on the unique features of the objects (e.g., the specific loops in a digit '6').

Limitations and Future Work

  • Balanced Class Assumption: The $l_2$ orthogonality term inherently encourages clusters of similar sizes. While this works well for the balanced datasets used in the paper, it might struggle with highly imbalanced real-world data.
  • Local Minima: Like many unsupervised tasks, DDC can get stuck in local minima. The authors mitigate this by running the model 20 times and using a voting scheme, which adds computational overhead.
  • Future Directions: The authors suggest exploring alternative divergence measures and extending the framework to multi-view clustering, where data comes from multiple sources (e.g., image + text).

Summary updated

Abstract

A promising direction in deep learning research consists in learning representations and simultaneously discovering cluster structure in unlabeled data by optimizing a discriminative loss function. As opposed to supervised deep learning, this line of research is in its infancy, and how to design and optimize suitable loss functions to train deep neural networks for clustering is still an open question. Our contribution to this emerging field is a new deep clustering network that leverages the discriminative power of information-theoretic divergence measures, which have been shown to be effective in traditional clustering. We propose a novel loss function that incorporates geometric regularization constraints, thus avoiding degenerate structures of the resulting clustering partition. Experiments on synthetic benchmarks and real datasets show that the proposed network achieves competitive performance with respect to other state-of-the-art methods, scales well to large datasets, and does not require pre-training steps.
BibTeX
@article{kampffmeyer2019deep,
  author = {Michael Kampffmeyer and Sigurd Løkse and Filippo Maria Bianchi and Lorenzo Livi and Arnt-Børre Salberg and Robert Jenssen},
  title = {{Deep divergence-based approach to clustering}},
  journal = {Neural Networks},
  year = {2019},
  doi = {10.1016/j.neunet.2019.01.015},
}

Loading related content...

Figure