◢◤ ARKANE_
SYS_TIME UTC+0
Work with me

Chapter 19

Unsupervised Learning

Every model up to this chapter has required labels. Someone had to mark each example “malignant” or “benign,” “fraud” or “not fraud.” Labels are expensive. A radiologist reviewing scans, an analyst labelling transactions: both cost real time and money. For many real questions, like which customers resemble each other or whether a log entry looks unusual, there are no labels, only raw data. Unsupervised learning finds structure without labels. It’s less glamorous than supervised learning. But it’s often where the most interesting discoveries happen.

19.1 Motivation

There are two main tasks here. Clustering groups similar things together without being told what the groups are. Use cases include customer segmentation, document grouping, and finding natural categories in any dataset. Anomaly detection finds things that don’t fit. Use cases include fraud detection on new accounts with no labelled fraud yet, network intrusion detection, and manufacturing defect detection. Both tasks share an underlying question: what does it mean to be “similar,” and therefore “unusual,” in this space? The answer depends on how distance or density is defined.

19.2 Exposition

19.2.1 K-Means Clustering

K-Means is the clustering workhorse. Randomly initialise KK centroids. A centroid is just the cluster’s mean point: the average of every feature, taken across every point currently assigned to it. Assign each point to its nearest centroid. Recompute each centroid as the mean of its assigned points. Repeat until assignments stop changing. It converges to a local minimum, which is why it is often run several times from different starts, keeping the best result (n_init=10 in scikit-learn; the default 'auto' runs once with k-means++ initialisation). It’s fast, scalable, and easy to interpret. But it needs KK decided in advance, and assumes clusters are roughly spherical and similar in size.

Specifying KK is sometimes easy. A cancer-diagnosis dataset has an obvious K=2K=2: malignant or benign, fixed by the biology being studied, not a choice anyone has to make. Other times it’s close to impossible to know in advance. Segmenting an e-commerce platform’s customers could reasonably use 3 broad tiers (high, medium, low value) or 300 narrow micro-segments, one per campaign. Nothing about the data itself says which is right. The correct KK depends on what the business plans to do with the answer, not on the customers themselves.

That spherical, similar-size assumption fails on the wrong kind of data, as this chapter’s Worked Example shows directly. Choosing KK usually combines two tools. The elbow method plots inertia (the summed squared distance from each point to its assigned centroid) against KK and looks for diminishing returns. The second tool is the silhouette score (−1 to 1, higher better, measuring how well each point fits its own cluster against the next-best alternative).

19.2.2 Gaussian Mixture Models

K-Means assigns every point to exactly one cluster and assumes clusters are roughly spherical. A Gaussian Mixture Model (GMM) relaxes both assumptions. It models the data as if it were generated by a mixture of several Gaussian distributions, each with its own mean and covariance, and fits them with Expectation-Maximisation. The E-step computes each point’s probability of belonging to each Gaussian, a soft assignment, not a hard 0/1 label. The M-step updates each Gaussian’s mean, covariance, and weight to better fit those soft assignments, repeating until convergence. That’s structurally the same assign-then-recompute loop K-Means uses, made probabilistic.

Because each component has its own covariance matrix, GMM can fit elongated or rotated elliptical clusters, not just K-Means’s implicitly circular ones. And because membership is a probability rather than a label, a point near a cluster boundary can have, say, a 60/40 split between two components. That’s often a truer description of ambiguous real data than forcing a choice. GMM is a proper probabilistic model with a likelihood, so choosing the number of components can use BIC or AIC instead of K-Means’s elbow-and-silhouette combination above. Both are a single score that rewards a good fit but penalises extra components. The number of components that gets the lowest score is the one to pick. BIC (Bayesian Information Criterion) increases that penalty as the dataset grows larger. AIC (Akaike Information Criterion) keeps the penalty fixed no matter the size. In practice, try both. Plot the score against the number of components, and look for the point where the score stops dropping: the same diminishing-returns idea as the elbow method, just applied to a different number. The added flexibility isn’t free. Fitting a full covariance matrix per component costs more compute than K-Means’s single centroid per cluster. And GMM can still converge to a poor local optimum, the same failure mode K-Means has.

