Source-linked AI summary
Revisiting k-means: New Algorithms via Bayesian Nonparametrics
Brian Kulis, Michael I. Jordan
TL;DR
Classical k-means is scalable but lacks the flexible cluster-number and shared-cluster structure of Bayesian nonparametric models. The paper derives hard DP and HDP algorithms through asymptotic limits, proves a penalized k-means-like objective, and extends the approach to spectral and graph clustering.
Problem
k-means is simple and scalable but does not provide Bayesian nonparametric flexibility such as an unfixed number of clusters or shared clusters across data sets.
Method
The paper takes asymptotic limits of DP and HDP mixture inference to derive scalable hard-clustering algorithms, then develops spectral and normalized-cut extensions.
Results
The resulting hard DP algorithm monotonically minimizes a k-means-like objective with a cluster-count penalty, while hard HDP extends this structure to local and global clusters.
Takeaways & Limitations
The approach retains Bayesian models’ flexible clustering structure while featuring the speed and scalability associated with hard clustering and k-means.
Takeaways & Limitations
The DP asymptotic construction requires α to vary as a function of σ and ρ to obtain non-trivial assignments.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper develops scalable hard-clustering algorithms from a Bayesian nonparametric viewpoint, combining k-means-like simplicity with flexible cluster structure. It derives hard DP and HDP procedures, plus spectral and graph-clustering extensions.
- Bayesian nonparametric models support infinite mixtures and hierarchical models can share clusters across data sets, unlike fixed-cluster k-means.
- k-means remains widely used because it is straightforward to implement and scalable, despite requiring a fixed number of clusters.
- The paper uses the limit connecting equal-covariance Gaussian mixtures to k-means to derive hard clustering algorithms from Bayesian nonparametric inference.
- The hard DP algorithm creates a new cluster when a point is sufficiently far from existing centroids and monotonically approaches a local optimum of a penalized k-means-like objective.
- The hard HDP algorithm clusters multiple data sets with local clusters shared into global clusters, penalizing both local and global cluster counts.
- Additional extensions use thresholded eigenvectors for spectral relaxation and a penalized normalized-cut formulation whose graph cluster count is not fixed.
2 Background
The background reviews Gaussian mixtures, k-means, and DP mixtures, emphasizing their connections through EM updates, hard assignments, and infinite-mixture modeling.
- Gaussian mixture models represent observations using component-specific means, covariances, and mixing coefficients, with EM alternating between assignment and parameter-update steps.
- EM produces soft clusterings because γ(z_ic) gives each point’s probability of assignment to component c.
- k-means seeks a hard clustering by alternating point reassignment to the nearest centroid with recomputation of cluster means.
- With equal covariance σI, Gaussian-mixture EM has the k-means update structure, and as σ → 0 assignment probabilities concentrate on the nearest mean.
- A DP mixture extends Gaussian mixtures by allowing infinitely many components through a Dirichlet-process prior over component means and weights.
- DP Gibbs sampling repeatedly reassigns each point to existing clusters or a new cluster, then samples cluster means given their assigned points.
3 Hard Clustering via Dirichlet Processes
The DP Gibbs sampler has a hard-clustering limit analogous to k-means, forming a new cluster when a point is sufficiently far from existing centroids. The resulting algorithm monotonically minimizes a k-means objective augmented with a cluster-count penalty until local convergence.
- Asymptotics: The DP Gibbs sampler becomes a hard assignment procedure in the σ → 0 limit, choosing the smallest value among centroid distances and λ.Only the smallest distance or the new-cluster threshold receives non-zero assignment probability.
- DP-means algorithm: The mean update converges to the empirical mean of the points assigned to each cluster.As σ → 0, the posterior covariance vanishes and its mass concentrates at the assigned-point mean.
- DP-means algorithm: A new cluster is formed when a point is farther than λ from every existing cluster centroid.Otherwise, the point is assigned to its nearest existing centroid.
- Underlying objective: The objective combines the squared-distance k-means term with a penalty proportional to the number of clusters, controlled by λ.The threshold trades off within-cluster fit against cluster proliferation.
- Underlying objective: Algorithm 1 monotonically decreases the penalized objective until local convergence.Reassignment and mean-update steps are non-increasing, and finitely many clusterings remain possible.
- Underlying objective: The analysis provides a constructive algorithm for monotonic local convergence of the penalized k-means objective.The objective had previously been studied in connection with AIC, but the paper states that an algorithm had not been derived from it.
4 Clustering with Multiple Data Sets
The HDP extension clusters multiple data sets using local clusters linked through shared global means. Its asymptotic hard-clustering algorithm minimizes a global k-means objective with penalties for creating local and global clusters until local convergence.
- HDP model: The HDP models multiple data sets by clustering each set locally while sharing some cluster means across data sets.Each local cluster is associated with a global cluster mean.
- HDP model: The HDP adds a global Dirichlet-process layer above data-set-specific Dirichlet processes.The hierarchy uses G0 ∼ DP(γ, H) and Gj ∼ DP(α, G0) for each data set.
- Hard Gaussian HDP: The hard HDP algorithm uses separate local and global thresholds, λℓ and λg, to determine when new clusters are introduced.The resulting procedure is obtained through an asymptotic argument analogous to the hard DP derivation.
- Underlying objective: The optimized objective is a global k-means objective with penalties for creating either a new local cluster or a new global cluster.Appropriate threshold choices produce sharing of cluster structure across data sets.
- Underlying objective: Algorithm 2 monotonically minimizes the HDP objective until local convergence.The paper states that the proof is analogous to the single-DP case.
5 Further Extensions
The paper extends its penalized hard-clustering objective to spectral, kernel, weighted, and graph settings. These extensions replace fixed cluster counts with penalty- or threshold-based selection.
- Spectral relaxation: A spectral relaxation of the DP-means objective uses all kernel-matrix eigenvectors whose eigenvalues exceed λ.The relaxed objective is obtained by optimizing over orthonormal matrices rather than normalized indicator matrices.
- Spectral relaxation: Unlike standard k-means relaxation, which takes the top-k eigenvectors, DP-means thresholds eigenvalues without fixing k.Rows of the resulting eigenvector matrix are subsequently clustered.
- Graph clustering: The graph extension adapts DP-means to normalized and ratio cut objectives while allowing the number of clusters to vary through a penalty.The weighted kernel objective can be evaluated in O(|E|) time for the graph construction described.
- Kernel and weighted clustering: The DP-means and hard Gaussian HDP objectives can be applied in kernel space, where distances to cluster means are computed implicitly.Kernel k-means avoids explicit mean re-estimation by computing distances to implicit cluster means.
- Graph clustering: Weighted kernel k-means connects to penalized normalized cut by choosing K = σD^-1 + D^-1AD^-1 and W = D.Under this construction, optimizing J(K, W) + λk is equivalent to optimizing Cut(A) + λ′k, with λ′ = λ − σ − 1.
6 Experiments
Experiments show that DP-means retains clustering accuracy while converging faster than Gibbs sampling, and that hard Gaussian HDP improves shared-cluster recovery across data sets. The methods are evaluated with NMI and a farthest-first procedure for selecting λ.
- Setup: The experiments use NMI because it supports comparisons when the number of output clusters differs from ground truth, and select λ with a farthest-first heuristic.For hard HDP, local and global penalties are selected using analogous procedures across data sets.
- Synthetic DP-means: On three synthetic Gaussians, DP-means converges within 8 iterations, returns 3 clusters, and achieves average NMI .89 across 100 runs.It typically exceeds NMI .8 within three iterations, whereas Gibbs sampling requires approximately 3000 iterations to converge to three clusters under validation tuning.
- UCI benchmark: Across 8 UCI data sets, DP-means achieves higher NMI than k-means on 5 data sets and higher NMI than Gibbs sampling on 4.The reported results are averaged over 10 runs after the specified validation and sampling procedures.
- Scalability: On 312,320 Photo Tourism image patches, DP-means converges in 63 iterations, while full Gibbs convergence is infeasible.Per iteration, DP-means takes 37.9 seconds versus 29.4 seconds for Gibbs sampling.
- Hard Gaussian HDP: For shared-cluster synthetic data, hard Gaussian HDP achieves average NMI .81, compared with .77 for pooled k-means and .73 for pooled DP-means.Hard Gaussian HDP finds 17 global clusters and averages 4.4 local clusters per data set.
7 Conclusions and Open Problems
The paper connects Dirichlet-process mixtures with scalable hard-clustering algorithms that retain benefits of Bayesian nonparametric and hierarchical modeling. It identifies several directions for extending the initial analysis.
- Conclusions: The paper develops scalable hard-clustering algorithms from Bayesian nonparametric and hierarchical modeling connections.The stated goal is to retain Bayesian-modeling benefits while providing hard-clustering procedures.
- Open problems: Future work includes local-search improvements, HDP spectral or semidefinite relaxations, and extensions to other nonparametric processes.The paper also proposes exponential-family generalizations and additional comparisons with sampling-based and variational inference methods.