#k-means — Apprentissage non supervisé

Regrouper sans étiquettes : des centroïdes qui se déplacent, l'inertie qui baisse, le choix de k — et les formes où k-means échoue.

Ce que tu vas manipuler

Bienvenue dans #k-means. À l'écran : 150 points gris dans un cube, visiblement rassemblés en quatre paquets… que personne n'a étiquetés. Les quatre grosses sphères colorées sont les centroïdes : on vient de les poser au hasard sur quatre points du jeu, et aucun point n'est encore colorié. C'est tout ce que k-means sait : un nuage, un nombre k et une règle simple à répéter. Pas de bonne réponse à copier : c'est de l'apprentissage non supervisé.
Fais un tour : /iterer. Deux temps. Assignation : chaque point rejoint le centroïde le plus proche et prend sa couleur. Mise à jour : chaque centroïde saute au milieu (la moyenne) des points qu'il vient de gagner.
Encore /iterer. Quelques points changent de camp à la frontière entre deux groupes, et les centroïdes bougent moins que la première fois. Regarde l'inertie dans le panneau de droite : la somme des distances² de chaque point à son centroïde. Elle baisse à chaque tour, jamais l'inverse : chacune des deux étapes ne peut que la réduire.
Laisse tourner jusqu'au bout : /tout. Quand plus aucun point ne change de camp, les centroïdes ne bougent plus : c'est la convergence. Mais regarde bien le résultat : avec ce départ, deux centroïdes tombés dans le même paquet se le partagent, pendant qu'un seul centroïde doit couvrir deux paquets à la fois. C'est un minimum local : rien ne les délogera plus.
Le remède le plus courant est un meilleur départ : /init kmeans++. Le premier centroïde est tiré au hasard ; chaque suivant est tiré avec une probabilité proportionnelle au carré de sa distance au centroïde déjà posé le plus proche. Les points isolés, loin de tout, ont bien plus de chances d'être choisis : les centroïdes de départ s'éloignent les uns des autres, et il y a beaucoup moins de mauvais départs.
Relance /tout et compare l'inertie finale avec celle du run précédent (je te la rappelle). Même jeu de points, même k : seul le point de départ a changé.
Changeons la forme du nuage : /dataset anneaux. Deux anneaux concentriques, l'un dans l'autre, dans le plan horizontal. Pour un œil humain, deux groupes évidents.
D'abord /tout, pour voir la coupe en parts : k-means ne « voit » pas la forme d'un groupe, seulement la distance à un centre (pour les anneaux, il faudra #dbscan). Ensuite, la question qu'on esquive depuis le début : pourquoi 4 ? Tape /coude : je relance k-means pour k = 1 à 8 et je relève l'inertie finale de chacun.
À toi de jouer : /dataset blobs puis /coude pour un coude net à k = 4 ; /k 2 puis /tout sur les anneaux (deux parts, pas deux anneaux) ; /dataset lunes et /dataset allonge, deux autres formes que k-means découpe de travers ; /init aleatoire avec plusieurs /graine pour collectionner les minima locaux ; /liens pour voir qui appartient à qui ; /reinit pour repartir. Ensuite : #pca, pour projeter ces nuages en 2D avant de les regrouper, et #clustering-hierarchique, qui se passe du choix de k.

Commandes du canal

/k <1..8> — Change le nombre de clusters ; repose les centroïdes, itération 0.
/iterer — Une itération de Lloyd : assignation puis mise à jour des centroïdes.
/tout — Itère jusqu'à convergence (déplacement < 1e-4) ou 30 tours.
/init <aleatoire|kmeans++> — Change l'initialisation des centroïdes ; repart à l'itération 0.
/graine <1..99> — Retire les points et les centroïdes de départ avec une autre graine.
/dataset <blobs|anneaux|lunes|allonge> — Change la forme du nuage de points ; repart à l'itération 0.
/liens — Affiche ou masque un trait fin de chaque point vers son centroïde.
/coude — Méthode du coude : inertie finale pour k = 1..8.
/reinit — Revient aux blobs, k = 4, init aléatoire, itération 0.

Glossaire

k-means: Algorithme de partitionnement qui range n points en k groupes en minimisant la somme des distances² de chaque point au centre de son groupe. Rapide et simple, mais il suppose des groupes en « boules » et exige de choisir k à l'avance.
centroïde: Centre d'un cluster : la moyenne (barycentre) de tous les points qui lui sont assignés. C'est le seul « souvenir » qu'un cluster laisse à k-means.
inertie: Somme, sur tous les points, du carré de la distance euclidienne au centroïde de leur cluster. C'est la quantité que k-means fait baisser à chaque itération ; elle décroît toujours quand k augmente.
assignation / mise à jour: Les deux temps de l'algorithme de Lloyd : chaque point rejoint le centroïde le plus proche (assignation), puis chaque centroïde saute au barycentre de ses points (mise à jour). On répète jusqu'à ce que plus rien ne bouge.
convergence: Moment où plus aucun point ne change de cluster : les centroïdes ne bougent plus et l'inertie ne baisse plus. Ici on s'arrête quand le déplacement moyen passe sous 1e-4, ou après 30 tours.
minimum local: Partition où k-means s'arrête sans qu'elle soit la meilleure possible : deux centroïdes se partagent un même groupe pendant qu'un autre en couvre deux. L'algorithme n'a aucun moyen d'en sortir ; seul un autre départ peut faire mieux.
k-means++: Initialisation qui tire le premier centroïde au hasard, puis chaque suivant avec une probabilité proportionnelle au carré de sa distance au centroïde déjà posé le plus proche. Les centroïdes de départ sont écartés, ce qui évite la plupart des mauvais minima locaux.
méthode du coude: Façon de choisir k : on trace l'inertie finale pour k = 1, 2, 3… et on retient le k où la courbe casse, le « coude » : au-delà, un centroïde de plus n'apporte presque rien.
apprentissage non supervisé: Apprendre sans étiquettes : on ne donne au modèle que les données, jamais la bonne réponse. Le clustering (k-means), la réduction de dimension (PCA) et la détection d'anomalies en font partie.
cluster: Groupe de points jugés semblables entre eux et différents des autres. Le partitionnement (clustering) consiste à découper un jeu de données en clusters sans connaître de catégories à l'avance.

Autres canaux du thème Apprentissage non supervisé

#k-means — Regrouper sans étiquettes : des centroïdes qui se déplacent, l'inertie qui baisse, le choix de k — et les formes où k-means échoue.
#pca — Analyse en composantes principales : trouver les axes où les données varient le plus, projeter, compresser — et mesurer ce qu'on perd.
#clustering-hierarchique — Fusionner les points deux à deux jusqu'à n'en faire qu'un : le dendrogramme, les critères de lien, et la hauteur de coupe qui décide du nombre de clusters.
#dbscan — Regrouper par densité : epsilon, MinPts, points cœur, bordure et bruit — l'algorithme qui trouve des formes quelconques et ignore les intrus.
#detection-anomalies — Repérer ce qui ne ressemble à rien : score z / Mahalanobis, Isolation Forest, LOF — trois façons de dire « ce point est bizarre ».
#t-sne-umap — Cartographier la haute dimension : t-SNE et UMAP déplient des données à 10 dimensions en une carte 2D lisible — perplexité, voisins, et pièges de lecture.