19.2.3 DBSCAN

DBSCAN needs no KK decided in advance. It defines clusters as dense regions separated by sparse ones, using two parameters: eps (the neighbourhood radius) and min_samples (how many neighbours within eps make a point a “core point”). Core points and everything density-reachable from them form a cluster. Anything left over is labelled noise (-1), which doubles as automatic outlier detection. DBSCAN finds arbitrarily shaped clusters that K-Means structurally cannot. That comes at the cost of sensitivity to its two parameters and difficulty with clusters of varying density.

19.2.4 Hierarchical Clustering

Hierarchical (agglomerative) clustering builds a dendrogram: a tree showing the order clusters were merged, which can be cut at any height to get any number of clusters. It’s useful for exploratory work when the right number of clusters isn’t known in advance. But its time and memory costs grow at least quadratically with the number of rows (O(n3)O(n^3) time for the naive algorithm), which makes it impractical past roughly 10,000 rows.

19.2.5 Isolation Forest

Isolation Forest works on the idea that anomalies are few and different, so they’re easy to isolate. Build a forest where each tree splits on a randomly chosen feature and split value. A genuine anomaly, sitting apart from the bulk of the data, needs far fewer random splits to end up alone in its own partition than a typical point does. The anomaly score is based on average path length to isolation across all trees. A short path means easy isolation means likely anomaly. It scales well and works in high dimensions. But results vary run to run (it’s inherently random), and the contamination parameter (expected anomaly fraction) has to be set from real domain knowledge.

19.3 Trade-offs and Limits

Without ground-truth labels, there’s no objective way to know if the “right” clusters were found. Silhouette and similar internal metrics measure geometric compactness and separation, not business usefulness. A clustering with a mediocre silhouette score can still be the most actionable one, if a domain expert confirms the groups map to real, distinct behaviour. Anomaly detection has the same problem. “Anomaly” is domain-specific: a large purchase is normal for one customer and suspicious for another. Results are very sensitive to the contamination assumption. Ground-truth labels, when available, always beat unsupervised detection. Unsupervised methods are where you turn when labels don’t exist yet.

19.4 Procedures

Procedure 19.1 (Choose the Number of Clusters). When to use: before running K-Means or any fixed-KK algorithm.

Listing 19.1: Elbow method and silhouette score together
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score

inertias, silhouettes = [], []
for k in range(2, 11):
    km = KMeans(
        n_clusters=k, random_state=42, n_init=10
    ).fit(X_scaled)
    inertias.append(km.inertia_)
    silhouettes.append(silhouette_score(X_scaled, km.labels_))

Common mistake: picking KK purely from an ambiguous elbow chart. Cross-check with the silhouette score, and, more important than either, check whether the resulting clusters make sense to someone who knows the domain.

Procedure 19.2 (Run K-Means, GMM, DBSCAN, and Agglomerative Clustering). When to use: a feature matrix with rows to group.

Listing 19.2: Four clustering approaches for four different assumptions
from sklearn.cluster import KMeans, DBSCAN, AgglomerativeClustering
from sklearn.mixture import GaussianMixture

km = KMeans(
    n_clusters=4, random_state=42, n_init=10
).fit_predict(X_scaled)
gm = GaussianMixture(
    n_components=4, random_state=42
).fit_predict(X_scaled)
db = DBSCAN(eps=0.5, min_samples=5).fit_predict(X_scaled)
agg = AgglomerativeClustering(
    n_clusters=4, linkage='ward'
).fit_predict(X_scaled)

Common mistake: calling DBSCAN(eps=0.5, ...) on unscaled features. eps is a raw distance threshold, so a feature ranging 0-100,000 will dominate the distance calculation over one ranging 0-1 entirely.

Procedure 19.3 (Detect Anomalies with IsolationForest). When to use: flagging unusual rows without enough labelled anomalies to train a supervised classifier.

Listing 19.3: IsolationForest with a domain-informed contamination rate
from sklearn.ensemble import IsolationForest

