🤖 AI

How to evaluate clustering with ground truth?

This paper reviews common external validity indexes for evaluating clustering with ground truth, recommending the centroid index (CI) for its intuitive, explainable cluster-level results while also highlighting pair-set index (PSI) and clustering accuracy (ACC) as suitable alternatives for point-level or size-unbiased assessments.

Original authors: Pasi Fränti

Published 2026-06-26

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Pasi Fränti

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a teacher trying to grade a class of students who have been asked to sort a pile of mixed-up colored blocks into separate boxes.

In a standard test (classification), the teacher has an answer key. They just check: "Is this red block in the red box? Yes? Good. No? Bad." It's a simple pass/fail.

But in clustering, the teacher didn't give the students an answer key. The students just decided, "Let's put all the big blocks in one box and small ones in another," or "Let's group by texture." The teacher doesn't know which grouping is the "right" one because the students invented the groups themselves.

This paper, written by Pasi Fränti, is about how a teacher can grade these students when they do have a secret "Ground Truth" (the perfect, ideal way the blocks should have been sorted). The paper reviews different ways to calculate a score to see how well the students did.

Here is the breakdown of the paper's main ideas using simple analogies:

1. The Three Ways to Grade

The author says there are three ways to judge a clustering algorithm:

The "Big Picture" Test: Does this sorting help the final product work better? (e.g., Does sorting voice recordings help identify speakers?) The author says this is often too vague. Sometimes, almost any sorting method works "okay," so it doesn't tell you which algorithm is truly the best.
The "Internal" Test: This is like asking the students, "How tidy are your boxes?" without looking at the answer key. You just check if the blocks inside a box look similar to each other. This is easy to do, but it doesn't tell you if the students actually sorted them correctly according to the real world.
The "External" Test (The Focus of the Paper): This is comparing the students' boxes against the Ground Truth (the perfect answer key). This is what the paper is all about.

2. The Problem with "Pairwise" Graders

The first type of external grader looks at every possible pair of blocks.

The Logic: "If Block A and Block B are in the same box in the answer key, they should be in the same box in the student's result."
The Flaw: There are millions of pairs of blocks. Most pairs are different colors anyway. So, if a student just puts everything in one giant box, they get a high score because they correctly identified that most pairs are different.
The Fix: The paper mentions ARI (Adjusted Rand Index) and NMI (Normalized Mutual Information). These try to fix the math so they don't get tricked by the sheer number of pairs. However, the author warns that these scores can still be misleading. A score of 0.95 might look great, but it doesn't tell you why it's great or how many mistakes were actually made. It's like getting a "95%" on a test without seeing which questions you got wrong.

3. The "Set-Matching" Graders (The New Approach)

Instead of looking at pairs, these graders look at the groups (clusters) as whole units. They try to match the student's "Red Box" to the teacher's "Red Box," the "Blue Box" to the "Blue Box," and so on.

The paper discusses several ways to do this matching:

Mapping: "Find the best match for every student box." (One-way street).
Pairing: "Match the boxes up so no two student boxes claim the same teacher box." (Two-way street).

The most popular method here is Clustering Accuracy (ACC). It's like saying, "We matched the boxes perfectly. Now, how many blocks are in the right box?"

Pros: It's very precise.
Cons: It can be biased. If one box has 1,000 blocks and another has 1, the big box dominates the score. If the student messes up the small box but gets the big one right, the score still looks great.

4. The Author's Favorite: The Centroid Index (CI)

The author strongly recommends a specific measure called the Centroid Index (CI).

The Analogy:
Imagine the "Center of Gravity" (centroid) of each box.

If the teacher's "Red Box" is centered at the kitchen table, and the student's "Red Box" is centered at the kitchen table, that's a perfect match.
If the student's "Red Box" is centered in the backyard, that's a mismatch.

Why the author loves CI:

It's Explainable: If the score is 0, it means every single box center is in the right place. If the score is 7, it means 7 boxes are in the wrong place.
No Mystery Numbers: Unlike the other scores where you wonder, "Is 0.85 good? Is 0.90 good?", CI gives you a clear count of errors. "You missed 7 clusters." That's it.
The Catch: It only counts how many boxes are misplaced. It doesn't care if a few blocks inside the box are slightly out of place. It's a "macro" view, not a "micro" view.

5. The Final Verdict (Recommendations)

The paper concludes with a simple guide for anyone trying to evaluate clustering:

If you want to know "How many groups did I get wrong?": Use the Centroid Index (CI). It's the most honest and easy-to-understand score. It tells you exactly how many clusters are in the wrong spot.
If you need to know "How many individual items are in the wrong spot?": Use Clustering Accuracy (ACC). It's a bit more complex but gives a fine-tuned, point-by-point score.
If you want a score that treats every group equally (big or small): Use PSI (Pair-set Index).
Avoid: The old-school Rand Index. The author says it's biased and gives high scores even when the clustering is terrible.

In Summary:
The paper argues that we should stop using confusing math scores that look good but mean little. Instead, we should use Centroid Index to count how many groups are misplaced (like counting how many boxes are in the wrong room) because it gives a clear, human-readable answer: "You got 7 groups wrong." If you need more detail, use Clustering Accuracy, but stick to the basics for a clear explanation.

Technical Summary: Evaluating Clustering with Ground Truth

