08_Clustering

Module 7 — Clustering

Sources: Lec 16 — Overview of Data Clustering; Lec 17 — Partitional Clustering; Lec 18 — Hierarchical Clustering (incl. DBSCAN); Lec 19 — Evaluation Criteria for Clustering. · Prev: Module 6 · Next: Module 8 — PCA · Index: 00_INDEX_and_Coverage

Notation

$S=\{{\vec{X}}_1,\dots ,{\vec{X}}_n\}\subset {\mathbb{R}}^m$; clusters $C_1,\dots ,C_k$; centroid ${\vec{\mu }}_j$; distance $\rho$ (default Euclidean).

Python helpers — run once, the checks below reuse them

import numpy as np
from scipy.cluster.hierarchy import linkage, fcluster
from sklearn.cluster import DBSCAN
 
def lloyd(X, mu):
    """Lloyd's k-means from given seeds. Returns (labels, centroids, J)."""
    X2 = np.asarray(X, float).reshape(len(X), -1); mu2 = np.asarray(mu, float).reshape(len(mu), -1)
    while True:
        a = np.argmin(((X2[:, None] - mu2[None])**2).sum(-1), axis=1)          # assign
        new = np.array([X2[a == j].mean(0) for j in range(len(mu2))])           # update
        if np.allclose(new, mu2): break
        mu2 = new
    J = sum(((X2[a == j] - mu2[j])**2).sum() for j in range(len(mu2)))
    return a, mu2.squeeze(), J
 
Jsq = lambda parts: sum(((np.array(p, float) - np.mean(p))**2).sum() for p in parts)   # 1-D squared loss
 
def cluster_F(T):                       # T = contingency table (rows categories, cols clusters)
    T = np.asarray(T, float); r, s, N = T.sum(1), T.sum(0), T.sum(); Fi = []
    for i in range(len(r)):
        f = [2*(T[i,j]/r[i])*(T[i,j]/s[j]) / (T[i,j]/r[i] + T[i,j]/s[j]) for j in range(len(s)) if T[i,j]]
        Fi.append(max(f))
    return np.round(Fi, 4), round(float((r / N * Fi).sum()), 4)
 
def NMI(T):                             # bits; returns MI, E(R), E(S), NMI
    T = np.asarray(T, float); N, r, s = T.sum(), T.sum(1), T.sum(0)
    MI = sum(T[i,j]/N*np.log2(N*T[i,j]/(r[i]*s[j])) for i in range(len(r)) for j in range(len(s)) if T[i,j])
    ER = -(r/N*np.log2(r/N)).sum(); ES = -(s/N*np.log2(s/N)).sum()
    return MI, ER, ES, MI / np.sqrt(ER * ES)

flowchart TD
    C[Clustering] --> P["Partitional (fixed k)<br/>k-means · bisecting · Buckshot · k-medoids<br/>C36–C38"]
    C --> H["Hierarchical (dendrogram)<br/>agglomerative C39 · divisive C40"]
    C --> D["Density-based<br/>DBSCAN C40"]
    C --> E["Evaluation<br/>F-measure C41 · NMI C42"]

---

C35. What Clustering Is: Formulation, Types, and Convexity

Intuition

Group objects so that members of a group resemble each other and differ from other groups — without anyone telling you the groups, like sorting a shop’s customers into segments. Quality depends entirely on how “similar” is measured.

Formal definition

A clustering of $S$ into $k$ clusters is a partition satisfying (i) $C_i\ne \varnothing$; (ii) $C_i\cap C_j=\varnothing$ for $i\ne j$; (iii) ${\bigcup }_{i=1}^k{C}_i=S$.

Types. Hierarchical (a tree of clusters, a dendrogram; agglomerative = bottom-up merging, divisive = top-down splitting) and partitional (a fixed, pre-chosen number $k$ of clusters).

Partitional loss (lecture): $L(P(C_1,\dots ,C_k))={\sum }_{j=1}^k{\sum }_{{\vec{X}}_i\in C_j}\rho ({\vec{X}}_i,{\vec{\mu }}_j),$ and the aim is a partition $P^{\prime }$ with $L(P^{\prime })\le L(P)$ for all partitions $P$.

Mathematical consequence: clusters are convex

For Euclidean $\rho$, a point is assigned to $C_1$ rather than $C_2$ iff $\Vert \vec{X}-{\vec{\mu }}_1\Vert \le \Vert \vec{X}-{\vec{\mu }}_2\Vert$, i.e. $2{\vec{X}}^T({\vec{\mu }}_2-{\vec{\mu }}_1)\le \Vert {\vec{\mu }}_2{\Vert }^2-\Vert {\vec{\mu }}_1{\Vert }^2,$ a half-space (a set bounded by a hyperplane — convex). The intersection of such half-spaces is convex. So the optimum of $L$ always produces convex-shaped clusters, which may not match the structure you want (ring-shaped or crescent-shaped clusters).

Key insights

• The number of partitions of $n$ points into exactly 2 non-empty clusters is $2^{n-1}-1$ (Stirling number $S(n,2)$) — exhaustive search is hopeless in general.
• Clustering is unsupervised: validity must be judged by external labels (C41–C42) or by internal criteria.

Worked examples

Example 1 — Very Easy · Valid partitions

• Problem: For $S=\{a,b,c,d\}$ which are valid partitions? (i) $\{a,b\},\{c,d\}$; (ii) $\{a,b\},\{b,c,d\}$; (iii) $\{a\},\{b\},\{c\}$; (iv) $\{a,b,c,d\},\varnothing$.
• Asked: Validity.
• Concept: Partition axioms.
• Approach: Test the three conditions.
• Solution: (i) valid. (ii) $b$ is in both ⇒ violates disjointness. (iii) $d$ is missing ⇒ violates covering. (iv) an empty cluster ⇒ violates non-emptiness.
• Final answer: Only (i).

Key lesson

Hard clustering ⇒ each point belongs to exactly one non-empty cluster.

Example 2 — Easy · Scoring two clusterings

• Problem: $S=\{1,2,3,10,11\}$ (1-D). Compute $L$ with $\rho =|\cdot |$ for $A=\{1,2,3\},\{10,11\}$ and $B=\{1,2\},\{3,10,11\}$.
• Asked: $L(A),L(B)$.
• Concept: Partitional loss.
• Approach: Centroids are means.
• Solution: $A$: $\mu =2$: $1+0+1=2$; $\mu =10.5$: $0.5+0.5=1$ ⇒ $L=3$. $B$: $\mu =1.5$: $1$; $\mu =8$: $5+2+3=10$ ⇒ $L=11$.
• Final answer: $L(A)=3<L(B)=11$.

Key lesson

Good clusterings have small loss.

Example 3 — Moderate · Counting partitions

• Problem: How many ways can $4$ labelled points be split into exactly 2 non-empty clusters? How many partitions in total (any $k$)?
• Asked: Counts.
• Concept: Combinatorics of partitions.
• Approach: Pin one point; the others choose a side.
• Solution: Fix point $1$ in cluster A; each other point is in A or B: $2^3=8$ assignments; exclude “all in A” ⇒ $7=2^3-1$. Total over all $k$: Bell number $B_4=1+7+6+1=15$ ($S(4,1)=1,S(4,2)=7,S(4,3)=6,S(4,4)=1$).
• Final answer: $7$ and $15$.

Python check

from sympy.functions.combinatorial.numbers import bell
print(2**3 - 1, bell(4), bell(10), bell(20))        # 7  15  115975  51724158235372

