Chapter 8: Clustering

Week 15-16

Discover hidden structure in unlabeled data through unsupervised learning. Master K-Means for partitioning, hierarchical methods for building cluster trees, density-based DBSCAN for arbitrary shapes, and learn to evaluate cluster quality without ground truth.

Topics: 3
Demos: 4
Min read: 26

Chapter Overview

Clustering is the quintessential unsupervised learning task: finding natural groupings in data without any labels to guide us. Unlike supervised learning where we have ground truth, clustering must discover structure purely from the data itself.

The applications are everywhere: segmenting customers by behavior, grouping similar documents, detecting anomalies that don't fit any cluster, compressing images by grouping similar colors, and exploring high-dimensional data by identifying natural categories.

Different clustering algorithms make different assumptions about what constitutes a "cluster." K-Means assumes clusters are spherical and roughly equal-sized. Hierarchical methods build trees that can be cut at any level. Density-based methods like DBSCAN find clusters of arbitrary shape and automatically identify outliers.

Choosing the right algorithm and parameters requires understanding these assumptions and evaluating results. Unlike classification, we can't simply measure accuracy. Instead, we use metrics like silhouette score that measure how well-separated clusters are, or domain knowledge to assess whether discovered groups are meaningful.

This chapter covers:

K-Means: Fast partitioning algorithm that iteratively assigns points to nearest centroids
Hierarchical: Bottom-up or top-down methods that produce dendrograms showing cluster relationships
DBSCAN: Density-based algorithm that finds clusters of any shape and identifies noise points
Evaluation: Metrics like silhouette score and methods like the elbow plot to assess clustering quality

Chapter Roadmap

Click any topic to jump in

Interactive demo

K-Means Clustering

Partition data into K spherical clusters by iterating between point assignment and centroid updates.

AlgorithmInertia (WCSS)Choosing KLimitations

Beyond spherical clusters

Hierarchical structure and arbitrary-shape density clusters

Hierarchical Clustering

Build a dendrogram by progressively merging clusters — cut at any level for different granularities.

Agglomerative ClusteringLinkage MethodsDendrogramAdvantages

DBSCAN

Find clusters of arbitrary shape using density, and automatically identify noise points as outliers.

Core PointsBorder PointsNoise PointsParameters

Topics

3 topics in this chapter

The previous chapter, Support Vector Machines, closed the book on supervised learning for now: every algorithm so far learned from labeled examples. Often there are no labels at all. A retailer has millions of purchase histories but no list of customer types; a biologist has gene expression profiles but no known cell categories. Can an algorithm discover groups on its own, using nothing but the similarity between points? This chapter, Clustering, studies that question with three families of methods that define a cluster in very different ways.

K-Means, the oldest and most widely used, defines a cluster by its center: every point belongs to the nearest of K centroids. This topic starts with the algorithm itself, Lloyd's alternation between assigning points and moving centers. We then define inertia, the within-cluster sum of squares that K-Means minimizes, and use it with the silhouette score to choose K. The topic closes with the method's limitations, including its sensitivity to initialization and its preference for round, equally sized clusters.

Definition

K-Means clustering partitions $n$ points into $K$ clusters by choosing centroids $\mu_1, \ldots, \mu_K$ and an assignment $c(i)$ of each point that together minimize the total within-cluster sum of squared distances from each point to its own centroid, $\sum_i \lVert x_i - \mu_{c(i)} \rVert^2$ . Lloyd's algorithm finds a local minimum by alternating nearest-centroid assignment and centroid averaging.

In this topic

1Algorithm
2Inertia (WCSS)
3Choosing K
4Limitations

1 of 4

Algorithm

Lloyd's algorithm alternates two steps. Assignment: give each point to its nearest centroid, measured by Euclidean distance. Update: move each centroid to the mean of the points assigned to it. Each step can only lower or keep the objective, the total squared distance from points to their centroids, so the algorithm converges, usually in a few dozen iterations, each costing $O(nKd)$ for $n$ points in $d$ dimensions. It converges to a local minimum, not necessarily the global one, so the starting centroids matter. Random initialization can place two centroids in one true cluster; k-means++ spreads the starting centroids out and is scikit-learn's default.

