Objectives
The objectives of this section are:
define density-based clustering
explain the major parts
introduce the DBSCAN algorithm
list the limitations and advantages of this method
Outcomes
By the time you have completed this section you will be able to:
explain the basic DBSCAN algorithm
label points into the appropriate group type
determine which scenarios this algorithm would yield good results.
Definition
Density-based clustering algorithms are algorithms that aim to discover areas of high density that are separated from each other by areas of low-density. DBSCAN is a popular density-based clustering algorithm but before we launch into a description one needs to understand some fundamental parts of a center-based approach.
In this approach density is estimated for a particular point in a data set by counting the number of points within a certain radius. The size of the radius is crucial because if the radius is too large then all points in the data set will have the same density and if the radius is too small then the density of each data point will be 1.
Data points can be classified into three categories
- Core points: these are points that have more than a specified number of points (MinPts) within the chosen radius (E). Graphically speaking, these are points that are in the interior of a cluster. MinPts is a user specified threshold.
- Border point: is a point that has fewer than MinPts within the radius (E) but is still in the neighborhood of a core point.
- Noise point: is any point that is neither a core point nor a border point.
Figure 1 is a labeled diagram which shows the classification of certain points.
