Clustering evaluation

Overview

When reference labels exist, a clustering can be scored by how well it agrees with them. The external indices on this page take the reference partition U and the found partition V and compare them. They do not need the cluster IDs to match, only which objects end up together 1612.08388 §4.2.

The shared core of the pair-counting indices is three counts over all pairs of objects 1612.08388 eq. 1–3:

1. a: pairs together in both U and V 1612.08388 eq. 1.
2. b: pairs together in U but split in V 1612.08388 eq. 2.
3. c: pairs split in U but together in V 1612.08388 eq. 3.

Each pair-counting index is a function of a, b and c. The information-based indices instead compare the label distributions, and are not defined through these counts 1612.08388 eq. 7.

Variants

Pair-counting indices

Jaccard is J = a / (a + b + c) 1612.08388 eq. 4. The adjusted Rand index (ARI) is given in 1612.08388 eq. 5. The Fowlkes–Mallows index is FM = a / √((a+b)(a+c)) 1612.08388 eq. 6. Card: Clustering Algorithms: A Comparative Approach.

The same ranking of methods can look different across these indices. On synthetic benchmarks with default settings, the margin of the best method over the next one is 7.22, 3.45 and 3.56 points for ARI, Jaccard and FM, and at least 12.49 points for NMI 1612.08388 tab. 2. The paper does not say whether these margins are percentage points or relative gains.

Information-based indices

Normalised mutual information is NMI = I(C,T) / √[H(C), H(T)] 1612.08388 eq. 7. The bracket in that formula is ambiguous, and the paper does not say which normalisation it means, so check the reference the paper cites before implementing it 1612.08388 §4.2.

Adjusted mutual information (AMI) is the metric of the object-grouping work 1708.03498 §4. That paper computes AMI while ignoring background and overlap regions of the images, so its numbers depend on that masking rule 1708.03498 §4. Card: Neural Expectation Maximization.

• Author-reported results (AMI). On static shapes, RNN-EM scores 0.826 ± 0.005 and N-EM 0.475 ± 0.043 1708.03498 §4.1. On flying shapes with three objects, the AMI is 0.970 ± 0.005 1708.03498 tab. 1. These are the authors' numbers, averaged over five runs, and are not reproduced here.

When to use which

Tuning results need care. The benchmark's default runs set K to the true number of classes, which a practitioner would not know, so the default-setting scores do not show what a user who must choose K would get 1612.08388 §5.1 1612.08388 tab. 2. See hyperparameter optimization for the tuning side.

Implementation sketch

Pair counts and the pair-counting indices, following the definitions in the first paper. The loop is quadratic in the number of objects.

# Pair counts between reference U and found partition V  [arxiv:1612.08388 eq. 1–3]
# Input:  u, v  (one label per object, N objects)
# Output: a, b, c

def pair_counts(u, v):
    a = b = c = 0
    for i in range(N):
        for j in range(i + 1, N):
            same_u = u[i] == u[j]
            same_v = v[i] == v[j]
            # a: together in both  [arxiv:1612.08388 eq. 1]
            # b: together in U, split in V  [arxiv:1612.08388 eq. 2]
            # c: split in U, together in V  [arxiv:1612.08388 eq. 3]
            if same_u and same_v:
                a += 1
            elif same_u:
                b += 1
            elif same_v:
                c += 1
    return a, b, c

# Jaccard from the pair counts  [arxiv:1612.08388 eq. 4]
# Fowlkes–Mallows from the pair counts  [arxiv:1612.08388 eq. 6]
# ARI and NMI are not sketched here: ARI is given in [arxiv:1612.08388 eq. 5]
# and NMI needs the normalisation check in the Variants section.

def jaccard(a, b, c):
    return a / (a + b + c)

def fowlkes_mallows(a, b, c):
    return a / sqrt((a + b) * (a + c))

Contradictions

None known. The two papers do not measure the same thing: the first scores seven clustering methods on 270 synthetic datasets with four pair-based and information-based indices 1612.08388 §4.1, and the second scores object grouping on shape and digit sequences with AMI 1708.03498 §4. Their numbers are not directly comparable.

Papers

• Clustering Algorithms: A Comparative Approach: defines the pair-counting and NMI indices and benchmarks seven clustering methods with default and tuned settings.
• Neural Expectation Maximization: reports AMI, ignoring background and overlap regions, for object grouping on synthetic shapes and digits.