DBSCAN (Density-Based Clustering)

shapes

The clusters have complex, non-spherical shapes

When is Density-Based Clustering particularly effective?

When clusters have varying densities

Why would you use Density-Based Clustering if the number of clusters is unknown or hard to estimate?

do not require the number of clusters to be specified in advance

Initialization

all points are marked as unvisited

Random selection

pick a random unvisited point from the dataset

Region query

for chosen point, retrieve its neighborhood defined by distance epsilon e

Expansion

if there are ‘minPts’ or more within e start a new cluster and add chosen point to new cluster, continue. If point has fewer than ‘minPts’ mark it as noise for now