On Efficient Multilevel Clustering via Wasserstein Distances
arXiv:1909.08787
Abstract
We propose a novel approach to the problem of multilevel clustering, which aims to simultaneously partition data in each group and discover grouping patterns among groups in a potentially large hierarchically structured corpus of data. Our method involves a joint optimization formulation over several spaces of discrete probability measures, which are endowed with Wasserstein distance metrics. We propose several variants of this problem, which admit fast optimization algorithms, by exploiting the connection to the problem of finding Wasserstein barycenters. Consistency properties are established for the estimates of both local and global clusters. Finally, experimental results with both synthetic and real data are presented to demonstrate the flexibility and scalability of the proposed approach.
arXiv comment32 pages, 8 figures, JMLR submission. arXiv admin note: substantial text overlap with arXiv:1706.03883
References in corpus (7)
- Fast Computation of Wasserstein Barycenters
- Revisiting k-means: New Algorithms via Bayesian Nonparametrics
- On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms
- Multilevel Clustering via Wasserstein Means
- Bayesian Nonparametric Multilevel Clustering with Group-Level Contexts
- Borrowing strengh in hierarchical Bayes: Posterior concentration of the Dirichlet base measure
- Discrete Wasserstein Barycenters: Optimal Transport for Discrete Data