Accueil › Glossaire › K-Means

K-Means (Clustering par K-Moyennes)

K-Means est un algorithme de clustering par partitionnement qui divise un dataset en K groupes homogènes en assignant chaque point au centroïde (centre de cluster) le plus proche, puis en recalculant les centroïdes itérativement jusqu’à convergence.

C’est l’algorithme de clustering le plus utilisé en machine learning, principalement grâce à sa simplicité, sa rapidité et son efficacité sur de grands datasets. L’algorithme est souvent attribué à Stuart Lloyd (Bell Labs, 1957, publié en 1982) et est parfois appelé algorithme de Lloyd. Malgré ses limites (nécessité de fixer K à l’avance, hypothèse de clusters sphériques), il reste le point de départ standard pour tout problème de clustering.

L’algorithme K-Means pas à pas

Étape 1 : Initialisation des centroïdes

L’algorithme place K centroïdes initiaux dans l’espace des features. La méthode d’initialisation la plus efficace est K-Means++ (défaut dans scikit-learn) : le premier centroïde est choisi aléatoirement, puis chaque centroïde suivant est choisi avec une probabilité proportionnelle au carré de sa distance au centroïde le plus proche. Cette stratégie garantit que les centroïdes initiaux sont bien dispersés dans l’espace, ce qui accélère la convergence et réduit le risque de tomber dans un mauvais minimum local.

Étape 2 : Assignation

Chaque point du dataset est assigné au centroïde le plus proche (en distance euclidienne par défaut). Cette étape crée K clusters.

Étape 3 : Mise à jour des centroïdes

Chaque centroïde est recalculé comme la moyenne (le « centre de gravité ») de tous les points assignés à son cluster. D’où le nom « K-Moyennes ».

Étape 4 : Itération

Les étapes 2 et 3 sont répétées jusqu’à ce que les centroïdes ne bougent plus (ou bougent moins qu’un seuil de tolérance), ou que le nombre maximum d’itérations soit atteint. La convergence est garantie, mais vers un minimum local, pas nécessairement le minimum global.

L’inertie : la fonction objectif

K-Means minimise l’inertie (aussi appelée WCSS, Within-Cluster Sum of Squares) : la somme des distances au carré entre chaque point et le centroïde de son cluster. Plus l’inertie est basse, plus les clusters sont compacts. Formellement : Inertie = Σᵢ Σₓ∈Cᵢ ||x - μᵢ||² où μᵢ est le centroïde du cluster Cᵢ.

K-Means en Python avec scikit-learn

Usage de base

from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
import numpy as np

# Standardiser les données (obligatoire pour K-Means)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# K-Means avec 4 clusters
kmeans = KMeans(n_clusters=4, init='k-means++',
                n_init=10, max_iter=300, random_state=42)
labels = kmeans.fit_predict(X_scaled)

# Résultats
print(f"Inertie : {kmeans.inertia_:.2f}")
print(f"Centroïdes : {kmeans.cluster_centers_.shape}")
print(f"Itérations : {kmeans.n_iter_}")
print(f"Points par cluster : {np.bincount(labels)}")

Prédiction sur de nouvelles données

Contrairement à beaucoup d’algorithmes de clustering, K-Means supporte .predict() pour assigner de nouvelles observations aux clusters existants :

# Assigner de nouveaux points au cluster le plus proche
new_labels = kmeans.predict(X_new_scaled)

Comment choisir K : le problème central

Le principal défi de K-Means est de déterminer le bon nombre de clusters. Trois méthodes complémentaires existent.

Méthode du coude (Elbow Method)

On trace l’inertie en fonction de K. La courbe décroît toujours (plus de clusters = inertie plus basse), mais le taux de décroissance diminue. Le « coude » est le point après lequel ajouter un cluster n’apporte plus d’amélioration significative.

import matplotlib.pyplot as plt

inertias = []
K_range = range(2, 11)

for k in K_range:
    km = KMeans(n_clusters=k, n_init=10, random_state=42)
    km.fit(X_scaled)
    inertias.append(km.inertia_)

plt.figure(figsize=(8, 5))
plt.plot(K_range, inertias, 'o-', color='#7c3aed', lw=2)
plt.xlabel('Nombre de clusters (K)')
plt.ylabel('Inertie (WCSS)')
plt.title('Méthode du coude')
plt.grid(alpha=0.3)
plt.tight_layout()
plt.show()

Score de silhouette

Le silhouette score mesure la qualité de chaque assignation en comparant la cohésion intra-cluster à la séparation inter-cluster. Il varie de -1 (mauvaise assignation) à +1 (parfait). Le K qui maximise le score moyen est un bon candidat.

from sklearn.metrics import silhouette_score

scores = []
for k in range(2, 11):
    km = KMeans(n_clusters=k, n_init=10, random_state=42)
    labels = km.fit_predict(X_scaled)
    score = silhouette_score(X_scaled, labels)
    scores.append(score)
    print(f"K={k} : Silhouette = {score:.4f}")

plt.figure(figsize=(8, 5))
plt.plot(range(2, 11), scores, 'o-', color='#7c3aed', lw=2)
plt.xlabel('Nombre de clusters (K)')
plt.ylabel('Score de silhouette')
plt.title('Silhouette Score vs K')
plt.grid(alpha=0.3)
plt.tight_layout()
plt.show()

Connaissance métier

