DBSCAN: Finding Clusters of Any Shape by Density, Not Distance

What is DBSCAN?

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is a density-based clustering algorithm that groups together points which are packed closely together (points with many nearby neighbors), marking as outliers points that lie alone in low-density regions. Unlike other clustering algorithms, such as K-means or hierarchical clustering, DBSCAN does not require the number of clusters to be specified beforehand and can discover clusters of arbitrary shape.

The key parameters of DBSCAN are `eps` (epsilon) and `min_samples`. The parameter `eps` defines the maximum distance between two points for them to be considered as in the same neighborhood. The parameter `min_samples` specifies the minimum number of points required to form a dense region.

How DBSCAN Works

DBSCAN starts with an arbitrary point that has not been visited and marks it as a core point if there are enough neighboring points within `eps` distance. It then recursively finds all points that are reachable from this core point, forming a cluster. This process continues until all points in the cluster have been visited or no more core points can be found. Points that do not belong to any cluster and are considered noise (outliers) if they do not meet the `min_samples` requirement within their neighborhood.

The algorithm also identifies border points, which are points that are neighbors of a core point but do not have enough neighbors themselves to be classified as core points.

Why It Matters

DBSCAN is particularly useful in scenarios where clusters may have irregular shapes or varying densities. Its ability to identify noise and outliers makes it robust against datasets with complex structures, which are common in real-world applications such as image segmentation, anomaly detection, and spatial data analysis.

Moreover, DBSCAN can be applied to high-dimensional spaces without requiring the number of clusters to be specified beforehand, making it a versatile tool for various machine learning tasks.

Real-World Applications

DBSCAN has been successfully used in numerous applications. For example, in image segmentation, DBSCAN can help identify regions of interest by clustering pixels based on their color and spatial proximity. In fraud detection, it can be employed to find unusual patterns that do not fit into the normal clusters formed by legitimate transactions.

In environmental science, DBSCAN has been used to analyze satellite images for land cover classification or to detect changes in vegetation patterns over time.

Frequently asked questions

Try it live

Everything above runs in your browser — open DBSCAN: Finding Clusters of Any Shape by Density, Not Distance (2D) and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.