DBSCAN Clustering (Density-Based Spatial Clustering of Applications with Noise) is an unsupervised algorithm that groups points lying in densely packed regions and labels points in sparse regions as noise.<\/p>\n\n\n\n
It requires no preset number of clusters and can recover clusters of arbitrary shape, making it a common alternative to K-Means for irregular, noisy data.<\/p>\n\n\n\n
eps<\/code> (neighborhood radius) and min_samples<\/code> (points required for a dense region). Features should be scaled first.<\/li>\n\n\n\n- It copes well with curved clusters and outliers, but it uses one global
eps<\/code>, so it handles clusters of different density and high-dimensional data poorly.<\/li>\n<\/ul>\n\n\n\n<\/p>\n\n\n\n
What is DBSCAN Clustering?<\/strong><\/h2>\n\n\n\nDBSCAN Clustering is a density-based method that defines a cluster as a maximal set of points connected through dense neighborhoods. <\/p>\n\n\n\n
A neighborhood is dense when it holds at least min_samples<\/code> points within a radius of eps<\/code>, and points that no dense neighborhood reaches are treated as noise.<\/p>\n\n\n\n<\/p>\n\n\n\n
Key Parameters<\/strong><\/h3>\n\n\n\neps<\/strong> is the largest distance at which two points count as neighbors. The neighborhood of a point contains every point within eps<\/code> of it, the point itself included. A value that is too small fragments clusters, and one that is too large merges them.<\/p>\n\n\n\nmin_samples<\/strong> (called minPts in the original paper) is the number of points a neighborhood must contain for its center to qualify as a core point. scikit-learn counts the point itself. Higher values demand denser regions and produce more noise. The defaults are eps=0.5<\/code> and min_samples=5<\/code>.<\/p>\n\n\n\n<\/p>\n\n\n\n
DBSCAN is one of dozens of algorithms a working ML engineer must choose between. HCL GUVI\u2019s Intel & IITM Pravartak Certified AI\/ML Course teaches that wider toolkit, from classical machine learning to deep learning and Generative AI, in live classes led by industry experts and Intel engineers, with no prior coding experience required!<\/em><\/strong><\/p>\n\n\nEnroll in HCL GUVI's AI\/ML Course<\/a><\/div>\n\n\n<\/p>\n\n\n\n
How DBSCAN Works<\/strong><\/h2>\n\n\n\nEvery point receives one of three roles:<\/p>\n\n\n\n
\n- Core point:<\/strong> at least
min_samples<\/code> points, itself included, lie within eps<\/code>.<\/li>\n\n\n\n- Border point:<\/strong> fewer than
min_samples<\/code> neighbors, but within eps<\/code> of a core point.<\/li>\n\n\n\n- Noise point:<\/strong> neither a core point nor a border point.<\/li>\n<\/ul>\n\n\n\n
The algorithm<\/a> runs as follows:<\/p>\n\n\n\n\n- Select an unvisited point and find every point within
eps<\/code> of it.<\/li>\n\n\n\n- If the count is below
min_samples<\/code>, tentatively mark the point as noise and move on.<\/li>\n\n\n\n- Otherwise, start a new cluster containing the point and its neighbors.<\/li>\n\n\n\n
- For each neighbor that is also a core point, add that neighbor’s own neighbors to the cluster. Continue until nothing more can be added.<\/li>\n\n\n\n
- Pick the next unvisited point and repeat until all points have been visited.<\/li>\n<\/ol>\n\n\n\n
A point first marked as noise can later be claimed as a border point by a cluster that reaches it.<\/p>\n\n\n\n
<\/p>\n\n\n\n
Density Reachability and Connectivity<\/strong><\/h2>\n\n\n\n\n- Directly density-reachable:<\/strong> point q is directly density-reachable from p if q lies within
eps<\/code> of p and p is a core point.<\/li>\n\n\n\n- Density-reachable:<\/strong> q is density-reachable from p if a chain of points leads from p to q, each directly density-reachable from the one before it.<\/li>\n\n\n\n
- Density-connected:<\/strong> p and q are density-connected if some point o exists from which both are density-reachable.<\/li>\n<\/ul>\n\n\n\n
A cluster is a maximal set of density-connected points. A border point cannot extend a chain, so reachability is asymmetric: a core point reaches a border point, but not the reverse. <\/p>\n\n\n\n
When a border point lies within eps<\/code> of core points from two clusters, it joins whichever cluster reaches it first, so its assignment can depend on the row order of the data.<\/p>\n\n\n\n<\/p>\n\n\n\n
DBSCAN Clustering Implementation in Python<\/strong><\/h2>\n\n\n\nThe code below, run with scikit-learn 1.9.1, generates 300 points in four blobs and compares three parameter settings.<\/p>\n\n\n\n
import numpy as np\nimport matplotlib.pyplot as plt\nfrom sklearn.cluster import DBSCAN\nfrom sklearn.datasets import make_blobs\nfrom sklearn.metrics import silhouette_score, adjusted_rand_score\n\nX, y_true = make_blobs(n_samples=300, centers=4, cluster_std=0.50, random_state=42)\n\nsettings = {\"A\": (0.2, 5), \"B\": (0.5, 5), \"C\": (0.5, 15)}\nresults = {}\n\nfor name, (eps, min_samples) in settings.items():\n labels = DBSCAN(eps=eps, min_samples=min_samples).fit_predict(X)\n results[name] = labels\n n_clusters = len(set(labels)) - (1 if -1 in labels else 0)\n n_noise = int(np.sum(labels == -1))\n sil = silhouette_score(X, labels)\n ari = adjusted_rand_score(y_true, labels)\n print(f\"Case {name}: clusters={n_clusters}, noise={n_noise}, \"\n f\"silhouette={sil:.2f}, ARI={ari:.2f}\")\n\nfig, axes = plt.subplots(1, 3, figsize=(15, 4))\nfor ax, (name, labels) in zip(axes, results.items()):\n noise = labels == -1\n ax.scatter(X[~noise, 0], X[~noise, 1], c=labels[~noise], cmap=\"tab10\", s=18)\n ax.scatter(X[noise, 0], X[noise, 1], c=\"black\", marker=\"x\", s=18)\n ax.set_title(f\"Case {name}: eps={settings[name][0]}, min_samples={settings[name][1]}\")\nplt.show()<\/code><\/pre>\n\n\n\nOutput:<\/strong><\/p>\n\n\n\nCase A: clusters=9, noise=126, silhouette=-0.11, ARI=0.22\nCase B: clusters=4, noise=7, silhouette=0.85, ARI=0.97\nCase C: clusters=4, noise=33, silhouette=0.71, ARI=0.84<\/code><\/pre>\n\n\n\nCase A <\/strong>uses an eps<\/code> too small for this data, so the points split into nine fragments and 126 of 300 are labeled noise. <\/p>\n\n\n\nCase B<\/strong> recovers the four generating groups almost exactly. <\/p>\n\n\n\nCase C<\/strong> keeps the same eps<\/code> but raises min_samples<\/code> to 15, which leaves four clusters but moves 33 points into noise.<\/p>\n\n\n\nAdjusted Rand Index (ARI) compares labels with known ground truth, so it applies only to labeled or synthetic data. <\/p>\n\n\n\n
The silhouette score above treats noise as one extra group and favors compact, convex clusters, so it is an unreliable judge of DBSCAN on curved shapes. Density-based validation (DBCV) suits unlabeled data better.<\/p>\n\n\n\n
<\/p>\n\n\n\n
What the -1 Label Means<\/strong><\/h2>\n\n\n\nDBSCAN.labels_<\/code> holds one integer per point. Values 0, 1, 2 and so on identify clusters, and -1 identifies noise. The value -1 is not a cluster and must be excluded from cluster counts. <\/p>\n\n\n\nThe indices of core points are stored in core_sample_indices_<\/code>, and any labeled point outside that array is a border point. In Case B, 277 points are core, 16 are border, and 7 are noise.<\/p>\n\n\n\n<\/p>\n\n\n\n
Distance Metric and Feature Scaling<\/strong><\/h2>\n\n\n\nNeighborhoods are measured with the metric<\/code> parameter, which defaults to Euclidean. Because eps<\/code> is one distance applied across all features, a feature measured in thousands will dominate one measured in decimals, so standardize features before clustering<\/a>. <\/p>\n\n\n\nFor latitude and longitude, use the haversine metric on coordinates converted to radians, and express eps<\/code> in radians by dividing kilometers by 6371.0088, the mean Earth radius.<\/p>\n\n\n\n<\/p>\n\n\n\n
from sklearn.preprocessing import StandardScaler\n\nX_scaled = StandardScaler().fit_transform(X)\n\n# Geographic data: coordinates in degrees, neighborhood radius of 0.5 km\ncoords = np.radians(latlon_degrees) # columns: latitude, longitude\ngeo = DBSCAN(eps=0.5 \/ 6371.0088, min_samples=10,\n metric=\"haversine\", algorithm=\"ball_tree\").fit(coords)<\/code><\/pre>\n\n\n\n<\/p>\n\n\n\n
How to Choose eps and min_samples<\/strong><\/h2>\n\n\n\nBegin with min_samples<\/code>. A common heuristic<\/a> is at least the number of features plus one, and often twice the number of features, which gives 4 for two-dimensional data. Then estimate eps<\/code> with a k-distance graph:<\/p>\n\n\n\n\n- Set k equal to
min_samples<\/code>.<\/li>\n\n\n\n- Compute, for every point, the distance to its k-th nearest neighbor. The point itself is returned as its own first neighbor, matching how scikit-learn counts
min_samples<\/code>.<\/li>\n\n\n\n- Sort these distances in ascending order and plot them.<\/li>\n\n\n\n
- Read
eps<\/code> from the elbow, where the curve turns sharply upward.<\/li>\n<\/ol>\n\n\n\n<\/p>\n\n\n\n
from sklearn.neighbors import NearestNeighbors\n\nmin_samples = 5\ndistances, _ = NearestNeighbors(n_neighbors=min_samples).fit(X).kneighbors(X)\nk_distances = np.sort(distances[:, -1])\n\nplt.plot(k_distances)\nplt.xlabel(\"Points sorted by distance\")\nplt.ylabel(\"Distance to neighbor 5 (point itself counted)\")\nplt.title(\"k-distance graph\")\nplt.show()<\/code><\/pre>\n\n\n\nOn the blob data, 90% of the points have a distance below about 0.47, after which the curve climbs to a maximum of 1.36. An eps<\/code> near 0.5 is therefore a sensible choice.<\/p>\n\n\n\nDuring tuning, one giant cluster means eps<\/code> is too large, while mostly noise means eps<\/code> is too small or min_samples<\/code> too high.<\/p>\n\n\n\n<\/p>\n\n\n\n
Choosing eps<\/code> and min_samples<\/code> is learned by running the algorithm on messy datasets, not by reading about it. HCL GUVI\u2019s Intel & IITM Pravartak Certified AI\/ML Course builds that experience through 20+ industry-grade projects and a capstone, with 1:1 doubt sessions with subject matter experts when a result looks wrong!<\/strong><\/em><\/p>\n\n\nEnroll in HCL GUVI's AI\/ML Course<\/a><\/div>\n\n\n<\/p>\n\n\n\n
DBSCAN vs K-Means vs Hierarchical Clustering<\/strong><\/h2>\n\n\n\n