Lab 02 — Unsupervised Learning: k-means + PCA via Power Iteration

Phase 32 · Lab 02 · Phase README · Warmup

The problem

Supervised learning has labels to tell it when it's wrong. Unsupervised learning doesn't — the algorithm has to find structure in X alone, and you have to decide whether the structure it found is real. The two structures that come up constantly in practice are groups (customer segments, anomaly clusters, embedding neighborhoods) and directions of variance (compression, visualization, decorrelation, noise reduction). The canonical algorithms for each — k-means and PCA — are one-liners in sklearn (KMeans(n_clusters=2).fit(X), PCA(n_components=2).fit_transform(X)), which is exactly why interviewers make you explain what's inside them: the objective being descended, why initialization decides everything for k-means, why the number one k-means bug is a silently-empty cluster, why PCA is an eigenvector problem, and how you get eigenvectors without calling numpy.linalg.eig.

You build both from scratch. For k-means: k-means++ initialization (a seeded, weighted draw that spreads the starting centroids), Lloyd's assign → update loop, the inertia objective it provably descends, empty-cluster repair, and a silhouette score to judge the result without labels. For PCA: center → covariance → power iteration — the "multiply and normalize" loop that converges to the dominant eigenvector — plus Hotelling deflation to peel off one component at a time, projection down, and reconstruction error to quantify what you threw away.

What you build

PieceWhat it doesThe lesson
kmeans_pp_initweighted D² draw over a seeded RNGinitialization quality decides which local optimum Lloyd's loop falls into
assign_clusters / update_centroidsthe two alternating halves of Lloyd's algorithmeach half provably lowers inertia — that's why k-means converges
empty-cluster repairrelocate a starved centroid to the farthest pointthe classic silent failure: k clusters requested, k−1 delivered
inertia + KMeansResult.inertia_historythe objective, recorded every iteration"did it converge" is a monotone curve you can assert on, not a vibe
silhouette_scorecohesion vs separation, (b−a)/max(a,b)how to evaluate clustering without ground-truth labels
center_data / covariance_matrixthe setup PCA actually runs onuncentered PCA finds the mean, not the variance
power_iterationdominant eigenvector by multiply-and-normalizeeigenvectors without linalg.eig; the same trick behind PageRank
deflate + fit_pcasubtract λvvᵀ, repeat for the next componentcomponents come out one at a time, variance-ordered
project / reconstruct / reconstruction_errordown to k dims and backthe error is exactly the variance you discarded

File map

FileRole
lab.pyyour implementation (fill the # TODOs)
solution.pyreference implementation + worked example (python3 solution.py)
test_lab.py28 tests: init determinism/spread, assign/update, empty-cluster repair, inertia descent, silhouette, covariance, power iteration, projection/reconstruction
requirements.txtpytest only

Run it

python3 -m pytest test_lab.py -q                     # your lab.py (red until you implement)
LAB_MODULE=solution python3 -m pytest test_lab.py -q # the reference (green)
python3 solution.py                                   # cluster 2 blobs + reduce 3-D data to 1-D

Success criteria

  • kmeans_pp_init is deterministic for a seeded random.Random, returns k actual data points, and lands its two picks in different blobs when the blobs are far apart.
  • assign_clusters picks the nearest centroid and breaks exact ties toward the lowest index.
  • update_centroids computes per-cluster means and repairs an empty cluster by relocating its centroid to the farthest point — never returns fewer than k centroids.
  • kmeans separates two well-separated blobs with 100% purity, its inertia_history is monotonically non-increasing, and the final two entries agree at convergence.
  • silhouette_score is high (>0.7) for clean blobs and higher for correct labels than for scrambled ones.
  • power_iteration recovers the dominant eigenvector/eigenvalue of a known matrix, with a deterministic sign convention.
  • fit_pca recovers the diagonal direction on data spread along y = x (alignment ≈ 1.0) and orders explained variance descending.
  • Projection outputs n × n_components; reconstruction error shrinks as components grow and is ~0 at full rank.
  • All 28 tests pass under both lab and solution.

How this maps to the real stack

  • sklearn.cluster.KMeans defaults to exactly this: init="k-means++", Lloyd's algorithm, inertia_ as the reported objective, and n_init restarts (run the whole thing several times, keep the lowest-inertia result) because k-means only finds a local optimum — our seeded single run is one of those restarts. Real implementations speed up the assign step with triangle-inequality pruning (Elkan's algorithm) and mini-batches (MiniBatchKMeans); the objective and the loop are unchanged.
  • Empty-cluster repair is real: sklearn relocates empty clusters to the points with the highest contribution to inertia — the same "farthest point" idea implemented here.
  • sklearn.metrics.silhouette_score is this exact (b−a)/max(a,b) formula; the single-member-cluster-scores-0 convention is sklearn's too.
  • sklearn.decomposition.PCA computes components via SVD of the centered data matrix rather than eigendecomposition of the covariance — numerically better, mathematically the same subspace. Power iteration is the mechanism inside the scalable variants: sklearn's PCA(svd_solver="randomized"), TruncatedSVD, and spark.ml's PCA all use power-iteration-family methods (randomized SVD / Lanczos), and PageRank is power iteration on the web's transition matrix.
  • explained_variance_ in sklearn is our eigenvalue list; explained_variance_ratio_ is it divided by the total — the number everyone actually quotes ("2 components keep 95%").
  • Embedding pipelines use exactly this stack: cluster sentence embeddings with k-means to find topic groups, PCA them to 2-D to plot, or PCA-truncate to cut vector-store dimensionality — the retrieval phases of this track consume these algorithms as black boxes; now they aren't.

Limits of the miniature. Real k-means uses multiple restarts and smarter distance pruning; ours is one seeded run over brute-force distances. Real PCA uses SVD (stable for ill-conditioned data, no explicit covariance matrix, which matters when dims are large); our explicit covariance is O(n·d²) and fine for d in the tens. Silhouette is O(n²) here and in real life — sample it on big datasets. Deflation accumulates floating-point error component by component; fine for the top few, not for hundreds.

Extensions (your own machine)

  • Add an elbow-method helper: run kmeans for k = 1..10, plot inertia vs k (text plot is fine), and find the knee.
  • Implement k-medoids (swap means for actual data points) and compare robustness to an outlier you inject.
  • Add explained_variance_ratio and pick n_components to reach 95% variance automatically.
  • Implement hierarchical agglomerative clustering (single/complete linkage) on the same blobs and compare the dendrogram cut against k-means labels.
  • Replace deflation with simultaneous (block) power iteration with Gram-Schmidt to extract several components at once.

Interview / resume signal

"Implemented k-means and PCA from first principles in pure Python: k-means++ seeded initialization with the D²-weighted draw, Lloyd's assign/update loop with monotone inertia tracking and empty-cluster repair, silhouette scoring without labels; PCA as center → covariance → power iteration with Hotelling deflation, verified against the known dominant direction, plus projection and reconstruction-error accounting — so KMeans.fit and PCA.fit_transform are APIs I can explain and debug, not incantations."