Quantization/Clustering: when and why does k-means work?

  • Clément Levrard

Résumé

Though mostly used as a clustering algorithm, k-means is originally designed as a quantization algorithm. Namely, it aims at providing a compression of a probability distribution with k points. Building upon Levrard (2015); Tang and Monteleoni (2016), we try to investigate how and when these two approaches are compatible. Namely, we show that provided the sample distribution satisfies a margin like condition (in the sense of Mammen and Tsybakov, 1999 for supervised learning), both the associated empirical risk minimizer and the output of Lloyd’s algorithm provide almost optimal classification in certain cases (in the sense of Azizyan et al., 2013). Besides, we also show that they achieved fast and optimal convergence rates in terms of sample size and compression risk.

Clément Levrard est lauréat du prix Marie-Jeanne Laurent Duhamel 2017.
Publiée
2018-03-26
Numéro
Vol. 159 No 1 (2018)
Rubrique
Article
Les auteurs dont l'article est accepté pour publication sont invités à télécharger, compléter soigneusement et signer le formulaire de transfert de copyright à la Société Française de Statistique.

Instructions

  • Pour les articles à plusieurs auteurs, un seul des auteurs est tenu de signer ce formulaire. Cet auteur est présumé avoir consulté ses co-auteurs et avoir reçu leur accord quant au contenu du formulaire.
  • Le formulaire complété et signé est scanné (au format JPEG ou PDF) et envoyé par courriel, comme fichier attaché, à Gilles Celeux

Remarques

  • En transférant le copyright d'un article à la Société Française de Statistique (SFdS) pour sa publication dans le Journal de la SFdS, l'(es) auteur(s) conserve(nt) les trois droits de propriété suivants:
    1. le droit de reproduire et d'utiliser l'article à des fins non lucratives dans un contexte éducatif, professionnel ou académique (par exemple, faire circuler des copies sous format papier ou électronique, déposer l'article complet sur un site internet), pour autant que, dans le corps du fichier électronique ou de la copie de l'article, le Journal de la Société Française de Statistique soit clairement citée comme source originale de publication et que les références bibliographiques complètes de l'article soient mentionnées (année, volume, numéro du fascicule, nombre de pages et adresse web/URL du J-SFdS), comme c'est le cas dans la version électronique originale;
    2. le droit d'accorder l'autorisation de reproduire des tableaux, graphiques ou illustrations qui apparaissent dans l'article, pour autant que le Journal de la SFdS soit clairement citée comme source originale de publication et que les références bibliographiques complètes de l'article soient mentionnées;
    3. la propriété intellectuelle.
  • Les auteurs peuvent contacter l'un des rédacteurs en chef du J-SFdS s'ils désirent obtenir l'autorisation pour d'autres formes de distribution de l'article.