Cluster Shape and Density
k-means never measures how spread out a cluster is. It only measures where points sit relative to centers. Any structure that depends on spread, density, or direction is invisible to the boundary rule.
A Belief Worth Testing
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 groups come out. 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.
What do you think happens?
If you pick the correct number of clusters for a dataset that really has three groups, will k-means always find those three groups?
Reveal answer
No, k-means can miss the real groups even when k is correct.
The shape of k-means's answer is determined by how it measures distance to centers. Choosing k only sets how many centers exist; it does not change the shape of the regions those centers carve out.
Tracing Where a Point Gets Its Label
k-means defines each cluster solely by its center. To label a point, the algorithm measures the distance from that point to every center and assigns the point to the nearest one. Walk through a small case by hand before thinking about any larger dataset.
Labeling a point between two centers
Two centers sit on a horizontal line: Center A at position 0 and Center B at position 10. A new point sits at position 6. Which cluster does it join?
- 1Measure distance to Center A
The point at 6 is 6 units from the center at 0.
- 2Measure distance to Center B
The point at 6 is 4 units from the center at 10.
- 3Compare and assign
Center B is closer, so the point joins Center B. Its label is decided by which center is nearer, not by any property of the point itself.
- 4Locate the boundary
The point at 5 is exactly 5 units from each center. Every point left of 5 joins A and every point right of 5 joins B. The dividing line sits exactly halfway between the two centers.
The point at 6 joins Center B, and the boundary between the two clusters is the midpoint at 5.
The key idea is that the boundary is not drawn by looking at the spread of the points. It is drawn by the centers alone. Whatever the points look like, the dividing line stays midway between the two centers, so every point is assigned by the same rule.
Convex Regions and the Equal-Diameter Rule
Because each cluster is defined only by its center and points go to the nearest center, the region belonging to each cluster is convex. A region is convex when you can connect any two of its points with a straight line that stays inside the region. A cluster can therefore only be a shape you could fill by drawing straight lines between any two of its points. This is why the algorithm captures only relatively simple shapes.
The second assumption concerns size. k-means treats clusters as if they have a similar diameter, in the sense that the boundary between two clusters always falls exactly in the middle between their centers. 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.
k-means never measures how spread out a cluster is. It only measures where points sit relative to centers. Any structure that depends on spread, density, or direction is invisible to the boundary rule.
Three Ways the Assumptions Break
The convex-shape and equal-diameter assumptions lead to three recognizable failure situations. Each one looks different on a plot, but each traces back to the same midpoint rule. The three cases are taken in turn below.
Locating the Divergence in a Result
When a clustering result looks wrong, the useful question is where it departs from what you expected. A reliable approach is to plot the predicted labels against the structure you believe is in the data, then check each region in turn. Begin with the region that looks most mismatched. Ask whether the points there are close to their assigned center, and whether a neighboring center is nearly as close. If a neighboring center is almost as close, the point sits near the midpoint boundary and is a likely source of the mismatch.
A predicted result splits one of two half-moons across both predicted clusters. Name the expected grouping, name the predicted grouping, and state the location in the plot where the mismatch sits. Then say whether choosing a different k would fix it.
Hints
- Compare each expected moon with the predicted labels that appear on it.
- Ask whether the cut follows a straight midpoint boundary or the curve of the moon.
- Remember that the failure happens even when the number of clusters is correct.
Mistakes When Reading a Clustering Result
Common mistake Assuming that the correct number of clusters guarantees the expected groups
What it looks likeA dataset has three real groups and k is set to 3, yet the output still cuts a group in two.
Why it failsk only sets how many centers exist. The boundary between centers is always the midpoint, so the shape of the answer is fixed regardless of k.
Do this insteadTreat a wrong-looking result as a question about shape and density, not only about k.
Common mistake Believing a dense cluster is protected from neighboring labels
What it looks likeThe edge points of a dense cluster are assigned to a neighboring label even though they clearly belong to the dense region.
Why it failsAssignment depends on which center is nearer. Far-reaching points of a dense cluster can end up closer to a neighboring center.
Do this insteadCheck the edge points of each dense region against the nearest neighboring center.
Common mistake Reading the boundary as a property of the data
What it looks likeLooking at the output and concluding the data has a straight-line divide between two groups.
Why it failsThe straight boundary is drawn by the midpoint rule between centers, not discovered from the spread of points.
Do this insteadAsk what the centers are, then ask whether the true groups could be separated by a straight midpoint line.
Common mistake Thinking a stretched cluster is two clusters because its points lie far from one center
Predicting the Boundary Before the Result
What do you think happens?
One cluster is very tight and a neighboring cluster is widely spread out. Where does k-means place the boundary between them, and can it cut through the spread-out cluster?
Reveal answer
The boundary sits exactly midway between the two centers, and yes, it can cut through the spread-out cluster.
The midpoint rule does not account for spread. A tight cluster and a spread-out cluster get the same midpoint boundary, so points of the spread-out cluster that lie near that line can be assigned to the tight cluster's neighbor.
Key Takeaways
- k-means defines each cluster solely by its center, so each cluster's region is convex and the algorithm captures only relatively simple shapes.
- The boundary between two clusters is always placed exactly midway between their centers, which assumes clusters have a similar diameter.
- Three failure situations follow: clusters with different densities, stretched or non-spherical clusters, and complex shapes such as two interleaved half-moons.
- Choosing the correct number of clusters does not guarantee the expected grouping, because the shape of the answer is set by distance to centers.
- To locate a divergence, compare predicted labels with the structure you expect, starting from the region that looks most mismatched and checking points near the midpoint boundary.