Hugo Steinhaus : classification par k-moyennes, nuées dynamiques

Partitionnement à noyau

[Mise à disposition de l'article de Hugo Steinhaus de 1956, à l'origine de l'algorithme de partitionnement par les k-moyennes (available in English)]

Le partitionnement des données (data clustering ou clustering analysis) est une méthode "statistique" d'analyse de données visant à regrouper, dans un ensemble de données hétérogènes, des sous-ensembles de ces données en amas ou paquets plus homogènes. Chaque sous-ensemble doit ainsi présenter des caractéristiques similaires, quantifiée par des critères de similarité ou différentes mesures de proximité. Ces techniques appartiennent aux familles de classification, d'apprentissage automatique ou de segmentation, employées dans un nombre phénoménal d'applications, du traitement d'image à la bio-informatique.

L'une des méthodes de partitionnement ou d’agrégation les plus populaires est celle des k-moyennes (ou K-means), un problème d'optimisation combinatoire dont une version porte le joli nom de nuées dynamiques (pour une application qui m'intéresse : Kinetic transcriptome analysis reveals an essentially intact induction system in a cellulase hyper-producer Trichoderma reesei strain, Dante Poggi et al., Biotechnology and Biofuels, 2014).

Une histoire des k-moyennes est disponible dans Data Clustering: 50 Years Beyond K-Means, Anil K. Jain, Pattern recognition letters, 2010. Un autre point de vue est dans Origins and extensions of the k-means algorithm in cluster analysis, Hans-Hermann Bock, Journ@l Electronique d'Histoire des Probabilités et de la Statistique. Cet algorithme est profondément relié à l'algorithme dit de Lloyd-Max, développé par Lloyd en 1957, et redécouvert par Max trois ans après. Il permet notamment de construire un quantificateur scalaire optimal. 

Sur la division des corps matériels en parties (pdf)

Cette technique a cependant une source légèrement antérieure, publiée en français par Hugo Steinhaus en 1956 dans le Bulletin de l’Académie Polonaise des Sciences. Hugo Steinhaus (1887-1972) est un mathématicien polonais qui a contribué à de nombreuses branches des mathématiques, et est considéré comme l’un des précurseurs de la théorie des probabilités. Il a également œuvré en mathématiques appliquées, avec des collaborations avec des ingénieurs, géologues, économistes, des physiciens, biologistes. En manque d’informations fiables sur le déroulement de la 2e guerre mondiale, il « invente » un outil statistique pour estimer les pertes allemandes, en utilisant les annonces sporadiques des décès, partant d’un calcul de la fréquence relative d’annonces nécrologiques de soldats décédés mentionnant s’ils sont les 1er, 2e, 3e etc. fils d’une famille. Il est ainsi un précurseur de la science des données.

Cet article s'intitule "Sur la division des corps matériels en parties", et est le premier formulant de manière explicite, en dimension finie, le problème de partitionnement par les k-moyennes. Il est donc plus constructif que le théorème paradoxal de Banach-Tarski qui s'intéresse à la découpe d'une boule en deux boules de volume total double. Son écriture est plaisante, visant un usage pratique allant de la classification des types en anthropologie à la normalisation des objets industriels. 

Étant en langue française, dans une revue aux archives peu disponibles en ligne, cet article n'a pas eu la lecture qu'il méritait. Le voici transduit par Maciej Denkowski, transmis par Jérôme Bolte, et transcrit en LaTeX par votre serviteur, avec un effort majeur pour en conserver la pagination originale.

@Article{Steinhaus_H_1956_j-bull-acad-polon-sci_division_cmp-k-means,
  Title                    = {Sur la division des corps mat\'eriels en parties},
  Author                   = {Steinhaus, H.},
 File                     = {Steinhaus_H_1956_j-bull-acad-polon-sci_division_cmp-k-means.pdf:Steinhaus_H_1956_j-bull-acad-polon-sci_division_cmp-k-means:PDF},
  Journal                  = {Bulletin de l’Acad\'emie Polonaise des Sciences},
  Number                   = {12},
  Pages                    = {801--804},
  Volume                   = {Cl. {III} --- Vol. {IV}},
  Year                     = {1956},

  Owner                    = {duvall},
  Timestamp                = {2015.07.07.15.44}
}

Une version anglophone de ce billet s'intitule : Hugo Steinhaus, or K-means clustering in French.