Revisiting k-means: New Algorithms via Bayesian Nonparametrics

By Brian Kulis, Michael I. Jordan. International Conference on Machine Learning, 2011

412 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Signal Processing

View Paper: https://www.semanticscholar.org/paper/b026ae62a9789501e002d1bc5f7d3d417a3c1ab1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Signal Processing

Citations in the corpus

Robust continuous clustering (2017, methodology): “Signiﬁcant advances in the last two decades include spectral clustering (2–4), generalizations of classic center-based methods (5, 6), mixture models (7, 8), mean shift (9), afﬁnity propagation (10), subspace clustering (11–13), nonparametric methods (14, 15), and feature selection (16–20).”
Web-Scale Image Clustering Revisited (2015, methodology): “There are several methods for estimating k even dynamically like component annihilation [12], DP-Means [21] and EGM [2]; here we choose to integrate our approach with EGM, which comes as a natural extension at nearly zero cost.”
Practical Coreset Constructions for Machine Learning (2017, background): “By analyzing the case where σ approaches zero, Kulis and Jordan [2012] show that the Gibbs sampler converges to a hard clustering algorithm.”
Infinite Mixture Prototypes for Few-Shot Learning (2019, methodology): “To counter these issues, DP-means (Kulis & Jordan, 2012) λ , the distance threshold for creating a new cluster, is the sole hyperparameter for the algorithm.”
A tutorial on task-parameterized movement learning and retrieval (2015, methodology): “, determining the number of Gaussians in the GMM) is compatible with the techniques employed in standard GMM, such as the use of a Bayesian information criterion [81], Dirichlet process [73, 22, 64, 49], iterative pairwise replacement [82], spectral clustering [68, 84, 52], or based on segmentation ”
Control of robotic mobility-on-demand systems: A queueing-theoretical perspective (2014, methodology): “Demand prediction can be achieved with Bayesian nonparametric techniques such as Dirichlet process mixture models (Kulis and Jordan, 2012; Campbell et al., 2013).”
An embedded segmental K-means model for unsupervised segmentation and clustering of speech (2017, background): “It can be shown that standard K -means results from a GMM as the variances approach zero [41, § 20.3.5], [42].”
Variable Selection in Heterogeneous Datasets: A Truncated-rank Sparse Linear Mixed Model with Applications to Genome-wide Association Studies (2017, methodology): “ously [28], [2], however, these procedures require specifying unknown hyperparameters, even when replaced by sparse PCA [29] or Bayesian K-means [30].”
Convex Discriminative Multitask Clustering (2013, methodology): “In [48], Kulis and Jordan first revisited a regularized k-means algorithm in the view of the Dirichlet process and then extended it to MTC by sharing the clusters of the observations across the tasks.”
Transferable AutoML by Model Sharing Over Grouped Datasets (2019, methodology): “Since k-means is the well known hard decision cluster method, as well as its sequential version [13, 20], we will compare with k-means and sequential k-means in the experiments.”
SWIRL: A sequential windowed inverse reinforcement learning algorithm for robot tasks with delayed rewards (2018, methodology): “However, we apply results from Bayesian non-parametric statistics and jointly solve for the component parameters and the number of components using a Dirichlet Process [22].”
Discovering Latent Domains for Multisource Domain Adaptation (2012, methodology): “The hard HDP seeks to minimize the distance between data points and their local mean plus data points to their assigned global mean, whereas we introduce an intermediate latent variable for the local cluster means.”