Les méthodes statistiques donnent des pistes, mais le nombre de clusters doit avant tout avoir un sens métier. En segmentation client, le marketing peut imposer 4-5 segments actionnables. En quantification de couleurs, le nombre de clusters correspond au nombre de couleurs souhaitées. Aucune métrique ne remplace la compréhension du domaine.

Variantes de K-Means

Mini-Batch K-Means

Utilise des sous-échantillons aléatoires (mini-batches) à chaque itération au lieu du dataset complet. Résultat : 3-10x plus rapide que K-Means standard, avec une très légère perte de qualité. Indispensable pour les grands datasets (> 100 000 points).

from sklearn.cluster import MiniBatchKMeans

mbk = MiniBatchKMeans(n_clusters=5, batch_size=256,
                       n_init=10, random_state=42)
labels = mbk.fit_predict(X_scaled)

K-Medoids (PAM)

Utilise des points réels du dataset comme centres (medoids) au lieu de moyennes calculées. Plus robuste aux outliers car les medoids ne sont pas influencés par les valeurs extrêmes. Plus lent que K-Means (O(n²)) mais préférable quand les données contiennent des outliers ou quand la distance euclidienne n’est pas appropriée.

K-Means++

Ce n’est pas un algorithme séparé mais une méthode d’initialisation intelligente (Arthur & Vassilvitskii, 2007). Elle garantit une initialisation O(log K)-compétitive par rapport au K-Means optimal. C’est le défaut dans scikit-learn (init='k-means++') et il n’y a aucune raison de ne pas l’utiliser.

Applications classiques de K-Means

Segmentation client

L’application la plus classique. On regroupe les clients selon leur comportement d’achat (modèle RFM : Récence, Fréquence, Montant) pour créer des segments marketing ciblés. K-Means est rapide et facile à interpréter (le centroïde de chaque cluster décrit le « client type » du segment).

Quantification de couleurs

Réduire le nombre de couleurs d’une image : chaque pixel est un point 3D (R, G, B), et K-Means regroupe les couleurs similaires. En remplaçant chaque pixel par le centroïde de son cluster, on compresse l’image en K couleurs.

Prétraitement et feature engineering

L’ID de cluster peut servir de feature supplémentaire pour un modèle supervisé. La distance au centroïde le plus proche est aussi une feature utile, notamment pour la détection d’anomalies (points très éloignés de leur centroïde).

Initialisation d’autres algorithmes

K-Means sert souvent d’initialisation rapide pour des algorithmes plus complexes comme les Gaussian Mixture Models (GMM), accélérant leur convergence.

Limites et quand ne PAS utiliser K-Means

Obligation de fixer K à l’avance

K-Means nécessite de spécifier le nombre de clusters avant l’exécution. Si vous n’avez aucune idée du nombre de groupes naturels, c’est un handicap. Alternative : DBSCAN ou HDBSCAN déterminent automatiquement le nombre de clusters.

Hypothèse de clusters sphériques

K-Means suppose que les clusters sont convexes, de tailles et de densités similaires. Il échoue sur des clusters en forme de croissant, d’anneau, ou de densité variable. Alternative : DBSCAN gère les formes arbitraires.

Sensibilité à l’échelle

K-Means utilise la distance euclidienne, qui est sensible à l’échelle. Une feature en milliers dominera une feature en unités. Standardisez toujours les données avant K-Means.

Sensibilité aux outliers

Les outliers tirent les centroïdes vers eux, déformant les clusters. Un seul point aberrant peut significativement déplacer le centroïde d’un cluster. Solutions : détecter et supprimer les outliers en amont, ou utiliser K-Medoids.

Convergence vers un minimum local

K-Means trouve un minimum local, pas global. Le résultat dépend de l’initialisation. Scikit-learn atténue ce problème avec n_init=10 (10 exécutions, meilleur résultat retenu), mais le risque persiste sur des données complexes.

Bonnes pratiques

Standardisez toujours les données avant K-Means. Sans cela, les résultats seront dominés par les features à grande échelle.

Utilisez K-Means++ comme initialisation (c’est le défaut, ne le changez pas).

Gardez n_init ≥ 10 pour réduire l’impact de l’initialisation aléatoire.

Combinez le coude et le silhouette score pour choisir K. Utilisez le coude pour restreindre la plage, puis le silhouette pour affiner.

En haute dimension, appliquez une PCA avant K-Means pour réduire le bruit et accélérer le calcul.

Vérifiez les tailles des clusters. Un cluster avec très peu de points (< 1 % du dataset) peut être du bruit plutôt qu'un vrai groupe.

Interprétez les centroïdes. Chaque centroïde représente le « profil moyen » du cluster. Analysez ses valeurs pour donner un sens métier aux clusters.

Verdict

K-Means est le premier algorithme de clustering à maîtriser et à essayer. Sa simplicité et sa rapidité en font un outil indispensable pour l’exploration de données et la segmentation. Ses limites sont connues et bien comprises : clusters sphériques, K à fixer, sensibilité aux outliers.

En pratique, commencez par K-Means pour obtenir une première vue des données. Si les clusters ont des formes irrégulières ou si vous ne savez pas combien il y en a, passez à DBSCAN ou HDBSCAN. Pour les grands datasets en haute dimension, le pipeline PCA (50 composantes) → K-Means est un classique éprouvé. Et n’oubliez pas : le meilleur nombre de clusters est celui qui a du sens pour votre métier, pas celui qui maximise une métrique.