A graph-based estimator of the number of clusters

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

ESAIM: Probability and Statistics, Tome 11 (2007), pp. 272-280.

Assessing the number of clusters of a statistical population is one of the essential issues of unsupervised learning. Given $n$ independent observations $X_1,\cdots ,X_n$ 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 $ℒ\left(t\right)=\{x:f(x)\ge t\}$. The basic idea is to form a rough skeleton of the set $ℒ\left(t\right)$ 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.

[1] G.E. Bredon, Topology and Geometry, Springer-Verlag, New York, Graduate Texts in Mathematics 139 (1993). | MR | Zbl

[2] 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. | Zbl

[3] B. Cadre, Kernel estimation of density level sets. J. Multivariate Anal. 97 (2006) 999-1023. | Zbl

[4] I. Chavel, Riemannian Geometry: A Modern Introduction. Cambridge University Press, Cambridge (1993). | MR | Zbl

[5] T.H. Cormen, C.E. Leiserson and R.L. Rivest, Introduction to Algorithms. The MIT Press, Cambridge (1990). | MR | Zbl

[6] A. Cuevas, M. Febrero and R. Fraiman, Estimating the number of clusters. Canad. J. Statist. 28 (2000) 367-382. | Zbl

[7] A. Cuevas, M. Febrero and R. Fraiman, Cluster analysis: a further approach based on density estimation. Comput. Statist. Data Anal. 36 (2001) 441-459. | Zbl

[8] L. Devroye and G. Wise, Detection of abnormal behavior via nonparametric estimation of the support. SIAM J. Appl. Math. 38 (1980) 480-488. | Zbl

[9] R.O. Duda, P.E. Hart and D.G. Stork, Pattern Classification, 2nd edition. Wiley-Interscience, New York (2000). | MR | Zbl

[10] L. Györfi, M. Kohler, A. Krzyżak and H. Walk, A Distribution-Free Theory of Nonparametric Regression. Springer-Verlag, New York (2002). | MR | Zbl

[11] J.A. Hartigan, Clustering Algorithms. John Wiley, New York (1975). | MR | Zbl

[12] T. Hastie, R. Tibshirani and J. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer, New York (2001). | MR | Zbl

[13] S. Kobayashi and K. Nomizu, Foundations of Differential Geometry, Vol. I & II, 2nd edition. Wiley, New York (1996). | MR | Zbl

[14] U. Von Luxburg and S. Ben-David, Towards a statistical theory of clustering. PASCAL Workshop on Statistics and Optimization of Clustering (2005).

[15] M.D. Penrose, A strong law for the longest edge of the minimal spanning tree. Ann. Probab. 27 (1999) 246-260. | Zbl

[16] A. Polonik, Measuring mass concentrations and estimating density contour clusters-an excess mass approach. Ann. Statist. 23 (1995) 855-881. | Zbl

[17] B.L.S. Prakasa Rao, Nonparametric Functional Estimation. Academic Press, Orlando (1983). | MR | Zbl

[18] A.B. Tsybakov, On nonparametric estimation of density level sets. Ann. Statist. 25 (1997) 948-969. | Zbl