k-Means Clustering

Pick k points to act as centres, assign every example to its nearest one, move each centre to the mean of what it caught, and repeat. It converges quickly, and it converges to something that depends on where the centres started. Despite the name it has nothing to do with k-nearest-neighbours: this groups unlabelled data, that one classifies using labels.

Lloyd's algorithm alternates assignment and update, and each step lowers the objective, so it always converges — to a local minimum. Initialisation is therefore the whole ballgame, which is what spreading the initial centres is for. It also assumes clusters are roughly spherical and of similar size, and it fails quietly rather than loudly when they are not.

Minimise Σ sub _i  ‖x sub _i  − μ sub _c(i) ‖² over assignments c and centres μ. Each iteration costs Θ(nkd) and the objective decreases monotonically, but the problem itself is NP-hard — so what converges is a local optimum, and the iteration count is small in practice and unbounded in theory.