DBSCAN Clustering Algorithm
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
4. How DBSCAN Works
Choose values for eps and min_samples.
DBSCAN begins by selecting an unvisited observation.
All points within the epsilon distance are identified.
If enough points exist within the neighborhood, the point becomes a core point and a new cluster can be started.
Neighboring core points are recursively examined and their neighbors are added to the same cluster.
Points close to a core point but without enough neighbors themselves can become border points.
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_featuresThis 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
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)-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
epsandmin_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-extrasklearn_extra.cluster, while K-Means, DBSCAN and
Agglomerative Clustering are available through scikit-learn.
17. Overall Workflow
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 Results18. 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 |