Key lesson

The search space grows super-exponentially (20 points already have $5\times 10^{13}$ partitions).

Example 4 — Hard · The loss cannot find nested clusters

• Problem: Points $\{-10,10\}$ (an “outer” cluster) and $\{-0.5,0,0.5\}$ (an “inner” cluster). The desired clustering is inner vs outer. Compute $L$ ($\rho =|\cdot |$) for it and compare with the best two-cluster partition.
• Asked: Is the desired clustering optimal?
• Concept: The optimum of $L$ is convex-shaped.
• Approach: Enumerate the $2^4-1=15$ partitions.
• Solution: Desired: $\{-10,10\}$: $\mu =0$ ⇒ $20$; $\{-0.5,0,0.5\}$: $\mu =0$ ⇒ $1$. $L=21$. Enumerating all 15 partitions, the minimum is $L=15$ for $\{-10,-0.5,0,0.5\}|\{10\}$ (and its mirror image): centroids $-2.5$ and $10$: $7.5+2+2.5+3=15$. Next: $20.5$ (×2), $20.83$ (×2) — six partitions beat the desired one.
• Final answer: Desired $L=21$; optimal $L=15$ with interval clusters.

Python check

import itertools
S = [-10, 10, -.5, 0, .5]; L1 = lambda parts: sum(np.abs(np.array(p) - np.mean(p)).sum() for p in parts)
res = []
for mask in range(1, 2**4):
    A = [S[0]] + [S[i] for i in range(1, 5) if not (mask >> (i-1)) & 1]; B = [S[i] for i in range(1, 5) if (mask >> (i-1)) & 1]
    if B: res.append(round(L1([A, B]), 3))
print(sorted(res)[:7], L1([[-10, 10], [-.5, 0, .5]]))   # [15.0, 15.0, 20.5, 20.5, 20.833, 20.833, 21.0]  21.0

Key lesson

A non-convex cluster (outer points surrounding the inner ones) can never be an optimum of this criterion.

Example 5 — Very Hard · Concentric rings

• Problem: Concentric “rings”: inner $(\pm 1,0),(0,\pm 1)$; outer $(\pm 4,0),(0,\pm 4)$. (a) Show that for the desired ring partition both centroids coincide at the origin. (b) Compute $L$ (Euclidean distances) for the desired partition and for the half-space partition ”$x_1<0$ vs $x_1\ge 0$”. (c) What is the optimum over all 127 two-cluster partitions?
• Asked: Three computations.
• Concept: Half-space limitation.
• Approach: Centroids; sum distances.
• Solution: (a) Inner mean $=(0,0)$; outer mean $=(0,0)$. Equal centroids ⇒ the bisector is empty — a centroid-based assignment cannot even represent nested clusters. (b) Desired: inner distances $4\times 1=4$; outer $4\times 4=16$ ⇒ $L=20$. Half-space: left $\{(-1,0),(-4,0)\}$, $\mu =(-2.5,0)$ ⇒ $3$; right (6 points) $\mu =(\frac{5}{6},0)$: $d(1,0)=0.1667$; $d(4,0)=3.1667$; $d(0,\pm 1)=1.3017$ each; $d(0,\pm 4)=4.0858$ each; sum $=14.108$ ⇒ $L=17.11$. (c) Exhaustive minimum $=15.81$ (isolating one outer point).
• Final answer: Desired ring partition $L=20$ is worse than a plain half-space split $17.11$ and than the optimum $15.81$.

Python check

pts = np.array([(1,0),(-1,0),(0,1),(0,-1),(4,0),(-4,0),(0,4),(0,-4)], float)
Lp = lambda parts: sum(np.linalg.norm(p - p.mean(0), axis=1).sum() for p in parts)
print(Lp([pts[:4], pts[4:]]), Lp([pts[pts[:, 0] < 0], pts[pts[:, 0] >= 0]]))   # 20.0  17.1085
best = 1e9
for mask in range(1, 2**7):                                  # point 0 always on side 0
    side = np.array([0] + [(mask >> (i - 1)) & 1 for i in range(1, 8)])
    if side.min() != side.max():
        best = min(best, Lp([pts[side == 0], pts[side == 1]]))
print(best)                                                  # 15.8133

Key lesson

For non-convex clusters use density-based (C40) or single-linkage methods, not centroid-based ones.

Common mistakes

• Allowing overlapping or empty clusters in a hard clustering.
• Assuming the optimum of $L$ finds “natural” shapes.

Exam traps

• Partitional ⇒ $k$ fixed in advance; hierarchical ⇒ no $k$ in advance (but a cut level or stopping criterion is needed).
• $L$ gives convex clusters.

Connections: C36–C40 (algorithms), C41–C42 (evaluation), C17 (assignment = minimum distance to centroids).

Mastery checklist

• State the three partition axioms.
• Define the partitional loss $L$.
• Explain why $L$ yields convex clusters.

---

C36. The k-Means (Lloyd) Algorithm

Intuition

Alternate two easy steps: (1) assign every point to its nearest centre; (2) move every centre to the mean of its points. Each step lowers (or keeps) the total squared distance, so the process settles.

flowchart LR
    I["choose k seeds"] --> A["Assign each point<br/>to nearest centroid"]
    A --> U["Update each centroid<br/>to its cluster mean"]
    U --> Q{"centroids<br/>unchanged?"}
    Q -->|no| A
    Q -->|yes| S([stop])

Algorithm (Lloyd, as in the lecture)

1. Choose $k$ initial centroids ${\vec{\mu }}_j(0)$ randomly from the data. Set $I\leftarrow 0$.
2. Assign: $C_j(I+1)=\{{\vec{X}}_i:\rho ({\vec{X}}_i,{\vec{\mu }}_j(I))\le \rho ({\vec{X}}_i,{\vec{\mu }}_r(I))\forall r\}$.
3. Update: ${\vec{\mu }}_j(I+1)=\frac{1}{|C_j(I+1)|}{\sum }_{{\vec{X}}_i\in C_j(I+1)}{\vec{X}}_i$.
4. Stop if ${\vec{\mu }}_j(I+1)={\vec{\mu }}_j(I)\forall j$ or $I>\alpha$ (iteration cap); else $I\leftarrow I+1$ and go to step 2.

(MacQueen’s variant updates a centroid immediately after each single reassignment.)

Mathematical analysis

With $\rho$ the squared Euclidean distance the objective is $J={\sum }_j{\sum }_{\vec{X}\in C_j}\Vert \vec{X}-{\vec{\mu }}_j{\Vert }^2$.

• Update step is optimal for fixed assignments: $\frac{\partial }{\partial \vec{\mu }}{\sum }_{\vec{X}\in C}\Vert \vec{X}-\vec{\mu }{\Vert }^2=-2\sum (\vec{X}-\vec{\mu })=0\Rightarrow \vec{\mu }=\frac{1}{|C|}\sum \vec{X}$ (the mean); second derivative $2|C|>0$ ⇒ minimum.
• Assignment step is optimal for fixed centroids (each point picks the smallest term).
• Hence $J$ never increases; with finitely many partitions the algorithm terminates at a local minimum.
• Cost per iteration $O(nkm)$ (linear in $n$).

Limitations

$k$ must be given; sensitive to initial seeds and to the distance function; local optima; sensitive to outliers (the mean); convex clusters only.

Worked examples

Example 1 — Very Easy · One assignment step

