Central Description Length clustering index

The problem

To tune a clustering algorithm, you need a score that says how good a partition is. Ground-truth labels are not available, so a clustering validation index (CVI) fills that role. Most common CVIs favour compact, convex clusters. Thus, they often choose the wrong number of clusters when the clusters have arbitrary shapes.

The approach

Central Description Length (CDL) scores a partition from three quantities: the within-cluster compactness, the estimated cluster centres and the estimated covariances. It estimates an upper bound on the description length that is tied to the true, unobservable centres. The index needs no labels.

The results

On synthetic benchmarks with non-convex clusters, CDL selected the reference number of clusters more often than the conventional CVIs that we tested. It also reached higher Adjusted Rand Index (ARI) values. The paper also reports results on MNIST, CIFAR-10 and STL-10.

Context

CDL comes from my Ph.D. work at Toronto Metropolitan University with Soosan Beheshti. The thesis studied hyperparameter selection that replaces grid search with a single training run. The same line of work produced the S&S ratio for SVM parameter selection and the $\epsilon$-CoAC learnability framework for regression.