K-Means, Distance, and Iteration

K-means is one of the simplest algorithms for understanding how clustering can emerge from repeated computation.

The user chooses k, the number of clusters. The algorithm then repeats two operations:

1. assign each point to its nearest centroid;
2. update each centroid to the mean position of the points assigned to it.

The cycle continues until the assignments stabilize or another stopping rule is reached.

The centroids are summaries

A centroid is not necessarily a real observation. It is the average location of a cluster in feature space.

If three one-dimensional points are 2, 4, and 9, their centroid is:

(2 + 4 + 9) / 3 = 5

No original point has value 5, but 5 summarizes the group under the mean.

In two dimensions the same idea applies to both coordinates.

Choosing k changes the question

If you run the same data with k = 2 and k = 4, you are asking the algorithm to create different numbers of groups. It should not surprise us when the output changes.

That is why “the algorithm found four clusters” is incomplete unless the method and k are documented.

Initialization and outliers matter too

Different starting centroids can lead to different final groupings. Unusual points can also pull a centroid away from the dense region it is supposed to summarize.

Production libraries often use better initialization strategies and repeat the algorithm to reduce these problems, but the conceptual boundary remains: the result depends on choices made by the analyst and the data representation.

Before moving on

Describe the assign-and-update loop in your own words. Then predict what an extreme outlier might do to the mean location of one cluster.