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.

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).

---

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. 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, 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

• 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

• 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$: $0.5+0.5=1$; $\mu =8$: $|3-8|+|10-8|+|11-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

• 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; others choose side.
• Solution: Fix point $1$ in cluster A; each other point is in A or B: $2^3=8$ assignments; exclude “all in A” (B empty) ⇒ $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$.
• Key lesson: The search space grows super-exponentially.

Example 4 — Hard

• 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: Optimum of $L$ is convex-shaped.
• Approach: Enumerate the $2^4-1=15$ partitions.
• Solution: Desired: $\{-10,10\}$: $\mu =0$ ⇒ $10+10=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\}$ and $\{10\}$ (centroids $-2.5$ and $10$: $7.5+2+2.5+3=15$). Next best values are $20.5,20.5,20.83$. The desired partition ($21$) is not even in the top three.
• Final answer: Desired $L=21$; optimal $L=15$ with interval clusters.
• Key lesson: A non-convex cluster (outer points surrounding the inner ones) can never be an optimum of this criterion.

Example 5 — Very Hard

• 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 $=\frac{1}{4}[(1,0)+(-1,0)+(0,1)+(0,-1)]=(0,0)$; outer mean $=(0,0)$. Equal centroids ⇒ the bisector $\Vert \vec{X}-{\vec{\mu }}_1\Vert =\Vert \vec{X}-{\vec{\mu }}_2\Vert$ is empty/undefined — 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)$ ⇒ $1.5+1.5=3$; right (6 points) $\mu =(\frac{5}{6},0)$: $d(1,0)=0.1667$; $d(4,0)=3.1667$; $d(0,\pm 1)=\sqrt{0.6944+1}=1.3017$ each; $d(0,\pm 4)=\sqrt{0.6944+16}=4.0858$ each; sum $=0.1667+3.1667+2.6034+8.1716=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$.
• 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 need for $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.

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

• 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$; similarly $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

• 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+(5.6^2+4.6^2+2.4^2+3.4^2+4.4^2)=31.36+21.16+5.76+11.56+19.36=89.2$. Assign 2: $1\to C_1$; $2$: $|2-1|=1<5.6\to C_1$; $3$: $2<4.6\to C_1$; $10$: $9>2.4\to C_2$; $11,12\to C_2$. Update 2: ${\mu }_1=2$, ${\mu }_2=11$; $J=(1+0+1)+(1+0+1)=4$. Assign 3: unchanged ⇒ stop.
• Final answer: $\{1,2,3\},\{10,11,12\}$; $J:89.2\to 4.0$.
• Key lesson: $J$ decreases monotonically.

Example 3 — Moderate

• 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)=\sqrt{9+9}=4.24$ ⇒ $C_1$. $C$: $d(C,A)=\sqrt{9+4}=3.61$, $d(C,D)=\sqrt{1+1}=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: $B$ to ${\mu }_1$: $0.5$; to ${\mu }_2$: $\sqrt{6.25+6.25}=3.54$ ✓; $C$: to ${\mu }_2$ $\sqrt{0.25+0.25}=0.71$ vs to ${\mu }_1$ $\sqrt{6.25+4}=3.2$ ✓. No change. $J=2(0.25)+2(0.5)=0.5+1.0=1.5$.
• Final answer: $\{A,B\},\{C,D\}$, $\mu =(1.5,1),(4.5,3.5)$, $J=1.5$.
• Key lesson: Converged when centroids stop moving.

Example 4 — Hard

• 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$ (nearest centroid $18$: distances $0,6,7,9$ vs to $4$: $14,\dots$). Update: $\mu =(2,4,23.5)$ — unchanged on re-assignment ⇒ converged. $J=0+0+[(18-23.5{)}^2+(24-23.5{)}^2+(25-23.5{)}^2+(27-23.5{)}^2]=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$.
• Key lesson: k-means converges, but not necessarily to the best answer — run several seeds.

Example 5 — Very Hard

• 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 (derivative above) ⇒ $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$ (after first update) then $4.0$ ✓ decreasing, then unchanged.
• 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 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: sample hierarchical cost $O((kn)\cdot )$ small; repeated runs give different partitions; poor if the sample is unrepresentative; still needs $k$.

Worked examples

Example 1 — Very Easy

• 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

• 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

