Machine Learning Algorithms - Second Edition

Cluster instability

Another approach is based on the concept of cluster instability which is defined in Cluster stability: an overview, Von Luxburg U., arXiv 1007:1075v1, 7 July 2010. Intuitively, we can say that a clustering approach is stable if perturbed versions of the same dataset produce very similar results. More formally, if we have a dataset, X, we can define a set X_n of m perturbed (down-sampled or noisy) versions:

Considering a distance metric, d(C(X₁), C(X₂)), between two clusterings with the same number (k) of clusters, the instability is defined as the average distance between couples of clusterings of noisy versions:

For our ...