Chapter 8: Clustering

K-Means alternates between two steps that each reduce the objective $J = \sum_{i=1}^{n}||x_i - \mu_{c(i)}||^2$. The assignment step finds the optimal cluster for each point given fixed centroids (minimum distance). The update step finds the optimal centroid for each cluster given fixed assignments (the mean). Since each step decreases or maintains $J$, and $J$ is bounded below by 0, the algorithm must converge. However, it converges to a local minimum — the result depends on initialization, which is why K-Means++ matters.

Inertia $J = \sum_{i=1}^{n}||x_i - \mu_{c(i)}||^2$ is the total within-cluster sum of squares. It decomposes as $J = \text{TSS} - \text{BSS}$, where TSS is the total scatter and BSS is the between-cluster scatter. Minimizing inertia is equivalent to maximizing BSS — pushing clusters apart. The inertia always decreases with $K$ (adding a cluster center can only reduce distances), reaching 0 when $K = n$. This monotonic decrease is why the elbow method looks for diminishing returns rather than an absolute minimum.

The elbow method plots inertia $J(K)$ versus $K$ and identifies the point of maximum curvature. Mathematically, this is where the second derivative $J''(K)$ is maximized — the transition from steep decline to gradual decline. The silhouette score $s(i) = (b(i) - a(i))/\max(a(i), b(i))$ provides a complementary view: $a(i)$ is the mean intra-cluster distance (cohesion) and $b(i)$ is the mean nearest-cluster distance (separation). Values near $+1$ indicate well-clustered points; near $0$ means boundary points; near $-1$ means likely misassigned.

K-Means assumes clusters are isotropic Gaussians (spherical, equal variance). The Voronoi cell assignment $c(i) = \arg\min_k ||x_i - \mu_k||^2$ creates convex, polygonal decision boundaries — it cannot capture non-convex cluster shapes like crescents or rings. The objective $\sum||x_i - \mu_{c(i)}||^2$ treats all directions equally, so elongated clusters get split along their major axis. For non-spherical clusters, consider Gaussian Mixture Models (which model covariance) or density-based methods like DBSCAN.

Agglomerative clustering starts with $n$ singleton clusters and performs $n-1$ merges. At each step, it merges the two closest clusters according to a linkage criterion, producing a binary tree (dendrogram). The time complexity is $O(n^3)$ for naive implementation or $O(n^2 \log n)$ with a priority queue. Unlike K-Means, it does not require specifying $K$ upfront — the full hierarchy encodes all possible $K$ values from 1 to $n$, and any specific clustering is obtained by cutting the dendrogram at the appropriate height.

Single linkage uses $d(A,B) = \min_{a \in A, b \in B} d(a,b)$ — it can find elongated, chain-like clusters but is sensitive to noise bridges between clusters (chaining effect). Complete linkage uses $d(A,B) = \max_{a \in A, b \in B} d(a,b)$ — it produces compact, spherical clusters but is sensitive to outliers. Ward's method minimizes the total within-cluster variance increase $\Delta(A,B) = \frac{|A||B|}{|A|+|B|}||\bar{A}-\bar{B}||^2$ — it is equivalent to K-Means in the sense that it optimizes the same inertia objective, but in a greedy, hierarchical fashion.

The dendrogram is a tree where each internal node represents a merge event at distance (height) $d_{\text{merge}}$. A horizontal cut at height $h$ produces a clustering with $K$ clusters, where $K$ is the number of branches crossing the cut line. Large vertical gaps in the dendrogram indicate natural cluster separations — the optimal cut is typically at the largest gap. The cophenetic distance $c(i,j)$ between two points is the height at which they first merge; the cophenetic correlation between pairwise distances and cophenetic distances measures how well the dendrogram preserves the original distance structure.

Hierarchical clustering produces a complete hierarchy of nested clusterings — a richer output than any flat clustering method. The dendrogram reveals multi-scale structure: cutting at different heights yields different granularities. It works with any distance metric (not just Euclidean), making it applicable to domains with custom similarity measures like edit distance for strings or Jaccard distance for sets. The deterministic nature (no random initialization) means results are reproducible without multiple restarts.

A core point $p$ has at least $\text{minPts}$ points within its $\epsilon$-neighborhood: $|N_\epsilon(p)| \geq \text{minPts}$, where $N_\epsilon(p) = \{q : d(p,q) \leq \epsilon\}$. Core points anchor cluster expansion — they sit in dense regions and pull nearby points into their cluster. The density threshold is $\rho \geq \text{minPts}/(\pi\epsilon^2)$ in 2D (or $\text{minPts}/V_d(\epsilon)$ in $d$-D where $V_d$ is the volume of a $d$-ball). Points that are density-reachable from a core point (connected through a chain of core points) belong to the same cluster.

Border points are within $\epsilon$ of at least one core point but have fewer than $\text{minPts}$ neighbors themselves: $|N_\epsilon(p)| < \text{minPts}$ but $\exists$ core point $q$ with $d(p,q) \leq \epsilon$. They sit on the periphery of dense regions. Border points can be density-reachable from multiple core points in different clusters — DBSCAN assigns them to the first cluster discovered during traversal, making border point assignment non-deterministic (order-dependent). This is the only source of non-determinism in DBSCAN.

Noise points are neither core nor border: they are not within $\epsilon$ of any core point. DBSCAN labels them as $-1$, effectively treating them as outliers. The fraction of noise points depends on the density threshold set by $(\epsilon, \text{minPts})$. This built-in outlier detection is a major advantage over K-Means and hierarchical clustering, which force every point into a cluster. The noise fraction can serve as a diagnostic: too many noise points suggests $\epsilon$ is too small or $\text{minPts}$ is too large.

The parameters $(\epsilon, \text{minPts})$ jointly define the density threshold. The k-distance plot (sort distances to the $k$-th nearest neighbor in descending order) helps choose $\epsilon$: the elbow corresponds to the boundary between dense clusters and sparse noise. The recommended $k = \text{minPts}$ for this plot. A common heuristic sets $\text{minPts} \geq d + 1$ (dimensionality + 1) to ensure the density estimate is robust. DBSCAN's main limitation is a single global $(\epsilon, \text{minPts})$ — it cannot handle clusters with varying densities. HDBSCAN addresses this by running DBSCAN over all $\epsilon$ values and extracting the most persistent clusters.