§ 8. Unsupervised Learning & Evaluation

1. Overview

Unsupervised learning discovers structure in data without labels — clustering groups similar examples, while dimensionality reduction finds compact representations. Evaluation metrics and cross-validation then answer the orthogonal question: once we have a model (supervised or not), how do we measure and select it without fooling ourselves? These two halves of this page are complementary: good clustering features feed good classifiers; good evaluation practice separates papers that generalise from papers that overfit their test set.

2. Clustering Algorithms

K-Means

K-means minimises the Within-Cluster Sum of Squares (WCSS):

WCSS = Σ_{k=1}^K Σ_{x ∈ C_k}  ‖x − μ_k‖²

The algorithm alternates between two steps: assign each point to its nearest centroid (Voronoi partition), then recompute each centroid as the mean of its assigned points. Both steps guarantee WCSS cannot increase, so the algorithm always converges — but to a local minimum. k-means++ initialization (spread initial centroids proportional to squared distance from existing ones) dramatically reduces the chance of a bad local minimum.

Choosing k: Plot WCSS vs k (the "elbow" curve). The elbow point is where adding another cluster yields diminishing returns. Silhouette score offers a principled alternative: it measures how much tighter each point fits its own cluster vs the nearest other cluster (range −1 to +1; higher = better).

Limitations: Assumes spherical, equal-size clusters; sensitive to outliers; must specify k in advance; not deterministic (random init).

Gaussian Mixture Models (GMM) via EM

GMM models the data as a weighted sum of Gaussians:p(x) = Σ_k π_k · N(x; μ_k, Σ_k). Unlike K-means (hard assignment), GMM assigns soft responsibilities — a point near two cluster boundaries belongs fractionally to each. The Expectation-Maximization (EM) algorithm maximises the log-likelihood by alternating between computing responsibilities (E-step) and updating parameters (M-step).

GMM generalises K-means: setting all covariances to σ²I and taking the hard-assignment limit recovers K-means exactly. Full covariance matrices allow the model to capture elliptical clusters. The BIC / AIC criteria help select K.

DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) does not require specifying k. A point is a core point if at least min_samples points lie within radius eps. Clusters grow by connecting core points that are density-reachable. Points reachable from no core point are labelled noise (−1). This makes DBSCAN robust to outliers and able to find arbitrarily shaped clusters — something K-means and GMM cannot do.

Hierarchical Clustering

Agglomerative hierarchical clustering starts with each point as its own cluster and greedily merges the two closest clusters (by linkage criterion) until one cluster remains. The result is a dendrogram — cut it at any height to get the desired k. Linkage options: single (min distance, chain-like clusters), complete (max distance, compact), average (UPGMA), and Ward (minimises WCSS increase on merge — produces compact, spherical clusters similar to K-means but hierarchically).

3. Dimensionality Reduction

PCA — Principal Component Analysis

PCA finds the orthogonal directions of maximum variance in the data. The first principal component (PC1) is the unit vector v that maximisesVar(Xv) = v^T Cov(X) v, subject to ‖v‖=1. The solution is the eigenvector of the covariance matrix with the largest eigenvalue. In practice, computing the covariance matrix explicitly is numerically unstable for high-D data; instead we use the SVD of the centered data matrix, which is equivalent and more numerically stable.

Why SVD equals PCA: The covariance matrix isC = (1/N) X_c^T X_c. If X_c = U S V^T, thenC = (1/N) V S^2 V^T. The columns of V are the eigenvectors of C (principal axes), and the eigenvalues areλ_j = s_j² / N. So running SVD on X_c gives PCA for free — no explicit covariance computation needed.

t-SNE

t-SNE (van der Maaten & Hinton, 2008) is a non-linear embedding method designed for visualisation. It converts pairwise high-dimensional distances into conditional probabilities (using a Gaussian kernel with bandwidth tuned by perplexity), then minimises the KL divergence between those high-D probabilities and low-D Student-t probabilities. The heavy tails of the Student-t prevent the "crowding problem" — nearby clusters stay separated even when mapping from hundreds of dimensions to 2D.

