Clustering

The idea

Clustering asks: do these unlabeled points form groups? k-means makes that concrete by choosing $k$ centroids $\mu_j$ to minimize within-cluster squared distance (inertia):

$J = \sum_{j=1}^{k} \sum_{x_i \in C_j} \|x_i - \mu_j\|^2$

Lloyd's algorithm solves it by alternating two moves, each of which can only lower $J$:

1. Assign each point to its nearest centroid.
2. Update each centroid to the mean of its points (the mean is the unique minimizer of squared distances — that is why it is k-means).

Finitely many partitions + monotone descent ⇒ guaranteed convergence, but to a local minimum: initialization decides which one. Standard practice is k-means++ seeding (new seeds picked with probability proportional to squared distance from existing seeds, spreading them out) plus a few restarts, keeping the lowest-inertia solution. Cost per iteration is $O(nkd)$ — this is the clustering algorithm that scales.

The objective silently assumes: Euclidean geometry (so scale your features), convex roundish clusters of similar size and density, and a known $k$. Each broken assumption has a designated successor:

• Elliptical, overlapping, different-size clusters → GMM: fit $k$ Gaussians with EM, get soft memberships and per-cluster covariances. k-means is exactly the degenerate GMM with shared spherical covariance $\sigma^2 I$ as $\sigma \to 0$ — hard assignments re-emerge in the limit.
• No known $k$, or the hierarchy is the point → agglomerative clustering: start with every point as a cluster, greedily merge the closest pair (per single/complete/average/Ward linkage), read any granularity off the dendrogram. Price: $O(n^2)$ distances.
• Non-convex shapes, noise, unknown k → DBSCAN: density-based, finds rings and moons, labels outliers as noise — but struggles with varying density.

Choosing k (for the methods that need it): the inertia-vs-$k$ curve only ever decreases, so look for the elbow where the marginal drop collapses; cross-check with the silhouette

$s_i = \frac{b_i - a_i}{\max(a_i, b_i)}$

($a_i$ = mean distance to own cluster, $b_i$ = mean distance to nearest other cluster; average $s_i$ near 1 is tight-and-separated, near 0 is mush) — and then let the domain veto: a segmentation nobody can act on has the wrong $k$ regardless of the curves.

Worked example

Six 1-D points, $k = 2$: $\{1, 2, 3, 10, 11, 12\}$, initial centroids $\mu_1 = 1$, $\mu_2 = 12$.

Iteration 1 — assign: distances to $(\mu_1, \mu_2)$: point 3 is $|3-1| = 2$ vs $|3-12| = 9$ → cluster 1; point 10 is $9$ vs $2$ → cluster 2. Result: $C_1 = \{1,2,3\}$, $C_2 = \{10,11,12\}$.

Iteration 1 — update: $\mu_1 = (1+2+3)/3 = 2$, $\mu_2 = (10+11+12)/3 = 11$.

Iteration 2 — assign: no point changes side → converged.

$J = (1{+}0{+}1) + (1{+}0{+}1) = 4$

Silhouette of point 3 (the boundary-most point of cluster 1):

$a_3 = \frac{|3-1| + |3-2|}{2} = 1.5, \qquad b_3 = \frac{7 + 8 + 9}{3} = 8, \qquad s_3 = \frac{8 - 1.5}{8} \approx 0.81$

Even the worst-placed point scores 0.81 — this is what genuinely separated clusters look like. Contrast $k = 3$ on the same data: the best it can do is split one tight triple, say into $\{1\}$ and $\{2, 3\}$. Inertia falls to $0 + 0.5 + 2 = 2.5$ — lower than 4, as inertia always is with more clusters — but the silhouette collapses where the split happened: point 2 now has $a_2 = |2-3| = 1$ and $b_2 = |2-1| = 1$ (distance to the singleton cluster), so $s_2 = 0$, and the singleton $\{1\}$ gets $s_1 = 0$ by convention. Inertia rewards $k = 3$; silhouette exposes it. That disagreement is the everyday argument for never choosing $k$ from the elbow curve alone.

Cheat sheet

k-means objective: $J = \sum_j \sum_{i \in C_j} \|x_i - \mu_j\|^2$; Lloyd: assign-to-nearest / recompute-means; converges to local min; $O(nkd)$ per iter; k-means++ + restarts.

Silhouette: $s_i = (b_i - a_i)/\max(a_i, b_i) \in [-1, 1]$; average it to score a clustering; near 0 ⇒ overlapping/boundary.

• Scale features before any distance-based clustering; log-transform skewed ones first.
• Inertia ALWAYS decreases in $k$ — never compare raw inertia across $k$ without the elbow/gap-statistic framing.
• Choosing k: elbow + silhouette + stability under resampling + business actionability; agreement metrics (adjusted Rand) across bootstraps separate structure from noise.
• k-means = GMM limit (shared $\sigma^2 I$, $\sigma \to 0$); use GMM when clusters are stretched or overlapping.
• k-means traps: outliers drag means (→ k-medoids), empty clusters on bad init, chain-shaped data sliced into balls.
• EM/GMM full covariance costs $d(d+1)/2$ parameters per cluster — restrict to diagonal when $d$ is large.
• Validate without labels: silhouette, Davies-Bouldin, stability; with side labels: adjusted Rand / NMI.