Hugo Steinhaus, or K-means clustering in French

Kernel clustering

[Modern transcription of the Hugo Steinhaus paper in 1956 (in French), at the source of k-means clustering algorithms, published first in a french-written post]

Data clustering or clustering analysis belongs to statistical data analysis methods. It aims at forming groups of objects that are similar in some way. Those groups are named clusters. The word cluster is related to clot, for thick mass of coagulated liquid or of material stuck together

The whole set of objects contains heterogeneous data, that ought to be grouped into subsets possessing a greater inner homogeneity. Such methods rely on similarity criteria or proximity measures. They are related to classification, machine learning, segmentation, pattern recognition, and have applications ranging from image processing to bioinformatics.

One of the most popular clustering method is known as K-means (k-moyennes in French). with a variation called dynamic clustering (beautifully called nuées dynamiques in French, for an application in bilogy: 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).

An history of K-means can be found in Data Clustering: 50 Years Beyond K-Means, Anil K. Jain, Pattern recognition letters, 2010. Other historic bits can be found in Origins and extensions of the k-means algorithm in cluster analysis, Hans-Hermann Bock, Electronic Journ@l for History of Probability and Statistics, 2008. This algorithm is deeply linked to Lloyd-Max algorithm, developed by Lloyd in  1957, and rediscovered by Max three after after. It is useful for optimal scalar quantifier design.

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

The K-means technique is a little older. It was published in French by Hugo Steinhaus in 1956 in the Bulletin de l’Académie Polonaise des Sciences (Bulletin of the Polish Academy of Sciences). Hugo Steinhaus (1887-1972) is a Polish mathematician, sometimes known as the discover of Stefan Banach. He contributed to numerous branches of mathematics, and considered a early founder of probability theory.

He also contributed to applied mathematics, working jointly with engineers, biologists, physician, economists, geologists, and "even lawyers". Lacking of trustworthy information during World War II, he invented a statistical tool to estimate German losses, using necrologic news from German soldiers on the front. He notably used the mention that the soldier killed was the first, second or third child from a family. He thus is a precursor of data science.

This paper is called "Sur la division des corps matériels en parties" (On the division of material bodies into parts). The first to explicitely  formulate in finite dimension the principle of k-mean clustering. It is much more constructive that the Banach-Tarski paradoxal theorem which delas with cutting a ball into two different balls, doubling in volume. This paper is pleasant to read, and evokes practical uses from type classification in anthropology to industrial object normalization.

Being in French, in a journal whose archives cannot be accessed easily, it has not been read as much as it deserved. . Here is it transduced by Maciej Denkowski, transmitted by Jérôme Bolte, and transcribed in LaTeX by  myself, with some effort to preserve the original typesetting and composition.

@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}
}

Dédoménologie : la science du traitement de données (signal, images, etc.)

