Unit 5 — Clustering Techniques

FORMULA

What makes a clustering good

Silhouette coefficient combines both, per point:

s(i) = (b(i) − a(i)) / max(a(i), b(i))

  a(i) = mean distance from i to the other points in ITS cluster
  b(i) = mean distance from i to the points of the NEAREST OTHER cluster

The mean silhouette over all points measures the whole clustering, and comparing it across values of k is the standard way to choose k.

Davies–Bouldin index — the average, over clusters, of the worst-case ratio of within-cluster scatter to between-cluster separation. Lower is better, which is the opposite of silhouette and a frequent source of confusion.

FORMULA

A full worked trace

Eight one-dimensional points: 2, 4, 10, 12, 3, 20, 30, 11, with k = 2 and initial centroids c₁ = 2, c₂ = 4.

Iteration 1 — assign

C1 = {2, 3}                      → new c₁ = 5/2       = 2.5
C2 = {4, 10, 12, 20, 30, 11}     → new c₂ = 87/6      = 14.5

Iteration 2 — assign with c₁ = 2.5, c₂ = 14.5

C1 = {2, 4, 3}              → new c₁ = 9/3   = 3.0
C2 = {10, 12, 20, 30, 11}   → new c₂ = 83/5  = 16.6

Iteration 3 — assign with c₁ = 3.0, c₂ = 16.6

Assignments are unchanged from iteration 2. The algorithm has converged.

Final: C1 = {2, 3, 4} with centroid 3.0
       C2 = {10, 11, 12, 20, 30} with centroid 16.6

WCSS = [(2−3)² + (3−3)² + (4−3)²]
     + [(10−16.6)² + (11−16.6)² + (12−16.6)² + (20−16.6)² + (30−16.6)²]
     = [1 + 0 + 1] + [43.56 + 31.36 + 21.16 + 11.56 + 179.56]
     = 2 + 287.2
     = 289.2

Notice that 30 is dragging c₂ upward — it contributes 179.56 of the 287.2, which is 62.5% of the total error from one of eight points. That is the outlier sensitivity of §5.3 in action.

FORMULA

Choosing k

The elbow method. Plot WCSS against k. WCSS always falls as k rises (at k = n it is zero), so you look for the elbow — the point after which the improvement flattens.

WCSS
   │╲
   │ ╲
   │  ╲
   │   ●───  ← elbow at k = 3
   │       ╲___
   │           ╲______
   └────────────────────► k
   1  2  3  4  5  6  7

The silhouette method is more objective: compute the mean silhouette for each k and take the maximum. The gap statistic compares WCSS against what a uniform random dataset would give.

No method is definitive. The elbow is often ambiguous, and the honest answer includes domain knowledge: if marketing can run four campaigns, k = 4.

FORMULA

Why the medoid is robust

Take the points 1, 2, 3, 4, 100.

Mean   = 110/5 = 22    ← lies in an empty region; no data anywhere near it
Median = 3             ← the medoid, a real point, in the middle of the mass

The mean of 22 is not close to any point in the data. This is exactly what happens to a K-Means centroid when a cluster contains an outlier — and it is why the medoid version resists it.

The trade-off is cost. Each PAM iteration evaluates k(n−k) possible swaps, each requiring a cost recomputation — quadratic in n, against K-Means's linear. CLARA applies PAM to samples, and CLARANS searches the swap space randomly, both to recover scalability.

FORMULA

Linkage criteria — "closest" means what?

Single linkage's chaining effect is its defining property, good and bad: it can follow a curved band of points that no other linkage would find, and it will also merge two well-separated clusters if a single stray point bridges them.

FORMULA

A worked dendrogram

Five points with this distance matrix:

Single linkage — merge the closest pair each time.

Step 1: the smallest entry is d(A,B) = 2. Merge → {A,B} at height 2.

New distances, taking the minimum to each remaining point:

