← Back to Tutorials Chapter 26

Unsupervised Learning & Dimensionality

Everything so far has been supervised: the data carried a label we learned to predict. Unsupervised learning removes the label entirely and asks the algorithm to discover structure on its own. This chapter covers the two pillars of unsupervised work — dimensionality reduction (led by PCA) and clustering (K-means, hierarchical, and DBSCAN) — plus the curse of dimensionality that motivates both.

Introduction to Unsupervised Machine Learning

In supervised learning the target guides the model. In unsupervised learning there is no target; the algorithm must find patterns from the input alone. Two broad families exist:

Clustering: group similar points together so points in the same group are closer to each other than to points in other groups. Used for customer segmentation, image compression, and organizing search results.
Dimensionality reduction: compress many features into fewer while preserving as much information as possible. Used for visualization, noise removal, and speeding up other algorithms.

Unsupervised methods are also the standard pre-processing companions to supervised pipelines — clusters can become new features, and reduced dimensions can become the input to a classifier.

The Curse of Dimensionality

Intuition built in 2D and 3D fails as the number of features grows. Consider a unit cube in d dimensions: the fraction of its volume near the boundary grows explosively with d. Similarly, in high-dimensional space almost every point is far from every other point, so distances stop being informative and "nearest" loses meaning.

Data becomes sparse: fixed datasets look tiny when spread across hundreds of features.
Distance-based models (KNN, clustering) degrade because distances all converge toward similar values.
Training time and overfitting risk both rise, since the model has more free parameters to fit.

The remedy is to keep only the features that matter, either by selecting a subset of the originals or by extracting new, smaller features from them.

Feature Selection and Feature Extraction

Feature selection picks a subset of the original columns and drops the rest. It is interpretable — you keep real measurements — but you can only remove, never create. Common tools: correlation filtering, variance thresholding, and mutual information.
Feature extraction builds new features as combinations of the old ones. It can shrink dimensions dramatically and remove redundant information, but the new features lose their original meaning. PCA is the classic example.

Both are dimensionality reduction; they differ in whether the surviving features are original or synthesized.

PCA Geometric Intuition

Principal Component Analysis (PCA) rotates the data to a new coordinate system aligned with its directions of greatest spread, then keeps only the first few coordinates.

The first principal component points along the direction of maximum variance — the long axis of a cloud of points.
The second principal component is perpendicular to the first and captures the next largest variance, and so on.
Each component is uncorrelated with the others, so no information is counted twice.

Picture a scatter of points shaped like a stretched ellipse. PCA finds the ellipse's long axis (component 1) and short axis (component 2). Dropping component 2 collapses the ellipse onto a line, losing little because the short axis held little spread.

PCA Math Intuition: Projection and Variance Maximization

Formally, PCA seeks a unit vector w such that projecting every point onto w maximizes the variance of the projected values. The projection of a point x onto w is the scalar dot product x . w, and the variance of those projections over the dataset is:

Var(proj) = w.T * S * w

where S is the covariance matrix of the centered data and w.T is the transpose of w. Maximizing this variance subject to w having unit length turns out to be an eigen-problem: the optimal w is the eigenvector of S belonging to its largest eigenvalue. The eigenvalue tells you how much variance that component explains.

Eigen-Decomposition on the Covariance Matrix

The recipe for PCA is short:

Center the data by subtracting each feature's mean.
Compute the covariance matrix S of the centered data.
Decompose S into eigenvectors w1, w2, ..., wk and eigenvalues l1, l2, ..., lk.
Order the eigenpairs by eigenvalue, largest first; the top m eigenvectors are the first m principal components.
Project the centered data onto those m vectors to get the reduced representation.

The ratio l1 / sum(l) tells you what fraction of the total variance the first component captures. In practice you keep enough components to cover 90–95% of the total variance.

PCA Implementation

from sklearn.decomposition import PCA
from sklearn.preprocessing import StandardScaler

scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

pca = PCA(n_components=2)          # keep two components
X_reduced = pca.fit_transform(X_scaled)
print(pca.explained_variance_ratio_)   # share of variance per component

Scale the features before PCA — otherwise a feature measured in large units dominates the covariance matrix regardless of how informative it is. The reduced two-column matrix can now be plotted directly as a scatter of points.

K-Means Clustering Geometric Intuition

K-means partitions the data into K clusters, each represented by its center (the mean of its points). The algorithm alternates two steps until nothing moves:

Assignment: assign every point to the nearest center (usually by squared Euclidean distance).
Update: recompute each center as the mean of the points assigned to it.

Geometrically you are sliding cluster centers around until each center sits at the "center of mass" of its territory. The final clusters are convex regions bounded by straight lines — K-means cannot find crescent or donut shapes.

How to Find K Values: Elbow and Silhouette

K-means needs K as input, and choosing K is part of the job.

Elbow method: run K-means for K = 2, 3, 4, ... and plot the total within-cluster sum of squares (inertia) against K. Inertia always falls as K grows, but the "elbow" is the point where the drop flattens — that K is a good choice.
Silhouette score: for each point, compare its distance to its own cluster (cohesion) with its distance to the nearest other cluster (separation). Scores near +1 mean well-separated clusters; near 0 means overlapping; negative means misassigned. The K with the highest average silhouette is often the best.

Heads up: the elbow is a visual judgment, not a law. If two K values both look reasonable, prefer the smaller one — simpler clusters are usually more useful for business decisions.

