DBSCAN

Cluster by density, without being told how many clusters there are.

DBSCAN takes a radius eps and a count min_samples, and labels every point:

• A point is a core point if at least min_samples points, including itself, lie within eps.
• Core points that are within eps of each other belong to the same cluster, transitively.
• A non-core point within eps of a core point joins that cluster as a border point, but does not spread the cluster any further.
• Everything else is noise, labelled -1.

Return labels of shape (n,) with clusters numbered from 0.

To make the numbering deterministic: scan points in index order, and each time you meet an unvisited core point start the next cluster id and grow it with a queue, appending newly found neighbours in ascending index order.

The subtlety is that border points must not expand the cluster. Only core points put their neighbours on the queue. Get that wrong and two clusters joined by a thin bridge of border points merge into one.

Unlike k-means, this finds clusters of any shape, decides the count itself, and has an explicit notion of noise. Use <= when comparing distances to eps.

Function signature

def dbscan(X, eps, min_samples):

Example

Input

X = np.array([[0.0], [0.1], [0.2], [10.0]])
dbscan(X, eps=0.5, min_samples=2)

Output

array([ 0,  0,  0, -1])

Reasoning

The first three points are all within 0.5 of each other, so each has at least 2 neighbours, itself included. They are core points and form cluster 0. The point at 10.0 has only itself, so it is noise.

Constraints and notes

• A point counts itself as a neighbour.
• Compare distances with <=.
• Border points join a cluster but do not grow it.