iso = IsolationForest(
    n_estimators=100, contamination=0.05, random_state=42
)
labels = iso.fit_predict(X_scaled)   # 1 = normal, -1 = anomaly
scores = iso.score_samples(X_scaled) # lower = more anomalous

Common mistake: treating contamination as a free parameter to tune for a “better-looking” result. It should reflect an actual prior belief about how much of the data is anomalous: tuning it to hit a desired output count is circular and either hides real anomalies or manufactures fake ones.

Procedure 19.4 (Validate Clustering Quality Without Ground Truth). When to use: after clustering, before trusting or shipping the result.

Listing 19.4: Internal clustering-quality metrics
from sklearn.metrics import (
    silhouette_score,
    davies_bouldin_score,
    calinski_harabasz_score,
)

# -1 to 1, higher better
sil = silhouette_score(X_scaled, labels)
# 0 to inf, lower better
db_score = davies_bouldin_score(X_scaled, labels)

19.5 Worked Example

Fitting K-Means to two interleaving crescent-shaped clusters (make_moons, 300 points, moderate noise) demonstrates the spherical-cluster assumption failing directly, not just in theory:

Listing 19.5: K-Means vs. GMM vs. DBSCAN on non-spherical clusters
km = KMeans(n_clusters=2, random_state=42, n_init=10).fit(X_scaled)
gm = GaussianMixture(n_components=2, random_state=42).fit(X_scaled)
db = DBSCAN(eps=0.3, min_samples=5).fit(X_scaled)

Measured, scored against the true crescent labels using the Adjusted Rand Index (1.0 = perfect agreement, 0 = random): K-Means achieves ARI 0.479. It finds a split of the data, since it always finds some split. But that split cuts across the two crescents rather than separating them, because K-Means divides space with straight boundaries halfway between centroids, so every cluster it finds is a convex region, and the true clusters are not remotely convex. A Gaussian Mixture Model, fit with two components on the same data, lands on the exact same ARI, 0.479, despite its elliptical covariance being strictly more flexible than K-Means’s fixed circular one. Here, that extra flexibility doesn’t help at all. The underlying problem isn’t circularity, it’s convexity. Two crescents can’t be well-approximated by two ellipses any more than by two circles. GMM shares K-Means’s assumption that each cluster is a single convex blob, so both algorithms end up drawing essentially the same dividing line. DBSCAN, with eps=0.3 chosen from a k-distance plot, achieves ARI 0.987, with only 2 of 300 points labelled noise. That’s close to a perfect recovery of both crescents. This isn’t DBSCAN being “better” in general. It’s DBSCAN’s density-based definition of a cluster matching this data’s actual shape, while K-Means’s and GMM’s centroid-based definitions structurally cannot.

A separate anomaly-detection problem is deliberately harder. It has 500 points drawn from a standard 2D normal distribution, plus 25 outliers scattered uniformly across a much wider range. An IsolationForest with contamination=0.05 (matching the true 25/525 ≈\approx 4.8% anomaly rate) flags 27 points as anomalies, with precision 0.852 and recall 0.920. It catches most of the real anomalies (23 of 25), while incorrectly flagging a small handful of ordinary points that happened to land unusually far from the bulk of the normal distribution just by chance. That’s a realistic result, not a perfect one. It’s a useful reminder that even a well-calibrated contamination estimate doesn’t produce perfect precision or recall on real, noisy data.

AWS SageMaker Equivalent
from sagemaker import KMeans as SageMakerKMeans
from sagemaker import RandomCutForest

kmeans_estimator = SageMakerKMeans(
    role=role,
    instance_count=1,
    instance_type='ml.c5.xlarge',
    k=4,
    output_path=f's3://{bucket}/kmeans-output',
)
kmeans_estimator.fit(
    kmeans_estimator.record_set(X_train.astype('float32'))
)

rcf_estimator = RandomCutForest(
    role=role,
    instance_count=1,
    instance_type='ml.c5.xlarge',
    num_trees=100,
    num_samples_per_tree=256,
)
rcf_estimator.fit(
    rcf_estimator.record_set(X_train.astype('float32'))
)