• Problem: $S=\{1,2,3,10,11,12\}$, $k=2$, initial centroids $1$ and $2$. Do one assignment step.
• Asked: Clusters after step 2.
• Concept: Assignment.
• Approach: Nearest centroid.
• Solution: $1$: distances $0$ vs $1$ ⇒ $C_1$. $2$: $1$ vs $0$ ⇒ $C_2$. $3$: $2$ vs $1$ ⇒ $C_2$. $10$: $9$ vs $8$ ⇒ $C_2$; likewise $11,12\to C_2$.
• Final answer: $C_1=\{1\}$, $C_2=\{2,3,10,11,12\}$.

Key lesson

Poor seeds give a poor first partition.

Example 2 — Easy · Run to convergence

• Problem: Continue Example 1 to convergence; report $J$ after each update.
• Asked: Final clusters and $J$.
• Concept: Lloyd iterations.
• Approach: Alternate.
• Solution: Update 1: ${\mu }_1=1$, ${\mu }_2=\frac{2+3+10+11+12}{5}=7.6$; $J=0+(31.36+21.16+5.76+11.56+19.36)=89.2$. Assign 2: $1,2,3\to C_1$; $10,11,12\to C_2$. Update 2: ${\mu }_1=2$, ${\mu }_2=11$; $J=2+2=4$. Assign 3: unchanged ⇒ stop.
• Final answer: $\{1,2,3\},\{10,11,12\}$; $J:89.2\to 4.0$.

Python check

print(lloyd([1, 2, 3, 10, 11, 12], [1, 2]))              # labels [0 0 0 1 1 1]  centroids [2. 11.]  J = 4.0

Key lesson

$J$ decreases monotonically.

Example 3 — Moderate · Four points in 2-D

• Problem: 2-D points $A(1,1),B(2,1),C(4,3),D(5,4)$, $k=2$, seeds $A$ and $D$. Run to convergence.
• Asked: Final clusters, centroids, $J$.
• Concept: Lloyd in 2-D.
• Approach: Euclidean distances.
• Solution: $B$: $d(B,A)=1$, $d(B,D)=4.24$ ⇒ $C_1$. $C$: $d(C,A)=3.61$, $d(C,D)=1.41$ ⇒ $C_2$. $C_1=\{A,B\}$, $C_2=\{C,D\}$; ${\mu }_1=(1.5,1)$, ${\mu }_2=(4.5,3.5)$. Re-assign: no change. $J=2(0.25)+2(0.5)=1.5$.
• Final answer: $\{A,B\},\{C,D\}$, $\mu =(1.5,1),(4.5,3.5)$, $J=1.5$.

Python check

print(lloyd([[1,1],[2,1],[4,3],[5,4]], [[1,1],[5,4]]))   # labels [0 0 1 1]  centroids [[1.5 1.][4.5 3.5]]  J = 1.5

Key lesson

Converged when the centroids stop moving.

Example 4 — Hard · Local vs global optimum

• Problem: $S=\{2,4,18,24,25,27\}$, $k=3$. (a) Seeds $\{2,4,18\}$. (b) Find the global optimum. Compare $J$.
• Asked: Local vs global optimum.
• Concept: Initialisation sensitivity.
• Approach: Run Lloyd; enumerate contiguous 3-partitions.
• Solution: (a) Assign: $2\to c_1$; $4\to c_2$; $18,24,25,27\to c_3$. Update: $\mu =(2,4,23.5)$ — unchanged on re-assignment ⇒ converged. $J=30.25+0.25+2.25+12.25=45$. (b) Best partition $\{2,4\},\{18\},\{24,25,27\}$: $J=2+0+4.667=6.667$ (centroids $3,18,25.33$).
• Final answer: Seeds $\{2,4,18\}$ give $J=45$ (local optimum); the global optimum has $J=6.667$.

Python check

S = [2, 4, 18, 24, 25, 27]
print(lloyd(S, [2, 4, 18])[2])                           # 45.0   (stuck)
print(min((Jsq([S[:i], S[i:j], S[j:]]), i, j) for i in range(1, 5) for j in range(i+1, 6)))   # (6.667, 2, 3)

Key lesson

k-means converges, but not necessarily to the best answer — run several seeds.

Example 5 — Very Hard · Why Lloyd always terminates

• Problem: Prove that Lloyd’s algorithm (squared Euclidean) never increases $J$ and terminates; then verify numerically on Example 2.
• Asked: Proof and check.
• Concept: Coordinate descent.
• Approach: Two-step monotonicity.
• Solution: Let $J(\mathcal{C},\mu )={\sum }_j{\sum }_{\vec{X}\in C_j}\Vert \vec{X}-{\vec{\mu }}_j{\Vert }^2$. Assign step: with $\mu$ fixed, moving a point from $C_a$ to the nearest $C_b$ replaces $\Vert \vec{X}-{\mu }_a{\Vert }^2$ by $\Vert \vec{X}-{\mu }_b{\Vert }^2\le \Vert \vec{X}-{\mu }_a{\Vert }^2$ ⇒ $J$ does not increase. Update step: with $\mathcal{C}$ fixed, the mean minimises each cluster’s sum of squares ⇒ $J$ does not increase. The sequence $J_0\ge J_1\ge \cdots \ge 0$ is bounded below. Because the number of partitions $k^n$ is finite and $J$ strictly decreases whenever the partition changes, no partition repeats ⇒ termination. Check: Example 2 gave $J=89.2$ then $4.0$ ✓.
• Final answer: Monotone decreasing, finite termination at a local minimum.

Key lesson

The proof requires the mean — it is the minimiser only for squared distances (for $|\cdot |$ the minimiser is the median, giving k-medians / k-medoids, C38).

Common mistakes

• Using k-means with arbitrary distances and still taking the mean.
• Stopping after one iteration.

Exam traps

• Stop rule: centroids unchanged for consecutive iterations (or an iteration cap).
• Complexity is linear in $n$ but iterations may be many.

Connections: C17 (minimum distance), C35, C37–C38, PCA preprocessing (C46).

Mastery checklist

• Run Lloyd’s algorithm by hand.
• Prove monotone decrease.
• Explain local optima and how to mitigate them.

---

C37. Bisecting k-Means and the Buckshot Algorithm

Intuition

Two repairs to k-means. Bisecting: build $k$ clusters top-down by repeatedly splitting the largest cluster with 2-means (deterministic structure, near-uniform sizes). Buckshot: get good seeds by clustering a small random sample hierarchically first.

Algorithms

Bisecting k-means: start with all data as one cluster; while fewer than $k$ clusters, pick the largest cluster and split it into two with ($k=2$) k-means. Buckshot: (1) draw a random sample of size $\sqrt{kn}$; (2) cluster the sample by (agglomerative) hierarchical clustering down to $k$ clusters; (3) use their $k$ centroids as seeds for ordinary k-means on all $n$ points.

Properties

• Bisecting produces clusters of almost uniform size: good when true clusters are balanced, poor when sizes differ greatly. It still needs $k$ and 2-means seeds.
• Buckshot: the hierarchical step is cheap (small sample); repeated runs give different partitions; poor if the sample is unrepresentative; still needs $k$.

Worked examples

Example 1 — Very Easy · Which cluster to split?

• Problem: Current clusters have sizes $10,6,4$. Which does bisecting k-means split next?
• Asked: Choice.
• Concept: “Largest cluster” rule.
• Approach: Max size.
• Solution: The size-10 cluster.
• Final answer: The size-10 cluster.

Key lesson

Selection is by size, not by within-cluster scatter.