[Où l'on propose le néologisme dédoménologie pour désigner la technique, la pratique, la science du traitement de signal et de l'analyse d'images, au cœur du domaine naissant de la science des données, en passant par Euclide]

Ce sont les mots qui existent, ce qui n'a pas de nom n'existe pas. Le mot lumière existe, la lumière n'existe pas. (Francis Picabia, ou Francis-Marie Martinez de Picabia, Écrits)

Quelle analyste d'image, quel traiteur de signal n'a jamais eu des difficultés à décrire son métier ? Pas en détail bien sûr :

En fait, je m'intéresse aux propriétés cyclostationnaires des coefficients d'ondelettes de mouvements browniens fractionnaires dans les images de textures. Enfin quand je dis cyclostationnaire, il faut entendre périodiquement corrélé, hein, je ne parle pas des processus presque périodiques.

Le traitement du signal, des images ou des données requiert très souvent des périphrases. Des exemples parlants :

Tu vois Photoshop ? 

Très mauvais exemple. L'interlocuteur voit rapidement une journée de "travail" à bouger le mulot pour changer une teinte, sélectionner des objets à la baguette magique.

Tu connais le mp3 ? Le format JPEG ?

Et de rentrer dans des détails sordides de données numériques redondantes, de quantification, dont on cherche à extraire uniquement la partie perceptible utile. Avec le risque de remarques déplacées :

Le son du mp3, moi je trouver ça nul par rapport au vinyl ! [C'est pas gagné...]

L'analyste de signaux, le traiteur d'images, mais quel bruit fait-il ? C'est souvent une histoire de bruit d'ailleurs, un signal propre, une image nette, des données obvies, personne ne nous demande jamais de les analyser, de les traiter. C'est un peu comme les médecins en occident : ils voient peu de gens en bonne santé, à part les hypocondriaques, qui ont bien sûr un petit problème de santé, à un autre niveau. Le traitement de signal, l'analyse de données, on n'en fait pas en petite classe, du moins pas directement. Ce n'est pas au baccalauréat. Donc cette matière, la plupart des gens n'ont pas eu à la subir, et ayant peu de contact avec des mesures expérimentales, rares sont ceux qui ont dû avouer qu'ils ne savaient pas traiter les échantillons chèrement acquis. Pourtant, la donnée numérique est au cœur du monde réel, et il est fort possible que cela ne fasse qu'empirer.

Traitement d'images pour la science de la physique des matériaux

Ah ça, les mathématiques, on voit bien. La physique, la biologie, c'est à peu près clair. La chimie, évident. De loin, on sent que c'est compliqué, mais que ces gens gens-là se comprennent. Il y a des cases pour cela à l'Académie des sciences. Parfois ils ont des prix Nobel. Pas en mathématiques, mais on sait bien qu'il  y une espèce de prix Nobel des mathématiques, la médaille Fields. Et pourtant on connait mal le sens de ces mots : mathématiques vient du grec par le latin, avec un sens original de "science, connaissance". Physique vient de la "connaissance de la nature". Dans biologie, il y a le vivant, les produits bios... La chimie, c'est un peu plus compliqué (des mélanges, de la magie noire, de l'arabe et du grec). Mais statistiques, on retrouve la trace de l’État : science qui a pour but de faire connaître l'étendue, la population, les ressources agricoles et industrielles d'un État. L'électronique, on voit bien les petits électrons qui bougent dans les fils.

Analyse de signal chromatographique bidimensionnel

Et pourtant, la réalité scientifique est bien plus éparpillée : un biologiste qui étudie une bactérie a souvent peu à partager avec une spécialiste des champignons. Rien à voir, comme un spécialiste des dauphins et un lombriculteur. Cédric Villani, qui fait un grand effort de divulgation ces derniers temps (Les mathématiques sont un art comme les autres), et qui sera invité du prochain congrès de la communauté francophone et groupement de recherche et d'études du traitement du signal et de l'image (GRETSI 2015) à Lyon, montre une prudence naturelle quand on l'interroge sur d'autres mathématiques que les siennes. Physiciens des particules et mécaniciens des fluides se rencontrent rarement. La carte des sciences est bien plus complexe que les contribuables ne le pensent généralement.

Une carte des sciences en graphe

Comme les médecins qui ne soignent pas uniquement leurs bobos, les traiteurs de signaux traitent souvent les problèmes des autres disciplines. Les images pour la physique des matériaux, les signaux de chromatographie pour les chimistes analytiques, les réflexions sismiques des géophysiciens. Les traiteurs de signaux, les analyseurs d'images doivent comprendre un peu de ces disciplines. Savoir utiliser différentes techniques (analyse spectrale, statistiques, algèbre linéaire, modélisation paramétrique, optimisation, normalisation) et les mettre en pratique par des algorithmes et des programmes, même du matériel.

Déconvolution aveugle de réflexions sismiques

Il y a donc de la pratique (praxis) et de la technique (tekné) dans cette discipline composite, à la frontière d'autres sciences et disciplines. Il a fallu d'abord des mesures expérimentales avant de pouvoir les traiter. Personnellement, je me sens un praticien de certains types de données. Je connais leurs pathologies de base, j'ai quelques traitements qui marchent parfois. Technicien de la donnée, praticien de l'échantillon, ça donnerait des métiers d'infopracteurs/trices ou infopraticiens/praticiennes, d'infotechniciens/ciennes. J’aime a priori l’idée de rendre leur noblesse aux termes de praxis et de tekné. Donc « infopraxie » ou « infotechnie » comme nom de discipline ? Mais -technie, -praxie ça fait rebouteux, mécanicien auto. Et puis info, c’est trop « informatique ». Datalogie, ça aurait pu être bien : c'est une racine composite latino-hellénique, qui reflète bien l'aspect interdisciplinaire de cette science. Malheureusement, c'est déjà pris par l'informatique à nouveau (computer science). Il faudrait donc un truc plus sérieux.

Et par un tournant de sérendipité, je tombe sur  un texte d’Euclide, Dedomena qui a vu son titre traduit en latin en « data ». Il s'agit d'un texte sur la nature et les implications d'information donnée pour résoudre un problème géométrique. On y est. Il définit comment un objet est décrit en forme, en position, en grandeur. Ces critères sont très nettement ceux que l'on extrait au quotidien de données numériques. Et puis Euclide, c'est un bel hommage : les espaces euclidiens sont à la base de nombreux concepts algorithmes, et la minimisation de la distance euclidienne, c'est notre pain quotidien. Il suffit de regarder cet interlude de Martin Vetterli, From Euclid to Hilbert, Digital Signal Processing.

Alors je propose de renommer le traitement de signal ou des images, des données en général, en  dédoménologie, ou l’art de ceux qui parlent de, qui analysent des données. Cela plonge directement le traitement des signaux et des images au centre de la science des données en général. Ça aurait de la gueule sur une carte de visite, non ? Une mnémonique pour retenir ce terme : des domaines aux logis.

A partir de là, on peut étendre le vocabulaire à la dédoménotaxie, pour les opérations de classement, de tri de données (pour coller Euclide dans un taxi, c'est ici), à la dédoménotropie pour les flux de données, la dédoménomancie pour les aspects de prédiction (façon predictive analytics). Dénoménonomie, à la manière de l'astronomie, c'est peut-être dur à porter. Voila pour la science. Pour les aspects sociétaux, la mode est à la crainte des usages de manipulation de l'opinion et d'une gouvernance accrue par les données : dédoménodoxie et dédoménocratie. Attention donc à la dédoménophobie.

P. S. : après des recherches complémentaires, en anglais, le mot dedomenology pour désigner le concept de data science semble déjà avoir été émis, sans trop de succès.
P. S. 2 : on me signale (Hervé T.) que l'homophonie avec démonologie est suspecte. D'un : le dialbe est dans les détails, en science des données aussi. De deux : le démon de Maxwell, sans autre la qualité d'un filtre, est le parangon du tri du bon grain et de l'ivraie. De trois :  en informatique; un démon est : 

Un daemon (prononcé /ˈdiːmən/ ou /ˈdeɪmən/, du grec δαιμων) ou démon désigne un type de programme informatique, un processus ou un ensemble de processus qui s'exécute en arrière-plan plutôt que sous le contrôle direct d'un utilisateur.

Tout est dit.

The law of excessive gardening in education

Once upon a time. the term proletarian (or a Latin equivalent) used refer to  a Roman citizen who was so poor that he only had his children considered as his property. The term proles stands here for descendants (or litter). The term evolved through Marxism, to workers without capital or production means, who should sell their own work-force. The term can be somehow extended to the loss of knowledge of the production tools. An example lies in the comparison between the craftsman or artisan, who masters his tools, and may even be able to repair them, and manages a series of processes, as opposed to the factory worker, whose work has been taylorized and who lacks of knowledge in the whole meaning of the chain, or the functioning of the robots he "controls".

The concept of proletarianization has been used more recently by Bernard Stiegler (Ars Indutrialis), to describe a pauperization, not in terms of wealth, but in terms of ability to do, to make and to live. An externalization and therefore a loss of knowledge and memory. 

I believe proletarianization, in that sense, is rampant, and pervades all strata of the society: at every level of work, at least in institutions or companies, there is a loss of sense and understanding about the way stuff works. A corollary to Peter's principle. To make a long story short, strategic visions have progressively been replaced by indicator-based management. In science evaluation, the infamous impact factor or h-index are examples of such indicators. Stock-value and quality-based management are other examples. 

Peter's principle: (success>advancement)^n>failure

The top of proletarianization spread was given by Alan Greenspan, the former chairman of the Federal Reserve, who once told the CNBC that he did not fully understand the scope of the subprime mortgage market until well into 2005 and could not make sense of the complex derivative products created out of mortgages. Alan Greenspan, the chief banker of the world, was mystified... [EDIT 2021/0410: ThinkProgress archive : Greenspan: I Was ‘Mystified’ By The Subprime Mortgage Market]

So what's got the maths to do with it?

About two years ago, in April 2012, there was a conference called Fixing mathematical education. There i learned the effective law of excessive learning in mathematics from Alexandre V. Borovik:

To be able to use maths at certain level it is necessary to learn it at the next level

A week ago, Alexandre Borovik sent me a link to his preprint, Calling a spade a spade: Mathematics in the new pattern of division of labour:

The growing disconnection of the majority of population from mathematics is becoming a phenomenon that is increasingly difficult to ignore. This paper attempts to point to deeper roots of this cultural and social phenomenon. It concentrates on mathematics education, as the most important and better documented area of interaction of mathematics with the rest of human culture.
    I argue that new patterns of division of labour have dramatically changed the nature and role of mathematical skills needed for the labour force and correspondingly changed the place of mathematics in popular culture and in the mainstream education. The forces that drive these changes come from the tension between the ever deepening specialisation of labour and ever increasing length of specialised training required for jobs at the increasingly sharp cutting edge of technology.
    Unfortunately these deeper socio-economic origins of the current systemic crisis of mathematics education are not clearly spelt out, neither in cultural studies nor, even more worryingly, in the education policy discourse; at the best, they are only euphemistically hinted at.
    This paper is an attempt to describe the socio-economic landscape of mathematics education without resorting to euphemisms. 

The pdf is here. Alexandre claims that "The communist block was destroyed by a simple sentiment: If they think they pay me let them think I am working. Mathematics education in the West is being destroyed by a quiet thought (or even a subconscious impulse): If they think they teach me something useful, let them think I am learning." My experience as a part-time teacher is that it is increasingly difficult to have students learn things. Most of them are especially disgusted by the concept of "learning by heart" (wait, everything is in the Internet, isn't it?). While they could just try to understand. 

For a long time,  people could have proudly claimed that "I have never been good at mathematics, but I live happily without it". The XXth century has been rich in discoveries that have both pervaded the society (basically, from the transistor to the mp3). The pitfall is many users have no idea about the way these technologies work, and happily put their agenda, thoughts, entertainment time and finally life (pictures, films) in those hands. 

The world seemingly grows a local era where data becomes important (a new gold, a novel oil?) and big data or data science are slowly emerging as potentially disruptive technologies. Then, Alexandre states that "the West is losing the ability to produce competitively educated workers for mathematically intensive industries". It is high times to rethink (mathematical) education, as its changes may be much slower than the present evolution of technologies. 

Nota bene: and Igor, just for you, there is a phase transition ("The crystallisation of a mathematical concept (say, of a fraction), in a child's mind could be like a phase transition in a crystal") and an aha moment ("An aha! moment is a sudden jump to another level of abstraction")