La méthode des kmeans

visualisation des cluster du kmeans

 

Quel que soit le domaine dans lequel on travaille, il peut être intéressant de savoir construire des groupes d’observations qui se ressemblent. On appelle cela des clusters.

Il existe deux méthodes classiques pour réaliser des clusters :

  • la méthode des kmeans,
  • et celle du clustering hiérarchique.

Dans cet article, nous allons nous intéresser à la méthode des kmeans. C’est une approche que j’aime beaucoup parce que je trouve le principe vraiment astucieux !

Contexte de la méthode des kmeans

La méthode des kmeans permet de regrouper les objets (ou sujets, ou sites, ou point, etc…) en K clusters distincts. Ce nombre K doit être spécifié, mais il existe des approches pour déterminer son nombre optimal.

La méthode des kmeans repose sur la minimisation de la somme des distances euclidiennes au carré entre chaque objet (ou sujet, ou point) et le centroïde (le point central) de son cluster.

La méthode des kmeans est une approche de clustering non-hiérarchique (à l’intérieur d’un cluster les objets ne sont pas ordonnés en fonction de leurs ressemblance).

La méthode des kmeans appartient aux algorithmes de classification non supérvisée, de machine learning. Les termes “non supervisée” signifie que les groupes n’existent pas avant d’être créés ; il ne s’agit d’apprendre à partir des données comment construire des clusters existants. Il s’agit seulement de regrouper les données.

Dans la méthode des kmeans, les objets (ou sujets, ou sites, ou points, etc.) appartiennent à un seul cluster, et les clusters ne se chevauchent pas.

 

Principe

LAdistance euclidienne

La distance euclidienne est à la base de la méthode des kmeans, puisqu’il s’agit d’attribuer un cluster à chaque point, de façon à ce que la somme des distances euclidiennes au carré entre chaque point et le centroide de son cluster, soit la plus faible possible. On parle de minimisation de la variation intra-cluster (within-cluster variation en anglais).

La distance euclidienne est simplement une généralisation du théorème de Pythagore qui dit que ” le carré de la longueur de l’hypoténuse, qui est le côté opposé à l’angle droit, est égal à la somme des carrés des longueurs des deux autres côtés.”

 

pythagore et distance euclidienne

 

 

Ainsi, dans un espace à deux dimensions la distance euclidienne entre deux points peut être estimée par hypoténuse d’un triangle rectangle.

distance euclidienne

Dans un espace à n dimensions (u, v, …z), la distance euclidienne entre les points, ou deux observations $A(u_A, v_A,…,z_A)$ et $B(u_B, v_B,…,z_B)$ , est définie par :

$$d(A,B) = \sqrt{(u_A – u_B)^2 + (v_A – v_B)^2 +…(z_A – z_B)^2 }$$

Ainsi, deux observations identiques ont une distance nulle.

 

Remarque : si deux variables ne sont pas dans la même échelle, l’une pourrait avoir plus de poids dans le calcul de la distance euclidienne que l’autre. C’est pour cette raison qu’il est préférable de centrer réduire les données. En effet, le “centrage-réduction” permet d’obtenir des données indépendantes de leur unité.

L’algorithme

L’algorithme du kmeans est un algorithme itératif qui minimise la somme des distances entre chaque individu et le centroïde du cluster ; c’est la variabilité intra cluster.

Le principe est :

  1.  Attribuer un cluster à chaque objet (ou sujet, ou point), de façon aléatoire.
  2. Calculer le centroïde de chaque cluster (c’est-à-dire le vecteur des moyennes des différentes variables)
  3. Pour chaque objet (ou sujet ou point) calculer sa distance euclidienne avec les centroides de chacun des clusters
  4.  Attribuer à l’objet le cluster le plus proche de lui
  5. Calculer la somme de la variabilité intra-cluster
  6. Recommencer les étapes 2 à 5, jusqu’à atteindre un équilibre, on parle de convergence : plus aucun changement de clusters, ou stabilisation de la somme de la variabilité intra-cluster.

 

Voici un exemple de construction de 3 clusters avec 2 variables (2 dimensions) pour bien comprendre. algorithme du kmeans

Ces graphiques sont tirées de l’ouvrage “An introduction to statistical learning, de James, G., Witten, D., Hastie, T., & Tibshirani, (2013)“.

👉 Cliquez ici pour accéder au livre An Introduction to Statistical Learning.

 

 

Ci-dessous, des graphiques montrant l’évolution de la somme de la variabilité intra-cluster, en fonction de l’évolution des clusters:

 

minimisation de la variabilité intracluster

 

Vous trouverez plus d’information sur ce calcul dans le livre An introduction to statistical learning, de James, G., Witten, D., Hastie, T., & Tibshirani, (2013).

 

L’attribution initiale

Le résultat final, c’est-à-dire l’appartenance de chaque objet (ou sujet ou point) à un cluster donné peut dépendre de l’attribution initiale aléatoire des clusters qui a lieu dans la première étape de l’algorithme.

Pour contourner cette difficulté, il est nécessaire de lancer plusieurs fois l’algorithme et de regarder si la composition des clusters est modifiée ou non.

La fonction kmeans() réalise automatiquement ces multiples attributions aléatoires, et conservent uniquement les meilleurs résultats.

kmeans avec R

Les données

