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

[Quantification et/ou Classification non-supervisée : quand et pourquoi la méthode des centres mobiles marche-t-elle ?]

Levrard, Clément 

Journal de la société française de statistique, Tome 159 (2018) no. 1, pp. 1-26

Abstract (VO)

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 (2016a) , 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.

Résumé

Bien qu’utilisé comme algorithme de classification, les $k$-moyennes sont à la base conçus pour fournir un quantifieur, c’est-à-dire un moyen de compresser une distribution de probabilités avec $k$ points. En nous appuyant sur les travaux de Levrard (2015) et Tang and Monteleoni (2016a) , nous essayerons d’expliquer en quoi et sous quelles conditions ces deux objectifs a priori distincts sont compatibles. Plus précisément, nous montrerons que dans le cas où la distribution d’où sont tirés les points satisfait une condition de type marge (baptisée ainsi par analogie avec les conditions de marge établies en classification supervisée dans Mammen and Tsybakov, 1999 ), non seulement le minimiseur théorique du risque empirique associé mais aussi le résultat fourni par l’algorithme de Lloyd fournissent d’une part une classification sinon optimale (au sens de Azizyan et al., 2013 ) du moins pertinente et d’autre part une compression rapide (en la taille de l’échantillon) et optimale.

Détail

Keywords: $k$-means, clustering, quantization, separation rate, distortion
Mots-clés : $k$-means, classification non-supervisée, quantification, vitesse de séparation, distorsion