En clair
K-means est un algorithme de clustering, c'est-à-dire de regroupement automatique. Il répartit un ensemble de données en K groupes (les clusters). Il cherche des groupes où les points sont proches les uns des autres et bien séparés des autres groupes. Il mesure en général la proximité avec la distance euclidienne, la distance « à vol d'oiseau ».
L'algorithme avance par étapes qu'il répète.
- On choisit K points de départ qui servent de centres de groupes. On les appelle des centroïdes.
- Chaque point de données est rattaché au centroïde le plus proche.
- Chaque centroïde est recalculé comme la moyenne des points qui lui sont rattachés.
- On répète les étapes 2 et 3 jusqu'à ce que les groupes ne changent plus. On dit alors que l'algorithme a convergé.
Pourquoi c'est important
K-means est l'un des algorithmes de clustering les plus utilisés. Il est simple, rapide et tient bien la charge sur de grands volumes de données. Il fait apparaître des structures cachées sans étiquettes préalables. C'est pour cela qu'on le retrouve partout en apprentissage non supervisé : segmentation de clients, regroupement de documents, analyse d'images, détection d'anomalies.
Dans la pratique
Pour utiliser K-means il faut choisir le nombre de groupes K. C'est un choix décisif. Un K trop petit fusionne des groupes distincts et un K trop grand les découpe artificiellement. Le coefficient de silhouette aide à comparer la qualité du regroupement pour différentes valeurs de K.
L'algorithme dépend aussi des centroïdes de départ. Des variantes comme K-means++ les choisissent mieux et rendent le résultat plus stable. Enfin K-means suppose des groupes à peu près ronds et de tailles proches. Ce n'est pas toujours le cas dans la réalité.
À ne pas confondre avec
- La classification attribue des étiquettes connues à l'avance (c'est de l'apprentissage supervisé). K-means découvre des groupes sans étiquettes.
- Le clustering hiérarchique construit un arbre de groupes emboîtés. K-means produit une seule partition en K groupes.
- Les techniques de réduction de dimension comme l'ACP réduisent le nombre de variables. Elles ne regroupent pas les données.