Nous allons utiliser des données mtcars, présentes dans le package dataset, chargé par défaut dans R.

 

Plus précisément, nous allons conserver les données réellement numériques continues :

 

 

Standardisation des données

Comme expliqué précédemment, avant d’employer l’approche des kmeans, il est nécessaire de standardiser (centrage réduction) les données. Pour cela, nous pouvons employer la fonction scale():

 

La fonction kmeans()

Les deux principaux arguments de la fonction kmeans() sont :

  • centers qui correspond au nombre de clusters désirés,
  • nstart correspond au nombre de fois que l’algorithme est lancé. Seul le meilleur résultat est conservé :

 

Pour obtenir à quel cluster appartient chaque point, nous pouvons employer :

 

Et pour obtenir la valeur de la variabilité intra-cluster :

 

Choix du nombre de clusters

Trois méthodes sont généralement employées :

  • Elbow method : basée sur la minimisation de la somme des carrés des écarts à l’intérieur des clusters (SSwithin).
  • Average silhouette method : basée sur la maximisation du paramètre appelé “average silhouette”.
  • Gap statistic method : basée sur la comparaison de la variation totale intra-cluster pour différentes valeurs de k avec leurs valeurs attendues sous une distribution de référence nulle des données.

Elles sont décrites ici.

 

 

 

nombre de cluster par la méthode elbow

 

 

nombre de clusters par la méthode de la silhouette

 

 

nombre de clusters optimal par la méthode du gap statistic

Ces trois méthodes ne conduisent pas forcément au même résultat. Ici, pour deux d’entre elles, le nombre optimal de clusters est 2.

 

Visualisations

Nous pouvons visualiser la relation entre les clusters et chacune des variables utilisées pour les construire avec la méthode des kmeans.

Par exemple, si nous conservons 2 clusters :

 

visualisation des clusters

Il est également possible possible de représenter les clusters sur un plan, c’est-à-dire selon deux dimensions, en utilisant la fonction fviz_cluster(). Le plan est celui d’une ACP qui est réalisée en amont de la représentation.

visualisation des cluster du kmeans

 

👉 Cliquez ici pour accéder à l’article dédié à l’ACP

 

 

Si cet article vous a plu, ou vous a été utile, et si vous le souhaitez, vous pouvez soutenir ce blog en faisant un don sur sa page Tipeee 🙏

👉 Cliquez ici pour soutenir le blog Statistiques et Logiciel R

 

 

Partager l'article
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

13 commentaires

  1. REZAK Salima Répondre

    Bonjour Madame,
    je suis intéressée par tout ce que vous faites pour élaircir les méthodes statistiques en appliquant R.
    Comment interpréter le graphe (en sorte de matrice: les points rouge et points noir) dans le paragraphe visualisation?

    Mes sincères salutations

    • Claire Della Vedova Auteur de l’articleRépondre

      Bonjour,

      les points noirs correspondent à un premier cluster et les points rouges à l’autre cluster.
      Bonne continuation

  2. BONNEFOY Répondre

    Bonjour Claire

    L’illustration montre des clusters qui se chevauchent alors que le contexte indique que les clusters ne se chevauchent pas?

    • Claire Della Vedova Auteur de l’articleRépondre

      Bonjour,

      Ce sont les ellipses qui se chevauchent, pas les clusters en eux-même.

  3. BOUXIN Guy Répondre

    Personnellement, quand je fais des clusters (hiérarchique ou K means), mes données de végétation sont d’abord transformées, par une double transformation : d’abord transformer les données d’abondance (+,r, 1,2,3,4,5 selon la méthode phytosociologique) en tableau disjonctif et puis par une analyse non-symétrique des correspondances (souvent associée à une analyse factorielle multiple). Les coordonnées des variables sur les premiers axes de l’analyse sont utilisées pour calculer les distances euclidiennes. Le nombre utile d’axes est fixé par permutations.

    Guy Bouxin

    • Claire Della Vedova Auteur de l’articleRépondre

      Bonjour Guy,

      je ne connais pas la méthode de transformation phyotosociologique ! Quand je travaillais sur les abondances, j’avais l’habitude de faire une transformation de Hellinger puis une ACP. Est ce que vous auriez un publication d’introduction à me recommander ?

  4. nicolas Répondre

    Bonjour,
    merci de votre blog très pédagogique.
    Concernant l’attribution à chaque observation du cluster qui lui est le plus proche, est-il possible de récupérer l’équation finale permettant de la calculer?
    i.e. les coordonnées du centroïde?
    Mon idée est dans l’hypothèse d’une nouvelle donnée, d’être capable d’estimer à quel cluster elle se rattache sans avoir à recalculer les kmeans.
    Amicalement
    Nicolas

    • Claire Della Vedova Auteur de l’articleRépondre

      Bonsoir Nicolas,

      je pense que vous pouvez avoir accès aux coordonnées des centroides, avec les commandes suivantes :
      km.out=kmeans(mtcars_num_sc,centers=4,nstart =20)
      km.out$centers

      Bonne continuation.

  5. Tao Répondre

    j’aime beaucoup votre blog, très pédagogue sans superflu. Je vais continuer à vous suivre! Merci claire de ce partage !

    • Claire Della Vedova Auteur de l’articleRépondre

      Merci Tao ! Je suis ravie si le blog vous aide, c’est le but !
      Bonne continuation.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *