DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is a density-based clustering algorithm used in data mining and machine learning. It groups together points that are closely packed and marks as outliers points that lie alone in low-density regions. The algorithm relies on two parameters: epsilon (eps), the radius of the neighborhood around a point, and minPts, the minimum number of points required to form a dense region.

A point is a core point if its eps-neighborhood contains at least minPts points. Points that are not core points but lie within the eps-neighborhood of a core point are border points. Points that are neither core nor border are noise. Clusters are formed by connecting core points that are density-reachable and by including density-reachable border points. The method does not require specifying the number of clusters in advance and can identify clusters of arbitrary shape. It is relatively robust to outliers since noise points are not assigned to any cluster.

In terms of performance, the complexity depends on the data structure used for neighbor searches; with spatial indexes such as a k-d tree, the average time can be near O(n log n), though the worst-case is O(n^2). DBSCAN requires a distance metric, commonly Euclidean distance. It can struggle with datasets that contain clusters of varying densities or data in high-dimensional spaces where distances become less meaningful. Variants such as OPTICS and HDBSCAN address some of these limitations by handling density differences and yielding a hierarchy of clusters.

DBSCAN is implemented in many software libraries, including scikit-learn, MATLAB, and R. It is applied in geospatial analysis, anomaly detection, and image segmentation due to its ability to discover clusters with irregular shapes and to handle noise.