Lesson 2.1
Grouping points
Before product quantization can replace a chunk with a representative, it needs a way to find good representatives. That method is k-means.
Find the natural clumps
Scatter a pile of points on a table and your eye instantly sees the clumps (groups of nearby points, called clusters). k-means is the recipe that lets a computer do the same, and pin one representative point (a centre, also called a centroid) at the average position of each cluster. That centre stands in for every point near it, and those centres are exactly the representatives the next unit will compress with.
The recipe alternates two moves until nothing changes. Assign: colour each point by its nearest centre. Update: slide each centre to the average position of the points that chose it. Repeat. Drag a centre below to feel the assignment redraw, then press Step to watch the two moves run.
Drag a centre, or press Step to let k-means move them
k-means repeats two steps: assign every point to its nearest centre, then move each centre to the average of its points. It stops when the centres settle.
Where the centres start matters
k-means always settles somewhere, but not always in the best somewhere. Start the centres in a bad spot, say all three bunched in one corner, and they can lock onto a poor split that the updates never escape. The standard fix is a smarter start called k-means++: place the first centre at random, then each next centre with a preference for points far from the centres already chosen. Spreading the seeds out avoids most bad endings.
Try it in the demo: drag all three centres into one corner, then press Step a few times and see whether they recover or get stuck.
Key takeaways
k-means finds cluster centres by alternating assign (nearest centre) and update (move to the average).
It stops when the centres stop moving, which usually takes only a handful of rounds.
A good start (k-means++) spreads the seeds out and avoids most poor endings.