Clustering Validation: Silhouette, Gap, ARI and Choosing k

Draw 500 points uniformly in a square, a dataset with no clusters at all. Run k-means for \(k = 2, 3, 4, 6\) and compute the silhouette score: 0.36, 0.38, 0.41, 0.39. Many tutorials call that range "reasonable structure", and the best picks \(k=4\). On two interlocking crescents, DBSCAN recovers the true labels exactly and scores silhouette 0.33, while k-means, which cuts both crescents in half, scores 0.49. (Both results come from a small scikit-learn simulation.) The index found structure in noise and preferred the wrong answer on structured data. That is not a bug in silhouette; it is the limit of validation without ground truth.

Internal indices score against a built-in ideal

The silhouette of point \(i\) compares \(a(i)\), its mean distance to other members of its own cluster, with \(b(i)\), the smallest mean distance to the members of any other cluster (Rousseeuw, 1987, Silhouettes: a graphical aid to the interpretation and validation of cluster analysis, J. Comput. Appl. Math. 20):

The mean silhouette rewards compact, well-separated clusters, a convex ideal. Crescents have large \(a(i)\) because their ends are far apart, so the correct answer is penalised. It costs \(O(n^2)\) distances, so it is often computed on a sample.

The gap statistic asks a sharper question: is the within-cluster dispersion lower than it would be on data with no clusters? With \(W_k\) the pooled within-cluster sum of squares at \(k\) clusters (Tibshirani, Walther and Hastie, 2001, Estimating the number of clusters in a data set via the gap statistic, JRSS-B 63(2)):

where \(\mathbb{E}^*\) is estimated from \(B\) reference datasets drawn uniformly over the data's range, or over a box aligned with its principal components. With \(s_k\) the standard deviation of the reference \(\log W_k\) values scaled by \(\sqrt{1 + 1/B}\), the rule chooses the smallest \(k\) with \(\text{Gap}(k) \ge \text{Gap}(k+1) - s_{k+1}\). Because it compares against a null, the gap statistic can return \(k=1\), something silhouette cannot. Its cost is \(B\) full clustering runs per candidate \(k\), and its null is uniform noise, so it answers "better than uniform?" rather than "correct?".

Calinski-Harabasz and Davies-Bouldin use other ratios of between- to within-cluster spread. Every internal index encodes an ideal cluster shape and favours algorithms sharing it.

External indices need chance correction

When reference labels exist, the question becomes agreement between partitions. The Rand index is the fraction of point pairs on which two partitions agree (both together or both apart), and its baseline is badly inflated: two independent random labelings of 1,000 points into 10 groups agree on 82% of pairs, because most pairs are "apart" in both.

The adjusted Rand index subtracts the expectation under a permutation model with fixed cluster sizes (Hubert and Arabie, 1985, Comparing partitions, Journal of Classification 2):

so random agreement scores about 0 (the same two random labelings give \(-0.002\)) and identical partitions score 1.

Normalised mutual information has the same disease in a subtler form, and it worsens with the number of clusters. Two random labelings into 200 groups over 1,000 points have NMI 0.67, which looks like substantial agreement, while adjusted mutual information is \(-0.002\) (Vinh, Epps and Bailey, 2010, Information Theoretic Measures for Clusterings Comparison, JMLR 11). Papers that report raw NMI for methods producing many small clusters are, in effect, rewarding fragmentation. ARI tends to be dominated by the large clusters and AMI by the small ones; neither is uniformly preferred, and the choice should follow which errors matter.

Why no index can settle it

Kleinberg formalised the suspicion that "the right clustering" is underdetermined (Kleinberg, 2002, An Impossibility Theorem for Clustering, NeurIPS). Treat a clustering function \(f\) as a map from a distance function \(d\) on \(n \ge 2\) points to a partition, and ask for three properties:

• Scale invariance: \(f(\alpha d) = f(d)\) for every \(\alpha > 0\).
• Richness: every partition of the points is \(f(d)\) for some \(d\).
• Consistency: if \(d'\) shrinks distances within clusters of \(f(d)\) and stretches distances between them, then \(f(d') = f(d)\).

No function satisfies all three. Single linkage with a suitable stopping rule satisfies any two, and which two depends on the rule: stop at \(k\) clusters and richness fails; stop at a fixed distance threshold and scale invariance fails.

The theorem does not make clustering hopeless: weakening consistency or returning a hierarchy escapes it. The field disagrees about the lesson. One reading is that clustering is only well posed relative to a downstream purpose, so the only honest validation is task performance. Another is that stability under resampling is a usable proxy: recluster bootstrap resamples and keep the \(k\) whose partitions agree most (von Luxburg, 2010, Clustering Stability: An Overview, Foundations and Trends in Machine Learning 2(3)). Stability measures reproducibility, though, not correctness. Three well-separated blobs, two of them close together, can give a highly stable \(k=2\).

When it breaks

Selecting \(k\) with an index and then reporting that index is circular. The reported value is optimistically biased, like validation accuracy after tuning on it.

External labels are one valid partition among many. Benchmark "ground truth" is a human taxonomy, and a method finding finer or orthogonal structure scores low ARI while being right.

Every index depends on the representation. Silhouette on raw features, standardised features and a learned embedding can rank the same candidates three different ways. Choosing the representation is usually the larger part of validation.

The elbow is mostly absent. Dispersion usually falls smoothly, and reading an elbow off it is choosing \(k\) by eye.