Example 2 — Easy · Buckshot sample size

• Problem: Buckshot sample sizes for ($n=100,k=4$) and ($n=10^6,k=10$).
• Asked: Two sizes.
• Concept: $\sqrt{kn}$.
• Approach: Compute.
• Solution: $\sqrt{400}=20$; $\sqrt{10^7}=3162$.
• Final answer: $20$ and $3162$.

Key lesson

The sample is a vanishing fraction of the data for large $n$ ($0.3\%$ in the second case).

Example 3 — Moderate · Bisecting with k = 3

• Problem: Bisecting k-means with $k=3$ on $\{1,2,3,10,11,12,30,31\}$ (assume each 2-means finds the optimal split).
• Asked: Final clusters.
• Concept: Bisecting procedure.
• Approach: First split, then split the largest.
• Solution: 2-means on all 8: best contiguous split $\{1,2,3,10,11,12\},\{30,31\}$ ($J=126$; the competing split $\{1,2,3\},\{10,11,12,30,31\}$ has $J=460.8$). The largest cluster is the six-point one ⇒ 2-means: $\{1,2,3\},\{10,11,12\}$.
• Final answer: $\{1,2,3\},\{10,11,12\},\{30,31\}$.

Python check

print(Jsq([[1,2,3,10,11,12], [30,31]]), Jsq([[1,2,3], [10,11,12,30,31]]))   # 126.0  460.8

Key lesson

Splitting the largest cluster recovers the true structure here.

Example 4 — Hard · Buckshot step by step

• Problem: Buckshot on $\{1,2,3,4,20,21,22,23\}$, $k=2$: sample size $\sqrt{2\cdot 8}=4$; suppose the sample is $\{2,4,20,23\}$. Cluster it by single linkage to 2 clusters, then run k-means from those centroids.
• Asked: Seeds and final result.
• Concept: Buckshot.
• Approach: Hierarchical clustering on the sample.
• Solution: Sample distances: $2$–$4$: $2$; $20$–$23$: $3$; $4$–$20$: $16$. Single linkage merges $(2,4)$ then $(20,23)$ ⇒ clusters $\{2,4\},\{20,23\}$ with centroids $3$ and $21.5$ (seeds). k-means on all 8: $1,2,3,4\to 3$; $\mathrm{20..23}\to 21.5$. Update: $2.5$ and $21.5$; assignments unchanged ⇒ converged. $J=10$.
• Final answer: $\{1,2,3,4\},\{20,21,22,23\}$, $J=10$.

Python check

print(lloyd([1,2,3,4,20,21,22,23], [3, 21.5]))           # centroids [2.5 21.5]  J = 10.0

Key lesson

Seeds from a hierarchical pass avoid pathological starts.

Example 5 — Very Hard · Bisecting vs plain k-means

• Problem: Data $\{2,4,18,24,25,27\}$, $k=3$ (as in C36 Ex. 4). Compare bisecting k-means with plain k-means seeded $\{2,4,18\}$.
• Asked: $J$ of each.
• Concept: Bisecting as deterministic top-down.
• Approach: Optimal 2-splits.
• Solution: First split of all six: $\{2,4\}|\{18,24,25,27\}$: $2+45=47$; $\{2,4,18\}|\{24,25,27\}$: $156.7$; others larger ⇒ choose the first. The largest is the 4-point cluster: $\{18\}|\{24,25,27\}$: $4.667$; $\{18,24\}|\{25,27\}$: $20$ ⇒ choose the first. Final: $\{2,4\},\{18\},\{24,25,27\}$: $J=6.667$ (global optimum). Plain k-means from the unlucky seeds: $J=45$.
• Final answer: Bisecting $6.667$ vs plain k-means $45$.

Python check

print(Jsq([[2,4], [18,24,25,27]]), Jsq([[18], [24,25,27]]), Jsq([[18,24], [25,27]]))   # 47.0  4.667  20.0

Key lesson

Top-down splitting can avoid bad seeds — but is not guaranteed optimal in general.

Common mistakes

• Splitting the cluster with largest variance (the lecture’s rule is largest size).
• Taking a sample of size $\sqrt{k}n$.

Exam traps

• Bisecting ⇒ near-uniform sizes; fails with very unequal true sizes.
• Buckshot needs $k$ and a hierarchical step on $\sqrt{kn}$ points.

Connections: C36, C39.

Mastery checklist

• Execute bisecting k-means.
• Compute Buckshot’s sample size.
• State the weaknesses of each.

---

C38. k-Medoids

Intuition

The mean can be dragged away by an outlier and need not be a real data point. A medoid is an actual data point near the centre — robust, and usable with any dissimilarity. (Think of the median household income vs the mean once a billionaire moves in.)

Definitions (lecture)

• Medoid (minimax form): for each ${\vec{X}}_i$ compute $Z_i={\max }_j\rho ({\vec{X}}_i,{\vec{X}}_j)$; the medoid is the point achieving $Z^{\prime }={\min }_i{Z}_i$. Cost $O(n^2)$.
• Approximation: the member closest to the mean $\vec{\mu }$ of the set: ${\vec{X}}_0=\arg {\min }_{{\vec{X}}_i\in S}\rho ({\vec{X}}_i,\vec{\mu })$. Cost $O(n)$.
• (The lecture also describes the medoid as the member with minimal average distance to all others — the standard textbook definition; the three definitions often, but not always, coincide.)

The rest of the algorithm is k-means with medoids in place of means.

Key insights

• Robust to outliers; the centre is always a data point.
• Same limitations as k-means ($k$ fixed, seeds).

Worked examples

Example 1 — Very Easy · Mean vs medoid

• Problem: Medoid (closest-to-mean) of $\{1,2,3,100\}$.
• Asked: Medoid and mean.
• Concept: Approximation.
• Approach: Mean, then nearest member.
• Solution: Mean $=26.5$. Distances: $25.5,24.5,23.5,73.5$ ⇒ nearest is $3$.
• Final answer: Mean $26.5$, medoid $3$.

Key lesson

The mean is pulled by $100$; the medoid is not.

Example 2 — Easy · Three definitions

• Problem: For $\{1,2,3,100\}$ compute the minimax and average-distance medoids.
• Asked: Two medoids.
• Concept: Definitions.
• Approach: Table.
• Solution: Max distances: $1\to 99$, $2\to 98$, $3\to 97$, $100\to 99$ ⇒ minimax medoid $3$. Average distances: $1:25.5$; $2:25$; $3:25$; $100:73.5$ ⇒ tie between $2$ and $3$.
• Final answer: Minimax: $3$; average: $2$ or $3$.

Python check

x = np.array([1, 2, 3, 100.]); D = np.abs(x[:, None] - x[None])
print(D.max(1), D.mean(1))                               # [99 98 97 99]   [25.5 25. 25. 73.5]

Key lesson

Definitions can disagree on ties; state which you use.

Example 3 — Moderate · Centres of an outlier cluster

• Problem: Cluster $\{10,11,12,200\}$: mean, approximate medoid, and the distance of a new point $11.5$ to each.
• Asked: Compare centres.
• Concept: Outlier robustness.
• Approach: Compute.
• Solution: Mean $=58.25$. Distances of members to $58.25$: $48.25,47.25,46.25,141.75$ ⇒ approximate medoid $12$. Distance of $11.5$: to the mean $46.75$; to the medoid $0.5$.
• Final answer: Mean $58.25$ vs medoid $12$.

Key lesson