Mathematical Intuition

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.

Example:

K=2, centroids μ₁=(0,0), μ₂=(5,5). Point x=(1,2). Which cluster does it belong to?

2 of 4

Inertia (WCSS)

$\sum_{i=1}^{n} ||x_i - \mu_{c(i)}||^2$

Inertia, also called the within-cluster sum of squares (WCSS), adds up the squared distance from every point to its assigned centroid: the formula above, where $\mu_{c(i)}$ is the centroid of point $i$ 's cluster. It is exactly the objective K-Means minimizes, and lower means tighter clusters. Two cautions. First, inertia always falls as K grows, reaching zero when every point is its own cluster, so it cannot pick K by itself. Second, squaring makes it sensitive to outliers: one far point can pull a centroid toward it. Inertia also depends on feature scale, so standardize features before clustering, as with SVMs.

Mathematical Intuition

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.

Example:

Cluster 1: points {(0,0), (1,1)}, centroid (0.5, 0.5). Calculate inertia for this cluster.

3 of 4

Choosing K

Because inertia always decreases with K, choosing K needs a different criterion. The elbow method plots inertia against K and picks the point where further clusters stop paying off. It is subjective, and many datasets show no clear elbow. The silhouette score is more principled: for each point, $a$ is the mean distance to points in its own cluster and $b$ the mean distance to points in the nearest other cluster, and $s = (b - a)/\max(a, b)$ ranges from $-1$ to $1$ . Average it over points and pick the K with the highest value. The gap statistic compares inertia with that of random data. Domain knowledge often matters most.

Mathematical Intuition

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.

Example:

Inertia values: K=1→1000, K=2→400, K=3→350, K=4→340, K=5→335. Where's the elbow?

4 of 4

Limitations

K-Means makes strong implicit assumptions. Assigning each point to its nearest centroid splits space into convex regions, so clusters are effectively assumed to be round, similar in size, and similar in spread. Elongated, ring-shaped, or crescent clusters get cut apart, and a dense small cluster next to a sparse large one is mishandled. K must be chosen in advance. Results depend on initialization, which is why scikit-learn runs several starts and keeps the best. Every point must belong to some cluster, so outliers distort centroids. Gaussian mixture models relax the shape assumption, and DBSCAN, later in this chapter, handles arbitrary shapes and noise.

Mathematical Intuition

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.

Example:

Data has two crescent-moon shaped clusters. Will K-Means work with K=2?

Theory Exercise

Problem:

K-Means is run twice on the same data with different random initializations and produces two noticeably different clusterings with different inertia values. Why does this happen, and how would you make the result more reliable?

Hints:

What kind of minimum does K-Means converge to?
How does the starting position of centroids affect the outcome?
What does scikit-learn's n_init parameter do, and what is K-Means++?

Papers

Lloyd — Least Squares Quantization in PCM (1982)Arthur & Vassilvitskii — k-means++: The Advantages of Careful Seeding (2007)Sculley — Web-Scale K-Means Clustering (Mini-Batch K-Means, 2010)

Blogs

Scikit-Learn: K-Means Clustering Google ML: Clustering Overview

Coding Exercise

Problem:

Generate three blob clusters, then use the elbow method (inertia vs K) and the silhouette score to confirm the correct number of clusters. Print the inertia and silhouette for K = 2..6.

Hints:

make_blobs(n_samples=..., centers=3) gives a labeled-looking dataset, but cluster on X only
Loop K from 2 to 6, fit KMeans(n_clusters=K, n_init=10, random_state=0), record km.inertia_
silhouette_score(X, km.labels_) measures separation — the best K maximizes it

Definition

Agglomerative hierarchical clustering starts with each of the $n$ points as its own cluster and performs $n - 1$ merges, each time joining the two clusters that are closest under a chosen linkage criterion. The result is a binary tree, the dendrogram, whose merge heights record the distances at which clusters joined; cutting it yields a flat clustering.

