Introduction

DBSCAN is a density-based clustering algorithm that identifies clusters based on the density of data points in a given region.

The algorithm classifies points into three categories: core points, border points, and noise.

• A core point is a data point that has at least a specified number of neighbouring points (MinPts) within a given radius (eps).
• Border points are those that are within the neighbourhood of a core point but do not themselves have enough neighbours to be core points
• Points that do not fall into these two categories are considered noise.

DBSCAN starts by identifying core points and expanding clusters around them by including neighbouring points. The process continues until no more points can be added to any cluster. DBSCAN is particularly effective for identifying clusters of varying shapes and handling noise in the data.

More detail

Each point in the dataset is classified as a core point, border point, or noise based on two parameters: the radius ϵ and the minimum number of points MinPts within that radius.

A core point is one that has at least MinPts neighbours within a radius $ϵ$.

Border points are those that fall within the ϵ-neighbourhood of a core point but have fewer than MinPts neighbours. Any point that is neither a core nor a border point is classified as noise.

The algorithm starts by identifying core points and expanding clusters around them by including neighboring points within $ϵ$. This process continues until no more points can be added to any cluster. Mathematically, a point ppp is considered part of a cluster if:

$$ |p - q\| \leq \epsilon \quad \text{and} \quad |\{q : \|p - q\| \leq \epsilon\}| \geq \text{MinPts} $$

DBSCAN is particularly useful for identifying clusters of arbitrary shapes and handling noise in the data.

Next reading:

Gaussian Mixture Models