K-moyennes

Définition

Un algorithme de partitionnement (clustering) populaire qui regroupe des exemples dans l'apprentissage non supervisé. L'algorithme k-moyennes effectue les opérations suivantes :

Détermination de manière itérative des meilleurs k points centraux (appelés centroïdes). Assignation de chaque exemple au centroïde le plus proche. Les exemples les plus proches du même centroïde font partie du même groupe. L'algorithme k-moyennes choisit l'emplacement des centroïdes de manière à minimiser le carré cumulatif des distances entre chaque exemple et son centroïde le plus proche.

Supposons le graphe suivant représentant la taille de chiens en fonction de leur largeur :

Si k = 3, l'algorithme k-moyennes détermine trois centroïdes. Chaque exemple est assigné à son centroïde le plus proche, ce qui donne trois groupes :

Imaginez qu'un fabricant souhaite déterminer les tailles idéales de tricots pour chien petits, moyens et grands. Les trois centroïdes identifient la hauteur et la largeur moyennes de chaque chien du cluster correspondant. Ainsi, le fabricant devrait probablement baser les tailles de pull sur ces trois centroïdes. Notez que le centroïde d'un cluster n'est généralement pas un exemple du cluster.

Les illustrations précédentes montrent les k-moyennes pour des exemples avec seulement deux caractéristiques (hauteur et largeur). Notez que les k-moyennes peuvent regrouper des exemples pour de nombreuses caractéristiques.