Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Clustering and hierarchical clustering

Practical, exam-ready notes on clustering with emphasis on hierarchical (agglomerative and divisive) methods, linkage rules, dendrograms, 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 without labels, so an engineer uses it for data exploration, customer segmentation, anomaly detection, and preprocessing for supervised models. Hierarchical clustering builds a tree of clusters (a hierarchy) useful when you want a multi-scale view of structure or a dendrogram to choose the number of clusters.

Key ideas

  • Agglomerative (bottom-up) — Start with each object as a singleton cluster and repeatedly merge the closest two clusters until one cluster remains.

  • Divisive (top-down) — Start with all objects in one cluster and repeatedly split clusters (less common in practice).

  • Dendrogram — A tree diagram that shows the sequence of merges (or splits) and the distances (or dissimilarities) at which they occur. For an exam drawing: draw leaves (objects) on the x-axis, vertical lines showing merge heights equal to the linkage distance, and label merge heights on the vertical axis.

  • Distance measure — A function that quantifies dissimilarity between objects. Common choices (assume objects x, y in R^d):

    • Euclidean distance (L2): straight-line distance.
    • Manhattan distance (L1): sum of absolute coordinate differences.
    • Cosine distance: 1 minus cosine similarity (useful for high-dimensional direction-based data). Always state units (e.g. meters) if features have physical units; otherwise say unitless.
  • Linkage criterion — How to compute distance between clusters A and B from pairwise object distances. Common rules (A and B are clusters, x in A, y in B):

    • Single linkage — distance(A,B) = min_{x in A, y in B} dist(x,y). (Produces chaining; sensitive to noise.)
    • Complete linkage — distance(A,B) = max_{x in A, y in B} dist(x,y). (Produces compact clusters.)
    • Average linkage — distance(A,B) = average_{x in A, y in B} dist(x,y). Two versions: unweighted (UPGMA) or weighted (WPGMA). In UPGMA, distance is the average over all |A||B| pairs as written; in WPGMA, updates use equal cluster weights: for any other cluster X, d(A ∪ B, X) = (d(A, X) + d(B, X)) / 2.
    • Centroid linkage — distance(A,B) = dist(mu_A, mu_B), where mu is cluster centroid. Note: centroid linkage can produce inversions (non-monotonic dendrograms), where a later merge occurs at a lower height than an earlier one.
    • Ward's method — choose the merge that minimally increases total within-cluster sum-of-squares (SSE). This tends to create clusters with low variance and similar size.
  • Exact formula for Ward merge increase (commonly used in exams): if clusters A and B have sizes n_A and n_B and centroids mu_A and mu_B, then the increase in total within-cluster sum of squared deviations when merging A and B is delta(A,B) = (n_A * n_B) / (n_A + n_B) * ||mu_A - mu_B||^2. This formula assumes SSE defined as sum over points of squared Euclidean distance to cluster centroid and standard Euclidean geometry.

  • Algorithmic steps for agglomerative hierarchical clustering (exam-style):

    1. Start with each item i as its own cluster C_i.
    2. Compute the pairwise cluster distance matrix D using chosen linkage.
    3. Find clusters A, B with smallest D(A,B). Record merge at height D(A,B).
    4. Merge A and B into new cluster C = A ∪ B.
    5. Update distances between C and all other clusters according to the linkage formula.
    6. Repeat steps 3–5 until all items are merged into one cluster. Output the recorded merges and heights to draw a dendrogram.
  • Complexity and practical notes: naive agglomerative implementation is O(n^3) time and O(n^2) memory because after each merge you update an O(n^2) distance matrix and searching for closest pair costs O(n^2) if done naively. There are optimized algorithms (e.g., using priority queues, nearest-neighbor chains, or special cases like single-linkage with MST) that can reduce cost; practical libraries implement O(n^2) or O(n^2 log n) variants for many linkages.

  • Choice guidance: use single-linkage to find elongated clusters (but beware chaining), complete-linkage or average-linkage for compact clusters, Ward for compact spherical clusters with similar sizes. Always scale features before clustering if units differ (e.g., standardize to zero mean and unit variance).

Formulas

dist_E(x,y) = sqrt( sum_{i=1..d} (x_i - y_i)^2 ) — Euclidean distance between vectors x and y; symbol units: same as feature units (e.g., meters). Applies to real-valued features.

dist_L1(x,y) = sum_{i=1..d} |x_i - y_i| — Manhattan (L1) distance; units: same as feature units.

cosine_dist(x,y) = 1 - ( x·y / (||x|| ||y||) ) — cosine distance; unitless. Applies when vector direction matters more than magnitude.

single_link(A,B) = min_{x in A, y in B} dist(x,y) — single linkage distance; unit: same as dist.

complete_link(A,B) = max_{x in A, y in B} dist(x,y) — complete linkage distance; unit: same as dist.

avg_link(A,B) = (1/(|A||B|)) sum_{x in A} sum_{y in B} dist(x,y) — average linkage; unit: same as dist.

mu_A = (1/|A|) sum_{x in A} x — centroid (mean) of cluster A; unit: same as feature units.

Ward_delta(A,B) = (|A| * |B|) / (|A| + |B|) * ||mu_A - mu_B||^2 — increase in SSE when merging A and B under Ward's method; units: (feature unit)^2.

SSE = sum_{clusters C} sum_{x in C} ||x - mu_C||^2 — total within-cluster sum of squared errors; units: (feature unit)^2.

Worked examples