The Random Initialization Trap and K-Means++

K-means starts from random centers, and a bad start can park a center in an empty region or leave two centers fighting over one cluster while another cluster is ignored. The result is a poor local minimum. Two defenses exist:

Multiple restarts: run K-means many times from different random seeds and keep the run with the lowest inertia.
K-means++: choose the first center uniformly, then pick each next center with probability proportional to its squared distance from the already-chosen centers. This spreads the initial centers apart and almost always lands near a good solution. It is the default (init="k-means++") in scikit-learn.

K-Means Clustering Implementation

from sklearn.cluster import KMeans

kmeans = KMeans(n_clusters=3, init="k-means++", n_init=10, random_state=42)
labels = kmeans.fit_predict(X_scaled)
print(kmeans.inertia_)          # total within-cluster distance
print(kmeans.cluster_centers_)  # the final centers

The labels array holds each point's cluster id, ready for analysis, plotting, or as a new categorical feature.

Hierarchical Clustering

Hierarchical clustering builds a tree of clusters rather than a flat partition. There are two directions:

Agglomerative (bottom-up): start with every point as its own cluster, then repeatedly merge the two closest clusters until one remains.
Divisive (top-down): start with one cluster and recursively split it.

The tree of merges is called a dendrogram. To get a flat partition, cut the dendrogram horizontally at some height — clusters below the cut become the final groups. The choice of "distance between clusters" (linkage) matters: single linkage joins by the closest pair (good for elongated shapes, sensitive to noise), complete linkage by the farthest pair (compact clusters), and Ward's method by the increase in within-cluster variance.

Agglomerative Clustering Implementation

from scipy.cluster.hierarchy import dendrogram, linkage
from sklearn.cluster import AgglomerativeClustering

agg = AgglomerativeClustering(n_clusters=3, linkage="ward")
labels = agg.fit_predict(X_scaled)

Z = linkage(X_scaled, method="ward")   # for the dendrogram
dendrogram(Z)

Read the dendrogram from the bottom up: tall vertical gaps between groups indicate natural separations; the height where you cut determines the number of clusters.

K-Means vs Hierarchical Clustering

Speed: K-means is fast and scales to millions of points; hierarchical clustering builds a full tree and struggles past a few tens of thousands of points.
K input: K-means requires K up front; hierarchical clustering gives you the whole dendrogram and lets you choose K afterward.
Shapes: both assume reasonably compact, spherical clusters; neither handles crescents or rings natively.
Determinism: hierarchical is deterministic (given a linkage), while K-means depends on initialization (fixed by a seed and many restarts).

How DBSCAN Works

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) defines clusters by density instead of center distance. Two parameters control it:

eps: the radius of the neighborhood examined around each point.
min_samples: how many points must live inside that radius for the point to count as a core point.

The algorithm labels every point as core, border, or noise. Core points have at least min_samples neighbors within eps; border points are within eps of a core point but have too few neighbors; everything else is noise. A cluster is the set of points reachable by hopping between core points, together with their borders.

Examples After Applying DBSCAN

Because DBSCAN follows density, it finds shapes that center-based methods cannot:

A crescent moon dataset splits cleanly into two curving clusters, one on each arm.
A donut shape becomes a ring cluster, with the hole correctly left empty.
Real transaction data yields a few dense spending clusters plus a sprinkling of isolated points that DBSCAN reports as noise — those are often exactly the suspicious transactions.

Noise points are returned with the label -1, which makes DBSCAN a natural tool for anomaly detection (the next chapter uses this trick).

Pros and Cons of DBSCAN

Pros: no need to specify K; finds arbitrary shapes; robust to outliers; handles clusters of different densities reasonably when tuned.
Cons: eps is hard to choose and is sensitive to scaling — standardize features first; fails when clusters have very different densities, because one eps cannot serve both; needs more data to discover small clusters.

DBSCAN Clustering Implementation

from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler

X_std = StandardScaler().fit_transform(X)

db = DBSCAN(eps=0.5, min_samples=5)
labels = db.fit_predict(X_std)
print(set(labels))            # a -1 label marks noise points

Try a small range of eps values and check how many points become noise and how many clusters appear; eps around 0.3–0.6 is a sensible starting zone for standardized data.

Silhouette Score Intuition

The silhouette score judges a clustering without any labels. For each point i let a(i) be the mean distance to the other points in its own cluster and b(i) the mean distance to the points of the nearest other cluster. The silhouette of point i is:

s(i) = (b(i) - a(i)) / max(a(i), b(i))

s(i) ~ 1: the point is much closer to its own cluster than to any other — perfect placement.
s(i) ~ 0: the point sits on the boundary between two clusters.
s(i) < 0: the point is probably in the wrong cluster.

Averaging s(i) over all points gives a single number you can use to compare different K values (K-means), different linkages, or different eps values (DBSCAN), independent of the algorithm's own internal loss.

Which to use: K-means for fast, interpretable segmentation of large data; hierarchical clustering when you want a full merge tree and the dataset is small; DBSCAN when your clusters are oddly shaped or you specifically want to isolate outliers. Standardize features before all three.

Practice: generate or load the "blobs" and "moons" datasets from sklearn.datasets.make_blobs and make_moons. Run K-means, AgglomerativeClustering, and DBSCAN on both. Which algorithm recovers the true shapes of the moons, and which one fails? Compute the silhouette score for each result and explain whether the score agrees with what your eyes tell you.