Revisiting k-means: New Algorithms via Bayesian Nonparametrics

Abstract

Bayesian models offer great flexibility for clustering applications---Bayesian nonparametrics can be used for modeling infinite mixtures, and hierarchical Bayesian models can be utilized for sharing clusters across multiple data sets. For the most part, such flexibility is lacking in classical clustering methods such as k-means. In this paper, we revisit the k-means clustering algorithm from a Bayesian nonparametric viewpoint. Inspired by the asymptotic connection between k-means and mixtures of Gaussians, we show that a Gibbs sampling algorithm for the Dirichlet process mixture approaches a hard clustering algorithm in the limit, and further that the resulting algorithm monotonically minimizes an elegant underlying k-means-like clustering objective that includes a penalty for the number of clusters. We generalize this analysis to the case of clustering multiple data sets through a similar asymptotic argument with the hierarchical Dirichlet process. We also discuss further extensions that highlight the benefits of our analysis: i) a spectral relaxation involving thresholded eigenvectors, and ii) a normalized cut graph clustering algorithm that does not fix the number of clusters in the graph.

14 pages. Updated based on the corresponding ICML paper

Cited by in corpus (38)

• Discussion on Bayesian Cluster Analysis: Point Estimation and Credible Balls by Sara Wade and Zoubin Ghahramani
• Bayesian cluster analysis: Point estimation and credible balls
• $k$-POD: A Method for $k$-Means Clustering of Missing Data
• Cross-Entropy Clustering
• MAD-Bayes: MAP-based Asymptotic Derivations from Bayes
• Contingency-Aware Exploration in Reinforcement Learning
• $k$-means as a variational EM approximation of Gaussian mixture models
• SPF-CellTracker: Tracking multiple cells with strongly-correlated moves using a spatial particle filter
• Multilevel Clustering via Wasserstein Means
• MAD Bayes for Tumor Heterogeneity Feature Allocation with Non-Normal Sampling
• Dynamic Clustering via Asymptotics of the Dependent Dirichlet Process Mixture
• Large-Margin Metric Learning for Partitioning Problems
• Subspace clustering without knowing the number of clusters: A parameter free approach
• Player Behavior and Optimal Team Composition for Online Multiplayer Games
• A Sparse Non-negative Matrix Factorization Framework for Identifying Functional Units of Tongue Behavior from MRI
• Optimistic Concurrency Control for Distributed Unsupervised Learning
• Big Learning with Bayesian Methods
• A survey on Bayesian inference for Gaussian mixture model
• Fast Learning of Clusters and Topics via Sparse Posteriors
• Bayesian Hierarchical Clustering with Exponential Family: Small-Variance Asymptotics and Reducibility
• Prototypical Networks for Multi-Label Learning
• Further heuristics for $k$-means: The merge-and-split heuristic and the $(k,l)$-means
• Combinatorial Topic Models using Small-Variance Asymptotics
• Generalized Dirichlet-process-means for $f$-separable distortion measures
• Scalable Neural Network Compression and Pruning Using Hard Clustering and L1 Regularization
• SLAM with Objects using a Nonparametric Pose Graph
• AdaCluster : Adaptive Clustering for Heterogeneous Data
• Entropy Regularized Power k-Means Clustering
• Can Co-robots Learn to Teach?
• Bayesian Nonparametric Graph Clustering
• Penalized k-means algorithms for finding the correct number of clusters in a dataset
• Geometric Dirichlet Means algorithm for topic inference
• On Efficient Multilevel Clustering via Wasserstein Distances
• Simple Deep Random Model Ensemble
• Power-Law Graph Cuts
• Detailed Derivations of Small-Variance Asymptotics for some Hierarchical Bayesian Nonparametric Models
• Bayesian Nonparametric Modeling of Driver Behavior using HDP Split-Merge Sampling Algorithm
• Bregman-divergence-guided Legendre exponential dispersion model with finite cumulants (K-LED)