Clustering Stability: An Overview <s> Conclusion 3 (Instable clusterings). Assume that Q (∞) K <s> Over the past few years, the notion of stability in data clustering has received growing attention as a cluster validation criterion in a sample-based framework. However, recent work has shown that as the sample size increases, any clustering model will usually become asymptotically stable. This led to the conclusion that stability is lacking as a theoretical and practical tool. The discrepancy between this conclusion and the success of stability in practice has remained an open question, which we attempt to address. Our theoretical approach is that stability, as used by cluster validation algorithms, is similar in certain respects to measures of generalization in a model-selection framework. In such cases, the model chosen governs the convergence rate of generalization bounds. By arguing that these rates are more important than the sample size, we are led to the prediction that stability-based cluster validation algorithms should not degrade with increasing sample size, despite the asymptotic universal stability. This prediction is substantiated by a theoretical analysis as well as some empirical results. We conclude that stability remains a meaningful cluster validation criterion over finite samples. <s> BIB001 </s> Clustering Stability: An Overview <s> Conclusion 3 (Instable clusterings). Assume that Q (∞) K <s> We consider a framework of sample-based clustering. In this setting, the input to a clustering algorithm is a sample generated i.i.d by some unknown arbitrary distribution. Based on such a sample, the algorithm has to output a clustering of the full domain set, that is evaluated with respect to the underlying distribution. We provide general conditions on clustering problems that imply the existence of sampling based clustering algorithms that approximate the optimal clustering. We show that the K-median clustering, as well as K-means and the Vector Quantization problems, satisfy these conditions. Our results apply to the combinatorial optimization setting where, assuming that sampling uniformly over an input set can be done in constant time, we get a sampling-based algorithm for the K-median and K-means clustering problems that finds an almost optimal set of centers in time depending only on the confidence and accuracy parameters of the approximation, but independent of the input size. Furthermore, in the Euclidean input case, the dependence of the running time of our algorithm on the Euclidean dimension is only linear. Our main technical tool is a uniform convergence result for center based clustering that can be viewed as showing that the effective VC-dimension of k-center clustering equals k. <s> BIB002
has a unique global optimum. If Instab(K, n) is large, the idealized K-means clustering tends to have cluster boundaries in high density regions of the space. There exist two different derivations of this conclusion, which have been obtained independently from each other by completely different methods BIB002 von Luxburg, 2008, Shamir and BIB001 . On a high level, the reason why the conclusion tends to hold is that if cluster boundaries jitter in a region of high density, then more points "change side" than if the boundaries jitter in a region of low density. First derivation, informal, based on Tishby (2008b, 2009) . Assume that n is large enough such that we are already in the asymptotic regime (that is, the solution c (n) constructed on the finite sample is close to the true population solution c ( * ) ). Then the rescaled instability computed on the sample is close to the expression given in Equation (3.4). If the cluster boundaries B ij lie in a high density region of the space, then the integral in Equation (3.4) is largecompared to a situation where the cluster boundaries lie in low density regions of the space. From a high level point of view, this justifies the conclusion above. However, note that it is difficult to identify how exactly the quantities p, B ij and V ij influence RInstab, as they are not independent of each other. Second derivation, more formal, based on Ben-David and von Luxburg (2008) . A formal way to prove the conclusion is as follows. We introduce a new distance d boundary between two clusterings. This distance measures how far the cluster boundaries of two clusterings are apart from each other. One can prove that the K-means quality function Q K has a unique global optimum, we can invert this argument and show that if a clustering C is close to the optimal limit clustering C * , then the distance d boundary (C, C * ) is small. Now consider the clustering C (n) based on a sample of size n. One can prove the following key statement. If C (n) converges uniformly (over the space of all probability distributions) in the sense that with probability at least 1 − δ we have d boundary (C n , C) ≤ γ, then Instab(K, n) ≤ 2δ + P (T γ (B) ). (3.5) Here P (T γ (B)) denotes the probability mass of a tube of width γ around the cluster boundaries B of C. Results in BIB002 establish the uniform convergence of the idealized K-means algorithm. This proves the conjecture: Equation (3.5) shows that if Instab is high, then there is a lot of mass around the cluster boundaries, namely the cluster boundaries are in a region of high density. For stable clusterings, the situation is not as simple. It is tempting to make the following conjecture.