DBCAN Clusturing
DBSCAN is a density-based algorithm.
It stands for Density-based spatial clustering of applications with noise
Density = number of points within a specified radius (ε)
- ε (epsilon) = radius
- minPts = minimum number of points
There are 3 type of point in DBCAN Clusturing
.A point is a core point if it has more than a specified number of points (MinPts) within Eps .These are points that are at the interior of a cluster -> red points
.A border point has fewer than MinPts within Eps, but is in the neighborhood of a core point -> yellow
Get Yahia’s stories in your inbox
Join Medium for free to get updates from this writer.
.A noise point is any point that is not a core point or a border point.-> blue
DBSCAN Algorithm
- Label all points as core, border, or noise points.
- Eliminate noise points (robust to outlier).
- Connect all core points within ε (eps) of each other.
- Group connected core points into separate clusters.
- Assign each border point to one of the clusters of its associated core points.
don’t get confused in this fig core molecule is blue border moleclue is green and noise can say outlier is red
How it differ from k means clusturing
primary benefit of it can form arbitarly shaped clusture while in k means clusture only form spherical clusture is possible.
DBSCAN Advantages:
- No need to specify the number of clusters — Automatically determines the number of clusters based on density.
- Detects arbitrarily shaped clusters — Can find clusters of any shape, not just spherical.
- Handles noise and outliers — Identifies and separates noise points effectively.
- Efficient with large datasets — Can handle large datasets, especially with spatial indexing.
DBSCAN Disadvantages:
- Sensitive to ε and minPts — Requires careful tuning of parameters.
- Struggles with varying densities — Doesn’t perform well if clusters have significantly different densities.
- Computationally expensive in high dimensions — Performance degrades with very high-dimensional data.
How to decide Minpts and ε.
k distance value means we are calculating the distance of every point to its k nearest points(suppose k=4 it means the distance of point to its 4th nearest points) and after calculating we sorted the distance and then plot it and where ever has a sharp point (elbow point) it indicates the threshold for ε (eps) in DBSCAN, where the density drops significantly, helping to identify clusters and noise.(usuall we take k (knn)=2 or may be 3,4. we cannot find minpts by this graph.but usually minpts is your dimension of data+1)