In this topic

1Agglomerative Clustering
2Linkage Methods
3Dendrogram
4Advantages

1 of 4

Agglomerative Clustering

Agglomerative clustering is bottom-up. Start with $n$ singleton clusters and a matrix of pairwise distances. Repeatedly find the closest pair of clusters, merge them, and update the distances from the new cluster to every other cluster using the linkage rule, until a single cluster remains. The sequence of merges and their distances forms the dendrogram. The algorithm is deterministic, with no random initialization, and needs only pairwise distances, not coordinates, for most linkages. The cost is the problem: storing the distance matrix takes $O(n^2)$ memory and standard algorithms take $O(n^2)$ to $O(n^3)$ time, so it suits thousands of points, not millions. Divisive clustering works top-down instead.

Mathematical Intuition

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.

Example:

4 points: A, B, C, D. Distances: d(A,B)=2, d(A,C)=5, d(B,C)=3, d(C,D)=1. What merges first?

2 of 4

Linkage Methods

The linkage defines the distance between two clusters. Single linkage uses the closest pair of points across them; it can follow long, curved clusters but suffers from chaining, where a thin line of noise points joins two distinct groups. Complete linkage uses the farthest pair, favoring compact clusters of similar diameter, but is sensitive to outliers. Average linkage uses the mean of all cross-cluster distances, a compromise. Ward's method merges the pair that least increases total within-cluster variance, the same inertia K-Means minimizes, and tends to produce balanced, round clusters; it requires Euclidean distances. Ward is scikit-learn's default and works well when clusters are compact.

Mathematical Intuition

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.

Example:

Cluster X={A,B}, Cluster Y={C}. d(A,C)=3, d(B,C)=7. What's distance using single vs complete linkage?

3 of 4

Dendrogram

A dendrogram draws the merge history as a tree. Leaves at the bottom are individual points; each horizontal bar joins two clusters at a height equal to their linkage distance when they merged. Cutting the tree with a horizontal line at height $h$ yields a flat clustering whose number of clusters equals the number of vertical branches the line crosses. Low cuts give many small clusters, high cuts few large ones. A long vertical stretch with no merges signals a natural clustering, since those clusters stay separate over a wide range of distances. The cophenetic correlation measures how faithfully the merge heights preserve the original pairwise distances.

Mathematical Intuition

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.

Example:

Dendrogram has horizontal cut options at heights 5, 15, and 30. Height 5 gives 4 clusters, height 15 gives 2. What does height 30 give?

4 of 4

Advantages

Hierarchical clustering's main strength is that it returns every level of grouping at once. You need not choose K in advance, since one dendrogram serves all values of K, and you can choose after inspecting the structure. The tree itself is interpretable and suits domains that really are nested, such as taxonomies or document topics. Average, single, and complete linkage work with any distance or dissimilarity, such as edit distance for strings, so no coordinates are required, although Ward needs Euclidean data. Results are deterministic. The costs are quadratic memory, merges that can never be undone, and sensitivity to the linkage choice.

Mathematical Intuition

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. Single, complete, and average linkage work with any dissimilarity (not just Euclidean), making them applicable to domains with custom measures like edit distance for strings or Jaccard distance for sets; Ward's criterion $\Delta(A,B) = \frac{|A||B|}{|A|+|B|}\lVert\bar{A}-\bar{B}\rVert^2$ is defined through centroids, so it assumes squared Euclidean distance. The deterministic nature (no random initialization) means results are reproducible without multiple restarts, up to ties between equal distances.

Example:

You're clustering species by genetic similarity. Why might hierarchical clustering be ideal?

Theory Exercise

Problem:

You run agglomerative clustering on the same dataset with single linkage and with complete linkage and get very different dendrograms — single linkage produces one giant straggly cluster while complete linkage gives compact balls. Explain why, and when each linkage is appropriate.

Hints:

How does single linkage define the distance between two clusters?
What is the 'chaining effect'?
Which linkage favors compact clusters and which favors elongated ones?

Papers

