K-Means Clustering

Le clustering k-means est un algorithme d’apprentissage non supervisé qui répartit les données en k groupes, chacun représenté par son centroïde, c’est-à-dire la moyenne des points qui lui sont attribués. Il cherche la partition dont la somme des distances au carré au sein des groupes est la plus faible, une quantité appelée inertie, de sorte que les points d’un groupe restent proches de leur centroïde. La procédure standard est l’algorithme de Lloyd, que Stuart Lloyd a mis au point aux Bell Labs en 1957 pour quantifier des signaux ; le nom « k-means » vient d’un article de James MacQueen publié en 1967. Simple, rapide et capable de traiter des millions de points, k-means est un outil de référence pour l’exploration de données, la compression et l’étude de la structure des données non étiquetées.

Fonctionnement de l'algorithme#

Après avoir choisi les centroïdes initiaux, l’algorithme de Lloyd alterne entre une étape d’affectation et une étape de mise à jour jusqu’à ce que les groupes cessent de changer :

1. Initialisation : choisis k centroïdes initiaux. La méthode par défaut de Scikit-learn, k-means++, sélectionne le premier centroïde au hasard, puis choisit chacun des suivants avec une probabilité proportionnelle au carré de sa distance par rapport au centroïde déjà choisi le plus proche, afin d’espacer les points de départ.
2. Affectation : attribue chaque point au centroïde le plus proche, généralement selon la distance euclidienne.
3. Mise à jour : déplace chaque centroïde vers la moyenne des points qui lui sont désormais attribués.
4. Répétition : reprends l’étape d’affectation jusqu’à ce qu’aucun point ne change de groupe ou que les centroïdes se déplacent de moins qu’une tolérance donnée.

Aucune des deux étapes ne peut augmenter l’inertie ; la boucle converge donc toujours, mais uniquement vers un minimum local qui dépend des centroïdes de départ. Trouver l’optimum global est NP-hard ; les implémentations effectuent donc plusieurs initialisations et conservent celle qui donne l’inertie la plus faible. Dans KMeans de scikit-learn, la valeur par défaut de n_init="auto" lance l’algorithme une fois avec une initialisation k-means++ et dix fois avec une initialisation aléatoire.

Choisir le nombre de groupes#

Il faut fournir k à k-means. L’inertie diminue toujours lorsque k augmente, car davantage de centroïdes se rapprochent des points. La méthode du coude représente donc l’inertie en fonction de k et cherche le point où la baisse s’atténue. Pour chaque point, le score de silhouette compare la distance moyenne à son propre groupe à la distance moyenne au groupe voisin le plus proche. Il varie de -1 à 1 ; les valeurs élevées correspondent à des groupes compacts et bien séparés. Cet exemple calcule le score pour k allant de 2 à 6 sur des données réparties autour de quatre centres :

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score

# 600 unlabeled points drawn around 4 hidden centers
X, _ = make_blobs(n_samples=600, centers=4, cluster_std=1.0, random_state=7)

# Fit k-means for several k and score each partition
for k in range(2, 7):
    kmeans = KMeans(n_clusters=k, n_init="auto", random_state=0)
    labels = kmeans.fit_predict(X)
    print(f"k={k}  inertia={kmeans.inertia_:8.0f}  silhouette={silhouette_score(X, labels):.3f}")

L’inertie passe de 18 363 pour k=2 à 5 241 pour k=3, puis à 1 127 pour k=4 ; elle ne baisse ensuite qu’à 1 039 pour k=5 et à 922 pour k=6. Le coude se situe donc à k=4. Le score de silhouette confirme ce résultat : il atteint un maximum de 0.811 pour k=4, puis tombe à 0.687 pour k=5, retrouvant ainsi les quatre centres utilisés pour générer les données.

Hypothèses et variantes#

K-means fonctionne mieux lorsque les groupes sont approximativement sphériques, de taille similaire et séparés dans l’espace euclidien. Les caractéristiques à plus grande échelle dominent la distance ; les données sont donc généralement standardisées au préalable. Chaque point rejoint un groupe, et quelques valeurs aberrantes extrêmes peuvent éloigner un centroïde de son groupe. Plusieurs variantes assouplissent ces limites :

• K-means par mini-lots : met à jour les centroïdes à partir de petits lots aléatoires, sacrifiant un peu de précision au profit d’un entraînement beaucoup plus rapide sur de grands jeux de données.
• K-medoids : utilise des points réels des données comme centres de groupe, ce qui le rend plus robuste aux valeurs aberrantes et compatible avec toute mesure de distance.
• C-moyennes floues : attribue à chaque point un degré d’appartenance à chaque groupe, selon le principe de la logique floue, plutôt qu’une seule affectation stricte.
• Modèles de mélange gaussien : ajustent une distribution de probabilité par groupe, ce qui permet de représenter des groupes elliptiques de tailles différentes et renvoie des affectations probabilistes souples.

Applications en IA et en vision par ordinateur#

• Quantification des couleurs : Le regroupement des couleurs des pixels d’une image et le remplacement de chaque pixel par le centroïde de son groupe réduisent une photo comptant des milliers de couleurs à une palette de k couleurs. Cela compresse l’image et fournit aussi une forme rapide et approximative de segmentation d’image.
• Dictionnaires de codes et quantification vectorielle : Les centroïdes forment un dictionnaire de codes, et chaque vecteur est stocké sous forme d’indice de son centroïde le plus proche. La recherche d’images classique par sac de mots visuels construisait ses vocabulaires de cette façon à partir de descripteurs d’images locaux.
• Conception des boîtes d’ancrage : YOLOv2 exécutait k-means sur les largeurs et les hauteurs des boîtes d’entraînement, en utilisant 1 moins l’IoU comme distance, afin de choisir ses boîtes d’ancrage.
• Mise en palette des poids : L’exportation de YOLO26 vers Core ML avec quantize=8 regroupe par k-means les valeurs de chaque grand tenseur de poids en 256 centroïdes. Le modèle exporté stocke ainsi un indice de 8 bits par poids, ainsi qu’une petite table de correspondance.
• Segmentation de la clientèle : les commerçants regroupent les clients selon la fréquence d’achat, le montant du panier et la récence afin d’adapter les offres à chaque segment.

K-means et algorithmes apparentés#

• K plus proches voisins (KNN) : Le « k » commun prête à confusion. KNN est un algorithme supervisé qui attribue une étiquette à un nouveau point en fonction de ses k exemples étiquetés les plus proches, tandis que k-means est non supervisé et que k correspond au nombre de groupes qu’il crée.
• DBSCAN : Regroupe les points selon leur densité, détermine lui-même le nombre de groupes, suit des groupes de toutes formes et étiquette les points clairsemés comme du bruit au lieu de les forcer à rejoindre un groupe.
• Regroupement hiérarchique : Construit un arbre de groupes imbriqués en fusionnant de façon répétée les groupes les plus proches. On peut ainsi choisir k après coup en coupant l’arbre à n’importe quel niveau, au prix d’un coût qui augmente au moins de façon quadratique avec le nombre de points.