Evaluating clusters
How to measure the quality of clusters using internal, external and relative validity measures (SSE/WCSS, TSS/BSS, silhouette, Dunn, Davies–Bouldin, Rand index, purity, etc.), with formulas, derivations and worked examples.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Clustering groups similar data objects without labels. An engineer uses cluster evaluation to decide whether a clustering result is meaningful — for example, to choose K in K-means, to compare algorithms (K-means vs. hierarchical), or to check how close an unsupervised result is to a known ground truth used in an application.
Key ideas
- Cohesion (also called within-cluster compactness): how close members of the same cluster are to each other (small is better).
- Separation (between-cluster separation): how far different clusters are from each other (large is better).
- Internal validity measure: evaluates clustering using only the data and partition (no ground truth). Examples: Sum of Squared Errors (SSE, often called WCSS), Silhouette, Dunn index, Davies–Bouldin index.
- Assumptions: depends on chosen distance (usually Euclidean) and whether mean/centroid is meaningful.
- External validity measure: compares clustering to an external ground truth labeling. Examples: Rand index, Adjusted Rand Index (ARI), purity, F-measure for clustering, homogeneity and completeness.
- Assumptions: ground truth labels are correct, and mapping between cluster ids and labels is not required for many measures (they are permutation-invariant).
- Relative validity: comparing several clusterings (for different K or algorithms) using one of the above measures to choose the best.
Important theorems and derivations students are asked for
Decomposition of total variance into within-cluster and between-cluster parts (used in K-means analysis): Let data points x_i in R^d, global mean μ = (1/n) Σ_i x_i, clusters C_k with centroids μ_k and sizes n_k. Then TSS = Σ_i ||x_i - μ||^2 = Σ_k Σ_{x in C_k} ||x - μ_k||^2 + Σ_k n_k ||μ_k - μ||^2. Name the terms: TSS = WCSS + BSS (Total = Within + Between). Assumes Euclidean squared distance and arithmetic mean. Derivation steps to write in exam:
- Start with ||x - μ||^2 = ||x - μ_k + μ_k - μ||^2.
- Expand: = ||x - μ_k||^2 + 2 (x - μ_k)·(μ_k - μ) + ||μ_k - μ||^2.
- Sum over x in cluster C_k. The middle term vanishes because Σ_{x in C_k} (x - μ_k) = 0.
- Sum over all clusters to get the equality above.
Silhouette coefficient: for point i define
- a(i): average distance from i to all other points in the same cluster (cohesion).
- b(i): minimum over clusters (other than i's) of average distance from i to points in that other cluster (nearest-cluster separation).
- Then silhouette s(i) = (b(i) - a(i)) / max(a(i), b(i)). Values in [-1, 1]. Assumes a distance metric; if cluster has single point, define a(i)=0 and set s(i)=0 by convention or treat as undefined depending on source — mention this in exams.
Davies–Bouldin index (DB): for K clusters, for each pair compute ratio of (scatter_i + scatter_j) to distance(centroid_i, centroid_j), then DB is average over clusters of the maximum such ratio for each cluster. Lower is better. Assumptions: uses cluster scatter (e.g., average distance to centroid).
Dunn index: ratio of minimal inter-cluster distance to maximal cluster diameter. Higher is better. Sensitive to noisy clusters.
Rand index (pair-counting): considers all pairs of points and counts agreements (both in same cluster in both partitions or both in different clusters in both). Rand in [0,1]. Adjusted Rand Index corrects for chance (formula given below). Assumes flat partitions (no hierarchy).
Diagrams to draw for exam answers
- For TSS = WCSS + BSS: draw a 2D scatter plot with two clusters. Mark centroid of each cluster and global mean. Draw arrows from points to their cluster centroid (to show within-cluster variance) and arrows from centroids to global mean (to show between-cluster term). Label points x_i, μ_k, μ.
- For silhouette: draw one point, its cluster mates and a nearby cluster; indicate a(i) as average of short arrows to same-cluster points and b(i) as average to points in nearest other cluster.
Formulas
μ_k = (1 / n_k) · Σ_{x ∈ C_k} x — μ_k is centroid of cluster C_k; units: same as features (vector); applies when numeric features.
TSS = Σ_{i=1..n} ||x_i - μ||^2 — TSS (total sum of squares); unit: (feature unit)^2; applies for Euclidean squared distance.
WCSS = Σ_{k=1..K} Σ_{x ∈ C_k} ||x - μ_k||^2 — within-cluster sum of squares (same units); applies for centroid-based clusters.
BSS = Σ_{k=1..K} n_k · ||μ_k - μ||^2 — between-cluster sum of squares; unit: (feature unit)^2.
TSS = WCSS + BSS — decomposition; applies under Euclidean squared distance and arithmetic mean.
a(i) = (1 / (|C(i)| - 1)) · Σ_{j ∈ C(i), j ≠ i} d(i,j) — average intra-cluster distance for point i; unit: distance unit; requires cluster size >1.
b(i) = min_{C ≠ C(i)} ( (1 / |C|) · Σ_{j ∈ C} d(i,j) ) — average distance to nearest other cluster; unit: distance.
s(i) = (b(i) - a(i)) / max(a(i), b(i)) — silhouette value for i; unitless; in [-1,1].
Silhouette score = (1 / n) · Σ_{i=1..n} s(i) — average over points; unitless.
DB = (1 / K) · Σ_{i=1..K} max_{j ≠ i} ((S_i + S_j) / d(μ_i, μ_j)) — Davies–Bouldin index; S_i is cluster scatter (e.g., average distance of points in i to μ_i); lower is better; unitless.
Dunn = (min_{i ≠ j} d(C_i, C_j)) / (max_k diam(C_k)) — Dunn index; higher is better; where d(C_i, C_j) is inter-cluster distance (e.g., minimum pairwise) and diam is cluster diameter (max pairwise distance).
Calinski–Harabasz = (BSS / (K - 1)) / (WCSS / (n - K)) — variance ratio criterion; higher is better; assumes Euclidean squared distances so BSS and WCSS are as defined above.
Let contingency table between clusters (rows k) and true labels (columns j) be n_{kj}; then
Rand = (TP + TN) / (n choose 2) — pair agreements fraction; unitless.
Purity = (1/n) · Σ_k max_j n_{kj} — fraction of cluster members assigned to the majority true class in that cluster; unitless.
F_measure (clustering): For each true class j and cluster k, define precision P_{k,j} = n_{kj} / n_k and recall R_{k,j} = n_{kj} / n_j, then F1_{k,j} = (2 · P_{k,j} · R_{k,j}) / (P_{k,j} + R_{k,j}); an overall score often used in exams is F = (1 / n) · Σ_j n_j · max_k F1_{k,j}. Adjusted Rand Index (ARI) = [Σ_{k,j} C(n_{kj}, 2) − (Σ_k C(n_k, 2) · Σ_j C(n_j, 2)) / C(n, 2)] / [0.5 · (Σ_k C(n_k, 2) + Σ_j C(n_j, 2)) − (Σ_k C(n_k, 2) · Σ_j C(n_j, 2)) / C(n, 2)], where n_k = Σ_j n_{kj}, n_j = Σ_k n_{kj}, C(a,2) = a · (a − 1) / 2, and n is the total number of points.
Worked examples
Example 1 — WCSS, TSS and BSS (centroid-based decomposition) Data (2D), four points (units: arbitrary feature units):
- A = (1, 1)
- B = (2, 1)
- C = (4, 4)
- D = (5, 5)
Partition: C1 = {A, B}, C2 = {C, D}.
Step 1: centroids
μ1 = ((1+2)/2, (1+1)/2) = (1.5, 1.0)μ2 = ((4+5)/2, (4+5)/2) = (4.5, 4.5)Step 2: WCSS (sum squared distances to centroids) Cluster 1: A -> ||A-μ1||^2 = (1-1.5)^2 + (1-1)^2 = 0.25 + 0 = 0.25 B -> ||B-μ1||^2 = (2-1.5)^2 + 0 = 0.25
WCSS1 = 0.25 + 0.25 = 0.5 Cluster 2: C -> ||C-μ2||^2 = (4-4.5)^2 + (4-4.5)^2 = 0.25 + 0.25 = 0.5 D -> same = 0.5 WCSS2 = 1.0 Total WCSS = 0.5 + 1.0 = 1.5 Step 3: global mean μ = ((1+2+4+5)/4, (1+1+4+5)/4) = (3.0, 2.75) Step 4: TSS = Σ ||x - μ||^2 A: (1-3)^2 + (1-2.75)^2 = 4 + 3.0625 = 7.0625 B: (2-3)^2 + (1-2.75)^2 = 1 + 3.0625 = 4.0625 C: (4-3)^2 + (4-2.75)^2 = 1 + 1.5625 = 2.5625 D: (5-3)^2 + (5-2.75)^2 = 4 + 5.0625 = 9.0625 TSS = 7.0625 + 4.0625 + 2.5625 + 9.0625 = 22.75 Step 5: BSS = TSS - WCSS = 22.75 - 1.5 = 21.25 Check by centroid distances: for each cluster n_k · ||μ_k - μ||^2 = 2·5.3125 + 2·5.3125 = 21.25. Final answers in same units (feature units)^2:
- WCSS = 1.5
- BSS = 21.25
- TSS = 22.75 (and TSS = WCSS + BSS holds)
Example 2 — Silhouette score for same 4-point partition Compute pairwise Euclidean distances (rounded to 4 decimals): d(A,B)=1.0000; d(A,C)=4.2426; d(A,D)=5.6570 d(B,C)=3.6056; d(B,D)=5.0000 d(C,D)=1.4142 For A (in cluster with B): a(A) = average distance to same-cluster = 1.0000 b(A) = average distance to cluster {C,D} = (4.2426 + 5.6570) / 2 = 4.9498 s(A) = (4.9498 - 1.0000) / 4.9498 = 0.7979 For B: a(B)=1.0000; b(B)=(3.6056 + 5.0000)/2 = 4.3028 => s(B)=0.7675 For C: a(C)=1.4142 (to D); b(C)=(4.2426 + 3.6056)/2 = 3.9241 => s(C)=0.6396 For D: a(D)=1.4142; b(D)=(5.6570 + 5.0000)/2 = 5.3285 => s(D)=0.7344 Average silhouette = (0.7979 + 0.7675 + 0.6396 + 0.7344) / 4 = 0.7349 (approx). Good clustering since value ≈ 0.73 (closer to 1 means better separation).
Example 3 — Rand index quick count (short) Ground truth partition: {A,B}, {C,D}. Predicted partition: {A,C}, {B,D}. All unordered pairs: (A,B),(A,C),(A,D),(B,C),(B,D),(C,D) = 6 pairs. Agreements (both same in both or both different): (A,D) and (B,C) are both different in both partitions → 2 agreements. Rand = 2/6 = 0.3333.
Common mistakes
- Mixing up purity and Rand index: purity ignores true negatives and tends to increase with more clusters (e.g., singleton clusters give purity 1).
- For DB and Dunn indices, using inconsistent definitions of inter-cluster distance (min vs. centroid distance) without stating it; always state which definition you used.
- When using external measures, not handling label permutations (e.g., assuming cluster ID 1 must map to class 1).
For your exam
Types of questions
- Definitions and short notes: define internal vs external validity, cohesion vs separation, silhouette, Dunn, DB, Rand, purity.
- Derivation: show TSS = WCSS + BSS step-by-step and mention assumptions.
- Numerical: compute WCSS/TSS/BSS from small numeric data; compute silhouette values for a few points; compute Rand or purity from small contingency table.
- Diagram: sketch clusters, centroids and global mean; label terms.
- Short programming/algorithm trace: show one iteration of K-means and compute new SSE.
What a full-mark answer includes
- Clear definitions with bold term names.
- Statement of assumptions (e.g., Euclidean distance, use of centroid).
- Correct step-by-step algebra for derivations (middle term vanishing argument for TSS decomposition).
- For numericals: show intermediate arithmetic, units, and final numeric answers in bold.
- For indices: describe interpretation (higher/lower better) and edge cases.
Quick check
- What is the silhouette value range and what do the extremes mean?
- State the decomposition identity connecting TSS, WCSS and BSS and name each term.
- If clustering perfectly matches the ground truth partition, what is the Rand index value? Answers: 1) [-1, 1], +1 very good (well-separated), near 0 overlapping, negative means wrong cluster assignment; 2) TSS = WCSS + BSS where TSS = total sum of squared distances to global mean, WCSS = sum of squared distances to cluster centroids (within-cluster), BSS = sum over clusters of n_k times squared distance of centroid to global mean (between-cluster); 3) Rand = 1.0 (perfect agreement).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?