An Empirical Analysis on the Stability of Clustering Algorithms

One of the aspects of a clustering algorithm that should be considered for choosing an appropriate algorithm in an unsupervised learning task is stability. A clustering algorithm is stable (on a dataset) if it results in the same clustering as it performed on the whole dataset, when actually performs on a (sub)sample of the dataset. In this paper, we report the results of an empirical study on the stability of two clustering algorithms, namely k-Means and normalized spectral clustering, along with some analysis on those results that are useful for practitioners who deal with scalability and researchers who employ stability as a tool for model selection.