A graph-based estimator of the number of clusters
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 ,,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 (t)={x:f(x)t}. The basic idea is to form a rough skeleton of the set (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.

DOI : 10.1051/ps:2007019
Classification : 62G05, 62G20
Mots clés : cluster analysis, connected component, level set, graph, tubular neighborhood
@article{PS_2007__11__272_0,
     author = {Biau, G\'erard and Cadre, Beno{\^\i}t and Pelletier, Bruno},
     title = {A graph-based estimator of the number of clusters},
     journal = {ESAIM: Probability and Statistics},
     pages = {272--280},
     publisher = {EDP-Sciences},
     volume = {11},
     year = {2007},
     doi = {10.1051/ps:2007019},
     mrnumber = {2320821},
     zbl = {1187.62114},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ps:2007019/}
}
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
PY  - 2007
SP  - 272
EP  - 280
VL  - 11
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ps:2007019/
DO  - 10.1051/ps:2007019
LA  - en
ID  - PS_2007__11__272_0
ER  - 
%0 Journal Article
%A Biau, Gérard
%A Cadre, Benoît
%A Pelletier, Bruno
%T A graph-based estimator of the number of clusters
%J ESAIM: Probability and Statistics
%D 2007
%P 272-280
%V 11
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ps:2007019/
%R 10.1051/ps:2007019
%G en
%F PS_2007__11__272_0
Biau, Gérard; Cadre, Benoît; Pelletier, Bruno. A graph-based estimator of the number of clusters. ESAIM: Probability and Statistics, Tome 11 (2007), pp. 272-280. doi : 10.1051/ps:2007019. http://archive.numdam.org/articles/10.1051/ps:2007019/

[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

Cité par Sources :