\( \newcommand{\vect}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\mat}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\mathbb{E}} \newcommand{\Prob}{\mathbb{P}} \newcommand{\T}{^{\top}} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\ihat}{\mkern1mu\hat{\boldsymbol{\imath}}\mkern2mu} \newcommand{\jhat}{\mkern1mu\hat{\boldsymbol{\jmath}}\mkern2mu} \newcommand{\pd}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\argmax}{\operatorname*{arg\,max}} \newcommand{\argmin}{\operatorname*{arg\,min}} \newcommand{\cdata}[1]{\class{c-data}{#1}} \newcommand{\cmodel}[1]{\class{c-model}{#1}} \newcommand{\ctruth}[1]{\class{c-truth}{#1}} \newcommand{\cgrad}[1]{\class{c-grad}{#1}} \newcommand{\closs}[1]{\class{c-loss}{#1}} \newcommand{\cparam}[1]{\class{c-param}{#1}} \newcommand{\csecond}[1]{\class{c-second}{#1}} \renewcommand{\,}{\mkern3mu} \)

ML03.1 · k-means and how it fails

A free, illustrated module of 4 lessons and one interactive in ML03 Unsupervised Learning: Clustering as an objective; Lloyd’s algorithm; Starting well and choosing K; How k-means fails.

ML03.1 L2 · Intermediate 4 lessons · about 100 min Live · in review

Part of ML03 Unsupervised Learning in the Machine Learning track.

With no labels to check against, a clustering has to be judged by a score. These four lessons build k-means from its score up: the sum of squared distances from points to their centres and the two facts that minimise it, Lloyd’s algorithm that alternates them and its proof of descent, k-means++ and several starts for escaping poor local minima, the elbow for choosing K, and then the data on which even the best score is the wrong answer, with k-medoids as a first repair.

What you need first. Distances, standardising features and k-nearest neighbours (ML01.3), and partial derivatives and the gradient (M04.10). NumPy arrays and broadcasting help for the code.

Lessons

1. Clustering as an objective ML03.1.1 25 min

   With no labels to check against, a clustering has to be judged by a score. Meet the k-means objective J, the sum of squared distances from points to their centres, and derive its two facts: the best centre is the mean, and the best cluster for a point is its nearest centre.

2. Lloyd’s algorithm ML03.1.2 25 min

   Alternate the two facts of k-means: assign every point to its nearest centre, then move every centre to the mean of its points. Prove that J never goes up and that the algorithm stops, trace it by hand on nine points, and see why it can stop at a local minimum.

3. Starting well and choosing K ML03.1.3 25 min

   Where Lloyd’s algorithm starts decides where it stops. Seed it with k-means++, which spreads the first centres out, run it from several starts, read the elbow of J against K for a bend rather than a minimum, and quantise the colours of a photo with MiniBatchKMeans.

4. How k-means fails ML03.1.4 25 min

   k-means looks for round clusters of similar spread and size, because J measures squared distance to a single centre. See each failure beside the right answer, with stretched blobs, moons, unequal spreads, mixed units and an outlier, and meet k-medoids and its PAM swap step.

The interactive

ML03.1-X1 · k-means stepper. Choose a data set and K, place centres by clicking or by random or k-means++ seeding, and run Lloyd’s algorithm half a step at a time, with the Voronoi cells tinted, each centre’s move drawn as an arrow and J printed after every half-step. Drag points to see the cells react. It lives in Lloyd’s algorithm.