20 Questions to Test your Skills on DBSCAN Clustering Algorithm

The most widely used density-based algorithm is Density-Based Spatial Clustering of Applications with Noise (DBSCAN), which uses the idea of density reachability and density connectivity.

Density-Based Clustering is an unsupervised machine learning method that identifies different groups or clusters in the data space. These clustering techniques are based on the concept that a cluster in the data space is a contiguous region of high point density, separated from other such clusters by contiguous regions of low point density.

Partition-based(K-means) and Hierarchical clustering techniques are highly efficient with normal-shaped clusters while density-based techniques are efficient in arbitrary-shaped clusters or detecting outliers.

The DBSCAN algorithm uses the following two user-defined as the input parameters for clustering:

• Epsilon (eps): It is defined as the maximum distance between two points which are considered as neighbouring points as well as can be viewed as the radius around each point.
• Minimum Points (min_samples or min_pts): This defines the minimum number of neighbouring points that a given point needs to be considered a core data point including the point itself. In general terms, it can be considered as the minimum number of observations that should be around that point within that radius.

For example, if we set the parameter min_pts to 4, then a given point needs to have 3 or more neighbouring data points to become a core data point.

Moreover, if the minimum number of points meet the epsilon distance requirement then they are considered as a cluster.

In the case of higher dimensions, the parameter epsilon can be viewed as the radius of that hypersphere and min_pts as the minimum number of data points required inside that hypersphere.

Reachability in terms of density sets up a point to be reachable from another if it lies within a distance of epsilon i.e, the radius of the circle from it.

On the contrary, Connectivity involves a transitivity based chaining-approach to determine whether points are located in a particular cluster.

For example, Two points x and y points could be connected if x->r->s->t->y where a->b implies that b is in the neighbourhood of a.

The DBSCAN Algorithm is sensitive to the choice of epsilon. When we have clusters with varying densities, then two cases arise i.e.,

If epsilon is too small: In such cases, we define the sparser clusters as noise i.e, result in the elimination of sparse clusters as outliers.

If epsilon is too large: In such cases, the denser clusters may be merged together, which gives the incorrect clusters.

Yes, the DBSCAN algorithm is very sensitive to the values of epsilon and min_pts. Therefore, it is crucial to understand how to choose the values of epsilon and min_pts. A minor variation in these values can change the results significantly produced by the DBSCAN algorithm.

The choice of distance function is tightly linked to the choice of epsilon and has a major impact on the outcomes. In general, it will be necessary to first identify a reasonable measure of similarity for the data set, before the parameter epsilon can be chosen.

There is no estimation for this parameter, but the distance functions need to be chosen appropriately based on the nature of the data set.

DBSCAN uses Euclidean distance by default, although other methods can also be used.

For Example, For geographical data, we use the great circle distance.

– Direct Density Reachable

– Density Reachable

– Density Connected

Direct density reachable: A point is called direct density reachable if it has a core point in its neighbourhood.

Density Reachable: A point is known as density reachable from another point if they are connected through a series of core points.

Density Connected: Two points are called density connected if there is a core point that is density reachable from both points.

We get three types of points upon applying a DBSCAN algorithm to a particular dataset – Core point, Border point, and noise point.

• Core Point: A data point is considered to be a core point if it has a minimum number of neighbouring data points (min_pts) at an epsilon distance from it. These min_pts include the original data points also.
• Border Point: A data point that has less than the minimum number of data points needed but has at least one core point in the neighbourhood.
• Noise Point: A data point that is not a core point or a border point is considered noise or an outlier.

In other words, we can say that if the number of neighbourhood points around x is greater or equal to MinPts then x is treated as a core point, if the neighbourhood points around x are less than MinPts but are close to a core point then x is treated as a border point. If x is neither a core point nor a border point then x is considered as a noisy point or an outlier.

 

The value for epsilon can then be chosen by using a K-distance Graph, which is a plot of the distance to the k = min_pts – 1 nearest neighbour ordered from the maximum to the minimum value. Then, choose the values of epsilon where this plot shows an “elbow”.

• Too small epsilon: If epsilon is chosen much too small, then a large part of the data will not be clustered.
• Too large epsilon: If epsilon is chosen much too large, then clusters will merge and the majority of objects will be in the same cluster.

Therefore in general smaller values of epsilon are preferable and usually, only a small fraction of points remain within this distance of each other.

 

Core Point: The data point x is the core point since it has at least min_pts (n) within epsilon (eps) distance.

Border Point: The data point y is the border point since it has at least one core point within epsilon (eps) distance and lower than min_pts (n) within epsilon (eps) distance from it.

Noise Point: The data point z is the noise point since it has no core points within epsilon (eps) distance.

 

Partitioning methods like K-means, PAM clustering, etc, and hierarchical clustering work for finding spherical-shaped clusters or convex clusters i.e, they are suitable only for compact and well-separated clusters and are also critically affected by the presence of noise and outliers in the data. Since real-life data often contain various irregularities such as:

• Clusters can be of arbitrary shape.
• Data may contain noisy points.

To overcome such problems DBSCAN is used as it produces more reasonable results than k-means across a variety of different distributions. We can elucidate this through the following fact:

                                                                  Image Source: Google Images

The different complexities of the algorithm are(N= no of data points) as follows:

Best Case: If we use a spatial indexing system to store the dataset like kd-tree or r-tree such that neighbourhood queries are executed in logarithmic time, then we get O(N log N) runtime complexity.

Worst Case: Without the use of index structure or on degenerated data the worst-case run time complexity remains O(N²).

Average Case: It is the same as the best/worst case depending on data and implementation of the algorithm.

As a rule of thumb, the minimum bound of the parameter “min_pts” can be computed from the number of dimensions D in the data set, as min_pts ≥ D + 1.

Case-1: The low value of min-Pts i.e, min_pts=1 does not make sense, as then every point on its own will already be a cluster.

Case-2: When min_pts ≤ 2, the result will be the same as that of the hierarchical clustering with the metric as a single link, having dendrogram cut at a height of epsilon.

Therefore, min_pts must be chosen at least 3.

However, larger values of min_pts are usually better when the data sets are having noise and as a result, it will yield more significant clusters.

Generally, as a rule of thumb min_pts = 2*D can be used.

To choose larger values, it may be necessary that the:

• Data is very large
• The Data is noisy i.e, contains outliers
• Data contains many duplicates

Some of the advantages of the DBSCAN algorithm are as follows:

1. It does not need a predefined number of clusters i.e, not require an initial specification of the number of clusters.

2. Basically, clusters can be of any random shape and size, including non-spherical ones.

3. It is able to identify noise data, popularly known as outliers.

4. Unlike K means, In DBSCAN the user does not give the number of clusters to be generated as input to the algorithm.

5. DBSCAN can find any shape of clusters.

6. Also, the cluster doesn’t have to be circular.

7. Density-based clustering algorithms don’t include the outliers in any of the clusters. Outliers were considered as noise while clustering and hence they will be eliminated from the cluster after the algorithm completion.

Some of the disadvantages of the DBSCAN algorithm are as follows:

1. DBSCAN clustering will fail when there are no density drops between clusters.

2. It seems to be difficult to detect outlier or noisy points if there is a variation in the density of the clusters.

3. It is sensitive to parameters i.e. it’s hard to determine the correct set of parameters.

4. Distance metric also plays a vital role in the quality of the DBSCAN algorithm

5. With high dimensional data, it does not give effective clusters

6. Not partitionable for multiprocessor systems.