DBSCAN (Density-Based Spatial Clustering) › Worked Example

Let's work through a concrete numerical example to see how DBSCAN's mathematical concepts translate into actual clustering decisions. We'll use a small dataset where we can trace every calculation by hand, building intuition for how the algorithm discovers clusters.

Consider nine points in 2D space, arranged to form two distinct groups with one isolated point:

We'll use parameters: eps = 1.5 and min_samples = 3

First, we need to find which points are neighbors. Using Euclidean distance:

$$d(p, q) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$$

Let's calculate key distances for point A:

• $d(A, B) = \sqrt{(1-1)^2 + (2-1)^2} = \sqrt{0 + 1} = 1.0$ ✓ (within eps)
• $d(A, C) = \sqrt{(2-1)^2 + (1-1)^2} = \sqrt{1 + 0} = 1.0$ ✓ (within eps)
• $d(A, D) = \sqrt{(2-1)^2 + (2-1)^2} = \sqrt{1 + 1} = 1.414$ ✓ (within eps)
• $d(A, E) = \sqrt{(8-1)^2 + (8-1)^2} = \sqrt{49 + 49} = 9.899$ ✗ (too far)
• $d(A, I) = \sqrt{(5-1)^2 + (5-1)^2} = \sqrt{16 + 16} = 5.657$ ✗ (too far)

Since the lower-left and upper-right clusters are symmetric, similar calculations apply.

For each point, we identify all neighbors within eps = 1.5:

Notice that points A, B, C, D form a tightly connected group where everyone is neighbors with everyone else. The same is true for E, F, G, H. Point I stands alone.

Now we apply the density test: $|N_{eps}(p)| \geq min\_samples$

With min_samples = 3:

All points in the two dense groups qualify as core points. Point I, with only itself in its neighborhood, fails the density test.

Now we execute the DBSCAN algorithm, visiting points and expanding clusters:

Iteration 1: Visit point A

1. Mark A as visited
2. A is a core point → Create Cluster 1
3. Add A to Cluster 1: {A}
4. Queue A's neighbors for expansion: {B, C, D}
5. Process B: visited, core point, add to Cluster 1, queue B's unvisited neighbors
6. Process C: visited, core point, add to Cluster 1, queue C's unvisited neighbors
7. Process D: visited, core point, add to Cluster 1
8. Queue is empty → Cluster 1 complete: {A, B, C, D}

Iteration 2: Visit point E (first unvisited point)

1. Mark E as visited
2. E is a core point → Create Cluster 2
3. Add E to Cluster 2: {E}
4. Queue E's neighbors for expansion: {F, G, H}
5. Process F, G, H similarly
6. Cluster 2 complete: {E, F, G, H}

Iteration 3: Visit point I (last unvisited point)

1. Mark I as visited
2. I is NOT a core point (only 1 neighbor)
3. I is not in any core point's neighborhood
4. Mark I as noise

DBSCAN successfully identified two distinct clusters based on density while correctly classifying the isolated point I as noise. The algorithm never required us to specify the number of clusters; it discovered them naturally by following density connections.