• 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 largest.
• Solution: 2-means on all 8: best contiguous split $\{1,2,3,10,11,12\},\{30,31\}$ ($J=125.5+0.5=126$; the competing split $\{1,2,3\},\{10,11,12,30,31\}$ has $J=2+458.8=460.8$). Largest cluster = the six-point one ⇒ 2-means: $\{1,2,3\},\{10,11,12\}$ ($J=2+2$). Three clusters now.
• Final answer: $\{1,2,3\},\{10,11,12\},\{30,31\}$.
• Key lesson: Splitting the largest cluster recovers the true structure here.

Example 4 — Hard

• 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 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=(2.25+0.25+0.25+2.25)+(2.25+0.25+0.25+2.25)=10$.
• Final answer: $\{1,2,3,4\},\{20,21,22,23\}$, $J=10$.
• Key lesson: Seeds from a hierarchical pass avoid pathological starts.

Example 5 — Very Hard

• 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: contiguous options: $\{2,4\}|\{18,24,25,27\}$: $2+45=47$; $\{2,4,18\}|\{24,25,27\}$: $152+4.667=156.7$; others larger ⇒ choose $\{2,4\},\{18,24,25,27\}$. Largest = the 4-point cluster: splits $\{18\}|\{24,25,27\}$: $0+4.667$; $\{18,24\}|\{25,27\}$: $18+2=20$ ⇒ choose the first. Final: $\{2,4\},\{18\},\{24,25,27\}$: $J=2+0+4.667=6.667$ (global optimum). Plain k-means from the unlucky seeds: $J=45$.
• Final answer: Bisecting $6.667$ vs plain k-means $45$.
• 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.

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

• 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

• 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:\frac{0+1+2+99}{4}=25.5$; $2:\frac{1+0+1+98}{4}=25$; $3:\frac{2+1+0+97}{4}=25$; $100:\frac{99+98+97}{4}=73.5$ ⇒ tie between $2$ and $3$.
• Final answer: Minimax: $3$; average: $2$ or $3$.
• Key lesson: Definitions can disagree on ties; state which you use.

Example 3 — Moderate

• 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 $=\frac{233}{4}=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

• 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