The mean is far from every real member.

Example 4 — Hard · Cost of exact vs approximate

• Problem: For $n=1000$ compare the number of distance evaluations for the exact minimax medoid vs the mean-based approximation (per cluster).
• Asked: Counts.
• Concept: Complexity.
• Approach: Pairs vs points.
• Solution: Exact: all ordered pairs, $n^2=10^6$ (or $\left(\genfrac{}{}{0ex}{}{n}{2}\right)\approx 5\times 10^5$ distinct). Approximate: compute the mean ($O(nm)$) then $n=1000$ distances.
• Final answer: $\sim 10^6$ vs $\sim 10^3$ distances.

Key lesson

Hence the approximation in practice, at the price of exactness.

Example 5 — Very Hard · k-medoids with an outlier

• Problem: $S=\{1,2,3,10,11,12,200\}$, $k=3$, $\rho =|\cdot |$. Start with medoids $\{1,10,200\}$ and run to convergence; report cost.
• Asked: Final medoids and clusters.
• Concept: k-medoids iteration.
• Approach: Assign; recompute medoids (minimising total distance).
• Solution: Assign: $\{1,2,3\}\to 1$, $\{10,11,12\}\to 10$, $\{200\}\to 200$. New medoids: for $\{1,2,3\}$ total distance to $2$ is $2$ (vs $3$ for $1$) ⇒ $2$; for $\{10,11,12\}$ ⇒ $11$; $\{200\}\to 200$. Re-assign: unchanged. Cost $=2+2+0=4$.
• Final answer: Medoids $2,11,200$; clusters $\{1,2,3\},\{10,11,12\},\{200\}$; cost $4$.

Key lesson

The outlier $200$ gets its own cluster rather than distorting a centroid.

Common mistakes

• Using the mean and calling it a medoid.
• Believing the medoid must minimise squared distance (that is the mean).

Exam traps

• A medoid is a data point; a mean need not be.
• Both k-means and k-medoids need $k$ and seeds.

Connections: C36, robust statistics (median), C37.

Mastery checklist

• Compute a medoid by the three definitions.
• Explain outlier robustness.
• State the cost of exact vs approximate medoids.

---

C39. Agglomerative Hierarchical Clustering: Single, Complete, Average Linkage

Intuition

Start with every point alone; repeatedly merge the two closest clusters; record the merges in a tree (dendrogram). “Closest” for sets of points needs a definition — that choice is the linkage.

 height
  4 |        ┌──────────┐
  3 |        │          │
  2 |   ┌────┘       ┌──┴──┐        ← cut here ⇒ 3 clusters
  1 | ┌─┴─┐        ┌─┴─┐   │
    +─0───1────────4───6───10──→ points

Algorithm

1. Every point is a singleton cluster. 2. Compute distances between all pairs of clusters. 3. Merge the closest pair. 4. Repeat 2–3 until one cluster (or until the desired number of clusters). Cutting the dendrogram at a height gives a flat clustering.

Linkages (lecture)

For clusters $C_1=\{X_{1i}{\}}_{i\le p}$, $C_2=\{X_{2j}{\}}_{j\le q}$: $d_{single}={\min }_{i,j}\rho (X_{1i},X_{2j}),d_{complete}={\max }_{i,j}\rho (X_{1i},X_{2j}),d_{avg}=\frac{1}{pq}{\sum }_{i=1}^p{\sum }_{j=1}^q\rho (X_{1i},X_{2j}).$ Update rule after merging $i,j$ into $(ij)$, for another cluster $k$ (Lance–Williams): single $d_{k,(ij)}=\min (d_{ki},d_{kj})$; complete $\max (d_{ki},d_{kj})$; average $\frac{n_i{d}_{ki}+n_j{d}_{kj}}{n_i+n_j}$.

Behaviour

• Single: can follow chains of close points ⇒ long, straggly clusters; the chaining effect: two clusters joined by a thin bridge of noise points get merged.
• Complete: compact, roughly spherical clusters; sensitive to outliers.
• Average: in between.
• Naive complexity $O(n^3)$ time, $O(n^2)$ memory. Choosing where to stop is the main practical difficulty.

Python helper for the checks in this section

def heights(pts, method):                # merge heights of the dendrogram
    return np.round(linkage(np.array(pts, float)[:, None], method)[:, 2], 3)

Worked examples

Example 1 — Very Easy · The three distances

• Problem: $C_1=\{1,2\}$, $C_2=\{5,9\}$ (1-D). Compute the three linkage distances.
• Asked: Three numbers.
• Concept: Linkage definitions.
• Approach: All cross distances: $|1-5|=4,|1-9|=8,|2-5|=3,|2-9|=7$.
• Solution: Single $=\min =3$; complete $=\max =8$; average $=\frac{4+8+3+7}{4}=5.5$.
• Final answer: $3,8,5.5$.

Key lesson

Single $\le$ average $\le$ complete, always.

Example 2 — Easy · Dendrogram heights

• Problem: Points $0,1,4,6,10$. Give the merge sequence and heights for single, complete, average.
• Asked: Three dendrograms.
• Concept: Algorithm.
• Approach: Merge the closest pair each time.
• Solution: All three first merge $\{0,1\}$ (height $1$), then $\{4,6\}$ (height $2$). Next: single: $3$; complete: $6$; average: $\frac{4+6+3+5}{4}=4.5$. Then $10$ joins $\{0,1,4,6\}$: single $=4$; complete $=10$; average $=\frac{10+9+6+4}{4}=7.25$.
• Final answer: Heights — single: $1,2,3,4$; complete: $1,2,6,10$; average: $1,2,4.5,7.25$.

Python check

for m in ("single", "complete", "average"): print(m, heights([0, 1, 4, 6, 10], m))
# single [1 2 3 4]   complete [1 2 6 10]   average [1 2 4.5 7.25]

Key lesson

Same merge order here, different heights.

Example 3 — Moderate · Doubling gaps

• Problem: Points $1,2,4,8,16$. Merge heights for the three linkages.
• Asked: Heights.
• Concept: Height behaviour.
• Approach: Sequential merges (all produce $\{1,2\}$, then $4$, then $8$, then $16$).
• Solution: Single: $1,2,4,8$. Complete: $1,3,7,15$. Average: $1,2.5,5.667,12.25$.
• Final answer: Single $1,2,4,8$; complete $1,3,7,15$; average $1,2.5,5.67,12.25$.

Python check

for m in ("single", "complete", "average"): print(m, heights([1, 2, 4, 8, 16], m))

Key lesson

Complete-link heights are the cluster diameters.

Example 4 — Hard · Three linkages, three answers

• Problem: Points $7,9,16,24,30,35$. Find the 3-cluster partition from each linkage.
• Asked: Three partitions.
• Concept: Linkages can disagree.
• Approach: Run three merges each.
• Solution: Pairwise gaps: $2,7,8,6,5$. Single: $(7,9)$ at 2; $(30,35)$ at 5; $24$ joins $\{30,35\}$ at 6 ⇒ $\{7,9\},\{16\},\{24,30,35\}$. Complete: $(7,9)$ at 2; $(30,35)$ at 5; next smallest: $d(16,24)=8$ (vs $d(16,\{7,9\})=9$, $d(24,\{30,35\})=11$) ⇒ $\{7,9\},\{16,24\},\{30,35\}$. Average: $d(16,\{7,9\})=8$ vs $d(24,\{30,35\})=8.5$ ⇒ $\{7,9,16\},\{24\},\{30,35\}$.
• Final answer: Three different partitions.