Problem Statement

Evaluating clustering algorithms presents a fundamental challenge distinct from classification. In classification, predicted labels can be directly compared to ground truth labels. In clustering, however, cluster indices are arbitrary numbers with no inherent correspondence to ground truth labels, and the number of clusters in the solution may differ from the ground truth. Consequently, standard classification accuracy metrics are inapplicable.

While internal validation (optimizing cost functions like Sum-of-Squared Errors) and application-level performance exist, they often lack clear interpretability or fail to provide deep insights into the algorithm's specific clustering behavior. When ground truth is available, external validity indexes are required. However, existing measures vary significantly in their bias, interpretability, and suitability for different clustering scenarios (e.g., balanced vs. unbalanced cluster sizes).

Methodology

The paper reviews and categorizes external validity indexes into two primary classes: Pairwise Measures and Set-Matching-based Measures.

1. Pairwise Measures

These measures evaluate the consistency of point pairs across two clusterings.

Rand Index (RI): Counts the percentage of consistent pairs (same cluster or different cluster in both solutions). It is criticized for being overwhelmed by agreements on pairs in different clusters, yielding high values for almost any reasonable clustering.
Adjusted Rand Index (ARI): Normalizes RI against random clustering expectations. While more useful, it remains biased toward the largest clusters when sizes are unbalanced.
Normalized Mutual Information (NMI): An information-theoretic measure quantifying shared information between cluster pairs. It is equivalent to several other indices (AVIS, NVIS, AMI) but is noted to be biased when the number of clusters is large.

2. Set-Matching-based Measures

These measures find the best-matching cluster in the ground truth for each cluster in the solution and calculate similarity. The methodology involves three design components:

Matching Strategy:
- Mapping: One-directional (e.g., Purity, F-Measure) or bidirectional (e.g., NVD, CI).
- Pairing: Prevents multiple clusters from mapping to the same target. This can be solved via Greedy Pairing (CH, CR) or Optimal Pairing using the Hungarian algorithm (ACC, PSI).
Similarity Metric:
- Raw Intersection: Counting shared points $|A \cap G|$ (ACC, NVD, CH). This favors larger clusters.
- Set Similarity: Using Jaccard (CSI), Braun-Banquet (PSI), or Sorensen-Dice (FM) to normalize for cluster size.
- Centroid Matching: Matching centroids directly (CI, CR, GCI).
Normalization:
- Most normalize by the total number of points ( $N$ ), ensuring all points contribute equally.
- Some (like CI) calculate scores at the cluster level (0 or 1 per cluster), allowing for an integer-based error count.

3. The Centroid Index (CI)

The paper places special emphasis on the Centroid Index (CI). Unlike point-level measures, CI is a cluster-level measure. It determines the number of ground truth centroids that do not have a corresponding centroid in the clustering result (orphan centroids).

Mechanism: It matches clusters based on nearest centroids (or maximum overlap in generalized versions) and counts mismatches.
Output: An integer value in the range $[0, k]$ , where $k$ is the number of clusters. A value of 0 indicates all clusters are correctly located.

Key Contributions and Results

The paper provides a comprehensive review of external indexes, highlighting specific strengths and weaknesses:

Interpretability: The authors argue that standard metrics like NMI and ARI produce values in $[0, 1]$ that are difficult to interpret intuitively (e.g., does 0.90 imply a "good" clustering?). In contrast, CI provides an explainable result: the exact number of incorrectly solved clusters.
Bias Analysis:
- NMI is shown to yield deceptively high scores for incorrect clusterings when the number of clusters is large (e.g., $k=100$ ), as demonstrated on the Birch2 dataset where an incorrect result received an NMI of 0.96.
- ARI is biased toward the agreement of the largest clusters in unbalanced scenarios.
- Rand Index is deemed unsuitable due to inherent bias regardless of cluster size or count.
Point-Level vs. Cluster-Level: The paper distinguishes between measures that capture point-level deviations (ACC, PSI) and those capturing cluster-level structural errors (CI). CI may miss fine-grained point-level deviations (e.g., slight centroid shifts) but excels at identifying gross structural failures (e.g., missing or merged clusters).
Implementation: The paper references available software implementations, including CBEVI for C and a Python library for ACC (supporting both pairing and matching variants).

Significance and Recommendations

The paper concludes with specific recommendations for practitioners evaluating clustering with ground truth:

Primary Recommendation (Cluster-Level): Use the Centroid Index (CI). It is recommended for its intuitive nature and explainable output (the count of errors). It is particularly effective for identifying whether the correct clustering structure was found.
Secondary Recommendation (Point-Level): If fine-tuned, point-level differences are required, Clustering Accuracy (ACC) is recommended. It is well-documented, behaviorally analyzed, and supported by accessible software.
Alternative for Normalization: If a normalized score is required that does not favor larger clusters, Pair-set Index (PSI) is suggested.
Cautions:
- NMI and ARI can be used but require awareness of their specific biases (NMI with many clusters, ARI with unbalanced sizes).
- Rand Index is explicitly not recommended.

The significance of this work lies in shifting the focus from abstract, hard-to-interpret scores to metrics that offer clear, actionable insights into clustering performance, specifically advocating for the Centroid Index as a robust, explainable standard for cluster-level evaluation.