Rand Index

Hook problem: Purity missed a split

The fixture has high Purity: 7/8 = 0.875. But the true graph cards are split across clusters A and B, and the true tree cards are split across clusters B and C.

Rand Index changes the question from “what is each cluster’s majority label?” to “what happened to every pair of items?”

First naive idea: keep the cluster-majority score

Purity gives cluster B one point because it contains one graph card and one tree card, so either label is a majority tie.

That hides the pair mistake: Cy and Di were placed together even though their reference labels differ.

Core invention: score pair agreement

For each unordered pair, ask:

• Are the two items in the same reference class?
• Are the two items in the same predicted cluster?

This creates pair counts:

• TP: same label and same cluster.
• FP: different labels but same cluster.
• FN: same label but different clusters.
• TN: different labels and different clusters.

Formal version

For n items, the number of unordered pairs is:

Rand Index is the fraction of pair decisions that agree:

For the fixture:

Interactive preset lab

Static no-JS fallback:

Correctness intuition

Each pair has exactly one status: TP, FP, FN, or TN. The numerator TP + TN counts exactly the pairs where both partitions make the same together/apart decision.

Limitation: true negatives can dominate

When many classes exist, most pairs may be different-label pairs. A clustering can get many TN agreements without doing a good job recovering the same-label groups.

That is why the next node adjusts for chance agreement.

Implementation sketch

function randIndex(items: { label: string; cluster: string }[]) {
  let tp = 0, fp = 0, fn = 0, tn = 0;

  for (let i = 0; i < items.length; i += 1) {
    for (let j = i + 1; j < items.length; j += 1) {
      const sameLabel = items[i].label === items[j].label;
      const sameCluster = items[i].cluster === items[j].cluster;
      if (sameLabel && sameCluster) tp += 1;
      else if (!sameLabel && sameCluster) fp += 1;
      else if (sameLabel && !sameCluster) fn += 1;
      else tn += 1;
    }
  }

  const total = tp + fp + fn + tn;
  return total === 0 ? null : (tp + tn) / total;
}

Complexity

Direct pair enumeration is O(n^2) time and O(1) extra counting space. If you already have a contingency table, the same counts can be computed from cell combinations without listing every pair.

Common confusions

• Rand Index uses pair TP/FP/FN/TN; these are not individual classifier examples.
• TN means “apart in both partitions,” not “the item is negative.”
• A high RI may still need chance adjustment.

Exercises

1. Which pair is the fixture’s only FP?
2. Why are there four FN pairs?
3. Why does RI include TN while FMI does not?

Graph connections : Rand Index