One of the many benefits of Bayesian nonparametric processes such as the Dirichlet process is that they can be used for modeling infinite mixture models, thus providing a flexible answer to the question of how many clusters exist in a data set. For the most part, such flexibility is currently lacking in techniques based on hard clustering, such as k-means, graph cuts, and Bregman hard clustering. For finite mixture models, there is a precise connection between k-means and mixtures of Gaussians, obtained by an appropriate limiting argument. In this paper, we apply a similar technique to an infinite mixture arising from the Dirichlet process (DP). We show that a Gibbs sampling algorithm for DP mixtures approaches a hard clustering algorithm in the limit, and further that the resulting algorithm monotonically minimizes an elegant underlying k-means-like objective that includes a penalty term based on the number of clusters. We generalize our analysis to the case of clustering multiple related data sets through a similar asymptotic argument with the hierarchical Dirichlet process. We discuss additional extensions that further highlight the benefits of our analysis: i) a spectral relaxation involving thresholded eigenvectors, and ii) a normalized cut graph clustering algorithm that requires O(|E|) time per iteration and automatically determines the number of clusters in a graph.

本文从贝叶斯非参数的角度出发，重新审视了k-means聚类算法。通过分析Dirichlet过程混合物的Gibbs抽样算法，我们发现这个算法在极限下接近于硬聚类算法，可以优雅且单调地最小化一个类似k-means的聚类目标，包括对聚类数的惩罚。我们将这个方法推广到了多个数据集的聚类情况，并讨论了进一步的扩展，包括门槛特征向量的光谱松弛和在图中不需要固定聚类数的归一化割图聚类算法。

基于贝叶斯非参数的k-means聚类新算法再探