Python check

for m in ("single", "complete", "average"):
    print(m, fcluster(linkage(np.array([7, 9, 16, 24, 30, 35.])[:, None], m), 3, "maxclust"))
# single [2 2 3 1 1 1]   complete [2 2 3 3 1 1]   average [1 1 1 3 2 2]

Key lesson

The linkage is the assumption about what a cluster looks like.

Example 5 — Very Hard · Chaining across a bridge

• Problem: Two blobs $\{0,1,2\}$ and $\{10,11,12\}$ connected by a sparse bridge $\{4,6,8\}$. Compare single and complete linkage; what does each give for 3 clusters?
• Asked: Chaining demonstration.
• Concept: Chaining effect.
• Approach: Merge heights.
• Solution: Single: four merges at height $1$ build $\{0,1,2\}$ and $\{10,11,12\}$; then every bridge gap is $2$, so all remaining merges happen at height 2 — the dendrogram cannot tell the bridge from the blobs, and a 3-cluster cut depends on tie-breaking (it may absorb the bridge into a blob). Complete: merge heights $1,1,2,2,2,4,8,12$; the 3-cluster cut gives $\{0,1,2\},\{4,6,8\},\{10,11,12\}$ — the true structure.
• Final answer: Single linkage chains through the bridge; complete linkage recovers three clusters.

Python check

pts = [0, 1, 2, 4, 6, 8, 10, 11, 12]
print(heights(pts, "single"), heights(pts, "complete"))   # [1 1 1 1 2 2 2 2]   [1 1 2 2 2 4 8 12]

Key lesson

Single linkage is fragile under noise bridges; complete linkage is robust (but outlier-sensitive).

Common mistakes

• Re-using the original distances after a merge (they must be updated).
• Forgetting ties.

Exam traps

• Single = min, complete = max, average = mean of all cross distances.
• Hierarchical methods need a halting criterion (the lecture’s main limitation).

Connections: C35, C37 (Buckshot step), C40 (DBSCAN avoids chaining).

Mastery checklist

• Compute all three linkages for two sets.
• Build a dendrogram by hand.
• Explain chaining.

---

C40. Divisive Clustering and DBSCAN

Intuition

Divisive: start with everything in one cluster and split — the mirror image of agglomerative. DBSCAN: clusters are dense regions separated by sparse regions; points in sparse regions are noise. It finds arbitrarily shaped clusters and does not need $k$.

  noise     border  core core core  border          core core core
    ·         ·  ● ● ● ·              ·  ● ● ● ·      ← each ● has ≥ r neighbours within ε
                 └── cluster 1 ──┘        └─ cluster 2 ─┘

Divisive clustering (lecture)

Start with the whole data set as one cluster. At each step choose one existing cluster (generally the one with the least overall similarity) and split it into two. Stop when only singletons remain or a halting criterion is met. Limitation: choosing the halting point for unknown data.

DBSCAN (Ester et al. 1996; as in the lecture)

Parameters: neighbourhood radius $ϵ>0$, minimum count $r>0$.

1. Neighbourhood of each point: $H_i=\{X_j\in S:\rho (X_i,X_j)\le ϵ\}$ (it includes $X_i$ itself).
2. Merge $H_i$ and $H_j$ into $H_i\cup H_j$ if $|H_i|\ge r$, $|H_j|\ge r$ and $H_i\cap H_j\ne \varnothing$.
3. Repeat until no merge occurs. Points belonging to no merged neighbourhood are noise.

(In common terminology: a point with $|H_i|\ge r$ is a core point; non-core points inside a core’s neighbourhood are border points.)

Key insights

• No $k$; detects noise; can find non-convex clusters.
• Avoids chaining because bridging requires dense neighbourhoods.
• Hard to choose $ϵ$ and $r$; a single global density can fail when densities vary.

Worked examples

Example 1 — Very Easy · One divisive step

• Problem: A cluster $\{1,2,3,10,11,12\}$. Which split minimises the sum of within-cluster scatter (2-means)?
• Asked: The split.
• Concept: Divisive splitting.
• Approach: Split into two groups.
• Solution: $\{1,2,3\},\{10,11,12\}$: $J=2+2=4$; any other contiguous split is larger (e.g. $\{1\},\{2,3,10,11,12\}$ has $J=89.2$).
• Final answer: $\{1,2,3\}|\{10,11,12\}$.

Key lesson

One divisive step can be a 2-means call.

Example 2 — Easy · DBSCAN by hand

• Problem: $S=\{1,2,3,4,10,11,12,25\}$, $ϵ=1.5$, $r=3$. Compute $|H_i|$, the core points and the clusters.
• Asked: DBSCAN output.
• Concept: The lecture’s algorithm.
• Approach: Count neighbours within $1.5$ (including self).
• Solution: $|H|$: $1:2$; $2:3$ $\{1,2,3\}$; $3:3$ $\{2,3,4\}$; $4:2$; $10:2$; $11:3$ $\{10,11,12\}$; $12:2$; $25:1$. Cores ($\ge 3$): $2,3,11$. $H_2\cap H_3=\{2,3\}\ne \varnothing$ ⇒ merge into $\{1,2,3,4\}$. $H_{11}=\{10,11,12\}$ alone. Point $25$ is in no neighbourhood ⇒ noise.
• Final answer: Clusters $\{1,2,3,4\}$ and $\{10,11,12\}$; noise $\{25\}$.

Python helper and check

db = lambda pts, eps, r: DBSCAN(eps=eps, min_samples=r).fit(np.array(pts, float)[:, None]).labels_   # -1 = noise
print(db([1, 2, 3, 4, 10, 11, 12, 25], 1.5, 3))          # [0 0 0 0 1 1 1 -1]

Key lesson

Border points $1,4,10,12$ join through cores.

Example 3 — Moderate · A bridge between two blobs

• Problem: Points $A=\{0,0.5,1,1.5,2\}$, bridge $\{3.2,4,4.8\}$, $B=\{6,6.5,7,7.5,8\}$, $ϵ=0.9$, $r=3$. Output?
• Asked: Clusters.
• Concept: Core / neighbourhood merging.
• Approach: Neighbour counts.
• Solution: $|H|$: $0:2,0.5:3,1:3,1.5:3,2:2$; $3.2:2$; $4:3$ $\{3.2,4,4.8\}$; $4.8:2$; and symmetric for $B$. Cores: $0.5,1,1.5$; $4$; $6.5,7,7.5$. $H_{0.5},H_1,H_{1.5}$ overlap pairwise ⇒ one cluster $\{0,\dots ,2\}$; $H_4$ stands alone ⇒ $\{3.2,4,4.8\}$; $B$ likewise. No noise.
• Final answer: Three clusters: $A$, bridge, $B$.

Python check

S3 = [0, .5, 1, 1.5, 2, 3.2, 4, 4.8, 6, 6.5, 7, 7.5, 8]
print(db(S3, .9, 3))                                     # [0 0 0 0 0 1 1 1 2 2 2 2 2]

Key lesson

The bridge is separated from the blobs because the gaps ($1.2$ and $1.2$) exceed $ϵ$.

Example 4 — Hard · Parameter sensitivity

