Density Based Clustering Techniques: Finding Arbitrary Shapes

Imagine trying to sort a crowd of people at a large, bustling city park on a sunny afternoon. Some people are clustered in tight groups for a picnic, others are in a long, winding line for an ice cream truck, and a few individuals are sitting alone, far from anyone else. If you tried to find the “center” of each group, you’d struggle. The picnic group has a center, but what about the line? And what about the person sitting alone-are they a “group of one”? This is the exact problem that many classic clustering algorithms, like K-Means, run into. They are great at finding nice, round, blob-like clusters (like the picnic group) but fail when faced with arbitrary shapes (like the ice cream line) or identifying the lone individuals (outliers). This is where density-based clustering comes in.

Instead of looking for a central point, density-based clustering algorithms redefine what a “cluster” is. They look for areas of high density. A cluster is simply a region where many points are packed closely together, separated from other clusters by regions of low density. It’s an intuitive, human-centric way of seeing patterns, and the most popular algorithm that uses this logic is called DBSCAN (Density-Based Spatial Clustering of Applications with Noise).

What is density-based clustering, really? 🔗

At its core, the concept is simple: clusters are dense neighborhoods. Think back to that park. The picnic group is a dense neighborhood. The ice cream line is also a dense neighborhood (people are standing close to each other). The person sitting alone is in a very sparse, low-density neighborhood. Density-based clustering is the process of identifying these dense areas and calling them clusters, while identifying the sparse areas and calling them noise.

This approach is fundamentally different from centroid-based methods like K-Means. K-Means tries to find a ‘center’ for a pre-defined number of clusters (which you have to guess) and then assigns every single point to the nearest center. This means it assumes clusters are spherical and convex (like a ball). It also means that outliers get dragged into a cluster, skewing the results.

DBSCAN, on the other hand, makes no assumptions about the shape of the clusters. It just follows the “trail” of high-density points, allowing it to find complex, non-linear shapes. It also has a built-in mechanism for identifying and ignoring outliers, making it incredibly robust for real-world, messy data.

How DBSCAN connects the dots 🔗

DBSCAN’s magic relies on two simple, yet powerful, parameters that you, the data scientist, must define. These parameters set the rules for what “dense” means.

Understanding ‘Eps’ (the neighborhood radius) 🔗

The first parameter is Epsilon, or Eps (ε). This is a distance measurement. Think of it as drawing a small circle around every single data point. The radius of this circle is ‘Eps’. This circle defines the “neighborhood” of that point. Any other point that falls inside this circle is considered a neighbor. If you set a small Eps, you’re being very strict about what ‘close’ means. If you set a large Eps, you’re allowing points to be farther apart and still be considered neighbors.

Understanding ‘MinPts’ (the density threshold) 🔗

The second parameter is MinPts, or Minimum Points. This is a count. It sets the minimum number of points that must be inside a point’s ‘Eps’ neighborhood (including the point itself) for it to be considered a “dense” point. This is the core density threshold. If you set MinPts to 5, you’re saying, “To even *start* a cluster, I need to find a point that has at least 5 total points (including itself) in its immediate neighborhood.”

The step-by-step clustering process 🔗

Once you’ve set your Eps and MinPts, DBSCAN begins its work. It’s like a chain reaction or an “infection” model:

1. Pick a point: The algorithm starts by picking a random point from the dataset that hasn’t been visited yet.
2. Check its neighborhood: It looks inside that point’s ‘Eps’ radius and counts how many neighbors it has.
3. Classify the point: This is where the magic happens, and it leads to three distinct types of points.

This process of classifying points is the most critical part of the algorithm, so let’s break it down further.

The three types of points: Core, Border, and Noise 🔗

DBSCAN classifies every single point in your dataset into one of three categories. This classification is what ultimately builds the clusters and identifies the outliers.

Core points (the trendsetters) 🔗

A point is a Core Point if its neighborhood (the circle with radius Eps) contains at least ‘MinPts’ points. These are the hearts of the clusters. They are in dense areas. Think of a core point as a bustling street corner in a city center. It’s not just a single building; it’s surrounded by many other buildings, all close together. These are the points that can “seed” a new cluster. When DBSCAN finds a core point, it says, “Aha! A new cluster is born (or I’ve just found a part of an existing one).”

Border points (the followers) 🔗

