Pick k centroids, then repeat two steps: give every point to its nearest centroid, and move every centroid to the mean of its points. Each step can only lower the total squared distance, so the clusters settle, usually within a few rounds.
Pick k centroids, then repeat two steps: give every point to its nearest centroid, and move every centroid to the mean of its points. Each step can only lower the total squared distance, so the clusters settle, usually within a few rounds.