• Problem: Same points. (a) $ϵ=0.6,r=3$; (b) $ϵ=1.3,r=3$. Outputs?
• Asked: Parameter sensitivity.
• Concept: Choosing $ϵ$.
• Approach: Recount.
• Solution: (a) Bridge points have no neighbour within $0.6$ ($|H|=1$ each) ⇒ not core, in no core neighbourhood ⇒ noise; clusters $A$ and $B$ remain. (b) $ϵ=1.3$: $|H_2|=\{1,1.5,2,3.2\}$ and $|H_{3.2}|=\{2,3.2,4\}$ both $\ge 3$ and intersect ⇒ $A$ merges with the bridge; similarly bridge with $B$ ⇒ everything becomes one cluster.
• Final answer: (a) 2 clusters + 3 noise points; (b) 1 cluster.

Python check

print(db(S3, .6, 3)); print(db(S3, 1.3, 3))              # [0 0 0 0 0 -1 -1 -1 1 1 1 1 1]   all 0

Key lesson

$ϵ$ controls whether sparse bridges are noise, separate clusters or merged.

Example 5 — Very Hard · Why DBSCAN resists chaining

• Problem: Explain, using this data, why DBSCAN avoids the chaining that plagues single linkage, and when it would still chain.
• Asked: Argument.
• Concept: Density vs distance.
• Approach: Compare merge conditions.
• Solution: Single linkage merges $A$ and the bridge once the gap $1.2$ is the smallest remaining distance, regardless of how thin the bridge is. DBSCAN merges two neighbourhoods only if both are dense ($\ge r$ points) and overlap. With $ϵ=0.9$ the gap $1.2$ exceeds $ϵ$, so nothing connects; even if a single point lay in the gap, its $|H|$ would be small (1–2), failing $|H|\ge r$. It chains only when the bridge itself is dense (as with $ϵ=1.3$).
• Final answer: DBSCAN requires density, not just proximity; a dense bridge defeats it.

Key lesson

The pair $(ϵ,r)$ encodes “how dense is a cluster”.

Common mistakes

• Forgetting the point itself in $H_i$.
• Counting border points as cores.

Exam traps

• Noise = points not in any merged neighbourhood.
• No $k$ needed, but $ϵ$ and $r$ are.

Connections: C39 (chaining), C35 (non-convex clusters).

Mastery checklist

• Run DBSCAN by hand.
• Contrast with single linkage.
• Explain the effect of $ϵ$ and $r$.

---

C41. Cluster Evaluation I: the F-measure

Intuition

If class labels exist, ask how well each class is recovered by some cluster: use the recall / precision of its best-matching cluster, then weight by class size.

Formal definition

$R$ = categories ($I$ of them), $S$ = clusters ($J$), $N$ points; $r_i$ = size of category $i$, $s_j$ = size of cluster $j$, $s_{ij}$ = overlap. ${\text{Recall}}_{ij}=\frac{s_{ij}}{r_i},{\text{Precision}}_{ij}=\frac{s_{ij}}{s_j},F_{ij}=\frac{2{\text{Recall}}_{ij}{\text{Precision}}_{ij}}{{\text{Recall}}_{ij}+{\text{Precision}}_{ij}}(F_{ij}=0\text{ if }{s}_{ij}=0),$ $F_i={\max }_j{F}_{ij},F={\sum }_{i=1}^I\frac{r_i}{N}{F}_i.$ Larger is better; $F\in [0,1]$.

Key insights

• Same formula as C11 with “category” = positive class and “cluster” = predicted group.
• Max over clusters: each category is matched to its best cluster (a cluster may be matched by several categories).
• Weakness: a single big cluster gets a high $F$ (Example 5).

Worked data used in Examples 2–4 (and C42)

$N=100$ customers, three known segments $R_1,R_2,R_3$ and three discovered clusters $S_1,S_2,S_3$ (rows = categories, columns = clusters): $\begin{array}{ccccc}& S_1& S_2& S_3& r_i\\ R_1& 35& 5& 0& 40\\ R_2& 8& 25& 2& 35\\ R_3& 2& 0& 23& 25\\ s_j& 45& 30& 25& 100\end{array}$

Worked examples

Example 1 — Very Easy · Recall and precision of one cell

• Problem: Category with $r_i=40$ members; cluster with $s_j=45$; overlap $s_{ij}=35$. Recall, precision?
• Asked: $R,P$.
• Concept: Definitions.
• Approach: Divide.
• Solution: Recall $=35/40=0.875$; precision $=35/45=0.7778$.
• Final answer: $0.875,0.778$.

Key lesson

Recall divides by the category size, precision by the cluster size.

Example 2 — Easy · F for two cells

• Problem: $F_{ij}$ for ($R_1,S_1$) and ($R_1,S_2$).
• Asked: Two $F$ values.
• Concept: $F_{ij}$.
• Approach: Harmonic mean.
• Solution: $(R_1,S_1)$: $\frac{2(0.875)(0.7778)}{0.875+0.7778}=0.8235$. $(R_1,S_2)$: $R=0.125$, $P=0.1667$, $F=0.1429$.
• Final answer: $0.8235$ and $0.1429$.

Key lesson

Only the best-matching cluster counts toward $F_i$.

Example 3 — Moderate · Best F per category

• Problem: Compute $F_1,F_2,F_3$.
• Asked: Category-wise best $F$.
• Concept: $F_i={\max }_j{F}_{ij}$.
• Approach: Compute the full $F_{ij}$ matrix.
• Solution:

	$S_1$	$S_2$	$S_3$	$F_i$
$R_1$	0.8235	0.1429	0	0.8235
$R_2$	0.2000	0.7692	0.0667	0.7692
$R_3$	0.0571	0	0.9200	0.9200

• Final answer: $(0.8235,0.7692,0.92)$.

Key lesson

Category 3 is recovered best.

Example 4 — Hard · Overall F, and merging two clusters

• Problem: The overall $F$ for the table, and how it changes if $S_2$ and $S_3$ are merged.
• Asked: $F$ and $F^{\prime }$.
• Concept: Weighted average; merging clusters.
• Approach: $F=\sum \frac{r_i}{N}{F}_i$.
• Solution: $F=0.4(0.8235)+0.35(0.7692)+0.25(0.92)=0.8286$. Merge $S_2\cup S_3$ ($s=55$): overlaps $R_1:5$, $R_2:27$, $R_3:23$. $F_1$ stays $0.8235$ (via $S_1$). $R_2$ vs merged: $R=0.7714,P=0.4909\Rightarrow F=0.6$ ⇒ $F_2=0.6$. $R_3$: $R=0.92,P=0.4182\Rightarrow F=0.575$ ⇒ $F_3=0.575$. $F^{\prime }=0.4(0.8235)+0.35(0.6)+0.25(0.575)=0.6832$.
• Final answer: $F=0.829$; after merging $F^{\prime }=0.683$.

Python check

T = [[35, 5, 0], [8, 25, 2], [2, 0, 23]]
print(cluster_F(T))                                      # ([0.8235 0.7692 0.92 ], 0.8286)
print(cluster_F([[35, 5], [8, 27], [2, 23]]))            # ([0.8235 0.6 0.575], 0.6832)   S2 ∪ S3 merged

Key lesson

Merging clusters lowers precision, hence $F$.

Example 5 — Very Hard · Degenerate clusterings

• Problem: Two categories of 50 points each. Compute $F$ for (a) perfect clustering, (b) one cluster containing everything, (c) $N=100$ singleton clusters. Comment.
• Asked: Three $F$ values.
• Concept: Degenerate clusterings.
• Approach: Per-category best match.
• Solution: (a) $R=P=1$ ⇒ $F=1$. (b) $s_j=100$, $s_{ij}=50$: $R=1$, $P=0.5$, $F_i=0.667$ ⇒ $F=0.667$. (c) Best cluster is a singleton: $R=\frac{1}{50}$, $P=1$, $F_i=\frac{2}{51}=0.0392$ ⇒ $F=0.0392$.
• Final answer: $1$, $0.667$, $0.039$.

