Days 4, 15, 22, 25 and 49 of this series built clustering algorithms, and every one of them ended by printing a number. This page is about the number.
Score two labellings of the same items against each other and the whole input is a contingency table. That means the chance level is a finite sum — something you compute, not something you shuffle for — and it is emphatically not zero.
See it: https://dev48.infy.uk/ml/day73-clustering-metric-chance.html
The comparison that matters
240 items. Under the fixed-margin permutation null, the expected mutual information has a closed form, and a labelling that knows nothing at all about the truth scores an exact 0.5637 on homogeneity at k′ = 100.
| labelling | homogeneity | chance-corrected |
|---|---|---|
| uniformly random, 93 clusters | 0.5033 | 0.0003 |
| genuinely gets half the items right | 0.3118 | 0.2919 |
The raw score ranks them backwards. The chance-corrected score ranks them correctly, and by 0.29 of the index's whole range.
Nothing is wrong with the random labelling except that it has a lot of clusters. Homogeneity asks "is each cluster pure?", and a cluster of size 2 is almost always pure. Push k′ up and you approach 1.0 while learning nothing.
Where the crossing happens
The exact k′ at which pure chance overtakes the half-right clustering:
| index | homogeneity | geometric | arithmetic |
|---|---|---|---|
| chance overtakes at k′ = | 50 | 92 | 116 |
Three normalisations of the same quantity, three different answers to "how many clusters before this metric is lying to me". None of them is far enough away to be safe: 50 clusters on 240 items is not an unusual configuration.
# the fix is not a bigger sample, it is a subtraction
adjusted = (observed - expected_under_null) / (max_possible - expected_under_null)
# expected_under_null has a closed form for the fixed-margin case.
# Compute it. Do not assume it is zero.
The rule
If you report a clustering score without subtracting its chance level, the number is a function of your k as much as your algorithm — and comparisons across different k are meaningless. Report the adjusted variant, or report k alongside and accept that the comparison is not one.
566 verifier asserts, 33 in-page checks, 0 failures.
