Skip to content

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):

\[ \min_{\mu_1,\dots,\mu_k} \; \sum_{i=1}^{n} \min_{j} \; \lVert x_i - \mu_j \rVert^2 \]

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.
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.

Run Lloyd's algorithm yourself — the data has 3 real blobs; watch what happens with k = 2 or k = 5, and how different random starts converge to different local optima:

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,
\[ s = \frac{b - a}{\max(a, b)} \in [-1, 1]. \]

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

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:

Linkage Distance between clusters Behavior
single closest pair of points finds elongated chains, sensitive to noise
complete farthest pair compact clusters
average mean pairwise distance compromise
Ward merge minimizing inertia increase k-means-like, most common default 
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

k-means vs DBSCAN on blobs and two moons

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

Situation Reach for
Convex, similar-size clusters; large n; need speed k-means (or MiniBatchKMeans)
Want a dendrogram / taxonomy; small n hierarchical (Ward)
Arbitrary shapes, noise/outliers expected DBSCAN
Arbitrary shapes with varying density (e.g. embeddings) HDBSCAN

Validate like a skeptic

With no labels, always inspect clusters: silhouette scores, 2D projections (PCA/UMAP), and — most importantly — whether the clusters mean something in the domain. A clustering nobody can name is rarely useful.

Class materials

Class notebook (in Portuguese)

Hands-on notebook used in class — Aula 07 — Clustering: open in Colab

Video

Algoritmo k-means (k-médias)

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

Quiz