Ward — Hierarchical Grouping to Optimize an Objective Function (1963)Murtagh & Contreras — Algorithms for Hierarchical Clustering: An Overview (2012)Müllner — Modern Hierarchical, Agglomerative Clustering Algorithms (2011)

Blogs

Scikit-Learn: Hierarchical Clustering Understanding Hierarchical Clustering — Analytics Vidhya

Coding Exercise

Problem:

Run agglomerative clustering with Ward linkage on a blob dataset and reproduce the merge structure as a dendrogram using scipy's linkage and dendrogram functions. Cut the tree into 3 clusters and report the cluster sizes.

Hints:

scipy.cluster.hierarchy.linkage(X, method='ward') returns the merge matrix Z
fcluster(Z, t=3, criterion='maxclust') cuts the tree into a fixed number of clusters
np.bincount on the resulting labels gives the size of each cluster

The previous topic, Hierarchical Clustering, built a full tree of nested groups, and K-Means before it found round clusters around centers. Both share two weaknesses. Every point must belong to some cluster, so outliers distort the result, and both struggle with clusters of arbitrary shape, such as crescents, rings, or winding streets on a map. Can we define a cluster not by a center or a merge order, but simply as a region where points are packed densely, separated from other such regions by sparse space?

DBSCAN, short for Density-Based Spatial Clustering of Applications with Noise, introduced by Ester and colleagues in 1996, does exactly that. It needs no number of clusters, finds arbitrary shapes, and labels isolated points as noise. This topic builds it from its three point types: core points in dense neighborhoods, border points on a cluster's edge, and noise points that belong nowhere. We then study its two parameters, the radius eps and the count min_samples, how to choose them with a k-distance plot, and why a single density threshold fails when clusters differ in density, the gap HDBSCAN fills.

Definition

DBSCAN groups points by density. A point is a core point if at least minPts points, counting itself, lie within radius $\epsilon$ . Clusters are formed by connecting core points within $\epsilon$ of each other and attaching border points within $\epsilon$ of a core point; all remaining points are labeled noise.

In this topic

1Core Points
2Border Points
3Noise Points
4Parameters

1 of 4

Core Points

A core point has at least minPts points within distance $\epsilon$ of it, a neighborhood dense enough to anchor a cluster. Clusters grow from core points: any two core points within $\epsilon$ of each other belong to the same cluster, and chains of such links let a cluster snake through space in any shape. That is why DBSCAN can follow crescents and rings that K-Means cuts apart. A counting convention matters: the original paper and scikit-learn's min_samples count the point itself. With minPts = 5, a point needs 4 other points within $\epsilon$ . Distances are computed with a spatial index, so typical runs scale far better than the quadratic hierarchical methods.

Mathematical Intuition

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\}$ includes $p$ itself. Core points anchor cluster expansion: they sit in dense regions and pull nearby points into their cluster. The implied density threshold is about $\text{minPts}/(\pi\epsilon^2)$ points per unit area in 2D (or $\text{minPts}/V_d(\epsilon)$ in $d$ dimensions, where $V_d$ is the volume of a $d$ -ball). Points that are density-reachable from a core point, through a chain of core points each within $\epsilon$ of the next, belong to the same cluster.

Example:

ε=1, minPts=3. Point A has 4 neighbors within distance 1. Point B has 2 neighbors. Which are core points?

2 of 4

Border Points

A border point has fewer than minPts points within $\epsilon$ , so it is not dense enough to be core, but it lies within $\epsilon$ of at least one core point. It joins that core point's cluster and sits on the cluster's edge. Border points never extend a cluster: expansion only continues from core points, which keeps a cluster from leaking across sparse regions. A border point within $\epsilon$ of core points from two different clusters is assigned to whichever cluster reaches it first, so its label can depend on the order of the data. That ambiguity aside, DBSCAN's result is deterministic, with no random initialization as in K-Means.

Mathematical Intuition

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.

Example:

Point B (2 neighbors) is within ε of core point A. What is B's classification?

3 of 4

Noise Points

