Density-based clustering

DBSCAN (density-based spatial clustering of applications with noise) defines clusters as dense regions separated by sparse ones. It has two parameters: a radius $\epsilon$ and a minimum number of points minPts.

• A core point has at least minPts neighbours within $\epsilon$.
• A border point is within $\epsilon$ of a core point but isn't core itself.
• A noise point is neither — it belongs to no cluster.

Clusters grow by connecting core points that are within $\epsilon$ of each other, plus their border points.

Advantages: finds clusters of any shape (rings, moons, snakes), labels outliers as noise, and you don't need to choose $k$. Weaknesses: struggles when clusters have very different densities, and $\epsilon$ is hard to set in high dimensions.