Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Clustering Validation

Mahmood Amintoosi, Fall 2026

Computer Science Dept, Ferdowsi University of Mashhad

This page follows chapter 17 of Zaki & Meira (2020), Clustering Validation.

Source

Introduction to Clustering Validation

Clustering validation assesses the quality of a clustering. Every algorithm returns some partition of the data; the question is whether that partition is any good, and how two candidate partitions can be compared. The measures fall into three families:

  1. External measures: use external information, the ground-truth labels.

  2. Internal measures: use only the data and the clustering result.

  3. Relative measures: compare two clusterings of the same data with each other, without any ground truth.

Learning objectives. By the end you should be able to

  1. build the contingency table of a clustering against the ground truth, and read it;

  2. compute and interpret purity, precision/recall/F, maximum matching, Jaccard, Rand and ARI, and say what each one ignores;

  3. explain why accuracy cannot be used on cluster labels;

  4. use internal measures (silhouette, SSE) and say why none of them identifies the “true” number of clusters;

  5. choose kk on the SSE curve with the elbow rule, and read the maximum-matching score as an assignment problem;

  6. find the measures that did not fit on this page — NMI, the gap statistic and the assignment problem in full — in the appendix.

Notation

Zaki writes rr for the number of clusters and kk for the number of ground-truth classes. This page keeps those letters, so that the formulas match the book; note that the k-means pages of this course use kk for the number of clusters. In every formula below nijn_{ij} counts the points of cluster CiC_i that belong to class TjT_j, and nn is the number of points.

External Measures

External measures assume that the correct or ground-truth clustering is known a priori, which is used to evaluate a given clustering.

Let D={xi}i=1n\mathbf{D} = \{\mathbf{x}_i\}_{i=1}^n be a dataset consisting of nn points in a dd-dimensional space, partitioned into kk clusters. Let yi∈{1,2,…,k}y_i \in \left\{ 1, 2,\ldots , k \right\} denote the ground-truth cluster membership or label information for each point.

The ground-truth clustering is given as:

T={T1,T2,…,Tk}\mathbf{T} = \left\{ T_1, T_2, \ldots, T_k \right\}

where the cluster TjT_{j} consists of all the points with label jj, i.e.,

Tj={xi∈D∣yi=j}T_{j} = \left\{ \mathbf{x}_i \in \mathbf{D} \mid y_i = j \right\}

We refer to T\mathbf{T} as the ground-truth partitioning, and to each TiT_i as a partition (class).

Let C={C1,…,Cr}\mathbf{C} = \{C_1, \ldots, C_r\} denote a clustering of the same dataset into rr clusters, obtained via some clustering algorithm, and let y^i∈{1,2,…,r}\hat{y}_i \in \left\{ 1, 2, \ldots, r \right\} denote the cluster label for xi\mathbf{x}_i.

External evaluation measures try to capture the extent to which points from the same partition appear in the same cluster, and the extent to which points from different partitions are grouped in different clusters.

All of the external measures rely on the r×kr \times k contingency table N\mathbf{N} that is induced by a clustering C\mathbf{C} and the ground-truth partitioning T\mathbf{T}, defined as follows:

N(i,j)=nij=∣Ci∩Tj∣\mathbf{N}(i,j) = n_{ij} = \left| C_i \cap T_{j} \right|

The count nijn_{ij} denotes the number of points that are common to cluster CiC_i and ground-truth partition TjT_{j}.

Let ni=∣Ci∣n_{i} = |C_i| denote the number of points in cluster CiC_i, and let mj=∣Tj∣m_{j} = |T_{j}| denote the number of points in partition TjT_{j}. The contingency table can be computed from T\mathbf{T} and C\mathbf{C} in O(n)O(n) time by examining the partition and cluster labels, yiy_i and y^i\hat{y}_i, for each point xi∈D\mathbf{x}_i \in \mathbf{D} and incrementing the corresponding count ny^i, yin_{\hat{y}_i,\,y_i} — the first index is the cluster label, the second the class label, so that rows of N\mathbf{N} are clusters and columns are classes.

Source

A first reference point: a perfect clustering

Before looking at anything that goes wrong, we need a baseline. The table below is obtained when every cluster matches exactly one ground-truth class. The contingency matrix is diagonal: every off-diagonal entry is zero.

This is the only case in which the “ideal” value of any reasonable external measure is reached (1 for purity and ARI). Every other example on this page should be compared against this baseline.

Loading...

A good clustering with a small, symmetric mistake

Most realistic clusterings are almost right. Here, C₀ is still perfectly pure, but C₁ and C₂ have swapped one point each: one point from class T₁ landed in C₂ and one from T₂ landed in C₁.

The table is almost diagonal, so purity and ARI will both be close to but slightly below 1. This is the typical “slightly imperfect” case that most practical algorithms produce.

Loading...

Cluster ids are arbitrary labels, not orderings

The partition below is exactly the same as the one in Example B; only the ids of the clusters have been permuted. C₁ in this example is what C₂ was before, and vice versa.

The table is the same as B with its rows rearranged — and every external measure gives the same numerical value. This is the reason all external measures must be invariant to permutations of the cluster ids: the numbers 0, 1, 2 returned by KMeans.labels_ are just names, not a ranking.

Loading...

A weak clustering with symmetric spread

Now the clustering is not close to the ground truth at all. Every cluster contains points from two different classes, and every class is split across two clusters. The table has several non-zero entries per row and per column, but no row or column is “pure”.

