Limitations of K-means Clustering and When It Fails

K-means clustering partitions data into $K$ groups by iteratively assigning each point to the nearest centroid and then recomputing centroids, with the goal of minimizing within-cluster distances (typically the within-cluster sum of squares, i.e., SSE). Its practical performance is limited by assumptions about cluster shape, equal variance, and the use of Euclidean distance—plus algorithmic issues such as sensitivity to initialization and convergence to local optima.2

Core terms to anchor the discussion:

• SSE
• Lloyd’s algorithm
• Local optimum
• Centroid initialization

Mermaid: how K-means moves from assignments to centroids

Two overarching limitations drive most “poor performance” cases:

1. Cluster geometry mismatch: K-means implicitly favors convex, roughly spherical, similarly sized clusters under Euclidean distance.
2. Sensitivity to initialization and outliers: poor starting centroids can slow convergence or yield suboptimal partitions; extreme points can pull centroids and distort SSE.2

Footnotes

1. K-means clustering — Wikipedia - Overview of Lloyd’s algorithm, SSE objective, and initialization concepts. ↩ ↩² ↩³

2. Lloyd's algorithm — Wikipedia - Discusses iterative assignment/update and convergence to local optimum behavior. ↩ ↩²

3. Cluster analysis — Wikipedia (K-means suitability notes) - Notes about K-means assumptions (spherical/convex tendencies) and failure modes for non-spherical clusters. ↩

What K-means optimizes (and what it can’t represent)

K-means minimizes SSE by alternating between assigning points to the nearest centroid and updating centroids to be the mean of assigned points.2 Because the objective is SSE with Euclidean geometry, cluster boundaries tend to be Voronoi-style (linear partitions in feature space), and K-means tends to struggle with non-convex structures (e.g., rings) or clusters with different densities/variances.

The method also commonly exhibits local minima: Lloyd’s algorithm can converge to a clustering that is not globally optimal SSE.2

Footnotes

1. K-means clustering — Wikipedia - Overview of Lloyd’s algorithm, SSE objective, and initialization concepts. ↩ ↩²

2. Lloyd's algorithm — Wikipedia - Discusses iterative assignment/update and convergence to local optimum behavior. ↩ ↩²

3. Cluster analysis — Wikipedia (K-means suitability notes) - Notes about K-means assumptions (spherical/convex tendencies) and failure modes for non-spherical clusters. ↩

Two scenarios where K-means performs poorly

Scenario 1: Non-spherical / non-convex clusters (e.g., “ring”, “two moons”, elongated shapes)

When it happens: If true clusters are non-convex, have curved boundaries, or are better described by multiple blobs connected by structure (like concentric rings), K-means’ SSE + mean-centroid assumption is a poor fit.

Why K-means performs poorly:

• SSE minimization with Euclidean distance encourages partitions that are approximately spherical in the feature space.
• Voronoi regions induced by centroids produce linear-ish decision boundaries, which cannot naturally trace curved/non-convex manifolds.
• Increasing $K$ can sometimes “approximate” curvature, but that increases fragmentation and often hurts interpretability and stability.

Observable symptoms:

• Centroids fall into the “wrong” parts of the structure.
• Points from different true groups get merged to reduce SSE.
• The clustering changes dramatically for different $K$ or initializations.

Possible improvements / alternatives:

1. Switch to density-based clustering (DBSCAN) when clusters have arbitrary shapes. DBSCAN groups points based on density connectivity rather than SSE-to-centroids.
2. Use a Gaussian mixture model (GMM) if clusters are approximately Gaussian but may differ in covariance; GMMs use probabilistic assignments and covariance modeling instead of fixed spherical centroids.
3. Use spectral clustering when the structure is non-convex; it operates on similarities/graph structure rather than centroid distances.
4. Feature engineering / kernel methods (e.g., transform data) can sometimes “make” clusters closer to spherical before applying K-means, but it’s problem-specific.

---

Scenario 2: Outliers and/or clusters with different variance/density

When it happens:

• There are outliers (points far away from the rest).
• Clusters have different spread (variance) or different densities (e.g., one tight cluster and one diffuse cluster).

Why K-means performs poorly:

• K-means uses the mean as the centroid; means are sensitive to extreme values, so outliers can heavily influence centroids and the SSE objective.2
• When variances differ, “equal-radius” spherical assumptions break: K-means can underfit the diffuse cluster or over-split dense regions to reduce SSE.

Observable symptoms:

• Centroids shift toward outliers; many points become assigned to the wrong nearest centroid.
• Clusters with larger variance are “squeezed” into multiple groups or absorbed by nearer centroids.
• Instability across runs is common (especially with naive initialization).

Possible improvements / alternatives:

1. Use robust centroid methods: replace the mean with a more robust location estimator (e.g., K-medoids / PAM) so one extreme point doesn’t dominate.
2. Use K-means++ initialization to reduce sensitivity to initialization by choosing initial centers more strategically.
3. Adopt algorithms that handle density differences: DBSCAN can separate dense clusters and treat sparse regions as noise (depending on parameters).
4. Use model-based clustering (GMM) with covariance structures (full/diag) to represent different cluster spreads rather than fixed spherical means.

Footnotes

1. Cluster analysis — Wikipedia (K-means suitability notes) - Notes about K-means assumptions (spherical/convex tendencies) and failure modes for non-spherical clusters. ↩ ↩² ↩³ ↩⁴ ↩⁵

2. DBSCAN — Wikipedia - Density-based clustering; can find arbitrarily shaped clusters and identifies noise. ↩ ↩²

3. Gaussian mixture model — Wikipedia - GMM uses probabilistic assignments and covariance to model clusters with different shapes/spreads. ↩ ↩²

4. Spectral clustering — Wikipedia - Uses graph/similarity structure to capture non-convex cluster structure. ↩

5. K-means clustering — Wikipedia - Overview of Lloyd’s algorithm, SSE objective, and initialization concepts. ↩ ↩²

6. Lloyd's algorithm — Wikipedia - Discusses iterative assignment/update and convergence to local optimum behavior. ↩

7. K-medoids — Wikipedia - Medoid-based clustering as a more robust alternative to mean-based K-means. ↩

Summary comparison (what fails and what to try)

Footnotes

1. DBSCAN — Wikipedia - Density-based clustering; can find arbitrarily shaped clusters and identifies noise. ↩ ↩² ↩³

2. Spectral clustering — Wikipedia - Uses graph/similarity structure to capture non-convex cluster structure. ↩

3. Gaussian mixture model — Wikipedia - GMM uses probabilistic assignments and covariance to model clusters with different shapes/spreads. ↩ ↩²

4. Cluster analysis — Wikipedia (K-means suitability notes) - Notes about K-means assumptions (spherical/convex tendencies) and failure modes for non-spherical clusters. ↩

5. K-means clustering — Wikipedia - Overview of Lloyd’s algorithm, SSE objective, and initialization concepts. ↩

6. K-medoids — Wikipedia - Medoid-based clustering as a more robust alternative to mean-based K-means. ↩ ↩²