Density-based Clustering Algorithm
A Density-based Clustering Algorithm is a clustering algorithm that define areas of higher density than the remainder of the data set.
- Example(s):
- Counter-Example(s):
- See: Density Estimation, Subspace Clustering Algorithm.
References
2013
- http://en.wikipedia.org/wiki/Cluster_analysis#Density-based_clustering
- In density-based clustering,[1] clusters are defined as areas of higher density than the remainder of the data set. Objects in these sparse areas - that are required to separate clusters - are usually considered to be noise and border points.
The most popular[2] density based clustering method is DBSCAN.[3] In contrast to many newer methods, it features a well-defined cluster model called "density-reachability". Similar to linkage based clustering, it is based on connecting points within certain distance thresholds. However, it only connects points that satisfy a density criterion, in the original variant defined as a minimum number of other objects within this radius. A cluster consists of all density-connected objects (which can form a cluster of an arbitrary shape, in contrast to many other methods) plus all objects that are within these objects' range. Another interesting property of DBSCAN is that its complexity is fairly low - it requires a linear number of range queries on the database - and that it will discover essentially the same results (it is deterministic for core and noise points, but not for border points) in each run, therefore there is no need to run it multiple times. OPTICS[4] is a generalization of DBSCAN that removes the need to choose an appropriate value for the range parameter [math]\displaystyle{ \varepsilon }[/math], and produces a hierarchical result related to that of linkage clustering. DeLi-Clu,[5] Density-Link-Clustering combines ideas from single-linkage clustering and OPTICS, eliminating the [math]\displaystyle{ \varepsilon }[/math] parameter entirely and offering performance improvements over OPTICS by using an R-tree index.
The key drawback of DBSCAN and OPTICS is that they expect some kind of density drop to detect cluster borders. Moreover they can not detect intrinsic cluster structures which are prevalent in the majority of real life data. A variation of DBSCAN, EnDBSCAN[6] efficiently detects such kinds of structures. On data sets with, for example, overlapping Gaussian distributions - a common use case in artificial data - the cluster borders produced by these algorithms will often look arbitrary, because the cluster density decreases continuously. On a data set consisting of mixtures of Gaussians, these algorithms are nearly always outperformed by methods such as EM clustering, that are able to precisely model this kind of data.
- In density-based clustering,[1] clusters are defined as areas of higher density than the remainder of the data set. Objects in these sparse areas - that are required to separate clusters - are usually considered to be noise and border points.
- ↑ Hans-Peter Kriegel, Peer Kröger, Jörg Sander, Arthur Zimek (2011). "Density-based Clustering". WIREs Data Mining and Knowledge Discovery 1 (3): 231–240. doi:10.1002/widm.30. http://wires.wiley.com/WileyCDA/WiresArticle/wisId-WIDM30.html.
- ↑ Microsoft academic search: most cited data mining articles: DBSCAN is on rank 24, when accessed on: 4/18/2010
- ↑ Template:Cite conference
- ↑ Template:Cite conference
- ↑ Template:Cite doi
- ↑ Template:Cite conference
2011
- (Sander, 2011) ⇒ Joerg Sander. (2011). “Density-Based Clustering.” In: (Sammut & Webb, 2011) p.270
1996
- (Ester et al., 1996) ⇒ Martin Ester, Hans-Peter Kriegel, Jorg Sander, and Xiaowei Xu. (1996). “A Density-based Algorithm for Discovering Clusters in Large Spatial Database with Noise.” In: Proceedings of the International Conference on Knowledge Discovery in Databases and Data Mining (KDD 1996).
- QUOTE: … Jain (1988) explores a density based approach to identify clusters in k-dimensional point sets. …
1988
- (Jain, 1988) ⇒ Anil K. Jain. (1988). “Algorithms for Clustering Data." Prentice Hall. ISBN:013022278X