K-Means, Its Failure Modes, and Gaussian Mixture Models

Clustering looks for useful groups when the data has no group label. K-means is often the first method an analyst tries because its loop is fast, concrete, and easy to inspect. But its answer contains assumptions. Today we will run that loop, break those assumptions on purpose, and then see what a Gaussian mixture adds. Think of each dot as one row of a data set and each axis as one measured feature. Clustering asks whether rows that sit near one another should be treated as members of the same group. K-means gives a hard answer. Each observation belongs to exactly one cluster, represented by one centre. The rule is simply: choose the nearest centre. A Gaussian mixture can give a softer answer. Instead of one cluster label, it gives one probability for every component. Those probabilities express uncertainty about observations near an overlap. That distinction matters operationally. A hard label is convenient for routing or summarizing records. A probability is useful when a borderline case should remain borderline rather than being forced across a sharp boundary. We will not treat the more flexible model as automatically better. K-means has fewer parameters and is often exactly the right baseline. The point is to know what geometry it can represent, what failures to expect, and when extra probability and covariance parameters have a real job to do.

Here is our concrete problem. We have twelve observations, two features, and a requested value k equals two. The algorithm must return two clusters. First put the data on the plane. At this stage the points have no fitted cluster identity. K-means needs starting centres. These two are deliberately away from the middle of the groups. They are guesses, not observations and not yet fitted means. The assignment step examines every observation. For each centre, compute squared Euclidean distance across the features, then give the observation to the centre with the smaller total. After that comparison, these six points belong to the red centre and these six belong to the green centre. The colour is the hard cluster label z. Now freeze the assignments and update one centre at a time. The new red centre is the coordinate-wise mean of the six red observations. The green centre is calculated in exactly the same way from the green observations. A centre is therefore a fitted average, not necessarily a row that actually occurs in the data. Move both centres to those means. As the centres travel, the assigned observations stay fixed. When the centres arrive, one full k-means pass is complete. Then repeat. With the centres in their new positions, calculate every nearest-centre assignment again. In this example every point keeps its colour. Recomputing the two means therefore returns the same two centres. The second pass changes neither the assignments nor the centres. That is convergence. Implementations may stop when assignments are identical, when centre movement is below a tolerance, or when a maximum iteration count is reached. The loop is alternating optimization. With centres fixed, nearest-centre assignment cannot increase the within-cluster sum of squares. With assignments fixed, replacing each centre by its mean cannot increase it either. So the objective falls or stays level on every pass. Because only finitely many hard assignments exist, the procedure eventually stops. What this does not prove is that it found the best possible clustering. It may have stopped at a merely local solution.

K-means can finish at different answers on the same data because its objective is not generally convex in all assignments and centres together. Here are two runs with k equal to three. On the left, the starting centres are spread across the visible groups. On the right, an unlucky draw crowds all three starting centres into the left-hand group. Run the same assignment and update loop on both sides. The favourable start settles with one centre in each visible group. The unlucky run spends two centres splitting the left group. Its remaining centre absorbs both right-hand groups, even though they are visibly separated. Another pass changes neither answer. Both are local solutions, but the right-hand solution has a larger within-cluster sum of squares and a much less useful interpretation. The practical remedy is not to trust one random start. K-means++ spreads seeds by favouring observations far from centres already chosen. It reduces bad starts, but does not abolish local minima. For routine analysis, make initialization part of the specification. Use a dispersed seeding rule, then run many independent starts. Retain the run with the lowest objective, but still inspect its groups. A numerical improvement can be immaterial, and several nearly tied runs can imply genuine ambiguity in the data. Record the number of starts, the random seed, and the spread of objective values. Reproducibility here is not clerical detail. It is evidence about how strongly the data supports the fitted partition.