Purity will be around 0.5, ARI will be clearly below 1. Notice that there is still some signal: the diagonal entries are not zero, so the clustering is not random — it is simply weak.

Loading...

A deceptive case: a perfectly uniform table

This example has a contingency table in which every entry is exactly equal. Every cluster contains one point from each class, and every class is spread evenly across all clusters.

This is the most instructive case on the page. The table looks neat and regular, yet it carries no information: knowing which cluster a point was assigned to tells us nothing about its true class.

Purity is exactly 1/3, and ARI is exactly 0 — the same values a completely random assignment would produce. Regularity of the table is not the same thing as usefulness of the clustering.

Loading...

When the number of clusters differs from the number of classes

All examples so far had k=rk = r: as many clusters as ground-truth classes. But K-means is run with a fixed K that the user chooses, and there is no guarantee that K matches the number of true classes.

In the example below, the ground truth has three classes but the algorithm produced four clusters — it has over-segmented one of the classes into two pieces. The contingency table is therefore not square, and no simple “accuracy” can be computed: there is no one-to-one correspondence between cluster ids and class ids.

Purity is still computable and still meaningful: it asks, for each cluster, how pure it is, and then averages. But an over-segmented clustering gets a suspiciously high purity, because small pure clusters are easy to form. ARI penalises this properly, which is exactly why it is preferred in practice when K is not known in advance.

Loading...

The opposite case: too few clusters

Here the situation is reversed: the algorithm was run with K=2K = 2, but there are three true classes. Two of them have been merged into a single cluster.

The contingency table is now a 2×32 \times 3 matrix, with one row containing points from two different classes. Purity drops immediately, because that row has two non-zero entries of comparable size. Under-segmentation is much harder to hide than over-segmentation.

Loading...

Efficient Contingency Table Computation with np.add.at

When implementing clustering validation metrics, constructing a contingency table is a key step. One efficient way to do this in NumPy is using np.add.at. This method ensures correct accumulation of counts when duplicate indices are present.

Why np.add.at?

Unlike simple indexed incrementation, such as:

contingency_table[cluster_map, class_map] += 1

NumPy’s fancy indexing creates a temporary copy, meaning updates to repeated indices may not accumulate correctly. Instead, np.add.at ensures in-place modifications:

np.add.at(contingency_table, (cluster_map, class_map), 1)

Example: Difference Between Direct Indexing and np.add.at

Here’s an example illustrating how np.add.at correctly handles duplicate indices while direct indexing may fail:

Using direct indexing:
Loading...

Using np.add.at:
Loading...

1. Purity

Purity measures how “pure” each cluster is by the fraction of points from the majority class:

purity=1n∑i=1rmax⁡j=1k{nij}\text{purity} = \frac{1}{n}\sum_{i=1}^r \max_{j=1}^k \{n_{ij}\}

Where:

  • n n = total number of points

  • r r = number of clusters

  • k k = number of true classes

  • nij n_{ij} = number of points in cluster i i from class j j

Let’s consider an example where we achieve high purity, ensuring our clustering is well-aligned with the ground-truth partitioning.

Example Data

Suppose we have the following clustering and ground-truth labels:

true_labels    = np.array([0, 0, 1, 1, 1, 2])
cluster_labels = np.array([0, 0, 1, 1, 2, 2])

Here, each cluster aligns better with a single true class.

Compute Contingency Table

Using the compute_contingency_table function, we obtain:

Class 0Class 1Class 2
C₀200
C₁020
C₂011

Middle Computations

Step 1: Find the max of each row:

  • max(C₀) = 2

  • max(C₁) = 2

  • max(C₂) = 1

Step 2: Sum the max values: ∑max⁡(nij)=2+2+1=5 \sum \max(n_{ij}) = 2 + 2 + 1 = 5

Step 3: Compute purity: Purity=∑max⁡(nij)∑nij=56≈0.833 \text{Purity} = \frac{\sum \max(n_{ij})}{\sum n_{ij}} = \frac{5}{6} \approx 0.833

Purity Score: 0.833

purity is invariant to cluster labels, meaning that relabeling clusters doesn’t change the score as long as the assignment itself remains consistent.

Let’s take the previous clustering but shift the cluster labels (e.g., renaming clusters C₀ →\rightarrow C₂, C₁ →\rightarrow C₀, C₂ →\rightarrow C₁):

Original Purity: 0.833
Shifted Labels Purity: 0.833

Why Does Purity Stay the Same?

  • The mapping between clusters and ground-truth partitions hasn’t changed, only their labels.

  • Since purity only depends on how well clusters match ground-truth partitions, renaming clusters doesn’t affect purity calculations.

2. Precision, Recall and F-measure

For each cluster Ci C_i :

  • Precision: Fraction of points in cluster from majority class

  • Recall: Fraction of points from class found in cluster

Precision

Given cluster CiC_i, let jij_i denote the partition that contains the maximum number of points from CiC_i,

ji=arg⁡max⁡j=1k{nij}j_i = \arg\max_{j=1}^{k} \left\{ n_{ij} \right\}

that is, the index of the largest entry in row ii of the contingency table. The precision of a cluster CiC_i is the same as its purity:

preci=1nimax⁡j=1k{nij}=nijini\mathit{prec}_i = \frac{1}{n_{i}}\max_{j=1}^k \left\{ n_{ij} \right\} = \frac{n_{ij_i}}{n_i}

Recall

The recall of cluster CiC_i is defined as:

