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):
  • DBSCAN Algorithm.
  • OPTICS Algorithm.
  • …
• Counter-Example(s):
  • a Hierarchical Clustering Algorithm, such as a Partitional Clustering Algorithm.
• See: Density Estimation, Subspace Clustering Algorithm.

---

---

References

• http://scholar.google.com/scholar?q=Density-based+clustering

2013

• http://en.wikipedia.org/wiki/Cluster_analysis#Density-based_clustering
  • In density-based clustering, 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 density based clustering method is DBSCAN. 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 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, 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 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.

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

---