When to prefer SageMaker’s built-in K-Means/Random Cut Forest: once clustering or anomaly detection needs to run on data too large to fit in memory on one machine, or as a scheduled production pipeline with monitoring and retraining. For exploratory work on data that fits in memory, like this chapter’s Worked Example, sklearn is faster to iterate with.

19.6 History and Further Reading

Murphy’s Introduction, Ch. 21-22, gives the full treatment of K-Means, Gaussian Mixture Models, and DBSCAN (Murphy 2022). Burkov, Ch. 9, gives an accessible unsupervised learning overview (Burkov 2019). Géron’s Hands-On Machine Learning, Ch. 9, covers K-Means, DBSCAN, and Gaussian Mixture Models with the Scikit-Learn code for each, a practical companion to this chapter’s algorithms (Géron 2019). Liu et al.’s original Isolation Forest paper gives the full algorithm and its complexity analysis (Liu et al. 2008).

19.7 How This Connects

This chapter builds on Chapter 6’s Python ecosystem and Chapter 9’s EDA (understanding data before clustering it), and on Chapter 15’s dimensionality reduction, which PCA/UMAP use to visualise high-dimensional clusters in 2D. It enables Book 2, Chapter 31’s retrieval-augmented generation, where document clustering and embedding-based similarity underpin how vector databases organise retrieval. It’s often confused with semi-supervised learning (some labels exist) and self-supervised learning (a model creates its own supervision signal, central to foundation model pretraining from Book 2, Chapter 29 onward). Both are related but distinct ideas, apart from the fully-unlabelled setting this chapter covers.

19.8 Exercises

  1. [W] Explain in one or two sentences why K-Means needs KK decided in advance while DBSCAN does not.

  2. [W] State which algorithm (K-Means or DBSCAN) is the better default for each: (a) a large, roughly spherical, well-separated set of customer segments; (b) an unknown number of irregularly shaped clusters with some genuine noise points mixed in.

  3. [A] Using Listing 19.5’s measured ARI scores (K-Means 0.479, DBSCAN 0.987), explain in your own words why a higher silhouette score for K-Means’s own clustering wouldn’t necessarily have revealed this failure: silhouette measures compactness given the clustering K-Means chose, not whether that clustering matches the true structure.

  4. [A] Using Listing 19.3’s measured results (27 flagged, precision 0.852, recall 0.920), compute the number of false positives and false negatives, and state which of the two errors this particular run made more of.

  5. [E] A customer wants to segment their customer base and reports “we found 6 clusters with a great silhouette score.” Using this chapter’s Trade-offs section, write the follow-up question you’d ask before treating those 6 clusters as actionable business segments.

  6. [E] A fraud team sets IsolationForest’s contamination=0.20 “because that gives us the cleanest-looking separation in our validation plots.” Using Procedure 19.3’s common mistake, explain why this reasoning is circular.

  7. [R] Read the original Isolation Forest paper’s (Liu et al., 2008) abstract. Identify the specific computational-complexity claim it makes relative to distance-based anomaly detection methods, and explain how that relates to this chapter’s “scales well, works in high dimensions” summary.

19.9 Mental Model

Clustering is map-making: drawing a map of the data space, grouping nearby points into regions. The map isn’t the territory. There’s no single “correct” clustering. Only clusterings useful for a given purpose. Different algorithms draw different maps, by definition. This chapter’s moons example is exactly what it looks like when the map’s assumptions don’t match the territory’s actual shape.

Burkov, Andriy. 2019. The Hundred-Page Machine Learning Book. Andriy Burkov.
Géron, Aurélien. 2019. Hands-on Machine Learning with Scikit-Learn, Keras, and TensorFlow: Concepts, Tools, and Techniques to Build Intelligent Systems. 2nd ed. O’Reilly Media.
Liu, Fei Tony, Kai Ming Ting, and Zhi-Hua Zhou. 2008. “Isolation Forest.” 2008 Eighth IEEE International Conference on Data Mining (Pisa, Italy), 413–22.
Murphy, Kevin P. 2022. Probabilistic Machine Learning: An Introduction. MIT Press.
online /books/classical-data-science/ch19-unsupervised-learning Newcastle, UK v0.1.0 // rss