DBSCAN

Prerequisites

• k-means, for comparison.
• Euclidean distance.
• The idea of density: many points in a small area.

The analogy

How it works

Parameters: ε: the neighbourhood radius. minPts: how many points (including itself) a point needs within ε to be a core point. Here ε = 0.6, minPts = 3.

Start with classifying five points

Points A(1, 1), B(1.5, 1.2), C(2, 1), D(3.4, 1.5), E(6, 1); ε = 0.6, minPts = 3. Predict, then open "Check".

Finish the picture: changing ε

Same points, minPts = 3.

• ε = 1.5. Predict the types of C and D.
  Check

  C now has B, C and D within 1.5 (D is 1.49 away): core. D has C and D only: border of C. The cluster is {A, B, C, D}; E is still noise.

• ε = 0.4. Predict the result.
  Check

  Nobody has 3 points within 0.4: everything is noise. Choosing ε well matters; a k-distance plot helps.

Full worked calculation

The five points of the page, A(1, 1), B(1.5, 1.2), C(2, 1), D(3.4, 1.5), E(6, 1), labelled by hand twice: with $\varepsilon = 0.6$ and with $\varepsilon = 1.5$, both with minPts = 3 (the point itself counts).

1. 1Distance matrix

   $$d(A, B) = \sqrt{0.5^2 + 0.2^2} = \sqrt{0.29} \approx 0.54, \qquad d(C, D) = \sqrt{1.4^2 + 0.5^2} = \sqrt{2.21} \approx 1.49$$

   DBSCAN only ever asks "is this pair within $\varepsilon$?", so computing all pairwise distances once is enough to answer every question below.

2. 2ε = 0.6: count neighbours

   $$|N(A)| = |\{A, B\}| = 2, \quad |N(B)| = |\{A, B, C\}| = 3, \quad |N(C)| = 2, \quad |N(D)| = |N(E)| = 1$$

   Read each row of the matrix and count the entries $\le 0.6$, including the 0 on the diagonal. Only B reaches minPts = 3.

3. 3ε = 0.6: label the points

   $$\text{core} = \{B\}, \qquad \text{border} = \{A, C\}, \qquad \text{noise} = \{D, E\}$$

   A and C are not core themselves, but each lies within 0.6 of the core point B, so they join its cluster as border points. D and E are near no core point: noise.

4. 4ε = 1.5: count neighbours again

   $$|N(A)| = |\{A, B, C\}| = 3, \quad |N(B)| = 3, \quad |N(C)| = |\{A, B, C, D\}| = 4, \quad |N(D)| = |\{C, D\}| = 2, \quad |N(E)| = 1$$

   A larger radius catches more neighbours. $d(A, C) = 1.0$ and $d(C, D) = 1.49$ are now inside the radius.

5. 5ε = 1.5: label and expand the cluster

   $$\text{core} = \{A, B, C\}, \qquad \text{border} = \{D\}, \qquad \text{noise} = \{E\}$$

   Starting from core point A, DBSCAN adds its neighbours B and C, and since both are core, their neighbours too, which brings in D. D is only a border point: it can join, but cannot extend the cluster further.

6. 6Why E stays noise

   $$\min_j d(E, j) = d(E, D) = 2.65 > 1.5$$

   E has no neighbour within $\varepsilon$ at all, so no core point can reach it. DBSCAN reports it as an outlier instead of forcing it into a cluster, which k-means could not do.

The rule in plain words

Find every core point (≥ minPts neighbours within ε). Connect core points that are within ε of each other: each connected group is a cluster.

Attach non-core points within ε of a core point as border points of that cluster; everything else is noise.

The code

Read this code after you have labelled the five points by hand. It will make more sense.

int region_count(double x[], double y[], int n, int p, double eps) {   /* includes p itself */
    int c = 0;
    for (int i = 0; i < n; i++)
        if ((x[i]-x[p])*(x[i]-x[p]) + (y[i]-y[p])*(y[i]-y[p]) <= eps * eps) c++;
    return c;
}

void point_types(double x[], double y[], int n, double eps, int min_pts, int type[]) {
    for (int p = 0; p < n; p++)                        /* 2 = core, 0 = not (yet) */
        type[p] = region_count(x, y, n, p, eps) >= min_pts ? 2 : 0;
    for (int p = 0; p < n; p++)                        /* 1 = border: near some core point */
        for (int q = 0; q < n; q++)
            if (type[p] == 0 && type[q] == 2 &&
                (x[p]-x[q])*(x[p]-x[q]) + (y[p]-y[q])*(y[p]-y[q]) <= eps * eps) type[p] = 1;
}

flowchart TD
  A["point p"] --> B{"at least minPts points within ε?"}
  B -->|yes| C["core point: starts or extends a cluster"]
  B -->|no| D{"within ε of some core point?"}
  D -->|yes| E["border point: joins that cluster"]
  D -->|no| F["noise"]
          

How costly is it?

The ε-neighbourhood of a point and the core condition:

Best for: spatial or low-dimensional data with irregularly shaped clusters and outliers, such as GPS points or anomaly detection.

• Pro: Finds clusters of any shape and the number of clusters automatically.
• Pro: Explicitly labels outliers as noise.
• Con: Sensitive to ε and minPts, and struggles when clusters have very different densities.
• Con: Distances lose meaning in high dimensions, like other distance-based methods.

Common mistakes

• Forgetting that a point counts as its own neighbour (or double-counting it), which changes core decisions.
• Calling every non-core point noise; border points belong to clusters.
• Not scaling features, so ε means different things in different directions.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• Clusters are dense regions because points join clusters through chains of core points.
• The number of clusters is automatic because it is the number of connected dense regions.
• Outliers are labelled noise because they are neither dense nor near a dense point.
• Any shape is possible because clusters grow along density, not around a centre.
• ε and minPts matter a lot because together they define what "dense" means.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is DBSCAN like spotting crowds from above?
   Sample answer

   Crowds are where people stand close together; people at the edges belong to them, and someone alone is not in any crowd.

2. Classify A, B, C, D, E with ε = 0.6 and minPts = 3.
   Sample answer

   B is core; A and C are border points of B's cluster; D and E are noise. One cluster {A, B, C}.

3. Why does point_types find core points in a first loop before labelling borders?

   A good answer mentions what "border" depends on.

   Sample answer

   A border point is defined by being near a core point, so all core points must be known first.

4. So what is DBSCAN, in one sentence?
   Sample answer

   A density-based clustering method that grows clusters from core points with enough neighbours within ε and labels sparse points as noise.

5. Why can DBSCAN find ring-shaped clusters while k-means can't?

   A good answer compares "around a centre" with "connected by density".

   Sample answer

   k-means assigns each point to its nearest centre, so clusters are round blobs. DBSCAN links neighbouring dense points, so a cluster can follow any shape.

6. What does DBSCAN cost?
   Sample answer

   $O(n^2)$ with brute-force neighbourhood search, about $O(n \log n)$ with a spatial index in low dimensions.

7. Give two pros and two cons.
   Sample answer

   Pros: any shape, automatic number of clusters, explicit noise. Cons: sensitive to ε and minPts, and weak with varying densities or high dimensions.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the complexity and HDBSCAN. I'd keep the crowd analogy, the five-point classification, and "core, border, noise; clusters are dense regions".

External resources

• scikit-learn: DBSCAN: parameters and examples.
• Naftali Harris: Visualizing DBSCAN: an interactive demo on tricky shapes.
• Wikipedia: DBSCAN: definitions and algorithm.

Videos

• YouTube search: StatQuest DBSCAN: StatQuest's visual explanation.