DBSCAN

Preface

Many familiar clustering methods describe each group in relation to a centre. K-means assigns observations to their nearest centroid and tends to work best with compact, roughly spherical groups. Gaussian mixture models are more flexible, allowing elliptical groups through a mean and a covariance. Both are useful when those shapes are a reasonable description of the data.

But groups do not always look like compact blobs. Cells captured at different stages of differentiation may trace a curved path, and observations in spatial data may follow a coastline, road, or river. Other observations may sit on their own without belonging to any group. A centre and a spread do not describe these situations particularly well.

DBSCAN starts from a different question. Instead of asking where the centre of a group is, it asks whether a point is sitting somewhere crowded. A cluster is then built by connecting these dense neighbourhoods, so it can bend around an irregular shape and the number of groups does not have to be chosen in advance. Points that are not connected to any sufficiently dense region are labelled as noise rather than forced into the nearest cluster.

Let’s start seeing how DBSCAN works. You do not need any previous experience with clustering. It is enough to be comfortable with the idea that a point has coordinates and that we can measure the distance between two points.

Start with the visual introduction.