- Descente, optimum local, non-convexité. Un algorithme qui ne fait que descendre s'arrête dans le creux où il est tombé, et rien dans ce qu'il observe ne dit si c'est le bon (p03-02 pas 4). Toute la seconde moitié de cette chaîne est ce constat, appliqué à des centroïdes.
- La moyenne minimise la somme des carrés. m ↦ Σ(xi − m)² est une parabole en m, de dérivée −2Σ(xi − m), nulle en la moyenne (p00-02 pas 3). C'est exactement le second demi-pas de Lloyd — on l'applique, on ne le redémontre pas.
- Les unités portent la distance. Une feature en milliers écrase toutes les autres dans une norme euclidienne (p04-04 pas 6). Même piège ici, même remède : standardiser avant, pas après.
- Le témoin atteignable. Quand un critère peut toujours être amélioré par un modèle plus gros qui reproduit le plus petit, ce critère ne choisit pas la taille (b02). C'est mot pour mot ce qui empêche J de donner k.
La chaîne
Le décor : un critère, deux inconnues
n points, k centroïdes à placer. Le critère est l'inertie (aussi : SSE intra-cluster) — la somme des carrés des distances de chaque point au centroïde qui lui est affecté.
Deux objets sont inconnus, pas un : l'affectation c : {1…n} → {1…k}, et les centroïdes μ1…μk. Il n'y a pas de y : J est à la fois ce qu'on optimise et tout ce qu'on peut mesurer.
« Le critère additionne le carré de la distance de chaque point à son centroïde, donc il dépend à la fois des affectations et des centroïdes, donc minimiser J c'est chercher deux objets à la fois, donc l'algorithme devra fixer l'un pour traiter l'autre. »
Six points sur une droite : 1, 2, 3, 10, 11, 12. k = 2, centroïdes de départ μ = (1 ; 2). L'affectation au plus proche donne {1} et {2, 3, 10, 11, 12} — 10 est à 8 de 2 et à 9 de 1, il part donc à droite.
| point | 1 | 2 | 3 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|
| plus proche | μ1 | μ2 | μ2 | μ2 | μ2 | μ2 |
| carré de l'écart | 0 | 0 | 1 | 64 | 81 | 100 |
Inertie de départ : J = 246. C'est le nombre que les deux demi-pas suivants vont faire tomber.
Deux inconnues, deux minimisations exactes tronc
Prise séparément, chacune des deux inconnues se résout en forme fermée, sans itération ni approximation.
La première est une décision point par point : les termes de J sont indépendants une fois μ figé. La seconde est un système linéaire en μ, un par cluster — la moyenne de p00-02, lue comme le demi-pas de b06 pas 3.
« À centroïdes fixés le meilleur cluster d'un point est le plus proche, donc le premier demi-pas se résout point par point, donc à clusters fixés le gradient en μ est linéaire et le meilleur centroïde est la moyenne, donc chaque demi-pas de Lloyd est un minimum exact et non une approximation. »
Sur le fil rouge, avec μ = (1 ; 7,6) obtenu au recentrage, le point 3 est à 2 de μ1 et à 4,6 de μ2 : il change de camp.
| demi-pas | ce qui bouge | résultat | J |
|---|---|---|---|
| départ | — | μ = (1 ; 2), {1} · {2,3,10,11,12} | 246 |
| recentrer | μ | μ2 = 38/5 = 7,6 | 89,2 |
| affecter | c | {1, 2, 3} · {10, 11, 12} | 41,68 |
| recentrer | μ | μ = (2 ; 11) | 4 |
Détail du 89,2 : à gauche 0, à droite 5,6² + 4,6² + 2,4² + 3,4² + 4,4² = 31,36 + 21,16 + 5,76 + 11,56 + 19,36. Aucun des deux gestes n'est un compromis : chacun est le minimum exact de J sur sa variable.
Lloyd : deux exacts alternés, donc ça s'arrête tronc
L'algorithme de Lloyd — ce qu'on appelle « k-means » — répète affecter, recentrer. Chaque demi-pas minimise J sur une variable, l'autre figée : il ne peut donc pas la faire monter.
L'argument de finitude est celui qui compte : deux passages par la même affectation donneraient la même valeur de J, or J décroît strictement tant que l'affectation change — aucune ne revient. Le recentrage est aussi un pas de gradient, avec η = 1/(2nj) qui tombe pile sur le minimum (b01 habit 3).
« Chaque demi-pas minimise J sur une variable à l'autre figée, donc J ne monte jamais, donc la suite décroît en restant au-dessus de zéro, donc elle converge — et comme les affectations sont en nombre fini, Lloyd s'arrête en un nombre fini d'itérations. »
Quatre demi-pas, puis un cinquième qui ne change rien : l'affectation est stable, donc le recentrage aussi, donc c'est fini.
| demi-pas | geste | J |
|---|---|---|
| 1 | affecter | 246 |
| 2 | recentrer | 89,2 |
| 3 | affecter | 41,68 |
| 4 | recentrer | 4 |
| 5 | affecter | 4 — rien ne bouge |
Et 4 est ici l'optimum global : parmi les cinq découpages en deux paquets contigus, {1,2,3} · {10,11,12} est le meilleur. Sur cet exemple aucune initialisation ne piège Lloyd — il faut deux dimensions pour fabriquer le piège, c'est le pas suivant.
Les six points sur leur droite, colorés par cluster ; les traits verticaux sont les centroïdes, et la barre sous chaque point est sa contribution (x − μ)² à l'inertie — J est la hauteur totale des barres. Clique « demi-pas » : un clic sur deux réaffecte (les couleurs changent, les centroïdes ne bougent pas), l'autre recentre (l'inverse). Regarde le readout J : il baisse aux deux gestes et ne remonte jamais. Au cinquième demi-pas plus rien ne bouge — et les barres ont alors pratiquement disparu : 4 contre 246 au départ.
Mais vers un optimum local
Chaque demi-pas est exact, et pourtant le résultat dépend du départ. J n'est pas convexe en (c, μ) : c'est un minimum de morceaux quadratiques, un par découpage possible — convexe sur chaque morceau, non convexe sur l'ensemble (b06 pas 3).
La raison mécanique tient en une ligne : un centroïde atterrit dans l'enveloppe convexe des points qui lui sont affectés — il va à leur moyenne, et une moyenne ne sort jamais de l'enveloppe de ce qu'elle moyenne. Et il ne reçoit que les points plus proches de lui que des autres centroïdes : une init dans un seul amas y reste. Les deux bouts ensemble : rien ne l'attire vers un amas qu'il n'a pas. Une fois la partition installée, chacun a ses points et plus personne n'a de raison de bouger — fût-ce pour aller séparer deux amas manifestement distincts.
« Un centroïde ne va qu'à la moyenne des points qui lui sont affectés, donc rien ne l'attire vers un amas qu'il n'a pas, donc deux centroïdes qui se partagent un même amas y restent tous les deux, donc Lloyd s'arrête avec deux amas fusionnés sous un seul centroïde et ne le signale pas. »
Attention à la formule courte : un centroïde peut traverser une zone vide — dans la figure 2, celui qui s'échappe saute de x ≈ 5,25 à x ≈ 1,64 par-dessus le trou, en un seul demi-pas, parce que ses points ont changé. Ce qui est vrai n'est pas qu'il ne traverse pas le vide, c'est qu'il ne va jamais ailleurs que dans l'enveloppe de ses propres points.
Trois amas gaussiens de 30 points (écart-type 0,6 par axe), centrés en (1 ; 1), (2,4 ; 3,6) et (6,4 ; 1,4). Même algorithme, deux initialisations.
| départ | itérations | ce qu'on obtient | J |
|---|---|---|---|
| un centroïde par amas | 2 | 30 · 30 · 30 | 65,18 |
| trois points de l'amas de droite | 7 | 60 · 16 · 14 | 165,30 |
Au premier recentrage, le plus à gauche des trois hérite d'un coup des 60 points des deux amas de gauche et va se poser à leur barycentre, entre les deux — il ne les séparera plus jamais, seul. Les deux autres ont chacun leurs points (16 et 14) : rien ne les appelle à l'aide. Coût : 2,5 fois l'optimum. Et J décroît proprement tout du long — 956 → 198 → 168 → 166,6 → … → 165,30 — sans jamais remonter et sans jamais avertir.
Le chiffre qui pique : le meilleur découpage à k = 2 vaut 174,36. Ce piège à k = 3 fait donc à peine mieux qu'avec un centroïde de moins — le troisième est gaspillé.
Choisis un départ, puis « jouer » (ou « demi-pas » pour avancer à la main). Les grands cercles creux sont les centroïdes, la ligne fine derrière chacun est sa trajectoire depuis l'init. Avec « init ratée », les trois partent dans l'amas de droite : le plus à gauche hérite dès la première affectation des 60 points des deux amas de gauche et va se poser à leur barycentre, entre les deux, en (1,64 ; 2,21) — il ne pourra plus les séparer, et les deux autres, qui se partagent l'amas de droite (16 et 14 points), ne viendront pas. Aucun centroïde ne reste vide : les trois gardent des points, et c'est bien pour ça que Lloyd s'arrête sans rien signaler. J se fige à 165,30 au lieu de 65,18. « init au hasard » tire trois points au sort à chaque clic : environ un lancer sur quatre finit dans ce piège.
Initialiser : k-means++ et redémarrages
Si le départ décide, alors le départ est l'algorithme. k-means++ : le premier centroïde est tiré uniformément parmi les points ; chacun des suivants est tiré avec une probabilité proportionnelle au carré de sa distance au plus proche centroïde déjà choisi.
Un amas non couvert a de grands d², donc il est probable. La garantie qui l'accompagne est en espérance et en ordre : 𝔼[J] = O(log k)·J*, avant même le premier demi-pas de Lloyd. Elle réduit le risque, elle ne l'annule pas : on lance donc ninit fois et on garde le plus petit J.
« Un point loin de tous les centroïdes déjà choisis a un d² grand, donc il est probable au tirage suivant, donc les centroïdes initiaux tombent dans des amas différents, donc le piège devient rare — rare et non impossible, donc on relance et on garde le plus petit J. »
| initialisation | lancers piégés | taux | 10 lancers tous piégés |
|---|---|---|---|
| trois points au hasard | 118 / 500 | 23,6 % | ≈ 5·10−7 |
| k-means++ | 47 / 500 | 9,4 % | ≈ 5·10−11 |
Un tirage de ninit = 10 lancers au hasard donne ici 8 fois 65,18, une fois 165,30 et une fois 168,71 : le minimum retenu est le bon. Garder le plus petit J est légitime — J est le critère qu'on optimise, pas une performance estimée sur des données mises de côté ; il n'y a rien ici à sur-ajuster par sélection (à l'inverse du cas supervisé).
Choisir k : le critère ne le donne pas
Ajouter un centroïde ne peut pas dégrader J : la solution à k reste atteignable à k+1, en posant le centroïde de trop sur un existant. C'est le témoin de b02, appliqué ici.
Restent trois lectures, aucune n'étant une preuve : le coude de J(k), la silhouette (nommée ici, pas détaillée), et le k dicté par l'usage — le nombre de segments qu'on saura traiter. k est un choix qu'on assume, pas un paramètre qu'on estime.
« k+1 centroïdes peuvent reproduire la solution à k en posant celui de trop sur un existant, donc J décroît toujours en k, donc J n'a pas de minimum à chercher, donc k se lit sur un coude ou se décide par l'usage — jamais ne se trouve. »
| k | J*(k) | gain sur k−1 |
|---|---|---|
| 1 | 630,2 | — |
| 2 | 174,4 | 455,8 |
| 3 | 65,2 | 109,2 |
| 4 | 53,9 | 11,2 |
| 5 | 44,9 | 9,0 |
| 6 | 36,7 | 8,2 |
| 7 | 31,0 | 5,7 |
| 8 | 27,2 | 3,9 |
Le coude est net : le gain passe de 109,2 (de k = 2 à 3) à 11,2, soit dix fois moins, en passant de k = 3 à k = 4. Au-delà, chaque centroïde supplémentaire rapporte un peu — et rapportera encore quelque chose jusqu'à k = 90, où J = 0. Le coude se lit, il ne se calcule pas.
En haut, dix lancers de Lloyd depuis des départs au hasard : chaque point est le J final d'un lancer, le trait horizontal marque le meilleur trouvé. Clique « relancer 10 » plusieurs fois — la plupart des lancers tombent sur 65,18, deux ou trois montent à 165, et le minimum des dix est presque toujours le bon : c'est tout ce que fait ninit. En bas, J*(k) pour k = 1…8 : toujours décroissante, avec un coude marqué en k = 3 — et rien, dans la courbe, qui dise que 3 est la bonne réponse plutôt que la réponse lisible.
Ce que la distance suppose tronc
Affecter au plus proche découpe l'espace en cellules de Voronoï : la frontière entre deux centroïdes est leur plan médiateur. Chaque cluster est donc un polyèdre convexe, et la question « quelles formes k-means sait-il produire ? » a une réponse exacte : celles-là, et pas d'autres.
D'où les échecs prévisibles : deux anneaux concentriques (non convexes), un amas allongé à côté d'un amas rond (le plan médiateur coupe le long), un amas de 1000 points contre un de 20 (le gros se fait couper en deux avant que le petit ait son centroïde). Pour ces formes-là : DBSCAN, mélanges gaussiens (nommés, pas développés).
« Affecter au centroïde le plus proche découpe l'espace en cellules de Voronoï, donc tout cluster produit par k-means est convexe, donc une forme non convexe ne peut pas en être un, donc l'algorithme la coupe en morceaux et s'arrête sans erreur. »
Deux groupes de 40, séparés par l'âge (30 ans contre 52 ans) et rigoureusement identiques en salaire (45 000 € ± 6 000, même loi pour les deux groupes). k = 2.
| écart-type âge | écart-type salaire | pureté des clusters | |
|---|---|---|---|
| données brutes | 11,2 | 5 641 | 53,8 % |
| standardisées | 1 | 1 | 100 % |
Le salaire pèse 502 fois l'âge dans la distance : k-means coupe donc sur le salaire — « hauts salaires » contre « bas salaires » — alors que le salaire ne porte aucune structure. 53,8 % de pureté, c'est le hasard. Une seule ligne de standardisation (p04-04 pas 6) et la structure réapparaît intacte.
k-means comme quantification
Remplacer chaque point par son centroïde, c'est une compression avec perte : on garde un codebook de k vecteurs et un index par point. L'erreur moyenne de cette compression est exactement J/n.
C'est la quantification vectorielle des index de recherche : un index IVF partitionne la base par k-means et ne parcourt que les listes dont le centroïde est proche de la requête ; la product quantization fait tourner un k-means par tranche de coordonnées. Même algorithme, autre nom, autre métier.
« Chaque point est remplacé par son centroïde, donc ce qu'on conserve de lui est un index sur k valeurs, donc l'erreur moyenne de reconstruction vaut J divisée par n, donc minimiser l'inertie c'est minimiser la distorsion d'un quantificateur. »
90 points en 2D, soit 180 nombres. Après k-means à k = 3 : 6 nombres de codebook et 90 index de 2 bits.
| valeur | |
|---|---|
| distorsion J*/n = 65,18/90 | 0,724 |
| bruit intrinsèque des amas : 2 × 0,6² | 0,720 |
Les deux nombres coïncident, et ce n'est pas un hasard : à k = 3 le quantificateur a atteint la dispersion des amas eux-mêmes. Aucun codebook de trois vecteurs ne fera mieux — pour descendre, il faut plus de centroïdes, c'est-à-dire des index plus longs. Le pas 6 devient ici un arbitrage de débit, et le coude un choix de compression.
Où ça casse casse
Les limites de k-means ont toutes la même racine : le critère est une somme de carrés euclidiens, et rien d'extérieur ne vient le contredire. Un résultat faux a exactement la même tête qu'un résultat juste.
« Il n'y a pas de y, donc aucune quantité observable ne distingue un bon arrêt d'un mauvais, donc chaque limite ci-dessous passe inaperçue au moment où elle agit, donc le seul garde-fou est de savoir ce que le critère récompense avant de le lancer. »
- Formes non sphériques, tailles inégales. Les clusters sont des cellules de Voronoï convexes (pas 7) : deux anneaux concentriques ou un amas allongé sont coupés en travers, avec un J parfaitement minimisé. Remède : changer d'algorithme (DBSCAN, mélanges gaussiens), pas de k.
- Échelles. Sans standardisation, la feature de plus grande échelle décide seule — 502 contre 1 dans l'exemple du pas 7, et 53,8 % de pureté. C'est la panne la plus fréquente, et la plus facile à corriger.
- Outliers. La moyenne est tirée par un point isolé (p05-01 pas 3). Ajoute un 60 au fil rouge : le meilleur découpage à k = 2 devient {1…12} et {60}, avec μ = (6,5 ; 60) et J = 125,5. Un seul point confisque un centroïde et efface la structure des six autres. Remède : k-medoids (nommé), ou retirer les outliers avant.
- Cluster vide. Un centroïde à qui plus aucun point n'est affecté n'a plus de moyenne : il ne bougera plus jamais, et k effectif tombe à k−1 sans que rien ne le dise. Les implémentations le réinitialisent sur le point le plus éloigné de son centroïde.
- k, encore. Choisi, jamais trouvé : J décroît toujours (pas 6), donc aucune optimisation ne le livrera. Coude et silhouette sont des lectures, et deux lecteurs peuvent lire deux k différents sur la même courbe.
Résumé
- J = Σ‖x − μc(x)‖² : deux inconnues, deux minimisations exactes — le plus proche, puis la moyenne.
- Lloyd alterne les deux ; J ne monte jamais et reste ≥ 0, et les affectations sont finies ⇒ convergence en temps fini.
- Non convexe ⇒ optimum local : rien n'attire un centroïde vers un amas qu'il n'a pas, donc l'initialisation décide (65,18 contre 165,30 sur les mêmes points).
- k-means++ (tirages ∝ d²) fait tomber le taux de piège de 23,6 % à 9,4 % ; les redémarrages font le reste — on garde le plus petit J.
- J*(k) décroît toujours (témoin atteignable, b02) : coude, silhouette ou usage — k est un choix.
- Euclidienne ⇒ cellules convexes, amas ronds de tailles comparables ; standardiser d'abord, sinon une seule feature décide.
- Quantification vectorielle (IVF, product quantization) : le même algorithme, avec la distorsion J/n pour nom.
Chaîne verbalisée — une prise, à voix haute
- Que minimise k-means ?L'inertie J = Σ‖xi − μc(i)‖², somme des carrés des distances de chaque point à son centroïde — en deux inconnues : l'affectation et les centroïdes.
- Pourquoi chaque demi-pas de Lloyd est-il exact ?À μ fixés, le meilleur cluster d'un point est le plus proche, point par point. À c fixée, le gradient en μ est linéaire et s'annule en la moyenne du cluster.
- Pourquoi ça converge, et pourquoi ça s'arrête ?J ne monte jamais et reste ≥ 0, donc elle converge ; et comme il y a un nombre fini d'affectations et qu'aucune ne revient, l'arrêt est atteint en un nombre fini d'itérations.
- Pourquoi pas vers l'optimum global ?J est non convexe en (c, μ), et un centroïde ne va qu'à la moyenne de ses points : rien ne l'attire vers un amas qu'il n'a pas, donc deux centroïdes coincés dans le même amas y restent.
- Que fait k-means++ ?Il tire les centroïdes initiaux avec une probabilité ∝ d² au plus proche déjà choisi, donc loin les uns des autres. Garantie O(log k) en espérance ; le reste est fait par les redémarrages.
- Pourquoi J ne donne-t-il pas k ?Parce que k+1 centroïdes reproduisent la solution à k : J* décroît toujours, jusqu'à 0 en k = n. Coude ou silhouette sont des lectures, pas des preuves.
Ponts et cartes
ml::inertie (J = Σ‖x − μc‖², décroît toujours en k) · ml::lloyd (deux minimisations exactes alternées ; convergence en temps fini) · ml::kmeans (optimum local, cellules de Voronoï, standardiser) · ml::kmeans-plus-plus (tirage ∝ d², O(log k) en espérance, ninit).
Une carte qui résiste après cette chaîne est une carte à refondre, pas une section à relire.