k-means: objective, initialization, empty clusters and instability

k-means is the first clustering mechanism and the initializer inside Gaussian mixtures. Its objective only descends, never to a global promise, so seeds and \(k\) decide the answer.

derive
implement

You can now

Derive the assignment and centroid updates and show each step cannot increase the inertia.
Implement Lloyd iterations from a blank file with k-means++ seeding and a fixed iteration cap.
Diagnose empty clusters, seed instability and \(k\) choice with inertia, silhouette and repeated runs.

Covers

k-means objective, assignment, update and initialization
Empty clusters, inertia and seed instability

Study, in this order

3 steps

k-means mechanics and k search
Hands-On Machine Learning with Scikit-Learn and PyTorch - dimensionality reduction and unsupervised learning

Book Chapter 8: k-Means Clustering (printed pp. 249-258). Notebook 08 cells: K-Means through Finding the optimal number of clusters: blob demo, the max_iter assignment and update walk, Inertia, Multiple Initializations with the n_init auto rule, k-means++ seeding, elbow plot and silhouette_score with the silhouette diagram

Depth · Skim Accelerated K-Means and Mini-Batch K-Means; keep the max_iter walk and the k-search plots.

Done
k-means objective and cluster evaluation
scikit-learn - decomposition, clustering and outlier detection

2.3.2 K-means: inertia objective, local minima with repeated initializations, k-means++ default; 2.3.11 cluster evaluation: silhouette coefficient \(s=(b-a)/\max(a,b)\) with its convex-cluster bias and the adjusted Rand index correcting for chance

Done
k-means on simulated data
ISLP - Unsupervised Learning

K-Means Clustering: \(K=2\) separation on the simulated 50-point data with random_state, \(K=3\) splitting behavior, and inertia_ as within-cluster sum of squares

Depth · The lab says the n_init default is 10; that predates scikit-learn 1.4. The default is now auto, one run under k-means++, which is why the lab passes n_init=20 explicitly.

Done

Focus on

Each assignment step and each mean update cannot increase the inertia, so Lloyd iterations converge, usually to a local minimum. Restarts pick among minima.
Since version 1.4 the default n_init=auto runs once under k-means++ and ten times under random init. One k-means++ run is not ten restarts.
Inertia always falls as \(k\) grows. Read \(k\) from elbows, silhouette and repeated-seed stability, never from one inertia value.
Empty clusters happen when a center loses every point. Know the repair: re-seed, drop, or error.

Reproduce closed-book

Closed-book, run one Lloyd round on \(\left[\begin{smallmatrix}0&0\\0&1\\5&0\\5&1\end{smallmatrix}\right]\) from centers \(\left[\begin{smallmatrix}0&0\\5&1\end{smallmatrix}\right]\): labels \(\left[\begin{smallmatrix}0&0&1&1\end{smallmatrix}\right]\), new centers \(\left[\begin{smallmatrix}0&0.5\\5&0.5\end{smallmatrix}\right]\), inertia 2.0 down to 1.0. State why the next round cannot raise it.

Traps

Comparing inertia across different k or seeds as quality. Inertia is comparable only for fixed data, fixed \(k\) and best-of-restarts.
Assuming n_init=10 always. Under the default k-means++ the auto default is a single run; set n_init=10 explicitly when stability matters.
Requesting more clusters than samples. scikit-learn 1.9 raises an error for n_samples=3 with n_clusters=5; it does not return empty clusters silently.

Practice

Deep-ML 17: K-Means Clustering

Problem 17: implement k_means_clustering(points, k, initial_centroids, max_iterations) returning centroids rounded to 4 decimals

The tests check exact centroids on a 2D two-group set and a 3D set from fixed starts. Re-derive one update by hand first, then match.

Self-test

Why do Lloyd iterations terminate?
Two seeds give inertia 120 and 95 at \(k=5\). Which clustering wins on the objective, and what stays unknown?
A center gets no points in one iteration. Name two sound repairs.
Silhouette prefers \(k=2\) on two stretched blobs while the task needs subgroups. What do you do?

Completion criterion

Stop when

Your implementation reproduces the hand round exactly, matches both Deep-ML centroid sets, and reports inertia spread across ten seeds for your \(k\).

Mark passed, then open 4.5 Only mark this when you can do it without notes.

Leads to

4.5 Gaussian mixtures and EM Soften hard assignments into responsibilities.
4.6 DBSCAN, agglomerative clustering and cluster validation Contrast partition geometry with density and merge geometry.

Comes after

4.3 PCA via SVD: directions, explained variance and sign ambiguityCluster in PCA space and compare stability with and without reduction.

Resources for this unit

Hands-On Machine Learning with Scikit-Learn and PyTorch - dimensionality reduction and unsupervised learning
Aurelien Geron (O'Reilly, 2025)primarycourse
Read Chapters 7 and 8 and run notebooks 07 and 08 for PCA, k-means, DBSCAN, agglomerative clustering, Gaussian mixtures and anomaly detection. Stop before extended semi-supervised and face-data projects.
scikit-learn - decomposition, clustering and outlier detection
scikit-learnreferencereference
Check decomposition orientation and solver behavior, cluster API semantics, and the distinction between novelty and outlier detection after the independent tests pass.
ISLP - Unsupervised Learning
James, Witten, Hastie, Tibshirani and Taylorrequiredtheory
Use Chapter 12 and its Python lab for the PCA derivations (12.2, including the low-rank approximation view and proportion of variance explained) and k-means (12.4.1), plus stability and interpretation limits, beside the notebook route.

Also in this section

Deep-ML - unsupervised problems
Deep-MLsupportpractice
Use 17 K-Means Clustering, 19 PCA, 341 Gaussian Mixture Model with EM, 259 DBSCAN and 367 Isolation Forest as unit checks after the local implementation passes. Their tests were read in review; each card states what they pin, including the 367 path-length convention.
scikit-learn - preprocessing data
scikit-learnreferencereference
Read 8.3.1 standardization with the sparse with_mean=False rule, 8.3.1.3 scaling data with outliers, and 8.3.4 categorical encoding with handle_unknown, infrequent and sparse_output behavior. Apply after the HOML notebook build works.
scikit-learn - pipelines and composite estimators
scikit-learnreferencereference
Read 8.1.1 Pipeline chaining with the no-leakage rule and transformer caching, and 8.1.4 ColumnTransformer for heterogeneous columns with remainder and fitted-state behavior. Use it to assemble and serialize the feature-selection pipeline.
scikit-learn - imputation of missing values
scikit-learnreferencereference
Read 8.4.2 univariate median and most_frequent strategies, 8.4.6 Marking imputed values with MissingIndicator or add_indicator=True for missingness flags, and 8.4.7 estimators that accept NaN directly. Decide impute-only versus impute-plus-indicator per column.
UMAP - basic usage and parameters
McInnes, Healy and the UMAP contributorsreferencereference
Work the Penguin scaling and fit_transform section and the Digits fit and transform section, then read the parameters page for the n_neighbors local-global tradeoff and min_dist packing. Stay in 2D exploratory views with fixed seeds.