9.2 K-Means

K-Means is the most popular clustering algorithm. You choose a number K of clusters, and the algorithm places K center points (centroids), assigns each data point to its nearest centroid, then moves each centroid to the average of its assigned points. It repeats these two steps until the centroids stop moving.

Think of organizing a market in Addis Ababa into 3 zones. You drop 3 flags, send each vendor to the nearest flag, then move each flag to the middle of its vendors. Repeat until the flags settle — that is exactly how K-Means finds its 3 groups.