# A graph-based estimator of the number of clusters

Gérard Biau; Benoît Cadre; Bruno Pelletier

ESAIM: Probability and Statistics (2007)

- Volume: 11, page 272-280
- ISSN: 1292-8100

## Access Full Article

top## Abstract

top## How to cite

topBiau, Gérard, Cadre, Benoît, and Pelletier, Bruno. "A graph-based estimator of the number of clusters." ESAIM: Probability and Statistics 11 (2007): 272-280. <http://eudml.org/doc/250119>.

@article{Biau2007,

abstract = {
Assessing the number of clusters of a statistical population is one of the essential issues of unsupervised learning. Given n independent observations X1,...,Xn drawn from an unknown multivariate probability density f, we propose a new approach to estimate the number of connected components, or clusters, of the t-level set $\mathcal L(t)=\\{x:f(x) \geq t\\}$. The basic idea is to form a rough skeleton of the set $\mathcal L(t)$ using any preliminary estimator of f, and to count the number of connected components of the resulting graph. Under mild analytic conditions on f, and using tools from differential geometry, we establish the consistency of our method.
},

author = {Biau, Gérard, Cadre, Benoît, Pelletier, Bruno},

journal = {ESAIM: Probability and Statistics},

keywords = {Cluster analysis; connected component; level set; graph; tubular neighborhood.; cluster analysis; tubular neighborhood},

language = {eng},

month = {6},

pages = {272-280},

publisher = {EDP Sciences},

title = {A graph-based estimator of the number of clusters},

url = {http://eudml.org/doc/250119},

volume = {11},

year = {2007},

}

TY - JOUR

AU - Biau, Gérard

AU - Cadre, Benoît

AU - Pelletier, Bruno

TI - A graph-based estimator of the number of clusters

JO - ESAIM: Probability and Statistics

DA - 2007/6//

PB - EDP Sciences

VL - 11

SP - 272

EP - 280

AB -
Assessing the number of clusters of a statistical population is one of the essential issues of unsupervised learning. Given n independent observations X1,...,Xn drawn from an unknown multivariate probability density f, we propose a new approach to estimate the number of connected components, or clusters, of the t-level set $\mathcal L(t)=\{x:f(x) \geq t\}$. The basic idea is to form a rough skeleton of the set $\mathcal L(t)$ using any preliminary estimator of f, and to count the number of connected components of the resulting graph. Under mild analytic conditions on f, and using tools from differential geometry, we establish the consistency of our method.

LA - eng

KW - Cluster analysis; connected component; level set; graph; tubular neighborhood.; cluster analysis; tubular neighborhood

UR - http://eudml.org/doc/250119

ER -

## References

top- G.E. Bredon, Topology and Geometry, Springer-Verlag, New York, Graduate Texts in Mathematics 139 (1993).
- M.R. Brito, E.L. Chavez, A.J. Quiroz and J.E. Yukich, Connectivity of the mutual k-nearest neighbor graph in clustering and outlier detection. Statist. Probab. Lett.35 (1997) 33–42. Zbl0898.62077
- B. Cadre, Kernel estimation of density level sets. J. Multivariate Anal.97 (2006) 999–1023. Zbl1085.62039
- I. Chavel, Riemannian Geometry: A Modern Introduction. Cambridge University Press, Cambridge (1993).
- T.H. Cormen, C.E. Leiserson and R.L. Rivest, Introduction to Algorithms. The MIT Press, Cambridge (1990). Zbl1158.68538
- A. Cuevas, M. Febrero and R. Fraiman, Estimating the number of clusters. Canad. J. Statist.28 (2000) 367–382. Zbl0981.62054
- A. Cuevas, M. Febrero and R. Fraiman, Cluster analysis: a further approach based on density estimation. Comput. Statist. Data Anal.36 (2001) 441–459. Zbl1053.62537
- L. Devroye and G. Wise, Detection of abnormal behavior via nonparametric estimation of the support. SIAM J. Appl. Math.38 (1980) 480–488. Zbl0479.62028
- R.O. Duda, P.E. Hart and D.G. Stork, Pattern Classification, 2nd edition. Wiley-Interscience, New York (2000). Zbl0968.68140
- L. Györfi, M. Kohler, A. Krzyżak and H. Walk, A Distribution-Free Theory of Nonparametric Regression. Springer-Verlag, New York (2002). Zbl1021.62024
- J.A. Hartigan, Clustering Algorithms. John Wiley, New York (1975). Zbl0372.62040
- T. Hastie, R. Tibshirani and J. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer, New York (2001). Zbl0973.62007
- S. Kobayashi and K. Nomizu, Foundations of Differential Geometry, Vol. I & II, 2nd edition. Wiley, New York (1996). Zbl0119.37502
- U. von Luxburg and S. Ben-David, Towards a statistical theory of clustering. PASCAL Workshop on Statistics and Optimization of Clustering (2005).
- M.D. Penrose, A strong law for the longest edge of the minimal spanning tree. Ann. Probab.27 (1999) 246–260. Zbl0944.60015
- A. Polonik, Measuring mass concentrations and estimating density contour clusters–an excess mass approach. Ann. Statist.23 (1995) 855–881. Zbl0841.62045
- B.L.S. Prakasa Rao, Nonparametric Functional Estimation. Academic Press, Orlando (1983). Zbl0542.62025
- A.B. Tsybakov, On nonparametric estimation of density level sets. Ann. Statist.25 (1997) 948–969. Zbl0881.62039

## Citations in EuDML Documents

top- Markus Maier, Ulrike von Luxburg, Matthias Hein, How the result of graph clustering methods depends on the construction of the graph
- Elena Di Bernardino, Thomas Laloë, Véronique Maume-Deschamps, Clémentine Prieur, Plug-in estimation of level sets in a non-compact setting with applications in multivariate risk theory

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.