recalli=niji∣Tji∣=nijimji\mathit{recall}_i = \frac{n_{ij_i}}{|\mathbf{T}_{j_i}|} =\frac{n_{ij_i}}{m_{j_i}}

where mji=∣Tji∣m_{j_i} = |\mathbf{T}_{j_i}|.

F-Measure

The F-measure is the harmonic mean of the precision and recall values for each CiC_i:

Fi=21preci+1recalli=2⋅preci⋅recallipreci+recalli=2  nijini+mjiF_i = \frac{2}{\frac{1}{\mathit{prec}_i} + \frac{1}{\mathit{recall}_i}} = \frac{2 \cdot \mathit{prec}_i \cdot \mathit{recall}_i}{\mathit{prec}_i + \mathit{recall}_i} = \frac{2 \; n_{ij_i}}{n_{i} + m_{j_i}}

The F-measure for the clustering C\mathbf{C} is the mean of clusterwise F-measure values:

F=1r∑i=1rFiF = \frac{1}{r} \sum_{i=1}^r F_i

3. Maximum Matching

Finds the best matching between clusters and true classes to maximize overlap:

match=1nmax⁡M∑(i,j)∈Mnij\text{match} = \frac{1}{n}\max_M \sum_{(i,j)\in M} n_{ij}

Where M M is a matching between clusters and classes.

Maximum weight matching (following Zaki & Meira (2020))

Let GG be a bipartite graph over the vertex set V=C∪TV = \mathbf{C} \cup \mathbf{T}, and let the edge set be E={(Ci,Tj)}E = \{ (C_i, T_{j}) \} with edge weights w(Ci,Tj)=nijw(C_i,T_{j}) = n_{ij}. A matching MM in GG is a subset of EE, such that the edges in MM are pairwise nonadjacent, meaning they do not have a common vertex.

The maximum weight matching in GG is given as:

match=max⁡M{w(M)n}\mathit{match} = \max_{M} \left\{ \frac{w(M)}{n} \right\}

where w(M)w(M) is the sum of all edge weights in matching MM, given as w(M)=∑e∈Mw(e)w(M) = \sum_{e \in M} w(e).

Maximum Matching Examples (Bipartite Graph Interpretation)

Example 1 — Over-segmentation: one cluster is left unmatched

Scenario. Ten fruits with three true classes. The algorithm has split the apples into two clusters (C1,C2C_1, C_2) and merged oranges and bananas into a single cluster (C3C_3).

True Categories (T₁ = apples, T₂ = oranges, T₃ = bananas):
T₁: apple1, apple2, apple3, apple4, apple5      (5 apples)
T₂: orange1, orange2, orange3                    (3 oranges)
T₃: banana1, banana2                             (2 bananas)

Cluster Assignments (C₁, C₂, C₃):
C₁: [apple1, apple2, apple3]                     → 3 apples
C₂: [apple4, apple5]                             → 2 apples       ← over-segmentation
C₃: [orange1, orange2, orange3, banana1, banana2] → 3 oranges, 2 bananas

Contingency table

Apples (T1T_1)Oranges (T2T_2)Bananas (T3T_3)nin_i
C1C_13003
C2C_22002
C3C_30325
mjm_j53210

Purity is optimistic

max⁡(C1)=3,max⁡(C2)=2,max⁡(C3)=3\max(C_1)=3,\qquad \max(C_2)=2,\qquad \max(C_3)=3
Purity=3+2+310=0.80\text{Purity} = \frac{3 + 2 + 3}{10} = \mathbf{0.80}

Purity sees three “pure” clusters and reports a high value, even though both C1C_1 and C2C_2 claim the apple class at the same time. The one-to-one constraint that a classifier would impose is invisible to Purity.

Maximum Matching sees the conflict

Clusters          Categories
   C₁ ──(3)────── T₁ (apples)   ← both compete for T₁
   C₂ ──(2)────── T₁ (apples)
   C₃ ──(3)────── T₂ (oranges)
      └──(2)────── T₃ (bananas)
Candidate matchingPairsTotal weight
AC1C_1–T1T_1 (3), C3C_3–T2T_2 (3)6 ✓
BC2C_2–T1T_1 (2), C3C_3–T2T_2 (3)5
CC1C_1–T1T_1 (3), C3C_3–T3T_3 (2)5
DC2C_2–T1T_1 (2), C3C_3–T3T_3 (2)4
Match=3+310=0.60\text{Match} = \frac{3 + 3}{10} = \mathbf{0.60}

C2C_2 is left unmatched (weight 0). It receives no label at all, because C1C_1 has the stronger claim on the apple class and C2C_2 has no other candidate.

Comparison

Purity=0.80vsMatch=0.60\boxed{\text{Purity} = 0.80 \quad\text{vs}\quad \text{Match} = 0.60}

The difference 0.20 is exactly the over-segmentation that Purity fails to penalise.


Example 2 — Conflict without any unmatched cluster

This example shows the subtler case: every cluster still receives a label, yet Purity is still optimistic because a cluster is pushed onto a class that is not its majority.

Scenario. Ten fruits with three true classes, three clusters, and two clusters both lean towards apples, but the “loser” of the conflict still has a non-zero overlap with bananas — so the Hungarian algorithm can assign every cluster to a distinct class.

True Categories:
T₁: apples   (total 5)
T₂: oranges  (total 3)
T₃: bananas  (total 2)

Cluster Assignments:
C₁: 3 apples, 1 orange                             → clearly apple-dominant
C₂: 2 apples, 1 banana                             → prefers apples, but has a banana tail
C₃: 2 oranges, 1 banana                            → clearly orange-dominant

