Limitations

K-means is remarkably successful across diverse applications, but it has fundamental limitations that every practitioner must understand. Blindly applying k-means to data that violates its assumptions leads to meaningless clusters, wasted effort, and incorrect conclusions.

In this page, we'll systematically examine k-means' limitations—not as criticisms, but as a guide for when to use it and when to choose alternatives. Understanding these limitations is the mark of a mature machine learning practitioner: knowing not just how to apply a technique, but when to apply it.

K-means' most fundamental limitation stems from its objective function: minimizing within-cluster variance with squared Euclidean distance inherently assumes spherical, isotropic clusters.

Why Spherical?

The Voronoi tessellation created by k-means divides space using perpendicular bisectors between centroids. Each cluster region is a convex polytope. This geometry implies:

1. Clusters are convex: K-means cannot discover non-convex shapes (crescents, rings, interleaved spirals)
2. Equal variance assumed: All clusters are assumed to have similar spread
3. Isotropic spread: Variance is equal in all directions (not elongated ellipses)

Elongated Clusters:

Even for convex clusters, k-means struggles with elongated shapes:

True clusters:           K-means finds:
                        
  /////                    ||||| |
 /////                     ||||| |
/////                      ||||| |
        \\\\\              | |||||
         \\\\\             | |||||
          \\\\\            | |||||

K-means cuts perpendicular to the line connecting centroids. If clusters are elongated diagonally, the cut misaligns with the true boundary.

Solution: Use Gaussian Mixture Models (GMMs) with full covariance matrices, which can learn ellipsoidal clusters of different orientations.

K-means requires specifying $k$ (number of clusters) upfront. This is often the most challenging aspect of using k-means:

• Too few clusters: Distinct groups get merged, losing information
• Too many clusters: Natural groups get split unnecessarily
• No "correct" k exists: The optimal k depends on the use case and scale of interest

Methods for Choosing K:

K-means is sensitive to both feature scales and outliers—problems that can produce meaningless clusters if not addressed.

Feature Scale Sensitivity:

Squared Euclidean distance treats all dimensions equally in magnitude: $$|\mathbf{x} - \boldsymbol{\mu}|^2 = \sum_{d=1}^{D} (x_d - \mu_d)^2$$

If feature 1 ranges [0, 1] and feature 2 ranges [0, 1000], feature 2 dominates completely:

• A difference of 0.1 in feature 1 contributes $0.01$
• A difference of 10 in feature 2 contributes $100$

Clusters are determined almost entirely by feature 2.

Outlier Sensitivity:

Because k-means minimizes squared distances, outliers have outsized influence:

• An outlier 10 units away contributes 100 to WCSS
• A normal point 1 unit away contributes 1

Centroids get "pulled" toward outliers, distorting cluster structure.

Example:

Points: 1, 2, 3, 4, 5, 100 (outlier)
Mean: (1+2+3+4+5+100)/6 = 19.2  ← Pulled far from majority
Median: 3.5  ← Robust to outlier

Solutions:

1. Preprocessing: Detect and remove outliers before clustering
2. K-medoids (PAM): Uses actual data points as centers, more robust
3. K-medians: Uses L1 distance and median as center, robust to outliers
4. Robust statistics: Use trimmed means or Huber loss

K-means has an implicit bias toward producing equally-sized clusters. When true clusters have very different sizes, k-means tends to split large clusters and merge small ones.

Why This Happens:

The WCSS objective doesn't penalize unequal cluster sizes. But with equal-radius spherical clusters, more points means higher WCSS. The optimization trades off:

• Keeping small clusters pure (low WCSS contribution)
• Splitting large clusters (reducing their WCSS contribution)

The result: boundaries shift toward large clusters, stealing points to balance sizes.

Example:

True clusters: 1000 points (dense cloud) + 50 points (small group)

K-means with k=2 might:

• Split the large cloud into two pieces
• Assign the small group to one of those pieces
• Result: Two equally-sized but meaningless clusters

Diagnosing the Problem:

After clustering, examine cluster sizes:

np.bincount(labels)
# array([250, 248, 252, 250])  ← Suspiciously equal

If cluster sizes are nearly equal despite expecting variation, k-means may be forcing balance.

Mitigation Strategies:

1. Overcluster then merge: Use larger k, then merge based on similarity
2. Use GMM: Gaussian mixtures naturally handle different cluster sizes/shapes
3. Weight points differently: Underweight dense regions to reduce their influence
4. Constrained k-means: Add size constraints (but computationally harder)

K-means' reliance on Euclidean distance makes it susceptible to the curse of dimensionality—the phenomenon where distance-based methods break down in high dimensions.

The Problem:

In high dimensions:

1. Distance concentration: All pairs of points become nearly equidistant
2. Nearest neighbor meaningless: The farthest point is barely farther than the nearest
3. Empty space dominates: Most of the space is empty (hypersphere volume shrinks)

Mathematical Form:

For uniformly distributed points in $d$ dimensions: $$\lim_{d \to \infty} \frac{d_{\max} - d_{\min}}{d_{\min}} = 0$$

The relative contrast between distances vanishes—everything looks equally far.

Solutions for High Dimensions:

1. Dimensionality Reduction First:

from sklearn.decomposition import PCA

pca = PCA(n_components=50)  # Reduce to 50 dimensions
X_reduced = pca.fit_transform(X)
kmeans.fit(X_reduced)

2. Feature Selection: Remove irrelevant features before clustering

3. Subspace Clustering: Find clusters in different subspaces

4. Use Different Distance: Cosine similarity works better for high-dimensional sparse data

5. Spectral Clustering: Build similarity graph and cluster on eigenvectors (lower dimensional representation)

Rule of Thumb:

If $d > 50$ and k-means produces poor silhouette scores, consider:

• Reducing dimensions to 10-50 components via PCA
• Switching to cosine k-means for text/sparse data
• Using spectral clustering

Given all these limitations, when should you actually use k-means? Here's a practical decision framework.

Module Complete:

Congratulations! You've completed the K-Means Clustering module. You now understand:

• Lloyd's algorithm: The iterative assignment-update procedure
• The objective function: WCSS and its mathematical properties
• Initialization: K-means++ and its O(log k) guarantee
• Convergence: Proofs, rates, and stopping criteria
• Limitations: When k-means works and when to choose alternatives

This knowledge prepares you for the k-means variants module (k-medoids, fuzzy c-means, mini-batch) and for understanding how other clustering algorithms address k-means' limitations.