How to cite this WIREs title:
WIREs Data Mining Knowl Discov

Impact Factor: 1.759

Density‐based clustering

Advanced Review

Hans‐Peter Kriegel, Peer Kröger, Jörg Sander, Arthur Zimek

Published Online: Apr 05 2011

DOI: 10.1002/widm.30

Full article on Wiley Online Library: HTML PDF

Can't access this content? Tell your librarian.

Clustering refers to the task of identifying groups or clusters in a data set. In density‐based clustering, a cluster is a set of data objects spread in the data space over a contiguous region of high density of objects. Density‐based clusters are separated from each other by contiguous regions of low density of objects. Data objects located in low‐density regions are typically considered noise or outliers. © 2011 John Wiley & Sons, Inc. WIREs Data Mining Knowl Discov 2011 1 231–240 DOI: 10.1002/widm.30

Figure 1.

Density‐distributions of data points and density‐based clusters for different density levels. Different colors indicate different clusters or noise.

[ Normal View | Magnified View ]

Figure 2.

Maunga Whau Volcano (Mt Eden).

[ Normal View | Magnified View ]

Figure 3.

Iris data (green: I. setosa, red: I. versicolor, blue: I. virginica).

[ Normal View | Magnified View ]

Figure 4.

Density connectivity.

[ Normal View | Magnified View ]

Figure 5.

The impact of different kernels on the density estimation.

[ Normal View | Magnified View ]

Figure 6.

Reachability plot for a sample 2D data set.

[ Normal View | Magnified View ]

References