Contingency table

Apples (T1T_1)Oranges (T2T_2)Bananas (T3T_3)nin_i
C1C_13104
C2C_22013
C3C_30213
mjm_j53210

Purity is again optimistic

max⁡(C1)=3,max⁡(C2)=2,max⁡(C3)=2\max(C_1) = 3,\qquad \max(C_2) = 2,\qquad \max(C_3) = 2
Purity=3+2+210=0.70\text{Purity} = \frac{3 + 2 + 2}{10} = \mathbf{0.70}

Purity again pretends that both C1C_1 and C2C_2 are “apple clusters”, because both of their row maxima sit in the apple column.

Maximum Matching forces a one-to-one label

Clusters          Categories
   C₁ ──(3)────── T₁ (apples)       ← conflict
   C₁ ──(1)────── T₂ (oranges)
   C₂ ──(2)────── T₁ (apples)       ← conflict
   C₂ ──(1)────── T₃ (bananas)
   C₃ ──(2)────── T₂ (oranges)
   C₃ ──(1)────── T₃ (bananas)

Three pairs have no edge at all (weight 0): C1C_1–T3T_3, C2C_2–T2T_2, and C3C_3–T1T_1. A matching may only use existing edges, so any pairing that includes one of these is not a valid matching.

A matching does not have to cover every cluster. Since all edge weights are non-negative, adding another allowed edge can only increase the total — so if a perfect matching exists, it is necessarily optimal. Here it does exist, and the relevant candidates are:

Perfect matchings (three edges):

MatchingPairsWeightsTotal
AC1 ⁣→ ⁣T1,  C2 ⁣→ ⁣T3,  C3 ⁣→ ⁣T2C_1\!\to\!T_1,\;C_2\!\to\!T_3,\;C_3\!\to\!T_23, 1, 26 ✓
BC1 ⁣→ ⁣T2,  C2 ⁣→ ⁣T1,  C3 ⁣→ ⁣T3C_1\!\to\!T_2,\;C_2\!\to\!T_1,\;C_3\!\to\!T_31, 2, 14

Partial matchings (two edges) — shown for completeness:

MatchingPairsWeightsTotal
DC1 ⁣→ ⁣T1,  C3 ⁣→ ⁣T2C_1\!\to\!T_1,\;C_3\!\to\!T_23, 25
IC2 ⁣→ ⁣T1,  C3 ⁣→ ⁣T2C_2\!\to\!T_1,\;C_3\!\to\!T_22, 24
CC1 ⁣→ ⁣T1,  C2 ⁣→ ⁣T3C_1\!\to\!T_1,\;C_2\!\to\!T_33, 14
EC1 ⁣→ ⁣T1,  C3 ⁣→ ⁣T3C_1\!\to\!T_1,\;C_3\!\to\!T_33, 14
FC1 ⁣→ ⁣T2,  C2 ⁣→ ⁣T1C_1\!\to\!T_2,\;C_2\!\to\!T_11, 23
JC2 ⁣→ ⁣T1,  C3 ⁣→ ⁣T3C_2\!\to\!T_1,\;C_3\!\to\!T_32, 13
KC2 ⁣→ ⁣T3,  C3 ⁣→ ⁣T2C_2\!\to\!T_3,\;C_3\!\to\!T_21, 23
G, H(remaining two-edge matchings)—2

The best partial matching is D with weight 5, but the perfect matching A reaches 6 and therefore wins. In general, when a perfect matching exists, it is optimal — but when it does not (as in Example 1), the optimum is a partial matching, and the comparison with partial matchings is essential.

The optimum A assigns C1 ⁣→ ⁣applesC_1\!\to\!\text{apples} (3), C3 ⁣→ ⁣orangesC_3\!\to\!\text{oranges} (2) and C2 ⁣→ ⁣bananasC_2\!\to\!\text{bananas} (1). Every cluster is labelled, but C2C_2 is pushed onto its minority class (bananas), because its majority class (apples) has already been claimed by the stronger C1C_1.

Match=3+1+210=0.60\text{Match} = \frac{3 + 1 + 2}{10} = \mathbf{0.60}

Comparison

Purity=0.70vsMatch=0.60\boxed{\text{Purity} = 0.70 \quad\text{vs}\quad \text{Match} = 0.60}

All three clusters still get labelled — the Hungarian algorithm returns three non-zero pairings — but one of the labels is a minority label, and Match captures this while Purity does not. This is the key pedagogical difference from Example 1:

  • Example 1: the conflict leaves a cluster unlabelled (weight 0).

  • Example 2: the conflict leaves a cluster mis-labelled (non-zero weight, but not the majority).

In both cases Purity > Match, and the gap is exactly the quantity of cluster–class overlap that cannot be reconciled with a one-to-one assignment.

Source
--- Example 1 — over-segmentation, one cluster unmatched ---
Contingency table:
[[3 0 0]
 [2 0 0]
 [0 3 2]]
Row maxima:                [3, 2, 3]  →  sum = 8
Purity:                    0.800
Optimal matching (row → col, weight): [(0, 0, 3), (1, 2, 0), (2, 1, 3)]
Match:                     0.600
Unmatched clusters (w=0):  [1]

--- Example 2 — conflict, every cluster gets a label ---
Contingency table:
[[3 1 0]
 [2 0 1]
 [0 2 1]]