UMAP

UMAP (McInnes et al., 2018) is grounded in Riemannian geometry and fuzzy simplicial sets. In practice it is 5–100× faster than t-SNE, better preserves global structure (macro-level relationships between clusters), and supports both unsupervised and semi-supervised modes. It is the preferred choice for production pipelines that need reproducible, interpretable 2D/3D embeddings (e.g., token-space visualisation, anomaly detection, nearest-neighbour retrieval).

4. Minimal Demo — PCA via SVD

The demo below implements PCA entirely from scratch using torch.linalg.svd. Three clusters hidden in a 4D space are correctly separated in the 2D PCA projection. Watch the explained variance ratios — PC1+PC2 should capture ≈ 90 % of variance because the data was deliberately generated with only 2D signal.

5. Evaluation Metrics

Confusion Matrix Basics

All binary classification metrics derive from four counts that depend on a decision threshold θ:

Accuracy  = (TP + TN) / N
Precision = TP / (TP + FP)        ← "of all alarms, how many were real?"
Recall    = TP / (TP + FN)        ← "of all positives, how many did we catch?"
F1        = 2 · P · R / (P + R)   ← harmonic mean; punishes extreme imbalance
FPR       = FP / (FP + TN)        ← false alarm rate (x-axis of ROC)

These metrics all depend on the threshold θ. To get a threshold-independent summary we sweep θ across all possible values and plot either the ROC curve (FPR vs TPR) or the PR curve (Recall vs Precision).

Calibration & Brier Score

A model is calibrated if its predicted probability p̂ = 0.7 means "this event happens 70% of the time". A reliability diagram bins predictions by p̂ and plots mean p̂ vs empirical fraction — a perfectly calibrated model falls on the diagonal. Models trained with cross-entropy tend to be better calibrated than margin-based models (SVM, RF), which often need Platt scaling or isotonic regression post-processing.

The Brier score is a proper scoring rule that measures both accuracy and calibration simultaneously:

Brier = (1/N) Σ_i (p̂_i − y_i)²     [0 = perfect, 0.25 = random, 1 = perfectly wrong]

Brier score is lower-bounded at 0 and decomposable into reliability + resolution − uncertainty. Use it when downstream decisions depend on calibrated probabilities (e.g., risk scoring, A/B test power calculations, cost-sensitive decisions).

6. Minimal Demo — Metrics Calculator

The demo simulates 50 binary predictions (20 positives, 30 negatives) and computes the full confusion matrix, P/R/F1/Acc at six thresholds, AUC-ROC via the trapezoidal rule, and the Brier score — all in plain Python with zero imports beyond random. Notice how precision rises and recall falls as the threshold increases.

7. Cross-Validation & Model Selection

k-Fold CV

Standard k-fold CV partitions the dataset into k equal folds, trains k times each leaving one fold out as the validation set, and averages the k scores. This gives a nearly unbiased estimate of generalisation performance while using all data for evaluation. Common choices: k=5 (good variance/bias tradeoff), k=10 (slightly lower bias, higher compute), leave-one-out (k=N, high variance on small datasets).

Stratified k-Fold

For imbalanced classification (e.g., 5% positive class), standard k-fold may place all positives in one fold by chance. Stratified k-fold ensures each fold has the same class proportion as the full dataset. Always use stratified CV for binary classification unless the dataset is large (> 10k per class).

Time-Series CV

For time-ordered data (stock prices, logs, sensor streams), standard k-fold is invalid: it uses future data to train models that predict the past. Use the walk-forward (expanding window) or sliding windowscheme instead: always train only on data before the validation window.

Walk-forward (expanding window):
  Train=[t0..t1]       Val=[t1..t2]
  Train=[t0..t2]       Val=[t2..t3]
  Train=[t0..t3]       Val=[t3..t4]

Sliding window:
  Train=[t0..t1]       Val=[t1..t2]
  Train=[t1..t2]       Val=[t2..t3]

Nested CV (Unbiased Hyperparam + Eval)

