k-Means Clustering Assumptions

A common first impression of k-means is that it is a general-purpose grouping tool. You choose a number of clusters, the algorithm runs, and out come groups. Many learners carry an unstated assumption with them: if the number of clusters is right, k-means will recover the groups that are really present in the data. This article tests that assumption. The short answer is that k-means can miss the groups even when the number of clusters is correct, because the shape of its answer is fixed by how it measures distance to centers.

The number k tells k-means how many groups to produce. It does not tell the algorithm what shape those groups must have. Recovering the true groups requires that the regions k-means draws line up with the regions the data actually occupies. Those two things are separate. A correct k can still produce a wrong partition, because the partition is determined by the algorithm's built-in assumptions about cluster shape and size, not by the count alone.

k-means defines each cluster solely by its center. Each point is assigned by its distance to the nearest center. Because of this rule, the region belonging to each cluster is convex. The algorithm can only capture relatively simple shapes, since every cluster is effectively a region around one center. The diagram below shows the structure: two centers, and the boundary that falls between them.

The second assumption concerns size. k-means treats all clusters as having the same diameter in some sense. It always places the boundary between two clusters exactly in the middle between their centers. The midpoint rule is the direct consequence of nearest-center assignment: a point on the midpoint is equally far from both centers, so the boundary falls there.

That single rule explains many surprising results. If one cluster is tight and another is spread out, the midpoint boundary can cut through the spread-out cluster, even though the points near that boundary really belong to it. The algorithm does not look at how far a cluster extends. It only looks at where the center sits.

The first failure case involves clusters that differ in density. Imagine a dense region in the lower left, a dense region in the upper right, and a sparser region in the center. A human looking at this picture would likely name these three groups: the dense lower-left region as the first cluster, the dense upper-right region as the second, and the less dense central region as the third.

The source reports what happens when k-means is run on this kind of data. Cluster 0 and cluster 1 both contain some points that are far away from the other points in their own cluster and that reach toward the center of the plot. The algorithm has pulled the edges of the dense regions into neighboring clusters. The midpoint rule places the boundary between centers, and a sparse cluster's points that drift toward the middle get assigned to a neighbor whose center happens to be closer.

The second failure involves clusters that are not round. k-means also assumes that all directions are equally important for each cluster. Picture a dataset with three clearly separated parts, where each part is stretched along a diagonal rather than being a circle. The groups remain easy to see, but the stretching means that a point along the long axis of one group can be closer to the center of a neighboring group than to its own group's center.

The source states the reason plainly: k-means only considers the distance to the nearest cluster center, and it cannot handle this kind of data. A stretched group has no single center that represents all of its directions equally. The algorithm sees one center and one distance, so it cannot represent a group that extends far in one direction and little in another.

The third failure involves clusters with complex shapes. The source uses a two-moons dataset in which two interleaved half-circles form two groups. Visually, the correct answer is obvious: each half-moon is one cluster. Here we would hope that the clustering algorithm can discover the two half-moon shapes, but this is not possible using the k-means algorithm.

Because each cluster is convex and separated by a straight midpoint boundary, k-means cuts across the moons instead of separating them. The number of clusters is correct, so the failure has nothing to do with choosing k. The comparison below sets the expected grouping beside the grouping k-means produces.

When a clustering result looks wrong, the useful question is where it departs from what you expected. A reliable way to find that spot is to plot the predicted labels against the structure you believe is in the data, then check each region in turn. Start with the region that looks most mismatched.

In the varying-density case, the mismatch sits along the edges of the dense regions, where far-reaching points get pulled into a neighbor. That location is the diagnostic clue: the divergence concentrates where the midpoint boundary crosses a region that extends further than its center suggests.