Data Clustering and Stability of Finite Samples

Опубликовано 6 сентября 2016, 16:45

Over the past few years, the notion of stability in data clustering algorithms has received growing attention among practitioners as a useful validation tool in a sample-based framework. However, recent theoretical work has shown that as the sample size increases, any clustering model will usually become asymptotically stable, regardless of its fit to the data. 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 validity criterion over finite samples.