Row maxima:                [3, 2, 2]  →  sum = 7
Purity:                    0.700
Optimal matching (row → col, weight): [(0, 0, 3), (1, 2, 1), (2, 1, 2)]
Match:                     0.600
Unmatched clusters (w=0):  []

4. Pairwise Measures

First, let’s define some key quantities used in external measures:

  • TP (True Positives): Pairs in same cluster and same true partition

  • FP (False Positives): Pairs in same cluster but different partitions

  • TN (True Negatives): Pairs in different clusters and different partitions

  • FN (False Negatives): Pairs in different clusters but same partition

Given clustering C\mathbf{C} and ground-truth partitioning T\mathbf{T}, let xi,xj∈D\mathbf{x}_i, \mathbf{x}_{j} \in \mathbf{D} be any two points, with i≠ji \ne j. Let yiy_i denote the true partition label and let y^i\hat{y}_i denote the cluster label for point xi\mathbf{x}_i.

If both xi\mathbf{x}_i and xj\mathbf{x}_{j} belong to the same cluster, that is, y^i=y^j\hat{y}_i = \hat{y}_{j}, we call it a positive event, and if they do not belong to the same cluster, that is, y^i≠y^j\hat{y}_i \ne \hat{y}_{j}, we call that a negative event. Depending on whether there is agreement between the cluster labels and partition labels, there are four possibilities to consider:

True Positives (TP)
xi\mathbf{x}_i and xj\mathbf{x}_{j} belong to the same partition in T\mathbf{T}, and they are also in the same cluster in C\mathbf{C}. The number of true positive pairs is given as:

TP=∣{(xi,xj):  yi=yj and y^i=y^j}∣\mathit{TP} = \bigl|\{(\mathbf{x}_i, \mathbf{x}_{j}):\; y_i = y_{j} \text{ and } \hat{y}_i = \hat{y}_{j} \}\bigr|

False Negatives (FN)
xi\mathbf{x}_i and xj\mathbf{x}_{j} belong to the same partition in T\mathbf{T}, but they do not belong to the same cluster in C\mathbf{C}. The number of false negative pairs is given as:

FN=∣{(xi,xj):  yi=yj and y^i≠y^j}∣\mathit{FN} = \bigl|\{(\mathbf{x}_i, \mathbf{x}_{j}):\; y_i = y_{j} \text{ and } \hat{y}_i \ne \hat{y}_{j} \}\bigr|

False Positives (FP)
xi\mathbf{x}_i and xj\mathbf{x}_{j} do not belong to the same partition in T\mathbf{T}, but they do belong to the same cluster in C\mathbf{C}. The number of false positive pairs is given as:

FP=∣{(xi,xj):  yi≠yj and y^i=y^j}∣\mathit{FP} = \bigl|\{(\mathbf{x}_i, \mathbf{x}_{j}):\; y_i \ne y_{j} \text{ and } \hat{y}_i = \hat{y}_{j} \}\bigr|

True Negatives (TN)
xi\mathbf{x}_i and xj\mathbf{x}_{j} neither belong to the same partition in T\mathbf{T}, nor do they belong to the same cluster in C\mathbf{C}. The number of such true negative pairs is given as:

TN=∣{(xi,xj):  yi≠yj and y^i≠y^j}∣\mathit{TN} = \bigl|\{(\mathbf{x}_i, \mathbf{x}_{j}):\; y_i \ne y_{j} \text{ and } \hat{y}_i \ne \hat{y}_{j} \}\bigr|

A pairwise view of the external measures

Both Jaccard and Rand look at the clustering problem in a different way from the contingency table: instead of comparing cluster ids to class ids, they ask a question about every pair of points.

For a pair (i, j) we can ask two yes/no questions:

  • are i and j in the same ground-truth class?

  • are i and j in the same cluster?

Four cases are possible:

same clusterdifferent cluster
same classTP (True Positive)FN (False Negative)
different classFP (False Positive)TN (True Negative)
  • TP — a pair that is together in the ground truth and together in the clustering.

  • TN — a pair that is apart in the ground truth and apart in the clustering.

  • FP — a pair that is apart in the ground truth but merged by the clustering.

  • FN — a pair that is together in the ground truth but split by the clustering.

Everything that follows is a different way of combining these four counts.

Jaccard Coefficient
Jaccard=TPTP+FN+FP\text{Jaccard} = \frac{TP}{TP + FN + FP}
Rand Index
Rand=TP+TNTP+FN+FP+TN=TP+TN(n2)\text{Rand} = \frac{TP + TN}{TP + FN + FP + TN} = \frac{TP + TN}{\binom{n}{2}}
Worked example: six points, counted pair by pair

The formulas above are easier to trust on a dataset small enough to enumerate by hand, and six points are enough:

point123456
class yiy_i000111
cluster y^i\hat{y}_i001211

The ground truth has two classes of three points; the clustering cuts the same six points into three clusters, so r=2r = 2 and k=3k = 3. There are (62)=15\binom{6}{2} = 15 pairs, and every one of them falls into one of the four cells of the table above. The cell below lists the pairs that are together in at least one of the two partitions — the eight pairs Jaccard looks at — and counts all fifteen.

pairs together in at least one partition:
   TP  (1, 2)
   FN  (1, 3)
   FN  (2, 3)
   FP  (3, 5)
   FP  (3, 6)
   FN  (4, 5)
   FN  (4, 6)
   TP  (5, 6)

