S. Ben-david, A framework for statistical clustering with constant time approximation algorithms for K-median and K-means clustering, Machine Learning, pp.243-257, 2007.
DOI : 10.1007/s10994-006-0587-3

J. Buhmann, Empirical risk approximation: An induction principle for unsupervised learning, 1998.

A. Czumaj and C. Sohler, Sublinear-time approximation algorithms for clustering via random sampling . Random Struct, Algorithms, vol.30, issue.12, pp.226-256, 2007.

L. Devroye, L. Györfi, and G. Lugosi, A Probabilistic Theory of Pattern Recognition, 1996.
DOI : 10.1007/978-1-4612-0711-5

M. Figueiredo and A. Jain, Unsupervised learning of finite mixture models, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.24, issue.3, pp.381-396, 2002.
DOI : 10.1109/34.990138

C. Fraley and A. Raftery, How Many Clusters? Which Clustering Method? Answers Via Model-Based Cluster Analysis, The Computer Journal, vol.41, issue.8, pp.41578-588, 1998.
DOI : 10.1093/comjnl/41.8.578

J. Fritz, Distribution-free exponential error bound for nearest neighbor pattern classification, IEEE Transactions on Information Theory, vol.21, issue.5, pp.552-557, 1975.
DOI : 10.1109/TIT.1975.1055443

M. Garey, D. Johnson, and H. Witsenhausen, The complexity of the generalized Lloyd - Max problem (Corresp.), IEEE Transactions on Information Theory, vol.28, issue.2, pp.255-256, 1982.
DOI : 10.1109/TIT.1982.1056488

P. Grünwald, The Minimum Description Length Principle, 2007.

S. Guattery and G. Miller, On the Quality of Spectral Separators, SIAM Journal on Matrix Analysis and Applications, vol.19, issue.3, pp.701-719, 1998.
DOI : 10.1137/S0895479896312262

J. Hartigan, Consistency of Single Linkage for High-Density Clusters, Journal of the American Statistical Association, vol.1, issue.374, pp.388-394, 1981.
DOI : 10.1080/00401706.1972.10488943

J. Hartigan, Statistical theory in clustering, Journal of Classification, vol.45, issue.B, pp.63-76, 1985.
DOI : 10.1007/BF01908064

M. Inaba, N. Katoh, and H. Imai, -clustering, Proceedings of the tenth annual symposium on Computational geometry , SCG '94, pp.332-339, 1994.
DOI : 10.1145/177424.178042

URL : https://hal.archives-ouvertes.fr/in2p3-01333933

P. Indyk, Sublinear time algorithms for metric space problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing , STOC '99, pp.428-434, 1999.
DOI : 10.1145/301250.301366

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.122.2385

S. Jegelka, Statistical learning theory approaches to clustering Master's thesis, 2007.

R. Kannan, S. Vempala, and A. Vetta, On clusterings, Journal of the ACM, vol.51, issue.3, pp.497-515, 2004.
DOI : 10.1145/990308.990313

C. Mcdiarmid, On the method of bounded differences, pp.148-188, 1989.
DOI : 10.1017/CBO9781107359949.008

G. Mclachlan and D. Peel, Finite Mixture Models, 2004.
DOI : 10.1002/0471721182

N. Mishra, D. Oblinger, and L. Pitt, Sublinear time approximate clustering, Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-01), pp.439-447, 2001.

M. Newman, Finding community structure in networks using the eigenvectors of matrices, Physical Review E, vol.74, issue.3, p.36104, 2006.
DOI : 10.1103/PhysRevE.74.036104

D. Pollard, Strong Consistency of $K$-Means Clustering, The Annals of Statistics, vol.9, issue.1, pp.135-140, 1981.
DOI : 10.1214/aos/1176345339

A. Rakhlin and A. Caponnetto, Stability of k-means clustering, Advances in Neural Information Processing Systems 19, 2007.

D. Spielman and S. Teng, Spectral partitioning works: Planar graphs and finite element meshes, 37th Annual Symposium on Foundations of Computer Science, pp.96-105, 1996.
DOI : 10.1016/j.laa.2006.07.020

A. W. Van-der-vaart and J. A. Wellner, Weak Convergence and Empirical Processes, 1996.
DOI : 10.1007/978-1-4757-2545-2

V. Vapnik, The Nature of Statistical Learning Theory, 1995.

U. Luxburg, A tutorial on spectral clustering, Statistics and Computing, vol.21, issue.1, pp.395-416, 2007.
DOI : 10.1007/s11222-007-9033-z

U. Luxburg and S. Ben-david, Towards a statistical theory of clustering, PASCAL workshop on Statistics and Optimization of Clustering, 2005.

U. Von-luxburg, M. Belkin, and O. Bousquet, Consistency of spectral clustering, The Annals of Statistics, vol.36, issue.2, pp.555-586, 2008.
DOI : 10.1214/009053607000000640

U. Von-luxburg, S. Bubeck, S. Jegelka, and M. Kaufmann, Consistent minimization of clustering objective functions, Advances in Neural Information Processing Systems (NIPS) 21, 2008.
URL : https://hal.archives-ouvertes.fr/inria-00185777