A point is a Border Point if it is *not* a core point (it has fewer than MinPts in its neighborhood), but it *is* a neighbor of a core point. These points are on the edge of a cluster. Think of them as the quiet suburban houses on the very edge of the city. They aren’t dense enough to start their own city, but they are clearly connected to the main city center. Border points are considered part of the cluster, but they can’t be used to expand it further. They are the “followers,” not the “trendsetters.”

Noise points (the loners) 🔗

A point is a Noise Point (or outlier) if it is neither a core point nor a border point. This is a point that has fewer than MinPts in its neighborhood, *and* it isn’t close enough to any core point to be a border point. These are the isolated points, the loners. In our city analogy, this is the remote farmhouse 50 miles outside of town. DBSCAN is celebrated for its ability to find these points and simply label them “noise”, effectively filtering them out of the clustering analysis. K-Means, by contrast, would have tried to force this farmhouse into a cluster, likely skewing the results.

So, the full algorithm works like this: It finds a core point, starts a cluster, and then expands that cluster by “infecting” all of its neighbors. If one of those neighbors is *also* a core point, it infects *its* neighbors, and so on. This chain reaction continues until the cluster can’t expand anymore (it only reaches border points). The algorithm then finds the next unvisited core point and repeats the process, creating a new cluster. Any point left unvisited at the end is noise.

Why choose density-based methods? 🔗

This approach gives DBSCAN and other density-based methods some significant advantages over their centroid-based cousins.

Advantage 1: It can find clusters of any shape 🔗

This is the superpower. Because DBSCAN is just following a trail of dense points (like connecting the dots), it doesn’t care if the final shape is a circle, a long snake, two crescents, or a “Mickey Mouse” head. If the data density forms that shape, DBSCAN will find it. This makes it invaluable for tasks like geospatial analysis (e.g., finding all houses along a winding river) or image segmentation (e.g., identifying all the pixels that make up a complex object).

Advantage 2: It automatically detects noise and outliers 🔗

In the real world, data is messy. You almost always have measurement errors, typos, or just genuinely weird, anomalous events. As we saw, K-Means forces these outliers into a cluster, which can pull the cluster’s center (centroid) in the wrong direction. DBSCAN’s ability to flag these points as ‘Noise’ is a massive feature. It gives you a cleaner, more honest representation of the true groups in your data. You can then choose to either remove these outliers or investigate them separately (as they are often very interesting!).

Advantage 3: You don’t need to guess the number of clusters 🔗

One of the biggest frustrations with K-Means is the ‘k’ parameter. You have to tell it, “find me 3 clusters” or “find me 5 clusters.” But how do you know the right number? While methods exist to estimate ‘k’ (like the elbow method), it’s still a guess. DBSCAN doesn’t need this. You only provide the density parameters (Eps and MinPts), and the algorithm discovers the number of clusters *organically* from the data. It might find 2 clusters, or it might find 20. It tells you what it found, rather than you telling it what to find.

Are there any downsides? 🔗

Of course, no algorithm is perfect. DBSCAN’s power also comes with a few challenges. Its performance can suffer in very high-dimensional data (the so-called “curse of dimensionality”), where the concept of ‘distance’ and ‘neighborhood’ becomes less meaningful.

Its biggest practical challenge, however, is that it struggles with clusters of varying density. Because you set *one* Eps and *one* MinPts for the whole dataset, it works best when all the clusters have roughly similar density. If you have one super-dense city center and one sparse rural village, a single set of parameters might fail-an Eps and MinPts that works for the city will miss the village, and settings that find the village will merge the entire city into one giant blob. (More advanced algorithms like OPTICS were developed to help solve this specific problem).

Ultimately, density-based clustering is a powerful tool for any data scientist. By moving away from the idea of a “center” and focusing on “density,” it unlocks the ability to find patterns that other algorithms would miss, all while cleaning up the noise along the way.

What do you think? Can you think of another real-world example (besides geography or parks) where data might form non-spherical clusters? And if you were tuning this algorithm, how do you think you would go about choosing the ‘right’ values for Eps and MinPts?

References

1. https://www.geeksforgeeks.org/dbscan-clustering-in-ml-density-based-clustering/
2. https://scikit-learn.org/stable/modules/clustering.html#dbscan
3. https://www.kdnuggets.com/2020/04/dbscan-clustering-algorithm-machine-learning.html
4. https://towardsdatascience.com/understanding-dbscan-algorithm-and-implementation-from-scratch-c2562894f9c