• 15 heures
  • Moyenne

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 01/02/2019

Découvrez l’algorithme k-means

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Commençons avec l'algorithme le plus célèbre en clustering : l'algorithme k-means, ou algorithme des centres mobiles en français.

Fonctionnement de l'algorithme

Vous allez voir, il est très intuitif et facile à comprendre.

Il faut tout d'abord déterminer combien de groupes on souhaite trouver : on appelle ce nombre $\(K\)$ .

L'objectif : trouver des groupes en faisant en sorte de minimiser l'inertie intraclasse.

L'algorithme du k-means travaille avec les centres de gravité des groupes. Seulement voilà, au départ, on ne connaît pas les groupes ! On ne peut donc pas connaître leur centre de gravité (que l'on appelle souvent des centroïdes). Mais ce n'est pas grave : on va supposer qu'on les connaît quand même, et les placer aléatoirement dans l'espace. Enfin... pas trop aléatoirement quand même : on va plutôt "piocher" au hasard des points qui font partie du nuage, pour y placer les centroïdes.

Une fois les centroïdes placés, on prend chaque point du nuage et on lui associe le cluster du centroïde dont il est le plus proche. On obtient donc un nuage de points dont chaque point appartient à l'un des K groupes.

Une fois cette opération faite, on calcule le centre de gravité de chaque groupe. Pour un groupe donné, le centre de gravité n'est généralement pas exactement au même endroit que là où l'on avait placé le centroïde initialement. On déplace donc ce centroïde sur le nouveau centre de gravité calculé.

Mais comme le centroïde a bougé, il faut recalculer, pour chacun des points du nuage, quel est le centroïde le plus proche, pour l'associer au bon cluster. Puis on recalcule le nouveau centre de gravité, et ainsi de suite... jusqu'à la convergence de l'algorithme.

Convergence ?

Ici, on dit que l'algorithme converge quand plus rien ne bouge d'une itération à l'autre, c'est-à-dire quand le centroïde reste immobile même après avoir recalculé pour chaque point son cluster.

Rien de tel qu'un petit schéma pour illustrer tout cela !

Source : Data mining et statistique décisionnelle: l'intelligence des données, Stéphane Tufféry
Source : Data mining et statistique décisionnelle : l'intelligence des données, Stéphane Tufféry

Avantages et inconvénients du k-means

L'algorithme du k-means converge en général très rapidement : il n'est pas rare qu'il atteigne la convergence au bout de 10 itérations, même avec beaucoup de points.

Malheureusement, le k-means n'est pas capable de déterminer le nombre de classes optimal : on est obligé de le lui spécifier au départ. Si on lui demande de trouver 3 clusters alors que vos données sont très clairement regroupées en 5 clusters, alors le k-means vous donnera 3 clusters, même si ce n'est visiblement pas la solution la meilleure.

Pour choisir le nombre optimal de clusters, on peut aussi lancer le k-means plusieurs fois, avec différentes valeurs de $\(K\)$ . Pour chacune d'entre elles, on note l’inertie intraclasse obtenue. Bien entendu, l’inertie intraclasse diminue forcément quand K augmente, mais en observant la valeur de K au-delà de laquelle la diminution est plus faible, on peut déterminer une bonne valeur de K. C'est la méthode du coude.

Exemple de certificat de réussite
Exemple de certificat de réussite