TP = 2   FP = 2   FN = 4   TN = 7   (total 15)
Jaccard = TP/(TP+FN+FP) = 2/(2+4+2) = 0.250
Rand    = (TP+TN)/total = (2+7)/15     = 0.600
What Jaccard actually measures

Jaccard only looks at the positive pairs — those that are together in at least one of the two partitions — and asks what fraction of them are together in both. The count TN is completely ignored.

Because TN grows very fast as the number of clusters increases, ignoring it is a deliberate choice: Jaccard stays meaningful even when the number of clusters is large or when the two partitions do not have the same number of groups. It is the most robust of the pairwise measures in that respect.

What Rand actually measures

Rand counts both kinds of agreement: pairs that are together in both partitions (TP), and pairs that are apart in both partitions (TN). The denominator is the total number of pairs, so Rand asks: in what fraction of all possible pairs do the two partitions agree?

Rand looks superficially similar to accuracy in classification, but the two measures are not the same thing. The next two subsections explain why.

Rand is not accuracy

At first glance, Rand looks like the clustering analogue of accuracy: both divide the number of “correct decisions” by the total number of decisions, both lie in [0, 1], and both are often described informally as “the percentage of agreement”. The similarity, however, is only superficial. Accuracy and Rand differ in three fundamental respects.

1. The unit being counted is different.

Accuracy asks a question about every sample: is the predicted label equal to the true label? Rand asks a question about every pair of points: are these two points on the same side of both partitions? A clustering of n points contains n(n-1)/2 pairs, so Rand makes a number of decisions that grows quadratically with the size of the dataset. These are not the same kind of decisions at all.

2. There is no one-to-one mapping between cluster ids and class ids.

In classification, each class has a meaningful, unique label. In clustering, the ids produced by KMeans.labels_ are arbitrary: cluster 0 in one run may be cluster 1 in the next. You cannot compute accuracy on cluster ids directly, because there is no ground-truth label to compare them against. Rand sidesteps the problem entirely: it never mentions ids, only the same/different relation between pairs, which is invariant to relabelling.

3. Rand is defined even when k ≠ r.

Accuracy presupposes a fixed number of classes. Rand does not: it works whether the algorithm produced more clusters than there are classes (over-segmentation) or fewer (under-segmentation). This is why Rand remains computable on the examples where accuracy simply has no meaning.

The one weakness they share. Accuracy is misleading on imbalanced data: predicting the majority class everywhere gives a high score while learning nothing. Rand has the analogous weakness for clusterings with many groups: as k grows, TN dominates the numerator and Rand approaches 1 even for a random labelling. The two measures fail in different ways, but neither is trustworthy on its own when the problem is unbalanced.

Adjusted Rand Index (ARI)

Because TN grows very fast as k increases, Rand is not corrected for chance: a completely random labelling of the same n points with the same k clusters already has a high expected Rand value. A useful measure should give 0 to such a random labelling and 1 only to a perfect one.

The Adjusted Rand Index does exactly that. It subtracts the value that Rand is expected to take under random labelling, and divides by the maximum possible correction:

ARI=Rand−E[Rand]max⁡(Rand)−E[Rand]\text{ARI} = \frac{\text{Rand} - \mathbb{E}[\text{Rand}]} {\max(\text{Rand}) - \mathbb{E}[\text{Rand}]}

The expected value is computed from the row and column sums of the contingency table (the sizes of the clusters and the sizes of the classes), so it does not assume anything about the data.

The interpretation of ARI is:

  • ARI = 1 — the two partitions are identical (up to relabelling).

  • ARI = 0 — the clustering is no better than a random labelling with the same cluster sizes.

  • ARI < 0 — the clustering is worse than random, which can genuinely happen when the algorithm systematically splits the same class in the same way across runs.

In practice ARI is the recommended default for comparing two partitions, because it is the only common external measure that is simultaneously:

  • invariant to relabelling of the clusters,

  • corrected for chance,

  • defined when k ≠ r,

  • bounded above by 1.

It is also the measure that scikit-learn reports by default when you call adjusted_rand_score(true_labels, cluster_labels).

Chance correction on the same six points

The data stay fixed; only the partition of those six points changes. Two of the four clusterings below are deliberately bad: one puts every point in a cluster of its own, the other scatters the points over clusters with no relation to their class.

Loading...

Four things in that table are worth pausing on:

  • Jaccard cannot be fooled by the degenerate clustering. It reads 0.000 for both one cluster per point and scattered, which is the honest answer: not a single pair that should be together is kept together. The price is that it also gives 0.000 to both, so it cannot rank them.

  • Rand does not fall when the clustering gets useless. Mixed and one cluster per point both score 0.600, although the second puts no two points together at all. Once the clusters are small, the great majority of pairs land in TN, and Rand stops measuring anything about the clustering.

  • ARI separates them. It reads 0.118 for mixed and 0.000 for the degenerate clustering, which is exactly the value a random labelling with the same cluster sizes is expected to reach. For the scattered clustering it even goes negative (-0.364): the labelling is worse than chance, which can happen when a partition systematically splits the same class the same way.

Summary: which measure to use
MeasureUnitCorrected for chanceWorks when k ≠ rRange
Accuracysample— (no chance correction)❌[0, 1]
Jaccardpair❌✅[0, 1]
Randpair❌✅[0, 1]
ARIpair✅✅[-1, 1]
  • Jaccard is the right choice when you care about the positive pairs (the “together” decisions) and want a measure that is not inflated by the large number of trivially-different pairs.

  • Rand is the historical baseline for pairwise comparison, useful for teaching, but it is not corrected for chance and inflates with k.

  • ARI is the recommended default: it is the closest analogue to accuracy that survives the two structural problems of clustering (arbitrary ids and unknown k).

The examples on this page are chosen to make these differences visible: the perfect clustering reaches Jaccard = Rand = ARI = 1, the weak clustering lowers all three, and the over-segmented case leaves Rand high while ARI drops, which is exactly the failure mode ARI was designed to fix.

Internal Measures

Internal measures use only the data D\mathbf{D} and the partition C\mathbf{C}: there are no ground-truth labels. They answer a different question from the external measures — not “is this the true grouping?” but “is this grouping internally coherent?” — and a high value never proves that the clusters mean something, only that they are compact and separated according to one particular definition.

Relative measures, the third family, compare two clusterings of the same data with each other, for example the same algorithm run with two parameter settings. They are not a separate formula: any internal or external measure can be used relatively, by evaluating it on both clusterings and comparing the numbers. The sweep over k=2,…,5k=2,\dots,5 at the end of this page is exactly that.

5. Silhouette Coefficient

The silhouette compares, for each point, its distance to its own cluster with its distance to the nearest other cluster. For a point xi\mathbf{x}_i in cluster CC let

  • aia_i be the mean distance from xi\mathbf{x}_i to the other points of CC (cohesion);

  • bib_i be the smallest mean distance from xi\mathbf{x}_i to the points of another cluster (separation).

Then

si=bi−aimax⁡(ai, bi)∈[−1,1],s=1n∑i=1nsis_i = \frac{b_i - a_i}{\max(a_i,\,b_i)} \in [-1, 1], \qquad s = \frac{1}{n}\sum_{i=1}^{n} s_i

A value near 1 means the point is much closer to its own cluster than to the next one, near 0 that the clusters touch, and negative that the point is probably in the wrong cluster. The score needs all pairwise distances, so it costs O(n2)O(n^2) — usable on Iris, expensive on a million points.

Wikipedia: silhouette

6. SSE (Inertia)

The objective of k-means is itself an internal measure:

SSE=∑i=1k∑x∈Ci∥x−μi∥2\mathrm{SSE} = \sum_{i=1}^{k}\sum_{\mathbf{x}\in C_i} \|\mathbf{x} - \mu_i\|^2

scikit-learn reports it as KMeans.inertia_. It is exactly the quantity of k-Means, so it is cheap: no pairwise distances, one pass over the data. The catch is that it cannot be used to choose kk: adding a centroid can never increase the SSE, so the minimum is always at k=nk = n, where the SSE is 0. The usual “elbow” rule — pick the kk after which the curve flattens — turns this into a decision, but the elbow is a visual judgement. The rule, its two quantitative versions and the Iris numbers are worked out in Choosing the Number of Clusters below.

Python Example on the Iris Dataset

Loading...
Purity:    0.887
Jaccard:   0.682
Rand:      0.874   (3,030 agreement pairs out of 11,175)
ARI:       0.716
SSE (inertia) of this k = 3 clustering : 78.9
silhouette coefficient (k = 3)         : 0.551

Interpretation of Results

  • Purity, Jaccard, Rand, ARI: higher is better, and 1 means the two partitions agree (up to relabelling). ARI can be compared between problems; purity and Rand cannot.

  • Silhouette: in [−1,1][-1, 1], higher is better.

  • SSE: lower is better, but it decreases with kk by construction, so it is not a criterion for choosing kk.

Two warnings follow from the numbers above.

Purity is optimistic. On Iris with k=3k=3 the purity is close to 0.9, although the versicolor and virginica classes are not separated at all: the points of these two classes are mixed, and purity only asks that each cluster have a majority class. A clustering that cuts one class into many small pure pieces collects a high purity without having found anything. ARI is the honest number here.

No single internal measure finds the true number of clusters. The silhouette sweep peaks at k=2k=2 (about 0.68) while the ground truth has three classes (about 0.55). The silhouette rewards a coarse and well separated split, and “setosa versus the rest” is exactly that: a very clean two-group solution that is nevertheless not the classification. This is the key lesson of the session — an internal measure encodes a definition of a good cluster, not the truth. It can be optimised, and optimising it can select the wrong answer. Report several measures, look at the data, and trust a measure only when the question it encodes is the question you are asking.

The figure below is drawn with the yellowbrick package (pip install yellowbrick); the scores it prints are the same silhouette_score values computed above.

{2: 0.681, 3: 0.553, 4: 0.498, 5: 0.491}
<Figure size 1800x960 with 4 Axes>

The SSE curve explains why the elbow rule is not a rule. The decrease is steep up to k=3k=3 and then flattens, but it never stops decreasing: at kk large enough every point is its own cluster and the SSE is exactly zero.

 k       SSE     gain  slope change
 1    681.37        -             -
 2    152.35   529.02        455.53
 3     78.86    73.49         51.99
 4     57.35    21.50         10.63
 5     46.47    10.88          3.47
 6     39.07     7.41          2.65
 7     34.31     4.76          0.93
 8     30.48     3.83          3.26
 9     29.91     0.57         -0.79
10     28.55     1.36             -

change of slope          -> k = 2  (drop 455.53)
farthest from the chord  -> k = 3  (distance 0.495, against 0.494 at k = 2)
<Figure size 840x480 with 1 Axes>

Choosing the Number of Clusters

None of the measures above returns kk by itself. The usual workflow is a sweep: cluster the data once for every candidate kk, compute a measure for each, and read the sequence. The silhouette and the gap statistic have a natural optimum — a peak, and a first crossing — while the SSE only decreases, so its curve needs a convention before it can be read. The oldest convention is the elbow.

The elbow rule

Run k-means for k=1,2,…,Kk = 1, 2, \dots, K and plot the SSE against kk. Every new centroid can only lower the objective, so the curve falls monotonically; the question is where it stops falling fast. The intuition is that while the clusters are still being carved out of the data, each extra centroid removes a large part of the error, and afterwards it only splits groups that were already tight. The kk at the bend of the arm is the answer.

The bend is where the gain of one more centroid stops being worth it. Write the gain of going from k−1k-1 to kk centroids as

Δk=SSE(k−1)−SSE(k).\Delta_k = \mathrm{SSE}(k-1) - \mathrm{SSE}(k).

While the curve is steep, each new centroid buys a lot; after the bend the next centroid buys much less than the previous one. The criterion is therefore the largest drop between two consecutive gains — the discrete second difference, or change of slope:

k⋆=arg⁡max⁡2≤k≤K−1(Δk−Δk+1).k^\star = \arg\max_{2 \le k \le K-1} \left( \Delta_k - \Delta_{k+1} \right).

Dividing the same quantity by Δk\Delta_k makes it unit-free and usually gives the same kk.

Do not use the largest relative gain rk=Δk/SSE(k−1)r_k = \Delta_k / \mathrm{SSE}(k-1) as the criterion. Going from one centroid to two always removes by far the largest fraction of the error — the first centroid sits at the centre of the whole cloud — so that rule answers k=2k = 2 on almost every dataset, whatever the structure is.

The geometric version — Kneedle, from Satopää et al. (2011) — needs no threshold at all: it rescales both axes to [0,1][0, 1], joins the first and the last point of the curve by a chord, and takes the point farthest from it.

k⋆=arg⁡max⁡k  ∣(yK−y1) xk′−(xK−x1) yk′+xKy1−yKx1∣(yK−y1)2+(xK−x1)2,k^\star = \arg\max_k \; \frac{\left|(y_K - y_1)\,x'_k - (x_K - x_1)\,y'_k + x_K y_1 - y_K x_1\right|} {\sqrt{(y_K - y_1)^2 + (x_K - x_1)^2}},

where xk′x'_k and yk′y'_k are the rescaled coordinates. It depends on the range [1,K][1, K] of the sweep, which the change-of-slope rule does not. Both versions are still heuristics: they turn a picture into a number, not into evidence.

With the change-of-slope rule the answer on Iris is k=2k = 2: the gains are 529, 73, 21.5, 10.9, 7.4, 4.8, 3.8, 1 and 1, so the drop between consecutive gains falls from 455 to 52 to 11 and then to single digits — after the second centroid nothing comparable is left to win. The chord puts the bend one step further, at k=3k = 3, but by 0.001 only (0.495 against 0.494 at k=2k = 2).

That near-tie is the honest lesson of the page, not a numerical accident: the curve describes the geometry of the data — one compact group (setosa) plus a spread-out remainder — and geometry does not contain a “true” number of classes. If the problem really has three species, that knowledge comes from the domain; the curve is at best consistent with it.

What the elbow rule is good for

  • It is cheap: one clustering per kk and no pairwise distances, so it scales to data where the silhouette does not.

  • It optimises exactly what k-means optimises. When compact, roughly spherical clusters are the goal, the bend is a defensible answer.

  • It cannot recover a kk that is not written into the geometry, it moves when the features are rescaled, and it should never be reported without the curve.

When the elbow is ambiguous, put it next to the silhouette sweep above (a peak, here at k=2k = 2) and to the gap statistic, which is worked out in the appendix together with NMI. If they still disagree, the data does not single out one kk: pick the one the downstream task can use.

Choosing the Right Metric

  1. Use external measures when ground truth is available

  2. Use internal measures when no labels exist

  3. Consider multiple metrics together for robust evaluation

Remember that no single metric tells the whole story - different metrics may be more appropriate for different clustering goals.

Summary

  • A clustering needs validation: without labels, “it converged” says nothing about quality.

  • External measures start from the r×kr \times k contingency table nijn_{ij} (row = cluster, column = class), computed in O(n)O(n).

  • Purity is the sum of the row maxima; it is optimistic, because it allows two clusters to claim the same class.

  • Precision, recall and F add the column view; the maximum matching forces a one-to-one pairing and is an assignment problem (linear_sum_assignment).

  • Pairwise measures count agreements on pairs of points: Jaccard ignores TNTN, Rand counts everything and is inflated by kk, ARI corrects Rand for chance.

  • Internal measures — silhouette and SSE — use only the data; neither identifies the true number of clusters, and optimising one of them can give the wrong answer.

  • The elbow rule reads the SSE curve as a sequence of gains: the bend is where the next gain is much smaller than the current one. On Iris that is k=2k = 2, the chord of the Kneedle variant says k=3k = 3 by a margin of 0.001, and the silhouette peaks at k=2k = 2: a heuristic, not a verdict.

  • NMI, the gap statistic and the full assignment-problem treatment live in the appendix.

  • Report several measures, and state which question each of them answers.

References
  1. Zaki, M. J., & Meira, W. (2020). Data Mining and Machine Learning: Fundamental Concepts and Algorithms (2nd ed.). Cambridge University Press. https://www.cambridge.org/9781108497367