MacQueen, J.Some methods for classification and analysis of multivariate observations.Fifth Berkeley Symposium on Mathematics, Statistics, and Probabilistics, vol.1,1967,1967–281.
Dempster, AP,Laird, NM,Rubin, DB.Maximum likelihood from incomplete data via the EM algorithm.J R Stat Soc, Ser B1977,39:1–31.
Carmichael, JW,George, JA,Julius, RS.Finding natural clusters.Syst Zool1968,17:144–150.
Hartigan, JA.Direct clustering of a data matrix.J Am Stat Assoc1972,67:123–129.
Sneath, PHA.The application of computers to taxonomy.J Gen Microbiol1957,17:201–226.
Fitch, WM,Margoliash, E.Construction of phylogenetic trees.Science1967,155:279–284.
Fisher, RA.The use of multiple measurements in taxonomic problems.Ann Eugenics1936,7:179–188.
Raup, DM.Geometric analysis of shell coiling: general problems.J Paleontol1966,40:1178–1190.
Williams, WT,Lambert, JM.Multivariate methods in plant ecology. V. Similarity analyses and information‐analysis.J Ecol1966,54:427–445.
Sibson, R.SLINK: an optimally efficient algorithm for the single‐link cluster method.Comput J1973,16:30–34.
Lance, GN,Williams, WT.A general theory of classificatory sorting strategies. 1. Hierarchical systems.Comput J1967,9:373–380.
Jardine, N,Sibson, R.The construction of hierarchic and non‐hierarchic classifications.Comput J1968,11:177–184.
Wishart, D.%22Mode analysis: a generalization of nearest neighbor which reduces chaining effects%22. In:Cole, AJ, eds.Numerical Taxonomy,London and New York: Academic Press;1969.
Hartigan, JA.Clustering Algorithms.New York, London, Sydney, Toronto: John Wiley %26 Sons;1975.
Devroye, LP,Wagner, TJ.The strong uniform consistency of nearest neighbor density estimates.Ann Stat1977,5:536–540.
Loftsgaarden, DO,Quesenberry, CP.A nonparametric estimate of a multivariate density function.Ann Math Stat1965,36:1049–1051.
Moore, DS,Yackel, JW.Consistency properties of nearest neighbor density function estimates.Ann Stat1977,5:143–154.
Parzen, E.On estimation of a probability density function and mode.Ann Math Stat1962,33:1065–1076.
Rosenblatt, M.Remarks on some nonparametric estimates of a density function.Ann Math Stat1956,27:832–837.
Cuevas, A,Febrero, M,Fraiman, R.Cluster analysis: a further approach based on density estimation.Comput Stat Data Anal2001,36:441–459.
Wong, MA,Lane, T.A kth nearest neighbour clustering procedure.J R Stat Soc: Ser B1983,45:362–368.
Ester, M,Kriegel, H‐P,Sander, J,Xu, X.A density‐based algorithm for discovering clusters in large spatial databases with noise. Proceedings of the 2nd ACM International Conference on Knowledge Discovery and Data Mining (KDD), Portland, OR,1996.
Hinneburg, A,Keim, DA.An efficient approach to clustering in large multimedia databases with noise. Proceedings of the 4th ACM International Conference on Knowledge Discovery and Data Mining (KDD), New York City, NY,1998.
Sander, J,Ester, M,Kriegel, H‐P,Xu, X.Density‐based clustering in spatial databases: the algorithm GDBSCAN and its applications.Data Min Knowl Discovery1998,2:169–194.
Ertöz, L,Steinbach, M,Kumar, V.Finding clusters of different sizes, shapes, and densities in noisy, high dimensional data. Proceedings of the 3rd SIAM International Conference on Data Mining (SDM), San Francisco, CA, 2003.
Pei, T,Jasra, A,Hand, DJ,Zhu, A‐X,Zhou, C.DECODE: a new method for discovering clusters of different densities in spatial data.Data Min Knowl Discovery2009,18:337–369.
Ankerst, M,Breunig, MM,Kriegel, H‐P,Sander, J.OPTICS: ordering points to identify the clustering structure. Proceedings of the ACM International Conference on Management of Data (SIGMOD), Philadelphia, PA,1999.
Stuetzle, W.Estimating the cluster tree of a density by analyzing the minimal spanning tree of a sample.J Classif2003,20:25–47.
Sander, J,Qin, X,Lu, Z,Niu, N,Kovarsky, A.Automatic extraction of clusters from hierarchical clustering representations. Proceedings of the 7th Pacific‐Asia Conference on Knowledge Discovery and Data Mining (PAKDD), Seoul, Korea,2003,2003–75.
Hartigan, JA.Statistical theory in clustering.J Classif1985,2:63–76.
Houle, ME,Kriegel, H‐P,Kröger, P,Schubert, E,Zimek, A.Can shared‐neighbor distances defeat the curse of dimensionality? Proceedings of the 22nd International Conference on Scientific and Statistical Database Management (SSDBM), Heidelberg, Germany,2010.
Kriegel, H‐P,Kröger, P,Zimek, A.Clustering high dimensional data: a survey on subspace clustering, pattern‐based clustering, and correlation clustering.ACM Trans Knowl Discovery Data (TKDD)2009,3:1–58.
Kailing, K,Kriegel, H‐P,Kröger, P.Density‐connected subspace clustering for high‐dimensional data. Proceedings of the 4th SIAM International Conference on Data Mining (SDM), Lake Buena Vista, FL,2004.
Assent, I,Krieger, R,Müller, E,Seidl, T.DUSC: dimensionality unbiased subspace clustering. Proceedings of the 7th IEEE International Conference on Data Mining (ICDM), Omaha, NE,2007.
Böhm, C,Kailing, K,Kriegel, H‐P,Kröger, P.Density connected clustering with local subspace preferences. Proceedings of the 4th IEEE International Conference on Data Mining (ICDM), Brighton, UK,2004.
Achtert, E,Böhm, C,Kriegel, H‐P,Kröger, P,Zimek, A.On exploring complex relationships of correlation clusters. Proceedings of the 19th International Conference on Scientific and Statistical Database Management (SSDBM), Banff, Canada,2007.
Achtert, E,Böhm, C,Kriegel, H‐P,Kröger, P,Zimek, A.Robust, complete, and efficient correlation clustering. Proceedings of the 7th SIAM International Conference on Data Mining (SDM), Minneapolis, MN,2007.
Böhm, C,Kailing, K,Kröger, P,Zimek, A.Computing clusters of correlation connected objects. Proceedings of the ACM International Conference on Management of Data (SIGMOD), Paris, France,2004.
Böhm, C,Plant, C.HISSCLU: a hierarchical density‐based method for semi‐supervised clustering. Proceedings of the 11th International Conference on Extending Database Technology (EDBT), Nantes, France,2008.
Lelis, L,Sander, J.Semi‐supervised density‐based clustering. Proceedings of the 9th IEEE International Conference on Data Mining (ICDM), Miami, FL,2009.
R project.Available at: http://www.r‐project.org/.
Achtert, E,Kriegel, H‐P,Reichert, L,Schubert, E,Wojdanowski, R,Zimek, A.Visual evaluation of outlier detection models. Proceedings of the 15th International Conference on Database Systems for Advanced Applications (DASFAA), Tsukuba, Japan,2010.
Murtagh, F.A survey of algorithms for contiguity‐constrained clustering and related problems.Comput J1985,28:82–88.

Access to this WIREs title is by subscription only.

Recommend to Your
Librarian Now!

The latest WIREs articles in your inbox

Sign Up for Article Alerts

Twitter: WileyCompSci Follow us on Twitter

https://t.co/UIKgkQNyoz

https://t.co/NWNnReyipM

https://t.co/tvl1fSJMuT

https://t.co/SwW6gNrmAd

https://t.co/GUbZOAl6gY

https://t.co/rxKYxYVXA3