• 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$ (e.g. $3$: $2$ vs $7$ ✓), $\{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 $=(1+0+1)+(1+0+1)+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

• Medoid is a data point; 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.

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.

Worked examples

Example 1 — Very Easy

• 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

• Problem: Points $0,1,4,6,10$. Give the merge sequence and heights for single, complete, average.
• Asked: Three dendrograms.
• Concept: Algorithm.
• Approach: Merge closest pair each time.
• Solution: All three first merge $\{0,1\}$ (height $1$), then $\{4,6\}$ (height $2$). Next: single: $\{0,1\}$–$\{4,6\}=\min (3,\dots )=3$; complete: $\max =6$; average: $\frac{4+6+3+5}{4}=4.5$. Then $10$ joins $\{0,1,4,6\}$: single $=4$ ($6$–$10$); 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$.
• Key lesson: Same merge order here, different heights.

Example 3 — Moderate

• Problem: Points $1,2,4,8,16$ (doubling gaps). 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,\max (3,2)=3,\max (7,6,4)=7,15$. Average: $1,\frac{3+2}{2}=2.5,\frac{7+6+4}{3}=5.667,\frac{15+14+12+8}{4}=12.25$.
• Final answer: Single $1,2,4,8$; complete $1,3,7,15$; average $1,2.5,5.67,12.25$.
• Key lesson: Complete-link heights are the cluster diameters.

Example 4 — Hard

• 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: merge $(7,9)$ at 2; $(30,35)$ at 5; $24$ joins $\{30,35\}$ at 6 ⇒ 3 clusters $\{7,9\},\{16\},\{24,30,35\}$. Complete: $(7,9)$ at 2; $(30,35)$ at 5; next smallest complete distance: $d(16,24)=8$ (vs $d(16,\{7,9\})=9$, $d(24,\{30,35\})=11$) ⇒ $\{7,9\},\{16,24\},\{30,35\}$. Average: $(7,9)$ at 2; $(30,35)$ at 5; $d(16,\{7,9\})=\frac{9+7}{2}=8$ vs $d(24,\{30,35\})=\frac{6+11}{2}=8.5$ ⇒ merge $16$ with $\{7,9\}$ ⇒ $\{7,9,16\},\{24\},\{30,35\}$.
• Final answer: Three different partitions.
• Key lesson: The linkage is the assumption about what a cluster looks like.

Example 5 — Very Hard

• 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: merges at height $1$ build $\{0,1,2\}$ and $\{10,11,12\}$; then every bridge gap is $2$ (2–4, 4–6, 6–8, 8–10), so all remaining merges happen at height 2 — the dendrogram cannot tell the bridge from the blobs; a 3-cluster cut (after 6 merges) depends on tie-breaking and may give $\{0,1,2,4,6\},\{8\},\{10,11,12\}$ — the bridge is absorbed into a blob. Complete: merge heights in order: $1$ ($\{0,1\}$), $1$ ($\{10,11\}$), $2$ ($\{0,1,2\}$), $2$ ($\{4,6\}$), $2$ ($\{10,11,12\}$), $4$ (adds $8$ to $\{4,6\}$), $8$ (joins $\{0,1,2\}$ with $\{4,6,8\}$), $12$ (final merge). A 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.
• 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 (must recompute/update).
• 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. This finds arbitrarily shaped clusters and does not need $k$.

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

• Problem: Divisive step: 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

• 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: Lecture’s algorithm.
• Approach: Count neighbours within $1.5$ (including self).
• Solution: $|H|$: $1:2$ $\{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 $\{1,2,3,4\}$. $H_{11}$ alone $=\{10,11,12\}$. Point $25$ is in no neighbourhood ⇒ noise.
• Final answer: Clusters $\{1,2,3,4\}$ and $\{10,11,12\}$; noise $\{25\}$.
• Key lesson: Border points $1,4,10,12$ join through cores.

Example 3 — Moderate

• 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$ $\{3.2,4\}$; $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,..,2\}$; $H_4$ stands alone ⇒ $\{3.2,4,4.8\}$; $B$ likewise. No noise.
• Final answer: Three clusters: $A$, bridge, $B$.
• Key lesson: The bridge is separated from the blobs because the gaps ($1.2$ and $1.2$) exceed $ϵ$.

Example 4 — Hard

• 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.
• Key lesson: $ϵ$ controls whether sparse bridges are noise, separate clusters or merged.

Example 5 — Very Hard

• 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, $|H|$ of that point would be small (1–2), failing $|H|\ge r$. It chains only when the bridge itself is dense (as with $ϵ=1.3$: points of the bridge then have $\ge 3$ neighbours and neighbourhoods overlap with those of $A$).
• 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

$N=100$. Contingency table (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

• 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

• 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}=\frac{1.3611}{1.6528}=0.8235$. $(R_1,S_2)$: $R=\frac{5}{40}=0.125$, $P=\frac{5}{30}=0.1667$, $F=\frac{2(0.125)(0.1667)}{0.2917}=0.1429$.
• Final answer: $0.8235$ and $0.1429$.
• Key lesson: Only the best-matching cluster counts toward $F_i$.

Example 3 — Moderate

• 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: $R_1$: $F_{11}=0.8235$, $F_{12}=0.1429$, $F_{13}=0$ ⇒ $F_1=0.8235$. $R_2$ ($r=35$): $F_{21}$: $R=\frac{8}{35}=0.2286,P=\frac{8}{45}=0.1778\Rightarrow 0.2$; $F_{22}$: $R=\frac{25}{35}=0.7143,P=\frac{25}{30}=0.8333\Rightarrow \frac{2(0.5952)}{1.5476}=0.7692$; $F_{23}$: $R=0.0571,P=0.08\Rightarrow 0.0667$ ⇒ $F_2=0.7692$. $R_3$ ($r=25$): $F_{33}$: $R=0.92,P=0.92\Rightarrow 0.92$; $F_{31}=0.0571$ ⇒ $F_3=0.92$.
• Final answer: $(0.8235,0.7692,0.92)$.
• Key lesson: Category 3 is recovered best.

Example 4 — Hard

• 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.3294+0.2692+0.2300=0.8286$. Merge $S_2\cup S_3$ ($s=55$): overlaps $R_1:5$, $R_2:27$, $R_3:23$. $R_1$: vs $S_1$: $0.8235$; vs merged: $R=\frac{5}{40},P=\frac{5}{55}$ ⇒ $F=0.1053$ ⇒ $F_1=0.8235$. $R_2$: vs merged: $R=\frac{27}{35}=0.7714,P=\frac{27}{55}=0.4909\Rightarrow F=0.6$; vs $S_1$: $0.2$ ⇒ $F_2=0.6$. $R_3$: vs merged: $R=0.92,P=\frac{23}{55}=0.4182\Rightarrow F=0.575$; vs $S_1$: $0.0571$ ⇒ $F_3=0.575$. $F^{\prime }=0.4(0.8235)+0.35(0.6)+0.25(0.575)=0.3294+0.21+0.14375=0.6832$.
• Final answer: $F=0.829$; after merging $F^{\prime }=0.683$.
• Key lesson: Merging clusters lowers precision, hence $F$.

Example 5 — Very Hard

• 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_i=1$ ⇒ $F=1$. (b) $s_j=100$, $s_{ij}=50$: $R=1$, $P=0.5$, $F_i=\frac{2(1)(0.5)}{1.5}=0.667$ ⇒ $F=0.667$. (c) best cluster is a singleton: $s_{ij}=1$: $R=\frac{1}{50}$, $P=1$, $F_i=\frac{2/50}{1/50+1}=\frac{2}{51}=0.0392$ ⇒ $F=0.0392$.
• Final answer: $1$, $0.667$, $0.039$.
• 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

• 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}=2(0.5){\log }_{2}2=1$. $E(R)=E(S)=1$. $NMI=1/\sqrt{1\cdot 1}=1$.
• Final answer: $1$.
• Key lesson: A perfect clustering has NMI 1.

