Probabilistic Multilevel Clustering via Composite Transportation Distance

Nhat Ho, Viet Huynh, Dinh Q. Phung, Michael I. Jordan

Abstract

In many real-world applications, data is organized into hierarchical structures, such as words within documents or tags within image collections. We introduce Multilevel Composite Transportation (MCT), a scalable framework for joint local and global clustering. By utilizing a specialized Optimal Transport formulation based on Kullback-Leibler (KL) divergence, MCT provides a robust optimization-based alternative to complex Bayesian nonparametric models, suitable for both continuous and discrete data regimes.

Introduction

In many datasets, observations are organized into groups, necessitating a multilevel approach to clustering. For instance, in a large-scale text corpus, words form topics within individual documents (local level), while documents themselves cluster into broader themes or genres (global level). Standard methods like K-means assume data independence and fail to capture these hierarchical dependencies. While Bayesian nonparametric models like the Hierarchical Dirichlet Process (HDP) address this, they often rely on computationally intensive Markov Chain Monte Carlo (MCMC) sampling, which limits their scalability.

Methodology: Multilevel Composite Transportation

The proposed MCT framework leverages the geometric properties of Optimal Transport to align hierarchical structures. The core innovation lies in the Composite Transportation Distance.

Distribution-Aware Metrics

Traditional Wasserstein distance typically employs Euclidean cost, which is often inappropriate for discrete data like word counts. MCT replaces this with KL divergence. This choice allows the model to naturally accommodate any data following an exponential family distribution, making it "distribution-aware."

Joint Optimization and Barycenters

MCT treats each group of data as a local mixture model. Global clustering is then achieved by finding the Wasserstein barycenter—the geometric average—of these local mixtures. Unlike two-stage approaches that cluster locally and then globally, MCT solves a joint optimization problem, allowing the model to "borrow strength" across groups. This is particularly beneficial for groups with sparse data.

MCT successfully rediscovering bar topics in synthetic discrete data.

To ensure computational efficiency, the authors employ entropic regularization and a coordinate descent algorithm, transforming the inference task into a series of fast iterative matrix operations.

Experimental Evaluation

The effectiveness of MCT was evaluated across synthetic and real-world datasets, spanning both continuous and discrete domains.

Synthetic Data

On synthetic discrete data consisting of "bar topics," MCT demonstrated a high degree of fidelity in rediscovering the underlying generative structures. As shown in the visual comparison of generated versus rediscovered data, the model accurately captures the latent topic distributions.

Real-World Performance

MCT was tested on the LabelMe dataset (continuous GIST features) and the NUS-WIDE dataset (discrete image tags).

  • LabelMe: MCT achieved a Normalized Mutual Information (NMI) of 0.485, significantly outperforming K-means (0.37) and Wasserstein-means (0.423).
  • NUS-WIDE: The advantage was more pronounced in the discrete domain, with MCT reaching an NMI of 0.423 compared to 0.356 for the nearest baseline.

Qualitative analysis of the NUS-WIDE results reveals that MCT successfully identifies semantically coherent clusters. For example, a "pet" cluster emerged containing tags such as bunny, adorable, and cute without prior supervision.

Tag clouds generated from NUS-WIDE clusters showing semantically related groupings.

Conclusion and Future Work

Multilevel Composite Transportation offers a scalable, optimization-centric approach to hierarchical clustering. By integrating KL divergence into the Optimal Transport framework, it bridges the gap between the flexibility of Bayesian models and the efficiency of geometric optimization. Future research directions include the automatic estimation of cluster cardinalities and the incorporation of group-level metadata to further enrich the clustering context.

Summary updated

Abstract

We propose a novel probabilistic approach to multilevel clustering problems based on composite transportation distance, which is a variant of transportation distance where the underlying metric is ...
BibTeX
@inproceedings{ho2019probabilistic,
  author = {Nhat Ho and Viet Huynh and Dinh Q. Phung and Michael I. Jordan},
  title = {{Probabilistic Multilevel Clustering via Composite Transportation Distance}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
}
Figure