d({A,B}, C) = min(6, 5) = 5
d({A,B}, D) = min(10, 9) = 9
d({A,B}, E) = min(9, 8) = 8

Step 2: smallest is d(D,E) = 3. Merge → {D,E} at height 3.

d({A,B}, {D,E}) = min(9, 8) = 8
d(C, {D,E})     = min(4, 5) = 4

Step 3: smallest is d(C, {D,E}) = 4. Merge → {C,D,E} at height 4.

d({A,B}, {C,D,E}) = min(5, 8) = 5

Step 4: merge everything at height 5.

height
  5 ┤        ┌────────────────────┐
  4 ┤        │           ┌────────┐│
  3 ┤        │           │   ┌───┐││
  2 ┤   ┌───┐│           │   │   │││
  0 ┴───A   B───────────C────D   E

Cutting the dendrogram at height 4.5 crosses two lines, giving {A,B} and {C,D,E} — two clusters. Cutting at 3.5 gives three: {A,B}, {C}, {D,E}.

Complete linkage on the same data would take the maximum at each merge: d({A,B},C) = max(6,5) = 6, and so on. The merge order happens to be the same here, but the merge heights are larger — a general property, since complete linkage always reports the farthest pair.

FORMULA

The two parameters and three point types

         ●   ← noise: sparse neighbourhood, not near any core

    ○ ○ ○ ○
  ○ ● ● ● ● ○      ● = core point
  ○ ● ● ● ● ○      ○ = border point (in a core point's neighbourhood,
    ○ ○ ○ ○              but not dense enough itself)

FORMULA

A worked example

Points on a line: 1, 2, 3, 8, 9, 10, 25, with ε = 2 and MinPts = 3.

Cluster 1 = {1, 2, 3}       (all mutually density-connected)
Cluster 2 = {8, 9, 10}
Noise     = {25}

K-Means with k = 2 would be forced to put 25 somewhere, dragging a centroid far from every real point. DBSCAN identifies it as noise and leaves it out — which is often the single most useful thing about the algorithm.

Change MinPts to 4 and every point becomes noise, since no neighbourhood holds four points. The parameters are that sensitive, which is DBSCAN's main practical difficulty.

FORMULA

DBSCAN versus K-Means

DBSCAN's failure case is varying density, and it is the exam answer: a single ε that is right for a dense cluster is too small for a sparse one, so the sparse cluster fragments into noise. OPTICS solves this by producing an ordering across a range of ε rather than one clustering.

Choosing the parameters: MinPts ≥ d + 1, commonly 2d; then plot the sorted distance from each point to its MinPts-th nearest neighbour (the k-distance graph) and take ε at the knee.

FORMULA

The Clustering Feature

Every sub-cluster is summarised by a triple:

CF = (N, LS, SS)

  N  = number of points
  LS = LINEAR SUM of the points     (a vector)   Σ xᵢ
  SS = SQUARE SUM of the points     (a scalar)   Σ ‖xᵢ‖²

From those three numbers alone you can compute the centroid, radius and diameter — without keeping any of the points:

centroid = LS / N
radius   = √( SS/N − ‖LS/N‖² )

That formula is the whole trick, and it is the same identity as the computational formula for variance in Statistical Foundations for Data Science: Var = E[X²] − (E[X])².

FORMULA

CF additivity

CF₁ + CF₂ = (N₁ + N₂,  LS₁ + LS₂,  SS₁ + SS₂)

Merging two sub-clusters is three additions. This is what makes BIRCH incremental and single-pass: a new point is a CF of (1, x, ‖x‖²), and absorbing it into a leaf is just addition.

Worked example. Points 2, 4, 6 in one dimension:

N  = 3
LS = 2 + 4 + 6           = 12
SS = 4 + 16 + 36         = 56

centroid = 12/3          = 4
radius   = √(56/3 − 4²)  = √(18.667 − 16) = √2.667 = 1.633

