DBSCAN

DBSCAN finds clusters as dense regions separated by sparse ones, discovering their number and flagging outliers as noise.

Density-based clustering

DBSCAN (density-based spatial clustering of applications with noise) groups points that are packed closely together and marks points in sparse regions as noise. Unlike k-means it does not need the number of clusters in advance and can find clusters of arbitrary shape.

Two parameters

• eps: the radius that defines a point's neighborhood.
• min_samples: how many points must lie within eps for a point to be a 'core' point.
• Core points grow clusters; border points join them; the rest are noise.

A cluster starts at a core point and expands to every point density-reachable from it. Points that belong to no cluster are labeled noise (-1), giving DBSCAN built-in outlier detection.

from sklearn.cluster import DBSCAN
db = DBSCAN(eps=0.5, min_samples=5).fit(X)
labels = db.labels_          # -1 marks noise points

Strengths and weaknesses

DBSCAN excels at non-convex shapes and is robust to outliers, but it falters when clusters have very different densities, because a single eps cannot fit all of them. Choosing eps is delicate: a k-distance plot (sorted distance to the k-th neighbor) reveals a good value at its elbow.

Related methods

HDBSCAN extends DBSCAN to variable density by building a hierarchy and extracting the most stable clusters, removing the need to fix eps. Compare with k-means, which needs k and assumes convex clusters, and with hierarchical clustering, which yields a full tree of nested groupings.