k-means

Théo Boulakia

13 novembre 2024

Wikipédia

Étant donné un ensemble de points et un entier k, le problème est de trouver une partition de ces points en k groupes minimisant la variance à l’intérieur de chaque groupe. Plus précisément, il s’agit de minimiser la somme des carrés des distances de chaque point à la moyenne des points de son groupe.

Problème

Le nombre de partitions possibles d’un ensemble de n éléments croît exponentiellement avec n.

Exemple

Il y a 580 606 446 partitions possibles de 20 éléments en 3 classes.

Heuristique

Avec Allison Horst

Données

Groupes

Centroïdes aléatoires

Allouer les points

Recalculer les centroïdes

Allouer les points

Recalculer les centroïdes

Allouer les points

Recalculer les centroïdes

Allouer les points

Recalculer les centroïdes

Allouer les points

Recalculer les centroïdes

Allouer les points

Recalculer les centroïdes