The nearest-centre rule creates Voronoi cells: regions separated by straight boundaries. That simple geometry explains several important failures. First, consider two long natural groups. Their gray outlines run diagonally across the feature space. With these fitted centres, nearest-centre assignment makes a nearly vertical cut. Red and green divide both long groups across their length rather than following the two elongated densities. K-means has a centre for location, but no parameter for orientation or different spread in different directions. Squared Euclidean distance therefore prefers compact, roughly spherical clusters. Second, place one small dense cluster beside one large diffuse cluster. The gray circles show the intended populations. The large group contributes many more squared distances to the objective. A centre can reduce that cost by moving toward it, while the boundary gives part of the large group to the small cluster. The result is mathematically consistent with the objective, but unfair to the smaller group as a density. K-means does not model cluster population or variance separately. Third, this is one connected cloud without three clear density peaks. We nevertheless request k equals three. K-means does not answer that the data contains one group. It returns exactly three nonempty partitions because three centres were requested. This is not a software defect. The value k is an input to the problem, not a conclusion reached by the algorithm. A tidy colour map does not prove that the corresponding groups exist. Before believing a k-means result, ask whether compact clusters are plausible in the scaled feature space, and whether their spreads and populations are comparable. Then test stability across initializations and resampled data. Finally, ask what k means in the business or scientific setting. If it has no interpretation, treat it as a modelling choice to validate, not a fact discovered by the colours.

To relax hard assignment, keep one membership number for every component. For observation i and component j, call that number the responsibility r i j. Consider this observation near the overlap. A hard rule must choose one side. The mixture instead evaluates how plausible the observation is under both fitted components. Suppose the resulting responsibilities are zero point three five and zero point six five. The second component is more plausible, but the first remains credible. The two values add to one. These are model-based probabilities, not calibrated truth supplied by the data. They depend on the fitted component shapes, their population weights, and the Gaussian mixture assumptions. A Gaussian mixture says that the observed density is a weighted sum of Gaussian component densities. The extra parameters each answer a distinct question. The mixture weight pi records the expected share of observations generated by a component. Unlike k-means, the model can explicitly represent one large component and one small component. The mean mu gives location, much like a k-means centre. Here the two means sit near the middle of their respective densities. The covariance matrix Sigma is the crucial addition. Its overall scale controls spread. Its unequal directional variances create elongation, and its off-diagonal relationship rotates that elongation. These ellipses are equal-density contours. They can follow the long axes of the two groups, which is exactly the geometric freedom missing from nearest-centre k-means. The usual fitting procedure alternates two weighted steps. In the E step, use the current weights, means, and covariances to compute every responsibility. In the M step, treat those responsibilities as fractional counts. Update each mixture weight from its total responsibility. Update each mean as a responsibility-weighted average. Then update each covariance from weighted deviations around that mean. Repeat the two steps until log likelihood no longer improves materially. Like k-means, this alternating fit can reach local optima, so restarts still matter. Return to the elongated example. On the left, k-means uses a straight nearest-centre boundary and slices across both natural groups. On the right, the Gaussian mixture learns two covariance ellipses. Their orientations follow the groups, and observations in the overlap can retain intermediate responsibilities instead of being treated as certain. The gain is real, but so is the cost. More parameters require more data, covariance estimates can become unstable, and a Gaussian component can chase a tiny group unless the fit is regularized and checked.

K-means and Gaussian mixtures answer related but different modelling questions. K-means asks for a hard partition that minimizes squared distance to centres. A Gaussian mixture asks for a probability density assembled from weighted components. It returns probabilistic membership and can learn a different covariance shape for every component. Choose k-means when a fast, interpretable hard partition is useful and compact groups are plausible after sensible scaling. Choose a Gaussian mixture when overlap, unequal populations, or elliptical covariance structure is part of the question. Neither model determines the scientifically correct number of groups by itself. K-means returns the k requested. A mixture with k components also fits the requested count, even if some fitted components become tiny or redundant. A defensible workflow begins before fitting. Scale features according to what distance should mean, then use several starts and check whether the result is stable. Compare several credible values of k. For k-means, inspect objective curves and resampling stability. For mixtures, likelihood criteria such as B I C can help penalize unnecessary parameters, but none of these replaces domain judgment. Inspect the fitted objects themselves. Look for clusters created only by one scale, uncertain responsibilities, tiny components, extreme covariance estimates, and solutions that change sharply across restarts. Finally, judge the clustering by the decision it supports. A useful segment, anomaly group, or population subtype must remain interpretable and stable where it will actually be used. The durable lesson is simple. K-means alternates nearest-centre assignment with mean updates, and that simplicity creates both its speed and its geometric limits. Gaussian mixtures replace certainty with responsibilities and add weights and covariance, but those extra freedoms deserve validation because they can fit both real structure and noise.