K-means: partition by nearest centroid
K-means picks k centroids, assigns every point to its nearest one, then moves each centroid to the mean of its assigned points — repeating until nothing changes. It is fast, simple, and guaranteed to converge, but it assumes clusters are roughly spherical, forces every point into some cluster, and requires choosing k in advance.
DBSCAN: grow clusters from density
DBSCAN instead defines a cluster as a dense region: any point with at least min-points neighbours within radius ε starts a cluster that grows by absorbing reachable dense neighbours. Points in no dense region are labelled noise rather than forced into the nearest group — often a more honest outcome for messy real-world data, and one that lets DBSCAN find arbitrarily shaped clusters that k-means cannot.
Where each one breaks
Run k-means on two interleaved crescents ("two moons") or concentric rings and it will slice straight through them, because k-means clusters are always convex regions — it can only draw straight decision boundaries between centroids. DBSCAN separates both shapes cleanly given a reasonable ε, at the cost of trading one parameter (k) for two harder-to-tune ones (ε and min-points).
Choosing k, and the curse of dimensionality
Common approaches to choosing k include the elbow method (plotting inertia against k and looking for a bend) and silhouette score. DBSCAN's neighbour search scales well in low dimensions but gets expensive without spatial indexing in high ones — and "density" itself becomes a less meaningful concept as dimensionality grows, a manifestation of the broader curse of dimensionality that affects most distance-based ML methods.
🧪 Try it yourself: the Clustering Algorithms Lab simulation lets you experiment with everything described above directly in your browser.