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 d'un data set, soit au partitionnement de données 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, traduit 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, il permet de regrouper les données similaires dans K groupes, K étant ici un nombre entier. Ces groupes (clusters) sont constitués de façon à minimiser une certaine fonction, sous le principe de l’exclusivité d’appartenance : il est impossible pour une même donnée de se retrouver dans deux clusters différents.

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" : les algorithmes employés n’ont 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 convient ici de déterminer des patterns dans les données, et de les rassembler selon leur similarité. Le clustering est hiérarchique ou non hiérarchique (partitionnement de données).

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

K-means fait appel à un algorithme non supervisé, qui apprend sans superviseur. La qualité de cet algorithme est déterminée par sa capacité à découvrir les motifs cachés dans un ensemble de données. En machine learning, ce type d’algorithme permet d’exécuter des tâches plus complexes qu’avec la méthode supervisée, bien qu’il soit davantage imprévisible. 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". Celle-ci consiste à lancer K-means avec différentes valeurs K, à calculer la variance entre les clusters, puis à placer les différents nombres de clusters K en fonction de la variance sur un graphique. On obtient alors une visualisation en forme de coude (elbow en anglais), où le nombre optimal de clusters est le point représentant la pointe du coude.

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 régression, alors que K-means sert exclusivement au partitionnement de données.

Dictionnaire de l'intelligence artificielle