K-means : comprendre la méthode de partitionnement de données

En machine learning, la méthode K-means ou K-moyennes sert au clustering de données, soit au partitionnement de data en fonction de leur ressemblance, en recourant à une technique d'apprentissage automatique non supervisée.

K-means, c'est quoi ?

Le partitionnement en K-means, ou en "K-moyennes", est une méthode de partitionnement de données faisant appel à un algorithme non supervisé de clustering non hiérarchique. Au sein d’un jeu de données chiffrés réparties sur un graphique en abscisse et en ordonnée, il permet de regrouper des individus ou objets ayant les caractéristiques les plus proches au sein de K groupes.

Ces groupes (clusters) sont constitués par itération successive de leur centre de gravité sur le graphique. La méthode ? On détermine d'abord un nombre de groupes à identifier. On appelle ce nombre K. On positionne ensuite aléatoirement leur centre de gravité (ou centroïde) sur le plan. Puis on associe chaque point aux centres de gravité dont il est le plus proche. On calcule ensuite le véritable centre de gravité de chaque groupe ainsi créé. Puis on le recalcule pour l'ensemble des points du nuage. Et ainsi de suite, jusqu'à ce que les centres de gravité soient parfaitement équilibrés. C'est ce que l'on appelle la convergence de l'algorithme.

Que signifie le K-means clustering ?

Le clustering désigne la particularité de la méthode d’apprentissage de K-means, dite "non supervisée" : l'algorithme employé n’a pas pour tâche de prédire une certaine valeur à partir d’éléments annotés ou de données étiquetées, comme c’est le cas pour l’apprentissage supervisé. Non, il consiste à regrouper les données en fonction de leur similarité. 

Quand utiliser K-means ?

K-means peut s'appliquer dans de nombreux domaines pour identifier des clusters au sein de données similaires. Il permet par exemple de regrouper des clients en fonction de leur degré de rentabilité en vue d'analyser leur profil. Dans la détection des fraudes, K-means peut aussi contribuer à identifier des actions potentiellement malhonnêtes en fonction de leur proximité avec des groupes de profil renvoyant à un modèle frauduleux.

K-means correspond à quel type d’algorithme de machine learning ?

K-means fait appel à un algorithme non supervisé, qui apprend sans superviseur. Cet algorithme permet de découvrir des motifs cachés dans un ensemble de données. K-means est parfois surnommé algorithme de Lloyd-Forgy, car il a été inventé séparément par Stuart Lloyd et Edward W. Forgy, à quelques années d’intervalle.

Quel est l'apport de la méthode Elbow dans K-means ?

Pour un même jeu de données, il y a de nombreux partitionnements possibles. Il faut donc choisir le nombre de clusters K le plus pertinent pour mettre en lumière les patterns intéressants. Hélas, il n’existe pas de procédé automatique pour cela.

Parmi les méthodes pour déterminer le nombre de clusters, il existe la méthode Elbow. Elle consiste à calculer la variance des différents volumes de clusters envisagés, puis à placer les variances obtenues sur un graphique. On obtient alors une visualisation en forme de coude (elbow en anglais), sur laquelle le nombre optimal de clusters est le point représentant la pointe du coude, c'est-à-dire celui correspondant au nombre de clusters à partir duquel la variance ne baisse plus significativement.

Quelle différence entre K-means et KNN (K-nearest neighbors) ?

Il existe des différences majeures entre la méthode K-moyennes et la méthode des k-voisins les plus proches (KNN ou K-nearest neighbors en anglais). D’une part, KNN fait appel à un mode d’apprentissage supervisé : les données doivent être étiquetées en amont. D’autre part, la méthode KNN est surtout utilisée pour les problèmes de classification et de régression, alors que K-means sert exclusivement au partitionnement de données.