{"id":21359,"date":"2020-09-26T11:04:32","date_gmt":"2020-09-26T05:34:32","guid":{"rendered":"https:\/\/www.mygreatlearning.com\/blog\/dbscan-algorithm\/"},"modified":"2025-01-14T15:25:27","modified_gmt":"2025-01-14T09:55:27","slug":"dbscan-algorithm","status":"publish","type":"post","link":"https:\/\/www.mygreatlearning.com\/blog\/dbscan-algorithm\/","title":{"rendered":"DBSCAN Algorithm | How does it work?"},"content":{"rendered":"\n

Clustering is an unsupervised learning method that divides data points into specific groups, such that data points in a group have similar properties than those in other groups. <\/p>\n\n\n\n

Contributed by: Pavan Kumar Raja <\/a><\/em><\/p>\n\n\n\n

There are a variety of algorithms, and each defines a cluster differently. Some algorithms look for instances centred around a particular point, called a centroid. Some algorithms look for continuous regions of densely packed instances: these clusters can take on any shape. Some algorithms are hierarchical, looking for clusters of clusters. Unfortunately, it\u2019s hard to tell which one is better for your dataset and the performance of each algorithm depends on the unknown properties of the probability distribution of the underlying dataset.<\/p>\n\n\n\n

Centrally, all clustering methods use the same approach i.e. first calculate similarities and then use it to cluster the data points. Here we will focus on the Density-based spatial clustering of applications with noise (<\/strong>DBSCAN)<\/strong> clustering method, which works well in spatial clustering applications.<\/p>\n\n\n\n

What is DBSCAN?<\/strong><\/h2>\n\n\n\n

DBSCAN is a clustering algorithm that defines clusters as continuous regions of high density and works well if all the clusters are dense enough and well separated by low-density regions.<\/p>\n\n\n\n

In the case of DBSCAN, instead of guessing the number of clusters, will define two hyperparameters: epsilon<\/em> and minPoints<\/em> to arrive at clusters.<\/p>\n\n\n\n

    \n
  1. Epsilon (\u03b5)<\/em><\/strong>: <\/strong>A distance measure that will be used to locate the points\/to check the density in the neighbourhood of any point.<\/li>\n\n\n\n
  2. minPoints(n)<\/em><\/strong>: <\/strong>The minimum number of points (a threshold) clustered together for a region to be considered dense.<\/li>\n<\/ol>\n\n\n\n

    Note: <\/strong><\/p>\n\n\n\n

    In the case of higher dimensions, epsilon<\/em> can be viewed as the radius of that hypersphere and minPoints<\/em> as the minimum number of data points required inside that hypersphere.<\/p>\n\n\n\n

    How does the DBSCAN Algorithm create Clusters?<\/strong><\/h2>\n\n\n\n

    Algorithms start by picking a point(one record) x <\/strong>from your dataset at random and assign it to a cluster 1. Then it counts how many points are located within the \u03b5 (epsilon) distance from x<\/strong>. If this quantity is greater than or equal to minPoints (n), then considers it as core point, then it will pull out all these \u03b5-neighbours to the same cluster 1. It will then examine each member of cluster 1 and find their respective \u03b5 -neighbours. If some member of cluster 1 has n <\/em>or more\u03b5-neighbours, it will expand cluster 1 by putting those \u03b5-neighbours to the cluster. It will continue expanding cluster 1 until there are no more examples to put in it. <\/p>\n\n\n\n

    In the latter case, it will pick another point from the dataset not belonging to any cluster and put it to cluster 2. It will continue like this until all examples either belong to some cluster or are marked as outliers. <\/p>\n\n\n\n

    One can observe three different instances\/points as a part of DBSCAN clustering.
    <\/p>\n\n\n\n