A noise point is neither core nor border: fewer than minPts points lie within $\epsilon$ of it, and it is not within $\epsilon$ of any core point. DBSCAN labels such points $-1$ instead of forcing them into a cluster, which makes it a natural outlier detector and keeps outliers from dragging cluster shapes the way they drag K-Means centroids. The amount of noise is controlled by the parameters: a small $\epsilon$ or large minPts raises the density bar, so more points become noise. A large noise fraction is a diagnostic: either the parameters are too strict or the data contain regions of very different density.

Mathematical Intuition

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.

Example:

Point C is isolated—no points within ε. What happens to C?

4 of 4

Parameters

ε (eps): neighborhood radius. minPts: minimum points for core.

DBSCAN has two parameters. $\epsilon$ (eps) is the neighborhood radius and minPts (min_samples) the count required for a core point; together they set a density threshold. Smaller $\epsilon$ means more noise and more, smaller clusters; larger $\epsilon$ merges clusters, eventually into one. A common heuristic sets minPts to at least the dimension plus one, often twice the dimension. To choose $\epsilon$ , compute each point's distance to its k-th nearest neighbor, with k = minPts - 1, sort these distances, and look for the elbow where they rise sharply. The main limitation is the single global threshold: clusters of very different densities cannot all be captured, which HDBSCAN addresses.

Mathematical Intuition

The parameters $(\epsilon, \text{minPts})$ jointly define the density threshold. The k-distance plot (each point's distance to its $k$ -th nearest neighbor, sorted) helps choose $\epsilon$ : the elbow marks the boundary between dense cluster points and sparse noise. Use $k = \text{minPts} - 1$ when minPts counts the point itself, as in scikit-learn. A common heuristic sets $\text{minPts} \geq d + 1$ , often $2d$ , so the density estimate is robust. DBSCAN's main limitation is a single global $(\epsilon, \text{minPts})$ : it cannot handle clusters with very different densities. HDBSCAN addresses this by considering all $\epsilon$ values at once and extracting the most persistent clusters.

Example:

ε=0.5 gives 10 clusters, 50 noise points. ε=2.0 gives 2 clusters, 5 noise points. What trade-off are we seeing?

Theory Exercise

Problem:

Your dataset has varying densities: one tight cluster and one sparse cluster. Which clustering algorithm would work best and why?

Hints:

Consider how each algorithm handles density
What does DBSCAN assume about density?
Think about parameter sensitivity

Papers

Ester, Kriegel, Sander & Xu — A Density-Based Algorithm for Discovering Clusters (DBSCAN, KDD 1996)Campello, Moulavi & Sander — Density-Based Clustering Based on Hierarchical Density Estimates (HDBSCAN, 2013)Schubert et al. — DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN (2017)

Blogs

Scikit-Learn: DBSCAN Clustering HDBSCAN Documentation Visualizing DBSCAN — Naftali Harris

Coding Exercise

Problem:

Generate two interleaving half-moons and cluster them with DBSCAN, showing that it recovers the non-convex shapes that K-Means cannot. Print the number of clusters found and how many points were labeled as noise.

Hints:

make_moons(n_samples=..., noise=0.06) creates two crescent shapes
DBSCAN(eps=0.2, min_samples=5).fit_predict(X) returns labels, with -1 meaning noise
Count clusters as the number of unique labels excluding -1; noise count is (labels == -1).sum()

K-Means Clustering

Hierarchical Clustering

DBSCAN

3 topics in this chapter

K-Means Clustering

Definition

In this topic

Algorithm

Inertia (WCSS)

Choosing K

Limitations

Theory Exercise

Problem:

Hints:

Coding Exercise

Problem:

Hints:

Related Problems on PixelBank

Hierarchical Clustering

Definition

In this topic

Agglomerative Clustering

Linkage Methods

Dendrogram

Advantages

Theory Exercise

Problem:

Hints:

Coding Exercise

Problem:

Hints:

DBSCAN

Definition

In this topic

Core Points

Border Points

Noise Points

Parameters

Theory Exercise

Problem:

Hints:

Coding Exercise

Problem:

Hints:

Related Problems on PixelBank