Clustering k-means — algorithme et fonctionnement

Le clustering k-means est une méthode pour regrouper des données numériques en $k$ clusters. Si vous choisissez $k$ et utilisez la version euclidienne standard, l’algorithme répète une même boucle : assigner chaque point au centre le plus proche, puis déplacer chaque centre vers la moyenne des points qui lui sont assignés.

En termes simples, il essaie de faire en sorte que les points d’un même groupe soient proches les uns des autres et que les points de groupes différents soient plus éloignés. Il est rapide et utile, mais il fonctionne bien seulement lorsque ces « groupes » sont assez compacts et que la distance a du sens.

Ce que le clustering k-means optimise

Dans sa forme euclidienne standard, k-means cherche à rendre les points à l’intérieur de chaque cluster aussi proches que possible du centroïde de ce cluster. Un objectif courant est

$$\sum_{j=1}^{k} \sum_{x_i \in C_j} \|x_i - \mu_j\|^2$$

Ici, $C_j$ est le $j$-ième cluster et $\mu_j$ est son centroïde.

C’est la somme des carrés intra-cluster. Des valeurs plus petites signifient que les points assignés sont plus resserrés autour de leurs centroïdes.

Cet objectif explique les deux parties de l’algorithme :

• Si les centroïdes sont fixés, la meilleure décision est d’assigner chaque point au centroïde le plus proche.
• Si les assignations sont fixées, le meilleur centroïde est la moyenne des points assignés.

C’est pourquoi la règle de mise à jour n’est pas arbitraire. Les « means » de k-means sont littéralement des moyennes arithmétiques.

Comment fonctionne l’algorithme k-means

La boucle habituelle est courte :

1. Choisir $k$ centroïdes initiaux.
2. Assigner chaque point au centroïde le plus proche.
3. Recalculer chaque centroïde comme la moyenne des points qui lui sont assignés.
4. Répéter jusqu’à ce que les assignations ne changent plus ou que l’amélioration devienne très faible.

Ce processus converge généralement rapidement, mais pas forcément vers le meilleur clustering possible. Des centroïdes de départ différents peuvent conduire à des résultats finaux différents, donc l’initialisation compte.

Exemple de clustering k-means étape par étape

Prenons ces points de données unidimensionnels :

$$1,\ 2,\ 3,\ 10,\ 11,\ 12$$

Supposons que nous voulions $k = 2$ clusters et que nous commencions avec des centroïdes en $1$ et $10$. C’est un bon exemple parce que les centroïdes se déplacent réellement après la première mise à jour.

Étape 1 : assigner les points au centroïde le plus proche

Les points $1, 2, 3$ sont plus proches de $1$.

Les points $10, 11, 12$ sont plus proches de $10$.

Les clusters sont donc

$$C_1 = \{1,2,3\}, \qquad C_2 = \{10,11,12\}$$

Étape 2 : mettre à jour les centroïdes

Le nouveau centroïde du premier cluster est

$$\mu_1 = \frac{1+2+3}{3} = 2$$

Le nouveau centroïde du second cluster est

$$\mu_2 = \frac{10+11+12}{3} = 11$$

Les deux centroïdes ont bougé, de $1$ à $2$ et de $10$ à $11$.

Étape 3 : assigner à nouveau

Vérifiez maintenant à nouveau le centroïde le plus proche en utilisant $2$ et $11$.

Les points $1, 2, 3$ appartiennent toujours au premier cluster, et les points $10, 11, 12$ appartiennent toujours au second cluster. Comme les assignations ne changent plus, l’algorithme a convergé.

C’est un exemple clair parce que les données se séparent naturellement en deux groupes compacts. Les jeux de données réels sont plus désordonnés, et c’est là que k-means peut commencer à induire en erreur.

Quand k-means fonctionne bien

K-means fonctionne le mieux lorsque ces conditions sont à peu près vraies :

• Les variables sont numériques.
• La distance euclidienne est une manière raisonnable de mesurer la similarité.
• Les clusters sont assez compacts, pas allongés ni courbés.
• Les variables ont été mises à l’échelle pour qu’aucune ne domine les autres.

Si ces conditions ne sont pas réunies, le résultat peut quand même sembler propre tout en manquant la vraie structure des données.

Erreurs courantes avec k-means

Traiter k-means comme une méthode de clustering universelle

K-means fonctionne mieux lorsque les clusters sont raisonnablement compacts et que la moyenne est un résumé pertinent. Ce n’est pas un bon choix par défaut pour tous les jeux de données.

Ignorer la mise à l’échelle des variables

Si une variable est mesurée sur une échelle beaucoup plus grande qu’une autre, elle peut dominer le calcul des distances. Standardiser ou normaliser les variables est souvent important avant d’exécuter k-means.

Supposer que la réponse est unique

K-means peut converger vers différents minima locaux selon les points de départ. C’est pourquoi on utilise souvent plusieurs exécutions ou des méthodes comme l’initialisation k-means++.

Utiliser des variables non numériques ou mal encodées

Comme les centroïdes sont des moyennes, le k-means standard est conçu pour des variables numériques. Si une variable est catégorielle, prendre une moyenne arithmétique peut ne pas avoir de sens.

L’utiliser sur des clusters fortement non sphériques

Si les vrais groupes sont allongés, courbés ou très inégaux en densité, k-means peut scinder un groupe naturel ou en fusionner deux différents. La méthode préfère des clusters compacts basés sur des centroïdes.

Oublier que les valeurs aberrantes peuvent déplacer les centroïdes

Comme les centroïdes sont des moyennes, des valeurs extrêmes peuvent les déplacer de façon notable. Si les valeurs aberrantes sont importantes dans vos données, vérifiez ce point avant de faire confiance au résultat.

Où le clustering k-means est utilisé

K-means est souvent utilisé pour le regroupement exploratoire, la segmentation de clients ou de comportements, la quantification des couleurs d’image, et comme base de référence rapide en apprentissage non supervisé.

Il est surtout utile lorsque vous avez des variables numériques, que vous voulez un modèle simple et rapide, et que vous vous attendez à des clusters à peu près compacts dans l’espace euclidien.

Un modèle mental simple

Imaginez que vous placez $k$ punaises mobiles sur un nuage de points. Chaque point s’attache à la punaise la plus proche. Ensuite, chaque punaise glisse vers la position moyenne des points qui lui sont attachés. Répétez cela jusqu’à ce que les punaises bougent très peu.

Cette image n’est pas seulement une intuition. C’est presque tout l’algorithme.

Essayez un problème de clustering similaire

Prenez un petit ensemble de points sur une droite, choisissez $k = 2$, et exécutez à la main un cycle complet assignation-mise à jour. Ensuite, changez les centroïdes de départ ou ajoutez une valeur aberrante et observez comment le résultat change. Si vous voulez aller un peu plus loin, essayez votre propre version sur un petit jeu de données et comparez ce qui se passe avant et après la mise à l’échelle des variables.