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. When "goodness" is measured by the distortion of K-means clustering, this paper proves spectral bounds on the distance  d ( C, C   opt  ). The bounds exist in the case when the data admits a low distortion clustering.
['Marina Meilă']
The uniqueness of a good optimum for K-means