Example 2 — Easy

• 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$.
• Key lesson: Cluster labels carrying no information give NMI 0.

Example 3 — Moderate

• 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: $\frac{40}{100}{\log }_2\frac{100\cdot 40}{50\cdot 50}=0.4{\log }_{2}1.6=0.4(0.6781)=0.2712$ (twice). Off-diagonal: $\frac{10}{100}{\log }_2\frac{100\cdot 10}{2500}=0.1{\log }_{2}0.4=0.1(-1.3219)=-0.1322$ (twice). $MI=2(0.2712)+2(-0.1322)=0.2781$. $E(R)=E(S)=1$ ⇒ $NMI=0.2781$.
• Final answer: $NMI\approx 0.278$.
• Key lesson: Off-diagonal terms contribute negatively (cells less populated than independence predicts).

Example 4 — Hard

• Problem: NMI (bits) for the $3\times 3$ table of C41.
• Asked: NMI.
• Concept: Full computation.
• Approach: Sum the nine terms; entropies of $r=(40,35,25)$, $s=(45,30,25)$.
• Solution: $E(R)=-0.4{\log }_{2}0.4-0.35{\log }_{2}0.35-0.25{\log }_{2}0.25=0.5288+0.5301+0.5=1.5589$. $E(S)=-0.45{\log }_{2}0.45-0.30{\log }_{2}0.30-0.25{\log }_{2}0.25=0.5184+0.5211+0.5=1.5395$. $MI=\sum \frac{s_{ij}}{100}{\log }_2\frac{100s_{ij}}{r_i{s}_j}$: $(1,1)$: $0.35{\log }_2\frac{3500}{1800}=0.35(0.9594)=0.3358$; $(1,2)$: $0.05{\log }_2\frac{500}{1200}=0.05(-1.2630)=-0.0632$; $(2,1)$: $0.08{\log }_2\frac{800}{1575}=0.08(-0.9774)=-0.0782$; $(2,2)$: $0.25{\log }_2\frac{2500}{1050}=0.25(1.2515)=0.3129$; $(2,3)$: $0.02{\log }_2\frac{200}{875}=0.02(-2.1292)=-0.0426$; $(3,1)$: $0.02{\log }_2\frac{200}{1125}=0.02(-2.4919)=-0.0498$; $(3,3)$: $0.23{\log }_2\frac{2300}{625}=0.23(1.8795)=0.4323$. $MI=0.8472$ bits. $NMI=\frac{0.8472}{\sqrt{1.5589\times 1.5395}}=\frac{0.8472}{1.5492}=0.5469$.
• Final answer: $NMI\approx 0.547$ (alongside $F=0.829$).
• Key lesson: Different criteria give different scales; NMI is stricter than F here.

Example 5 — Very Hard

• 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 }_{\text{points}}\frac{1}{N}\log \frac{N\cdot 1}{r_i\cdot 1}={\sum }_i\frac{r_i}{N}\log \frac{N}{r_i}=E(R)$. $E(S)=-{\sum }_j\frac{1}{N}\log \frac{1}{N}=\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.
• Key lesson: NMI is not zero for over-clustering; use it with the number of clusters in mind (complements F, which penalises 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

• 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.