13. Density-Based Clustering Algorithms
Society for Industrial and Applied Mathematics eBooks · 2007
The density-based clustering approach is a methodology that is capable of finding arbitrarily shaped clusters, where clusters are defined as dense regions separated by low-density regions. A density-based algorithm needs only one scan of the original data set and can handle noise. The number of clusters is not required, since density-based clustering algorithms can automatically detect the clusters, along with the natural number of clusters (El-Sonbaty et al., 2004). 13.1 DBSCAN Ester et al. (1996) proposed a density-based clustering algorithm called DBSCAN (Density-Based Spatial Clustering of Applications with Noise) to discover arbitrarily shaped clusters. Only one input parameter is required, and the algorithm also supports the user in determining an appropriate value for this input parameter. To describe the algorithm, we start with some definitions and notation. An important concept in density-based algorithms is the ϵ-neighborhood of a point. Let x be a point. Then the ϵ-neighborhood of x is denoted by Nϵ (x) and is defined as follows. Definition 13.1 (ϵ-neighborhood of a point). The ϵ-neighborhood of a point x is defined as Nϵ (x)= {y ∈ D : d (x,y)≤ϵ } , where D is the data set and d (·, ·) is a certain distance function. Definition 13.2 (Directly density-reachable). A point x is said to be directly density-reachable from a point y (with respect to ϵ and Nmin) if 1. x ∈ Nϵ (y); 2. | Nϵ(y) | ≥ Nmin, where | Nϵ (y) | denotes the number of points in Nϵ(y).