Density-Based Methods
June 5, 2023
Density-Based Methods
Density-Based Clustering refers to unsupervised learning methods that identify distinctive groups/clusters in the data, based on the idea that a cluster in data space is a contiguous region of high point density, separated from other such clusters by contiguous regions of low point density.
Density-Based Spatial Clustering of Applications with Noise (DBSCAN) is a base algorithm for density-based clustering. It can discover clusters of different shapes and sizes from a large amount of data, which is containing noise and outliers.
Types of Density Based methods :
There are a number of density based clustering methods such as DBSCAN, OPTICS, DENCLUE, VDBSCAN, DVBSCAN, DBCLASD and ST-DBSCAN.
There are three types of points after the DBSCAN clustering is complete:
• Core — This is a point that has at least m points within distance
n from itself.
• Border — This is a point that has at least one Core point at a
distance n.
• Noise — This is a point that is neither a Core nor a Border.
The Complexity of DBSCAN:
• Best Case: If an indexing system is used to store the dataset such
that neighborhood queries are executed in logarithmic time, we get O(nlogn) average
runtime complexity.
• Worst Case: Without the use of index structure or on degenerated
data (e.g. all points within a distance less than ε), the worst-case run time
complexity remains O(n²).
• Average Case: Same as best/worst case depending on data and
implementation of the algorithm.
Interview Questions :
1. What is Density based clustering?
2. What is DBSCAN?
3. What are the methods in Density Based clustering?
4. What is the best case Complexity of DBSCAN?
5. What is Core based DBSCAN?
Relative Blogs
June 10, 2023
June 10, 2023
Feb 27, 2023