Course contentsShow
← Machine Learning and Deep Learning
Lesson 347 of 3,5388. Unsupervised Learning: ClusteringFree lesson

Limitations of K-Means and Motivation for Density-Based Methods

Why K-Means fails on non-convex clusters and varying densities; introducing density as the clustering criterion.

Limitations of K-Means and Motivation for Density-Based Methods

What you'll learn: Why K-Means struggles with certain cluster shapes and how thinking about density offers a solution.

Why K-Means Can Fail

You've seen that K-Means works by assigning points to the nearest centroid and assumes clusters are roughly spherical (circular or ball-shaped). But what if your data doesn't cooperate?

Problem 1: Non-Convex Clusters

Imagine two crescent moon shapes that interlock. K-Means will draw straight lines from centroids and chop both moons into weird pieces—it can't "follow the curve" of the data. The distance-to-centroid criterion forces circular boundaries, so complex, winding, or irregularly shaped clusters get mangled.

Analogy: It's like trying to outline a winding river using only circles. You'll always spill over the banks or miss sections.

Problem 2: Varying Densities

K-Means treats all distances equally. If one cluster is tightly packed (high density) and another is spread out (low density), K-Means might split the dense cluster or merge sparse regions incorrectly. It doesn't understand that "closeness" should depend on how crowded the neighborhood is.

Analogy: Imagine mapping cities and rural areas. K-Means might group two distant farms together while splitting a compact downtown into pieces—it ignores population density.

Enter Density-Based Thinking

Instead of asking "which centroid is closest?", density-based methods ask: "Are these points in a crowded region together?" Points form a cluster if they're in a densely populated area, connected by other dense points. Sparse regions become boundaries or noise, not forced into clusters.

This approach naturally handles moons, spirals, and varying densities—no spherical assumption needed.

Key Takeaway: K-Means fails on non-convex shapes and varying densities because it relies on distance to centroids; density-based methods overcome this by clustering regions where points are tightly packed together.