DBSCAN Theory

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) identifies density-connected sets under a chosen metric, radius, and minimum-neighborhood size. It can recover many non-convex shapes and labels observations outside those sets as noise, but one global density threshold need not fit clusters of very different density.

1. Mathematical Foundations of DBSCAN

DBSCAN is rooted in the concept of density, where clusters are defined as regions of high point density separated by regions of lower point density. The algorithm uses two critical parameters:

• Epsilon ($\epsilon$): The maximum distance between two points for them to be considered as part of the same neighborhood.
• MinPts: The minimum number of points required within a neighborhood of radius $\epsilon$ for a point to be considered a core point.

1.1 Neighborhood and Core Points

The $\epsilon$-neighborhood of a point $p$ is defined as the set of all points within a distance $\epsilon$ of $p$:

$$N_\epsilon(p) = \{ q \in D \mid \text{dist}(p, q) \leq \epsilon \}$$

Where:

• $N_\epsilon(p)$ is the $\epsilon$-neighborhood of point $p$.
• $\text{dist}(p, q)$ is the distance between points $p$ and $q$.
• $D$ is the dataset.

A point $p$ is classified as a core point if its $\epsilon$-neighborhood contains at least MinPts points:

$$|N_\epsilon(p)| \geq \text{MinPts}$$

1.2 Border and Noise Points

Points that are not core points but fall within the $\epsilon$-neighborhood of a core point are called border points. These points are part of a cluster but do not have sufficient density around them to be core points.

Points that are neither core points nor border points are classified as noise points (or outliers). These points do not belong to any cluster.

2. Algorithmic Steps of DBSCAN

The DBSCAN algorithm can be broken down into the following steps:

Step 1: Initialize and Select a Point

• Begin with an unvisited point $p$ from the dataset $D$.
• Mark $p$ as visited.

Step 2: Retrieve the $\epsilon$-Neighborhood

• Retrieve the $\epsilon$-neighborhood $N_\epsilon(p)$ of the point $p$.

Step 3: Check Core Point Criteria

• If $|N_\epsilon(p)| \geq \text{MinPts}$, $p$ is a core point. A new cluster is created, and $p$ and all points in $N_\epsilon(p)$ are added to this cluster.
• If $|N_\epsilon(p)| < \text{MinPts}$, $p$ is marked as noise. However, $p$ may later be reclassified as a border point if it falls within the $\epsilon$-neighborhood of a core point.

Step 4: Expand the Cluster

• For each point $q$ in $N_\epsilon(p)$:
  • If $q$ is unvisited, mark it as visited and retrieve its $\epsilon$-neighborhood $N_\epsilon(q)$.
  • If $|N_\epsilon(q)| \geq \text{MinPts}$, add $N_\epsilon(q)$ to the cluster.
  • If $q$ is not already assigned to a cluster, add it to the current cluster.

Step 5: Repeat

• Repeat the process for all unvisited points in the dataset until all points have been processed.

Step 6: Result

• The result is a set of clusters, with each cluster containing core points and possibly border points. Noise points are not assigned to any cluster.

3. Properties of DBSCAN

DBSCAN has several important properties that make it a powerful clustering algorithm:

3.1 Handling of Noise and Outliers

One of the key advantages of DBSCAN is its ability to naturally identify and exclude noise points. This is achieved by the density-based approach, where points that do not meet the density criteria (i.e., not enough neighbors within the $\epsilon$-neighborhood) are classified as noise.

3.2 Clustering Arbitrary Shapes

DBSCAN does not restrict clusters to centroid-shaped Voronoi cells. It can identify many irregular shapes through chains of core neighborhoods, but nearby clusters can merge through dense bridges and variable-density clusters can be split or missed. Density is still defined by distances in the selected feature space.

3.3 Automatic Determination of the Number of Clusters

Unlike K-Means, DBSCAN does not accept a target cluster count. The returned count is an emergent property of the observations and the selected representation, metric, $\epsilon$, and MinPts parameters.

3.4 Sensitivity to Parameters

The effectiveness of DBSCAN depends on the appropriate selection of $\epsilon$ and MinPts. If $\epsilon$ is too small, many points will be classified as noise. If $\epsilon$ is too large, clusters may merge, leading to fewer clusters than expected. Similarly, the choice of MinPts affects the minimum density required for a cluster to form.

• Choosing $\epsilon$: A common diagnostic plots sorted distances to the min_samples-th neighbor when neighbor queries include the observation itself, as scikit-learn does. An apparent elbow supplies candidates, not an automatic optimum; verify a range of values.
• Choosing MinPts: A rule of thumb is to set MinPts to at least the dimensionality of the data plus one. However, this can vary depending on the application and dataset characteristics.

4. Mathematical Example of DBSCAN

Consider a simple 2D dataset with points distributed in two clusters and some noise:

$$D = \{(1, 2), (2, 2), (2, 3), (8, 7), (8, 8), (25, 80)\}$$

Let’s apply DBSCAN with parameters $\epsilon = 1.5$ and $\text{MinPts} = 2$.

1. Select Point $(1, 2)$:

   • $\epsilon$-neighborhood: $N_{1.5}((1, 2)) = \{(1, 2), (2, 2)\}$
   • $|N_{1.5}((1, 2))| = 2$, so $(1, 2)$ is a core point, and a new cluster is formed.

2. Expand Cluster:

   • Include $(2, 2)$ in the cluster.
   • Next, consider point $(2, 2)$.
     • $N_{1.5}((2, 2)) = \{(1, 2), (2, 2), (2, 3)\}$
     • $|N_{1.5}((2, 2))| = 3$, so $(2, 2)$ is a core point, and $(2, 3)$ is added to the cluster.

3. Move to Next Unvisited Point $(8, 7)$:

   • $N_{1.5}((8, 7)) = \{(8, 7), (8, 8)\}$
   • $|N_{1.5}((8, 7))| = 2$, so $(8, 7)$ is a core point, and a new cluster is formed.

4. Expand Cluster:

   • Include $(8, 8)$ in the cluster.
   • Consider point $(8, 8)$.
     • $N_{1.5}((8, 8)) = \{(8, 7), (8, 8)\}$
     • $|N_{1.5}((8, 8))| = 2$, so $(8, 8)$ remains in the cluster.

5. Move to Last Unvisited Point $(25, 80)$:

   • $N_{1.5}((25, 80)) = \{(25, 80)\}$
   • $|N_{1.5}((25, 80))| = 1$, so $(25, 80)$ is classified as noise.

Result:

• Cluster 1: $\{(1, 2), (2, 2), (2, 3)\}$
• Cluster 2: $\{(8, 7), (8, 8)\}$
• Noise: $\{(25, 80)\}$

5. Conclusion

DBSCAN can identify non-convex density-connected clusters and mark points outside them as noise. The returned number of clusters emerges from the data and the selected metric, scaling, $\epsilon$, and MinPts; it is not parameter-free discovery.

6. Computational considerations

With a suitable spatial index in favorable low-dimensional geometry, neighborhood queries can be efficient; worst-case time remains quadratic. Scikit-learn bulk-computes neighborhoods and can also require quadratic memory when eps is large and min_samples is low, whereas the original algorithm can be implemented with linear memory. Metric choice, dimension, and neighborhood density therefore matter as much as sample count.