If you use k-fold both to select hyperparameters and to report final accuracy, the reported score is optimistically biased (the validation folds were used to make model choices). Nested CV wraps an inner loop (hyperparameter selection) inside an outer loop (final score estimation):

Outer loop (k_out=5 folds — estimates generalisation error):
  for each outer fold j:
    Inner loop (k_in=3 folds on outer TRAIN split — selects best hyp):
      grid search over C, gamma, ...
      pick best_params_j
    Train final model on outer TRAIN with best_params_j
    Evaluate on outer VAL → score_j
Final estimate = mean(score_1..5)    ← unbiased

Nested CV is expensive (5 × 3 = 15 training runs per grid point) but is the gold standard for unbiased model comparison on small datasets. On large datasets (> 100k samples) a simple train/val/test split is usually sufficient.

8. Common Pitfalls

Data Leakage

Data leakage occurs when information from the validation/test set flows into model training. The result is an inflated training-time metric that collapses in production.

Label Noise

Label noise (mislabelled examples) inflates test error and makes learning harder. Detecting it: look for high-confidence wrong predictions from an ensemble, or use "cleanlab" / confident learning to flag suspicious labels. Mitigation: label smoothing (replaces hard 0/1 targets with ε/K), noise-robust loss functions (symmetric cross-entropy), or semi-supervised re-labelling.

Train/Test Contamination

A related but distinct problem: if the same entity appears in both train and test (e.g., the same user ID, same image with minor augmentation, same news article with different timestamps), the model learns to recognise the entity rather than the pattern. Fix: split at the entity level, not at the sample level.

9. Feature Engineering for Tabular Data

Still critical in production tabular ML (fraud detection, recommendation ranking, search). Deep learning has not displaced feature engineering for structured data with < 1M rows.

10. Production / Source Pointers

11. References

Papers

• van der Maaten & Hinton (2008) — Visualizing Data using t-SNE, JMLR 9.
• McInnes, Healy & Melville (2018) — UMAP: Uniform Manifold Approximation and Projection (arXiv:1802.03426)
• Ester et al. (1996) — A Density-Based Algorithm for Discovering Clusters (DBSCAN), KDD.
• Arthur & Vassilvitskii (2007) — k-means++: The Advantages of Careful Seeding, SODA.
• Dempster, Laird & Rubin (1977) — Maximum Likelihood from Incomplete Data via the EM Algorithm, JRSS-B.
• Platt (1999) — Probabilistic Outputs for SVMs (Platt scaling calibration).

Lectures

• Stanford CS229 — Andrew Ng: Lecture Notes on EM, PCA, k-Means (freely available)
• CMU 10-701 / 15-781 — Tom Mitchell / Eric Xing: Unsupervised Learning slides
• Caltech CS156 — Yaser Abu-Mostafa: Learning From Data (lecture 12 on validation)
• Oxford ML Hilary — Lecture 8: Clustering & Dimensionality Reduction
• MIT 6.036 — Lecture 10: Unsupervised Learning

Textbooks

• Hastie, Tibshirani & Friedman — The Elements of Statistical Learning, Ch. 13–14 (free PDF at web.stanford.edu/~hastie/ElemStatLearn)
• Bishop — Pattern Recognition and Machine Learning, Ch. 9 (EM), Ch. 12 (PCA)
• Murphy — Probabilistic Machine Learning: An Introduction, Ch. 20–22
• James et al. — Introduction to Statistical Learning with R/Python, Ch. 12

Code / Repos

• scikit-learn — sklearn.cluster, sklearn.decomposition, sklearn.model_selection
• umap-learn — github.com/lmcinnes/umap
• cleanlab — github.com/cleanlab/cleanlab — confident learning for label noise

Blog Posts

• distill.pub — How to Use t-SNE Effectively (Wattenberg et al., 2016)
• Sebastian Raschka — Model Evaluation, Model Selection, and Algorithm Selection in Machine Learning
• Andrej Karpathy — A Recipe for Training Neural Networks (covers leakage / overfit debugging)

12. Interview Prep