Machine Learning Algorithms

Cluster instability

Another approach is based on the concept of cluster instability defined in Von Luxburg U., Cluster stability: an overview, 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 of m perturbed (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 purposes, we need to find ...