Good (K-means) clusterings are unique (up to small perturbations)
Good (K-means) clusterings are unique (up to small perturbations)
复制标题
DOI：
10.1016/j.jmva.2018.12.008
复制
发表时间：
2019-09
期刊：
影响因子：
--
通讯作者：
M. Meilă
中科院分区：
文献类型：
--
作者：
M. Meilă
如果我们找到了数据集的“良好”聚类C，我们是否可以证明C与这些数据的（未知）最佳聚类C opt 相差不远？也许令人惊讶的是，这个问题的答案有时是肯定的。本文给出了距离 d (C, C opt) 的谱界限，适用于通过二次成本来衡量“优度”的情况，例如 K 均值聚类的平方失真或谱聚类的归一化切割准则。仅当数据承认“良好”、低成本的聚类时，边界才存在。本文的结果是非渐近且无模型的，即没有对数据生成过程做出任何假设。界限不依赖于未定义的常量，并且可以根据数据轻松计算。
If we have found a “good” clustering C of a data set, can we prove that C is not far from the (unknown) best clustering C opt of these data? Perhaps surprisingly, the answer to this question is sometimes yes. This paper gives spectral bounds on the distance d (C, C opt) for the case when “goodness” is measured by a quadratic cost, such as the squared distortion of K-means clustering or the Normalized Cut criterion of spectral clustering. The bounds exist only if the data admit a “good”, low-cost clustering. The results in this paper are non-asymptotic and model-free, in the sense that no assumptions are made on the data generating process. The bounds do not depend on undefined constants, and can be computed tractably from the data.