Clustering

Clustering is the flagship unsupervised task: group observations so that points in the same group are similar and points in different groups are dissimilar — with no labels to guide or evaluate the grouping. Typical uses: customer segmentation, anomaly detection, image compression, organizing documents (the road to topic modeling).

Because there is no ground truth, every clustering result is a hypothesis about structure, and the algorithm's assumptions determine what kind of structure it can find.

k-means

The classical algorithm (Lloyd, 1957/1982). Choose \(k\); find centroids \(\mu_1, \dots, \mu_k\) minimizing the within-cluster sum of squares (inertia):

Lloyd's algorithm alternates two steps until assignments stop changing:

1. Assign: each point joins its nearest centroid;
2. Update: each centroid moves to the mean of its assigned points.

Worked by hand

Six points, two obvious groups, and a deliberately bad start — both centroids on the left:

Start with \(\mu_1 = (1,1)\), \(\mu_2 = (2,1)\) and turn the crank:

Three things to take from that table. The inertia falls monotonically — 284, 20.7, 2.67 — and this is guaranteed: both steps can only decrease it, which is why the algorithm always terminates. The convergence test is on the assignments, not the inertia. And a start as bad as this one still recovered, in three iterations — but nothing guaranteed that, which is what n_init is for.

Step through the same two operations here. The arrows show where step 2 is about to move each cross:

from sklearn.cluster import KMeans

km = KMeans(n_clusters=3, n_init=10, random_state=0)   # n_init: restarts
labels = km.fit_predict(X_scaled)
km.inertia_          # within-cluster sum of squares
km.cluster_centers_

Properties and pitfalls:

• You must choose \(k\) in advance;
• Converges to a local optimum — hence multiple restarts (n_init);
• Assumes clusters are convex, roughly spherical, similar in size (it partitions space into Voronoi cells around centroids);
• Distance-based → scale your features (Preprocessing);
• Every point is assigned to a cluster — k-means has no concept of noise or outliers.

Choosing k

• Elbow method: plot inertia vs \(k\); inertia always decreases, so look for the "elbow" where gains flatten. Heuristic and often ambiguous.
• Silhouette score: for each point, with \(a\) = mean distance to its own cluster and \(b\) = mean distance to the nearest other cluster,

Average \(s\) near 1 → compact, well-separated clusters; near 0 → overlapping; negative → likely misassigned. Choose the \(k\) that maximizes the mean silhouette.

For point A = (1,1) in the worked example: its own group is {B, C}, at distances 1 and 1, so \(a = 1\). The other group is {D, E, F}, at mean distance \(b = 10.39\). That gives

which is what "comfortably inside its own group" looks like as a number. Pick any point in the simulator and watch the two averages it is built from:

Now sweep \(k\) and put the two criteria side by side. On clean blobs they agree; on other shapes they do not, and the elbow is the one that gives way:

from sklearn.metrics import silhouette_score
silhouette_score(X_scaled, labels)

Hierarchical clustering

Agglomerative clustering builds a dendrogram: start with every point as its own cluster, repeatedly merge the two closest clusters until one remains, then cut the tree at the desired level. No need to fix \(k\) beforehand — you choose it by cutting.

The definition of "closest clusters" is the linkage:

from sklearn.cluster import AgglomerativeClustering
labels = AgglomerativeClustering(n_clusters=3, linkage='ward').fit_predict(X_scaled)

Cost is \(O(n^2)\) memory/time — fine for thousands of points, prohibitive for millions.

DBSCAN and HDBSCAN: density-based clustering

DBSCAN (Ester et al., 1996) defines clusters as dense regions separated by sparse regions, using two parameters: eps (neighborhood radius) and min_samples (points required to call a neighborhood dense).

• Core point: has ≥ min_samples neighbors within eps;
• Border point: within eps of a core point, but not core itself;
• Noise: neither — DBSCAN labels outliers (label −1) instead of forcing them into clusters.

Strengths: finds arbitrarily shaped clusters, no \(k\) to choose, built-in noise detection. Weaknesses: a single global eps fails when clusters have different densities; eps is not intuitive to tune.

HDBSCAN (Campello, Moulavi & Sander, 2013) removes the global eps: it builds a hierarchy over all density levels and extracts the most stable clusters, handling variable-density data with essentially one intuitive parameter (min_cluster_size). This robustness is why BERTopic uses HDBSCAN to cluster document embeddings — documents that fit no topic simply become noise instead of polluting topics.

from sklearn.cluster import HDBSCAN   # scikit-learn ≥ 1.3
labels = HDBSCAN(min_cluster_size=10).fit_predict(X_scaled)

Assumptions matter: k-means vs DBSCAN

Before the comparison, see the failure directly. k-means imposes convex, similarly-sized, spherical groups on whatever you give it. Cycle through the five shapes below — the moons get cut across, the concentric rings are impossible for any set of centroids, the elongated groups get split along the wrong diagonal, and on pure noise it still returns tidy partitions:

The lesson is not that k-means is bad. It is that the metric does not always warn you: on several of those shapes the silhouette stays respectable while the partition is meaningless. A metric can only score the partition it is given against the assumptions it shares with the algorithm.

On convex blobs both succeed. On the two moons, k-means fails by construction — it can only draw Voronoi boundaries between centroids — while DBSCAN follows the density and recovers the crescents, marking stray points as noise.

Choosing an algorithm

Class materials

Video

Algoritmo k-means (k-médias) — in Portuguese

References

• Lloyd, S. P. "Least Squares Quantization in PCM." IEEE Trans. Inf. Theory 28 (1982). DOI
• Rousseeuw, P. J. "Silhouettes: A Graphical Aid to the Interpretation and Validation of Cluster Analysis." J. Comp. Appl. Math. 20 (1987). DOI
• Campello, R.; Moulavi, D.; Sander, J. "Density-Based Clustering Based on Hierarchical Density Estimates." PAKDD (2013). DOI

The full course bibliography is on the references page.

Quiz