Add the point 8 — no need to revisit 2, 4, 6:

N = 4, LS = 20, SS = 120
centroid = 5
radius   = √(120/4 − 25) = √5 = 2.236

FORMULA

STIRR

Sieving Through Iterated Relational Reinforcement (Gibson, Kleinberg, Raghavan, 1998).

The idea: represent the data as a graph whose nodes are attribute values, then propagate weights between values that co-occur, until the weights stabilise. Values that reinforce each other end up sharing a sign or magnitude, and those groups are the clusters.

Each distinct attribute VALUE is a node with a weight.
A tuple is a hyperedge joining the values it contains.

repeat until the weights converge:
    for each node v:
        new weight(v) = Σ over tuples containing v of
                        (combining function of the OTHER nodes' weights)
    normalise the weight vector

The system is a set of weight vectors called basins. The principal basin carries the dominant structure; non-principal basins, especially their positive and negative components, separate the data into groups.

Its character: STIRR is a spectral method — it is effectively finding eigenvectors of a co-occurrence operator — and its output is not a hard partition. A human must interpret the weight groupings. That is both its distinctive feature and its practical drawback.

FORMULA

ROCK

RObust Clustering using linKs (Guha, Rastogi, Shim, 1999). The most examinable of the three because its central idea is concrete.

The idea: do not cluster on similarity between pairs. Cluster on the number of common neighbours, which ROCK calls links.

neighbours: p and q are neighbours if sim(p, q) ≥ θ
            (θ is a user threshold; sim is usually Jaccard)

link(p, q) = the NUMBER OF COMMON NEIGHBOURS of p and q

Why links beat pairwise similarity — this is the exam answer. Two market baskets {bread, butter} and {bread, jam} share only one item, so their Jaccard similarity is low (1/3). But if many other baskets are neighbours of both, they clearly belong together. Links capture that global evidence; pairwise similarity cannot see it.

The algorithm is agglomerative, maximising a goodness measure:

                    link(Cᵢ, Cⱼ)
g(Cᵢ, Cⱼ) = ─────────────────────────────────────────────
            (nᵢ+nⱼ)^(1+2f(θ)) − nᵢ^(1+2f(θ)) − nⱼ^(1+2f(θ))

with f(θ) = (1 − θ)/(1 + θ) for market-basket data. The denominator is the expected number of links if the clusters merged by chance, so the ratio measures how much the observed linkage exceeds chance — normalising away the bias toward merging large clusters.

Worked example. With θ = 0.5 and Jaccard similarity, are {a, b, c} and {a, b, d} neighbours?

Jaccard = |intersection| / |union| = |{a,b}| / |{a,b,c,d}| = 2/4 = 0.5 ≥ 0.5  ✓

Yes — just. And {a,b,c} versus {a,d,e}: Jaccard = 1/5 = 0.2 < 0.5, not neighbours. If both are nonetheless neighbours of many common baskets, ROCK may still merge them; single-link on Jaccard would not.

FORMULA

CACTUS

Clustering Categorical Data Using Summaries (Ganti, Gehrke, Ramakrishnan, 1999).

The idea: summarise the data so it fits in memory, then find clusters inside the summaries. Like BIRCH, it is a summarisation strategy — but for categorical data.

Strong connections. Two attribute values from different attributes are strongly connected if they co-occur significantly more often than expected under independence:

support(aᵢ, bⱼ)  >  α × expected support under independence

expected = (|aᵢ| / |A|) × (|bⱼ| / |B|) × N

That comparison against an independence baseline is exactly the lift idea from Unit 3 §3.2, applied to attribute values instead of items.

The three phases:

Its strengths: typically two data scans, works on summaries that fit in memory, and it can find clusters in subspaces — clusters defined by only some of the attributes, which matters in high dimensions.

Its weakness: the candidate-generation step can produce spurious clusters that phase 3 must discard, and the α threshold is another parameter to guess.

FORMULA

The three compared