The stability of a good clustering
Marina Meilă · 2011
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 Copt of these data? Perhaps surprisingly, the answer to this question is sometimes yes. When “goodness” is measured by a quadratic function, such as the squared distortion of K-means clustering, or the Normalized Cut criterion of spectral clustering, this paper proves spectral bounds on the distance d(C, Copt). The bounds exist only when the data admits a “good”, low-cost clustering.