Density-Based Clustering

Botie plots sensor locations around two greenhouse paths. The paths curve, and a few readings come from isolated devices far away. Dividing everything among a fixed number of centres may cut a path in half or force an isolated point into a group.

Let's begin locally. If a point has enough neighbours nearby, it can support a group. We can then follow connected regions of these well-supported points. That gives us a way to handle irregular shapes and leave unsupported points unassigned.

A location becomes a core point only when its neighbourhood meets the chosen count. Change the radius or required count and check which locations gain or lose that support.

DBSCAN uses a distance threshold, usually called epsilon, and a minimum neighbourhood count. We include a point itself and include neighbours exactly at the radius in these examples. A core point meets the count threshold.

Those choices depend on feature units and the task. A radius measured in metres cannot be copied unchanged after converting the same coordinates to centimetres.

Positions: [0.0, 0.1, 0.2, 0.4]
Radius: 0.21; minimum count: 3
Neighbour counts: [3, 3, 4, 2]
Core flags: [1, 1, 1, 0]

The final point is not core, but that does not yet tell us whether it belongs to a cluster.

Start a cluster at an unvisited core point and inspect its neighbours. A neighbour that is also a core point can bring in its own neighbours. Repeating this step lets the cluster follow the curved path of densely placed sensors.

The distinction between core and border points matters here. Expansion continues through core points. A sparse chain of border points cannot extend the cluster indefinitely, even if each point is close to the next.

The ability to continue through core points explains how an irregular path can stay together.

A non-core point within the radius of a core point can join its cluster as a border point. It does not expand the cluster through its own neighbourhood. A point that is neither core nor adjacent to a core remains noise.

In the preceding example, the point at 0.4 is near the core at 0.2 and therefore joins at the border. Its low count does not make it noise.

Core at 0.2; non-core point at 0.4
Distance = 0.2, within radius 0.21
The point at 0.4 can join, but cannot extend the cluster.

A border point can touch two different core regions. Its assignment can then depend on traversal order. Numeric cluster IDs are labels, not ranked measurements.

Construct a distance table with one row and column per observation. Compare each distance with the radius to produce a zero-or-one neighbourhood table. Add each row and compare the count with the minimum.

Botie's construction asks for this core mask. It does not call that mask a finished clustering. The expansion step still has to connect core regions and attach border points.

This decomposition makes two common mistakes visible: omitting the point itself, and using a strict comparison when the chosen convention includes the radius boundary.

import numpy as np
X = np.array([[0.],[0.1],[0.2],[0.4]])
d = np.linalg.norm(X[:,None,:] - X[None,:,:], axis=2)
counts = (d <= 0.21).sum(axis=1)
print(counts.tolist())
print((counts >= 3).astype(int).tolist())

[3, 3, 4, 2]
[1, 1, 1, 0]

One radius may connect a dense group too aggressively while failing to recognise a sparse group. In many dimensions, distance itself may become a weak basis for neighbourhoods. Scaling, feature choice, and parameter sensitivity still matter.

Noise means unsupported under this particular definition. It does not prove a device is broken or an observation is an error. Review those points in the context of how they were collected.

Use the model to ask a specific grouping question, then inspect what happens when the neighbourhood assumptions change.

The core mask is only the local density test. To obtain clusters, start from an unassigned core point and follow neighbouring core points until no more are reachable. All of those core points belong to one connected dense region.

Then attach nearby non-core points as border points. A border point does not let the search continue farther. Keeping these roles separate prevents a chain of sparse points from joining two otherwise separate dense regions.

A frontier is a collection of positions still waiting to be explored. Removing one position, checking its neighbours and adding unseen core neighbours repeats until that collection is empty.

This example extracts the core regions explicitly. Border attachment is a separate decision after the core regions are known, so the intermediate output makes clear what has and has not been clustered.

import numpy as np
x = np.array([0., .1, .2, 2., 2.1, 2.2, 5.])
near = np.abs(x[:,None]-x[None,:]) <= .25
core = near.sum(axis=1) >= 3
labels = np.full(len(x), -1)
cluster = 0
for start in np.flatnonzero(core):
    if labels[start] >= 0:
        continue
    frontier = [int(start)]
    labels[start] = cluster
    while frontier:
        current = frontier.pop()
        for nxt in np.flatnonzero(near[current] & core & (labels < 0)):
            labels[nxt] = cluster
            frontier.append(int(nxt))
    cluster += 1
print(core.tolist())
print(labels.tolist())

[True, True, True, True, True, True, False]
[0, 0, 0, 1, 1, 1, -1]

A non-core point can lie within the radius of core points from two different regions. Assigning it to the first region reached is a common convention; its assignment can then depend on traversal order. The core regions themselves need not be ambiguous in that way.

Report that distinction when comparing implementations. Also vary the radius and minimum count deliberately. A cluster disappearing under a tiny change can reveal a fragile density assumption, while differing density levels may make one global radius unsuitable.