DBSCAN Clustering Algorithm
DBSCAN stands for
Density-Based Spatial Clustering of Applications with Noise.
It is an unsupervised machine learning clustering algorithm that groups
closely packed data points and identifies isolated points as noise.
1. What is DBSCAN?
DBSCAN creates clusters by looking at the density of data points.
Instead of asking how many clusters should be created, DBSCAN searches for
regions where points are sufficiently close together.
```
One important advantage is that DBSCAN can discover
non-spherical and arbitrary-shaped clusters.
It can also identify observations that do not belong to any dense region
as noise or outliers.
Unlike K-Means, DBSCAN does not require the number of clusters
to be specified beforehand.
```
2. Important DBSCAN Concepts
Core Point
A point is a core point when it has at least the required
number of neighboring points within the specified epsilon distance.
Border Point
A border point is close enough to a core point to belong to its cluster,
but it does not itself contain enough neighboring points to satisfy
the minimum-density requirement.
Noise Point
A noise point is neither a core point nor a border point.
DBSCAN can therefore leave this observation outside the discovered clusters.
3. Main DBSCAN Parameters
```
eps
Maximum distance used to determine whether two points are neighbors.
min_samples
Minimum number of samples required in a neighborhood for a point
to be considered a core point.
metric
Distance function used by DBSCAN. Euclidean distance is the default,
but Manhattan, Cosine, Haversine and other metrics can be used.
algorithm
Method used for nearest-neighbor search, such as auto, ball_tree,
kd_tree or brute.
leaf_size
Controls the leaf size used by tree-based nearest-neighbor searches.
p
Power parameter for the Minkowski distance when applicable.
```
4. How DBSCAN Works
Step 1 — Select Parameters
Choose values for eps and min_samples.
Step 2 — Select an Unvisited Point
DBSCAN begins by selecting an unvisited observation.
Step 3 — Examine Its Neighborhood
All points within the epsilon distance are identified.
Step 4 — Identify a Core Point
If enough points exist within the neighborhood, the point becomes
a core point and a new cluster can be started.
Step 5 — Expand the Cluster
Neighboring core points are recursively examined and their neighbors
are added to the same cluster.
Step 6 — Identify Border Points
Points close to a core point but without enough neighbors themselves
can become border points.
Step 7 — Identify Noise
Points that cannot be associated with a density-connected cluster
remain classified as noise.
5. Density Reachability
Density reachability describes how one point can be
reached from another through a chain of sufficiently dense points.
```
If point A is a core point and point B is within its epsilon neighborhood,
B can be directly density-reachable from A. A chain of such relationships
can connect points across an entire cluster.
```
6. Density Connectivity
Two points are density-connected when they can both
be reached through density-based connections from a suitable core point.
```
Density connectivity is therefore one of the foundations used by DBSCAN
to determine which observations belong to the same cluster.
```
7. Choosing the eps Parameter
Selecting an appropriate eps value is important.
One systematic approach is the k-distance graph.
```
- Choose a value of k related to
min_samples.
- Calculate each observation's distance to its k-th nearest neighbor.
- Sort these distances.
- Plot the sorted distances.
- Look for an elbow in the graph.
- Use the elbow as a possible starting point for
eps.
```
8. Choosing min_samples
A commonly suggested starting point is:
```
min_samples = 2 × number_of_features
This is only a starting guideline. The appropriate value depends on
the dataset, its dimensionality, noise level and clustering objective.
```
9. Distance Metrics
| Metric |
Typical Use |
| Euclidean |
General numerical data and geometric distance. |
| Manhattan |
Useful for grid-like or coordinate-based distances. |
| Cosine |
Useful for high-dimensional vectors such as text representations. |
| Haversine |
Useful when working with latitude and longitude coordinates. |
10. Why Feature Scaling Matters
Important:
DBSCAN depends directly on distance. If one feature has a much larger
numerical range than another, it can dominate the distance calculation.
Two commonly used scaling techniques are:
```
- StandardScaler — standardizes features around zero.
- MinMaxScaler — scales features into a specified range,
commonly 0 to 1.
```
11. Python Implementation of DBSCAN
The following example follows the workflow demonstrated in the
DataCamp tutorial using a two-moon dataset. The example uses
eps=0.15 and min_samples=5.
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
from sklearn.cluster import DBSCAN
from sklearn.neighbors import NearestNeighbors
# -----------------------------------
# 1. Create the dataset
# -----------------------------------
X, y = make_moons(
n_samples=200,
noise=0.05,
random_state=42
)
# -----------------------------------
# 2. Visualize original data
# -----------------------------------
plt.figure(figsize=(8, 5))
plt.scatter(
X[:, 0],
X[:, 1]
)
plt.title("Original Moon Dataset")
plt.xlabel("Feature 1")
plt.ylabel("Feature 2")
plt.show()
# -----------------------------------
# 3. K-distance graph
# -----------------------------------
k = 5
neigh = NearestNeighbors(n_neighbors=k)
neigh.fit(X)
distances, indices = neigh.kneighbors(X)
distances = np.sort(distances[:, k-1])
plt.figure(figsize=(8, 5))
plt.plot(distances)
plt.xlabel("Points")
plt.ylabel("5th Nearest Neighbor Distance")
plt.title("K-Distance Graph")
plt.show()
# -----------------------------------
# 4. DBSCAN
# -----------------------------------
epsilon = 0.15
min_samples = 5
dbscan = DBSCAN(
eps=epsilon,
min_samples=min_samples
)
clusters = dbscan.fit_predict(X)
# -----------------------------------
# 5. Visualize clusters
# -----------------------------------
plt.figure(figsize=(8, 5))
plt.scatter(
X[:, 0],
X[:, 1],
c=clusters
)
plt.title("DBSCAN Clustering")
plt.xlabel("Feature 1")
plt.ylabel("Feature 2")
plt.show()
# -----------------------------------
# 6. Count clusters
# -----------------------------------
n_clusters = len(
set(clusters)
) - (1 if -1 in clusters else 0)
n_noise = list(clusters).count(-1)
print("Number of clusters:", n_clusters)
print("Number of noise points:", n_noise)
In scikit-learn, DBSCAN represents noise points using the label
-1. The DataCamp example reports two clusters and five
noise points for its demonstrated configuration.
12. DBSCAN vs Other Clustering Techniques
| Feature |
K-Means |
K-Medoids |
Hierarchical |
DBSCAN |
| Type |
Centroid-based |
Medoid-based |
Hierarchy-based |
Density-based |
| Number of clusters |
Specify K |
Specify K |
Can choose using dendrogram/cut |
Not required beforehand |
| Cluster shape |
Generally convex/spherical |
Generally compact clusters |
Depends on linkage and distance |
Can discover arbitrary shapes |
| Noise detection |
No explicit noise class |
No explicit noise class |
No explicit DBSCAN-style noise class |
Yes |
| Outlier handling |
Every point assigned |
Every point assigned |
Every point placed in hierarchy |
Can label points as noise |
| Non-linear clusters |
Usually difficult |
Usually difficult |
Can handle many structures |
Strong capability |
| Main parameters |
K |
K |
Linkage/distance |
eps, min_samples |
The DataCamp comparison particularly highlights the differences between
DBSCAN and K-Means in cluster shape, predefined cluster count, noise handling,
scalability and parameter sensitivity.
13. When DBSCAN is Useful
- When the number of clusters is unknown.
- When clusters are not spherical.
- When the dataset contains possible outliers.
- When dense regions are more meaningful than distance from a centroid.
- When arbitrary-shaped clusters need to be discovered.
14. Limitations of DBSCAN
- Results can be sensitive to
eps and min_samples.
- Very different cluster densities can be difficult for standard DBSCAN.
- Distance becomes less intuitive in very high-dimensional data.
- Large datasets can require substantial computational resources.
- Feature scaling is important when features have different ranges.
```
Alternatives such as OPTICS and
HDBSCAN can be considered for datasets with
challenging or varying density structures.
```
15. Single Python Program — K-Means vs K-Medoids vs Hierarchical vs DBSCAN
The following program runs four clustering techniques on the same
two-moon dataset so that their behavior can be compared using the
same input data.
# ==========================================================
# COMPARISON OF CLUSTERING TECHNIQUES
# K-MEANS
# K-MEDOIDS
# HIERARCHICAL CLUSTERING
# DBSCAN
# ==========================================================
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import (
KMeans,
AgglomerativeClustering,
DBSCAN
)
from sklearn_extra.cluster import KMedoids
# ----------------------------------------------------------
# 1. Generate Dataset
# ----------------------------------------------------------
X, y = make_moons(
n_samples=200,
noise=0.05,
random_state=42
)
# ----------------------------------------------------------
# 2. Feature Scaling
# ----------------------------------------------------------
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)
# ----------------------------------------------------------
# 3. K-MEANS
# ----------------------------------------------------------
kmeans = KMeans(
n_clusters=2,
random_state=42,
n_init=10
)
kmeans_labels = kmeans.fit_predict(X_scaled)
# ----------------------------------------------------------
# 4. K-MEDOIDS
# ----------------------------------------------------------
kmedoids = KMedoids(
n_clusters=2,
random_state=42
)
kmedoids_labels = kmedoids.fit_predict(X_scaled)
# ----------------------------------------------------------
# 5. HIERARCHICAL CLUSTERING
# ----------------------------------------------------------
hierarchical = AgglomerativeClustering(
n_clusters=2,
linkage="ward"
)
hierarchical_labels = hierarchical.fit_predict(X_scaled)
# ----------------------------------------------------------
# 6. DBSCAN
# ----------------------------------------------------------
dbscan = DBSCAN(
eps=0.3,
min_samples=5
)
dbscan_labels = dbscan.fit_predict(X_scaled)
# ----------------------------------------------------------
# 7. Count DBSCAN Clusters and Noise
# ----------------------------------------------------------
dbscan_clusters = len(
set(dbscan_labels)
) - (1 if -1 in dbscan_labels else 0)
dbscan_noise = list(
dbscan_labels
).count(-1)
# ----------------------------------------------------------
# 8. Display Results
# ----------------------------------------------------------
print("====================================")
print("CLUSTERING COMPARISON")
print("====================================")
print("K-Means clusters : 2")
print("K-Medoids clusters : 2")
print("Hierarchical clusters : 2")
print("DBSCAN clusters :", dbscan_clusters)
print("DBSCAN noise points :", dbscan_noise)
# ----------------------------------------------------------
# 9. Visualization
# ----------------------------------------------------------
fig, axes = plt.subplots(
2,
2,
figsize=(14, 10)
)
# K-Means
axes[0, 0].scatter(
X_scaled[:, 0],
X_scaled[:, 1],
c=kmeans_labels
)
axes[0, 0].set_title("K-Means")
# K-Medoids
axes[0, 1].scatter(
X_scaled[:, 0],
X_scaled[:, 1],
c=kmedoids_labels
)
axes[0, 1].set_title("K-Medoids")
# Hierarchical
axes[1, 0].scatter(
X_scaled[:, 0],
X_scaled[:, 1],
c=hierarchical_labels
)
axes[1, 0].set_title("Hierarchical Clustering")
# DBSCAN
axes[1, 1].scatter(
X_scaled[:, 0],
X_scaled[:, 1],
c=dbscan_labels
)
axes[1, 1].set_title("DBSCAN")
for ax in axes.flat:
ax.set_xlabel("Feature 1")
ax.set_ylabel("Feature 2")
plt.tight_layout()
plt.show()
16. Important Installation for K-Medoids
pip install scikit-learn-extra
Note:
K-Medoids is commonly imported from
sklearn_extra.cluster, while K-Means, DBSCAN and
Agglomerative Clustering are available through scikit-learn.
17. Overall Workflow
Dataset → Preprocessing → Scaling → Choose Algorithm → Clustering → Visualization → Interpretation
For DBSCAN specifically:
```
Dataset
```
↓
Feature Selection
↓
Feature Scaling
↓
Choose min_samples
↓
Create K-Distance Graph
↓
Select eps
↓
Apply DBSCAN
↓
Identify Core / Border / Noise
↓
Visualize Clusters
↓
Interpret Results
18. Quick Summary
| Algorithm |
Main Idea |
Needs K? |
Noise Detection |
| K-Means |
Groups observations around centroids. |
Yes |
No |
| K-Medoids |
Groups observations around representative medoid points. |
Yes |
No explicit noise class |
| Hierarchical |
Builds a hierarchy of nested clusters. |
Can be selected by cutting hierarchy |
No explicit DBSCAN-style noise class |
| DBSCAN |
Groups points according to density. |
No |
Yes |