Example 1 — Agglomerative single-linkage with 1-D data (exam numerical): Data (units: unitless scores): A=1, B=2, C=5, D=8, E=10. Step 0: pairwise absolute distances (matrix, only upper triangle):

  • d(A,B)=1, d(A,C)=4, d(A,D)=7, d(A,E)=9
  • d(B,C)=3, d(B,D)=6, d(B,E)=8
  • d(C,D)=3, d(C,E)=5
  • d(D,E)=2 Merge steps (single linkage uses min pairwise distance between clusters):
  1. Smallest distance = 1 between A and B. Merge -> cluster AB; record height 1.
  2. Next smallest distance = 2 between D and E. Merge -> cluster DE; record height 2.
  3. Now clusters: AB, C, DE. Distances (single link):
    • d(AB,C) = min(d(A,C)=4, d(B,C)=3) = 3
    • d(AB,DE) = min(d(A,D)=7,d(A,E)=9,d(B,D)=6,d(B,E)=8) = 6
    • d(C,DE) = min(d(C,D)=3,d(C,E)=5) = 3 Smallest = 3. Suppose we merge AB with C (tie with C-DE but choose AB-C). Merge -> ABC; height 3.
  4. Finally merge ABC with DE. Single-link distance d(ABC,DE) = min distances = min(d(C,D)=3, others >=3) = 3. Final merge height 3. Dendrogram heights (in order): 1 (A+B), 2 (D+E), 3 (AB+C), 3 (ABC+DE). If examiner asks to cut the dendrogram at height 2.5, clusters would be {A,B}, {C}, and {D,E}. Final answer: bold cluster split at height 2.5 is {A,B}, {C}, and {D,E}.

Example 2 — Ward's method (2-D points on x-axis) — show formula use: Points (meters): P1=(0,0), P2=(1,0), P3=(4,0), P4=(5,0). Ward's pairwise merge increase for two singletons of distance d is 0.5 * d^2 (since n_A=n_B=1):

  • Delta(P1,P2) = 0.5 * (1)^2 = 0.5 m^2
  • Delta(P3,P4) = 0.5 * (1)^2 = 0.5 m^2
  • Delta(P2,P3) = 0.5 * (3)^2 = 4.5 m^2 Minimum merges are P1+P2 and P3+P4 (tie). Merge P1+P2 first. After merging A={P1,P2} (n_A=2, mu_A=(0.5,0)), to evaluate merging A with P3: use Ward_delta formula Delta(A,P3) = (2*1)/(2+1) * ||mu_A - mu_{P3}||^2 = (2/3) * (3.5)^2 = 0.6667 * 12.25 = 8.1667 m^2. So the next best merge is P3+P4 (0.5 m^2). After those merges, final merge of the two clusters will have larger delta. The algorithm produces clusters {P1,P2} and {P3,P4} first, which matches intuition for compact groups. Final answer: first merges are (P1,P2) and (P3,P4) at delta 0.5 m^2.

Example 3 — Short theoretical model answer (typical long question): Question: "Explain single vs complete linkage and draw dendrograms for a set of four points forming a line. Mention chaining and compactness." Model answer (concise points to include for full marks): define single and complete linkage, illustrate with 4 collinear points x1<x2<x3<x4 and compute merge order: single-link yields chaining that can join x1 with x2 then x2 with x3 etc., producing long-chain clusters; draw dendrogram with small merge heights between neighbors and a final long jump; complete-link yields merges that prefer compact groups (typically merges the most compact adjacent pairs, e.g., (x1,x2) and (x3,x4) when spacings are similar), draw dendrogram with more balanced heights. Conclude single-link sensitive to noise (outliers connect clusters) and complete-link produces tighter clusters but can split natural elongated clusters.

Common mistakes

  • Confusing single-link and complete-link formulas and their qualitative effects (chaining vs compactness).
  • Miscomputing Ward's delta by leaving out the factor (n_A * n_B)/(n_A + n_B).
  • When drawing dendrograms, plotting merge heights incorrectly (heights must equal the linkage distance used).
  • Stating complexity as O(n^2) without specifying the algorithm or linkage; naive is O(n^3) while optimized cases differ.

For your exam

Types of questions:

  • Definitions and short notes: define clustering, hierarchical methods, dendrogram, linkage rules, centroid, Ward's method.
  • Derivations: derive Ward's merge-increase formula from SSE definition, show computation of average-link or centroid updates.
  • Numericals: compute distance matrix and give merge sequence and dendrogram for small datasets (1–6 points). Show units and intermediate steps.
  • Diagrams: draw dendrogram and label heights; draw cluster partitions for a chosen cut height.
  • Short answers: discuss pros/cons of linkage choices, complexity and scaling, when to use hierarchical clustering vs K-means or DBSCAN.

What a full-marks answer includes:

  • Clear definitions with bold terms, stated distance metric, and units.
  • Correct step-by-step merges with distance updates and numbers carried through.
  • If asked, proper dendrogram drawn with labeled axes and merge heights (describe leaves in order and vertical merge lines at heights equal to recorded distances).
  • For derivations, start from the SSE definition and show algebraic steps to the Ward formula, mentioning assumptions (Euclidean norm, SSE definition).

Quick check

  1. What is the linkage rule that picks min_{x in A, y in B} dist(x,y)?
  2. Give the Ward delta formula for merging clusters A and B.
  3. Why should you standardize features before hierarchical clustering when scales differ? Answers: 1. Single linkage. 2. (|A|*|B|)/(|A|+|B|) * ||mu_A - mu_B||^2. 3. Because distance measures are scale-sensitive; without standardization features with larger scale dominate distances.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?