Python check

print(cluster_F([[50, 0], [0, 50]])[1], cluster_F([[50], [50]])[1], 2 / 51)   # 1.0  0.6667  0.0392

Key lesson

The trivial one-cluster solution scores surprisingly high ($0.667$); F rewards recall too generously — compare with the number of clusters and use NMI (C42) as a complement.

Common mistakes

• Averaging $F_{ij}$ over all clusters instead of taking the max.
• Weighting by cluster size instead of category size.

Exam traps

• $F={\sum }_i\frac{r_i}{N}{F}_i$ (category weights).
• $F_{ij}=0$ when $s_{ij}=0$.

Connections: C11, C42.

Mastery checklist

• Compute $F_{ij},F_i,F$.
• Explain the max over clusters.
• State the one-cluster weakness.

---

C42. Cluster Evaluation II: Normalised Mutual Information (NMI)

Intuition

Knowing the cluster of a point should tell you something about its category. Mutual information measures how many bits the cluster reveals about the category; dividing by the entropies puts it on a $[0,1]$ scale.

Formal definition (Strehl & Ghosh)

$MI(R,S)={\sum }_{i=1}^I{\sum }_{j=1}^J\frac{s_{ij}}{N}\log \frac{N{s}_{ij}}{r_i{s}_j},E(R)=-{\sum }_i\frac{r_i}{N}\log \frac{r_i}{N},E(S)=-{\sum }_j\frac{s_j}{N}\log \frac{s_j}{N},$ $NMI(R,S)=\frac{MI(R,S)}{\sqrt{E(R)E(S)}}.$ Conventions: $0\log 0=0$; every category and cluster non-empty. The log base cancels in the ratio.

Properties

• $MI\ge 0$; $MI=0$ iff $R$ and $S$ are independent ($s_{ij}=r_i{s}_j/N$).
• $NMI(S,S)=1$; $NMI\in [0,1]$.
• Invariant to relabelling clusters.

Derivation: $MI=0$ under independence

If $s_{ij}=r_i{s}_j/N$ then $\frac{N{s}_{ij}}{r_i{s}_j}=1$, $\log 1=0$ for every term. ∎

Worked examples

Example 1 — Very Easy · A perfect clustering

• Problem: Perfect clustering of two balanced categories ($N=100$, $s_{11}=s_{22}=50$, off-diagonals 0). NMI?
• Asked: NMI.
• Concept: $MI=E$.
• Approach: Compute (log base 2).
• Solution: $MI=2\cdot \frac{50}{100}{\log }_2\frac{100\cdot 50}{50\cdot 50}=1$. $E(R)=E(S)=1$. $NMI=1$.
• Final answer: $1$.

Key lesson

A perfect clustering has NMI 1.

Example 2 — Easy · Clusters that carry no information

• Problem: Same categories but each cluster has 25 of each category ($s_{ij}=25$). NMI?
• Asked: NMI.
• Concept: Independence.
• Approach: $\frac{N{s}_{ij}}{r_i{s}_j}=\frac{100\cdot 25}{50\cdot 50}=1$.
• Solution: Every log term $=0$ ⇒ $MI=0$ ⇒ $NMI=0$.
• Final answer: $0$.

Python check

print(NMI([[50, 0], [0, 50]])[3], NMI([[25, 25], [25, 25]])[3])   # 1.0  0.0

Key lesson

Cluster labels carrying no information give NMI 0.

Example 3 — Moderate · A noisy 2 × 2

• Problem: $N=100$, table $\left(\begin{array}{cc}40& 10\\ 10& 40\end{array}\right)$ (rows categories, columns clusters). Compute NMI (bits).
• Asked: NMI.
• Concept: Full formula.
• Approach: $r=s=(50,50)$.
• Solution: Diagonal terms: $0.4{\log }_{2}1.6=0.4(0.6781)=0.2712$ (twice). Off-diagonal: $0.1{\log }_{2}0.4=0.1(-1.3219)=-0.1322$ (twice). $MI=0.2781$. $E(R)=E(S)=1$ ⇒ $NMI=0.2781$.
• Final answer: $NMI\approx 0.278$.

Python check

print(NMI([[40, 10], [10, 40]]))                         # (0.2781, 1.0, 1.0, 0.2781)

Key lesson

Off-diagonal terms contribute negatively (cells less populated than independence predicts).

Example 4 — Hard · NMI of the 3 × 3 table

• Problem: NMI (bits) for the $3\times 3$ table of C41.
• Asked: NMI.
• Concept: Full computation.
• Approach: Sum the non-empty terms; entropies of $r=(40,35,25)$, $s=(45,30,25)$.
• Solution: $E(R)=0.5288+0.5301+0.5=1.5589$. $E(S)=0.5184+0.5211+0.5=1.5395$. Terms of $MI$: $(1,1)$: $0.3358$; $(1,2)$: $-0.0632$; $(2,1)$: $-0.0782$; $(2,2)$: $0.3129$; $(2,3)$: $-0.0426$; $(3,1)$: $-0.0498$; $(3,3)$: $0.4323$. $MI=0.8472$ bits. $NMI=\frac{0.8472}{\sqrt{1.5589\times 1.5395}}=0.5469$.
• Final answer: $NMI\approx 0.547$ (alongside $F=0.829$).

Python check

print(NMI([[35, 5, 0], [8, 25, 2], [2, 0, 23]]))          # (0.8472, 1.5589, 1.5395, 0.5469)

Key lesson

Different criteria give different scales; NMI is stricter than F here.

Example 5 — Very Hard · Singleton clusters

• Problem: Two categories of 50. Show that placing every point in its own cluster ($J=N=100$) gives $NMI=\sqrt{E(R)/\log N}$ and evaluate it; then comment.
• Asked: Formula and value.
• Concept: Bias toward many clusters.
• Approach: If each cluster is a singleton, $s_j=1$ and the cluster determines the category.
• Solution: $s_{ij}=1$ for the unique category of the point. $MI={\sum }_i\frac{r_i}{N}\log \frac{N}{r_i}=E(R)$. $E(S)=\log N$. $NMI=\frac{E(R)}{\sqrt{E(R)\log N}}=\sqrt{\frac{E(R)}{\log N}}$. Here (bits) $E(R)=1$, ${\log }_{2}100=6.644$ ⇒ $NMI=\sqrt{0.1505}=0.388$.
• Final answer: $NMI=0.388$ for the meaningless singleton clustering.

Python check

print(np.sqrt(1 / np.log2(100)))                         # 0.388

Key lesson

NMI is not zero for over-clustering; read it together with the number of clusters (F, by contrast, punishes singletons heavily: $0.039$).

Common mistakes

• Forgetting $0\log 0=0$.
• Using $\log \frac{s_{ij}}{N}$ instead of $\log \frac{N{s}_{ij}}{r_i{s}_j}$.

Exam traps

• The denominator is $\sqrt{E(R)E(S)}$ (geometric mean).
• $NMI(S,S)=1$.

Connections: Entropy and information gain (C4), F-measure (C41).

Mastery checklist

• Compute $MI$ and NMI from a contingency table.
• Show $NMI=0$ under independence.
• Discuss NMI and F together.