K-Means (Clustering) : Guide complet — Principes, Exemples et Implémentation Python

Résumé

Le K-Means clustering est l’algorithme de regroupement (clustering) non supervisé le plus utilisé en science des données. Simple, efficace et intuitif, il partitionne un ensemble de données en K groupes distincts appelés clusters, où chaque point appartient au cluster dont le centroïde (centre de gravité) est le plus proche. Depuis sa proposition par Stuart Lloyd en 1957, le K-Means est devenu un pilier incontournable de l’apprentissage non supervisé, avec des applications allant de la segmentation client à la compression d’images, en passant par l’analyse génomique et la détection d’anomalies.

Dans ce guide complet, vous découvrirez les fondements mathématiques du K-Means, son algorithme itératif, la méthode du coude pour choisir le nombre optimal de clusters, et une implémentation pas à pas en Python avec scikit-learn.

Principe mathématique

Minimisation de l’inertie (WCSS)

Le K-Means repose sur un objectif mathématique précis : minimiser l’inertie intra-cluster, aussi appelée WCSS (Within-Cluster Sum of Squares). L’inertie mesure la somme des distances au carré entre chaque point d’un cluster et le centroïde de ce cluster :

où :
– K est le nombre de clusters fixé a priori,
– c_k est le centroïde du cluster k (la moyenne des points qui lui appartiennent),
– x est un point de données appartenant au cluster k,
– ||x \u2212 c_k||\u00b2 est la distance euclidienne au carré.

L’algorithme cherche donc la partition qui rend les clusters les plus compacts possible : les points d’un même cluster doivent être proches les uns des autres, tandis que les points de clusters différents doivent être éloignés.

Algorithme alterné : Affectation \u2192 Mise à jour des centroïdes

Le K-Means fonctionne par alternance itérative entre deux étapes :

1. \u00c9tape d’affectation : Chaque point de données est assigné au cluster dont le centroïde est le plus proche (selon la distance euclidienne). Formellement, le point x_i appartient au cluster k qui minimise la distance au carré entre x_i et le centroïde c_j.
2. \u00c9tape de mise à jour des centroïdes : Pour chaque cluster, on recalcule son centroïde comme la moyenne arithmétique de tous les points qui lui sont assignés. Mathématiquement, chaque centroïde c_k est égal à la somme des points du cluster divisée par leur nombre.

Ces deux étapes sont répétées jusqu’à convergence, c’est-à-dire lorsque les centroïdes ne bougent plus significativement (ou qu’un nombre maximal d’itérations est atteint). À chaque itération, l’inertie WCSS ne peut que diminuer ou rester stable, ce qui garantit la convergence de l’algorithme vers un minimum local.

Initialisation K-Means++

L’une des faiblesses majeures du K-Means classique est sa sensibilité à l’initialisation. Si les centroïdes initiaux sont mal placés (par exemple, deux centroïdes très proches dans le même groupe naturel), l’algorithme peut converger vers un minimum local médiocre.

L’initialisation K-Means++ résout ce problème en plaçant les centroïdes initiaux de manière plus intelligente :

1. Le premier centroïde est choisi aléatoirement parmi les points de données.
2. Pour chaque point suivant, on calcule la distance D(x) au centroïde le plus proche déjà sélectionné.
3. Le prochain centroïde est choisi avec une probabilité proportionnelle à D(x)\u00b2 — autrement dit, les points éloignés des centroïdes existants ont plus de chances d’être sélectionnés.

Cette stratégie garantit des centroïdes initiaux bien répartis dans l’espace, ce qui conduit presque toujours à une meilleure convergence et un meilleur résultat final. C’est d’ailleurs l’initialisation par défaut dans scikit-learn (init=’k-means++’).

Intuition derrière le K-Means

Imaginez que vous dirigez une chaîne de magasins et que vous souhaitez regrouper vos clients par similarité de comportement d’achat. Vous commencez avec des milliers de clients, chacun décrit par des caractéristiques comme la fréquence d’achat, le panier moyen, la catégorie de produits préférée, etc.

Le K-Means fonctionne exactement comme un processus de raffinement progressif :

1. On choisit K centres au hasard — disons 4 centres représentant 4 types de clients hypothétiques.
2. On assigne chaque client au centre le plus proche — le client A ressemble au centre 1, le client B au centre 2, etc.
3. On déplace chaque centre vers la moyenne de ses clients — le centre du groupe \xab\u00a0clients fid\u00e8les\u00a0\xbb se rapproche du profil typique de ce groupe.
4. On répète jusqu’\u00e0 convergence \u2014 \u00e0 chaque tour, les groupes se précisent, les centres se stabilisent.

Au fil des itérations, les clusters deviennent de plus en plus homogènes. C’est un processus fascinant : à partir de centres placés au hasard, on converge naturellement vers des groupes significatifs. Visualisez cela comme des aimants qui attirent les points les plus proches, puis se repositionnent au centre de gravité de leurs points — encore et encore, jusqu’à ce que tout se stabilise.

Cependant, il existe un piège important : le K-Means suppose que les clusters sont sphériques et de taille comparable. Si vos données forment des groupes en forme de croissant, d’anneau ou de densités très différentes, le K-Means produira des résultats peu satisfaisants. Dans ces situations, des algorithmes comme DBSCAN ou le clustering hiérarchique sont plus adaptés.

Implémentation Python avec scikit-learn

Installation des dépendances

pip install scikit-learn matplotlib numpy

Création de données exemple et clustering K-Means

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score

# 1. Générer des données synthétiques
X, y_true = make_blobs(
    n_samples=500,
    centers=4,
    cluster_std=1.0,
    random_state=42
)

# 2. Appliquer le K-Means
kmeans = KMeans(
    n_clusters=4,
    init='k-means++',
    n_init=10,
    max_iter=300,
    random_state=42
)
kmeans.fit(X)
labels = kmeans.labels_
centroids = kmeans.cluster_centers_
inertie = kmeans.inertia_

print(f"Inertie : {inertie:.2f}")
print("Centro\u00efdes :")
print(centroids)

# 3. Visualisation des clusters
plt.figure(figsize=(10, 5))

# Graphique 1 : Donn\u00e9es r\u00e9elles
plt.subplot(1, 2, 1)
plt.scatter(X[:, 0], X[:, 1], c=y_true, cmap='viridis', s=30, edgecolors='k', alpha=0.7)
plt.title('Vrais clusters')
plt.xlabel('Caract\u00e9ristique 1')
plt.ylabel('Caract\u00e9ristique 2')

# Graphique 2 : Clusters K-Means
plt.subplot(1, 2, 2)
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', s=30, edgecolors='k', alpha=0.7)
plt.scatter(centroids[:, 0], centroids[:, 1], c='red', marker='X', s=200, label='Centro\u00efdes')
plt.title('K-Means (K={})'.format(len(centroids)))
plt.xlabel('Caract\u00e9ristique 1')
plt.ylabel('Caract\u00e9ristique 2')
plt.legend()

plt.tight_layout()
plt.savefig('kmeans_resultat.png', dpi=150, bbox_inches='tight')
plt.show()

Méthode du coude (Elbow Method) pour choisir K

Comment déterminer le bon nombre de clusters ? La méthode du coude consiste à tracer l’inertie en fonction de K et à repérer le \xab\u00a0coude\u00a0\xbb \u2014 le point où la diminution de l’inertie commence à ralentir.

# Méthode du coude pour trouver le K optimal
inerties = []
K_range = range(1, 11)

for k in K_range:
    km = KMeans(
        n_clusters=k,
        init='k-means++',
        n_init=10,
        max_iter=300,
        random_state=42
    )
    km.fit(X)
    inerties.append(km.inertia_)

# Visualisation de la méthode du coude
plt.figure(figsize=(8, 5))
plt.plot(K_range, inerties, 'bo-', linewidth=2, markersize=8)
plt.axvline(x=4, color='red', linestyle='--', label='K optimal')
plt.title('M\u00e9thode du coude \u2014 Inertie en fonction de K')
plt.xlabel('Nombre de clusters (K)')
plt.ylabel('Inertie (WCSS)')
plt.legend()
plt.grid(True, alpha=0.3)
plt.savefig('methode_coude.png', dpi=150, bbox_inches='tight')
plt.show()

Le coude se trouve généralement à K=4 dans notre exemple : au-delà, chaque cluster ajouté ne réduit que marginalement l’inertie. C’est le signe que la structure naturelle des données comporte 4 groupes.

Score de silhouette : validation de la qualité du clustering

Le score de silhouette mesure la qualité du clustering sur une échelle de -1 à 1 :
– Proche de 1 : le point est bien assigné à son cluster, loin des autres clusters.
– Proche de 0 : le point est à la frontière entre deux clusters.
– Proche de -1 : le point est probablement mal assigné.

# Calcul du score de silhouette pour différentes valeurs de K
silhouette_scores = []

for k in range(2, 11):
    km = KMeans(
        n_clusters=k,
        init='k-means++',
        n_init=10,
        max_iter=300,
        random_state=42
    )
    labels_k = km.fit_predict(X)
    score = silhouette_score(X, labels_k)
    silhouette_scores.append(score)
    print('K={}: Score de silhouette = {:.4f}'.format(k, score))

# Visualisation des scores de silhouette
plt.figure(figsize=(8, 5))
plt.plot(range(2, 11), silhouette_scores, 'go-', linewidth=2, markersize=8)
k_optimal = np.argmax(silhouette_scores) + 2
plt.axvline(x=k_optimal, color='red', linestyle='--',
            label='K optimal ({})'.format(k_optimal))
plt.title('Score de silhouette en fonction de K')
plt.xlabel('Nombre de clusters (K)')
plt.ylabel('Score de silhouette')
plt.legend()
plt.grid(True, alpha=0.3)
plt.savefig('silhouette_score.png', dpi=150, bbox_inches='tight')
plt.show()

Le score de silhouette complète la méthode du coude : si les deux pointent vers le même K, on peut être raisonnablement confiant dans le choix.

Prédiction sur de nouvelles données

Un avantage du K-Means est sa capacité à classifier de nouvelles observations :

# Nouvelles données à classifier
nouvelles_donnees = np.array([[2.0, 3.0], [-5.0, -4.0], [8.0, 1.0]])

# Assignation aux clusters existants
nouveaux_labels = kmeans.predict(nouvelles_donnees)
print('Assignations :', nouveaux_labels)

# Distance aux centroïdes
distances = kmeans.transform(nouvelles_donnees)
print('Distances aux centroïdes :')
print(distances)

Hyperparamètres essentiels

Le K-Means dans scikit-learn propose plusieurs hyperparamètres qu’il est crucial de comprendre :

# Configuration recommandée pour des résultats robustes
kmeans = KMeans(
    n_clusters=5,
    init='k-means++',
    n_init=20,
    max_iter=500,
    tol=1e-5,
    algorithm='elkan',
    random_state=42
)

Remarque sur la standardisation

Le K-Means utilise la distance euclidienne, ce qui le rend sensible à l’échelle des caractéristiques. Si une variable est mesurée en milliers (ex. : revenu annuel) et une autre en unités (ex. : nombre d’achats), la première dominera injustement le clustering. Standardisez toujours vos données avec StandardScaler avant d’appliquer le K-Means :

from sklearn.preprocessing import StandardScaler
from sklearn.cluster import KMeans

scaler = StandardScaler()
X_standardise = scaler.fit_transform(X_originales)

kmeans = KMeans(n_clusters=4, random_state=42)
kmeans.fit(X_standardise)

Avantages du K-Means

1. Simplicité et interprétabilité \u2014 L’algorithme est facile à comprendre, à implémenter et à expliquer à des non-spécialistes.
2. Efficacité computationnelle \u2014 Complexité O(n \u00d7 K \u00d7 d \u00d7 i), où n est le nombre de points, K le nombre de clusters, d la dimension et i le nombre d’itérations. Très rapide en pratique grâce aux optimisations comme l’algorithme d’Elkan.
3. Scalabilité \u2014 Fonctionne bien sur de grands jeux de données. Des variantes comme Mini-Batch K-Means (MiniBatchKMeans dans scikit-learn) permettent de traiter des millions de points.
4. Généralisation \u2014 Capable de classer de nouvelles données sans ré-entraînement, contrairement à certains algorithmes de clustering.
5. Convergence garantie \u2014 L’inertie diminue à chaque itération, assurant une convergence vers un minimum local.

Limitations du K-Means

1. Nombre de clusters à spécifier \u2014 K doit être connu a priori. Un mauvais choix de K conduit à des résultats non pertinents.
2. Sensibilité aux outliers \u2014 Les valeurs extrêmes tirent les centroïdes et dégradent la qualité du clustering. Un prétraitement (détection et suppression des outliers) est souvent nécessaire.
3. Hypothèse de clusters sphériques \u2014 Le K-Means suppose que les clusters sont convexes et isotropes. Il échoue sur des structures non sphériques (croissants, anneaux, bandes).
4. Minimum local \u2014 La convergence vers un minimum local n’est pas garantie d’être le minimum global, d’où l’importance de n_init et de l’initialisation K-Means++.
5. Sensibilité à l’échelle \u2014 Requiert une standardisation des données, car la distance euclidienne est dominée par les variables à grande variance.
6. \u00c9quipartition forcée \u2014 Le K-Means tend à produire des clusters de taille similaire, même quand la structure naturelle des données présenterait des groupes de tailles très différentes.

4 cas d’usage concrets du K-Means

1. Segmentation client en marketing

Un e-commerce regroupe ses clients en 4 segments basés sur le clustering : les dépensiers fréquents, les acheteurs occasionnels, les chasseurs de promos, et les clients dormants. Chaque segment reçoit une campagne marketing personnalisée \u2014 newsletters ciblées, offres spécifiques, programmes de fidélité adaptés \u2014 ce qui augmente le taux de conversion de 35 %.

# Exemple simplifié de segmentation client
from sklearn.preprocessing import StandardScaler

donnees_clients = np.column_stack([
    frequence_achats,   # nombre d'achats par mois
    panier_moyen,       # montant moyen par commande
    diversite_produits, # nb de catégories différentes
    anciennete          # mois depuis le premier achat
])

scaler = StandardScaler()
X = scaler.fit_transform(donnees_clients)

kmeans = KMeans(n_clusters=4, init='k-means++', n_init=15, random_state=42)
segments = kmeans.fit_predict(X)

2. Compression d’images par réduction de couleurs

Le K-Means peut compresser une image en réduisant le nombre de couleurs uniques. On traite chaque pixel comme un point dans l’espace RVB (3 dimensions), on applique le K-Means avec K=64, puis on remplace chaque pixel par la couleur de son centroïde. Le résultat : une image de 64 couleurs au lieu de 16,7 millions, avec une perte visuelle minime.

3. Analyse de documents et clustering textuel

En traitement automatique du langage (NLP), on vectorise des documents avec TF-IDF ou des embeddings (Word2Vec, BERT), puis on applique le K-Means pour regrouper automatiquement des articles, des avis clients ou des tickets de support en thèmes cohérents. Cela permet d’organiser de grandes collections de textes sans étiquetage manuel.

4. Détection d’anomalies dans des systèmes industriels

Dans l’industrie, le K-Means identifie des anomalies en mesurant la distance de chaque observation au centroïde de son cluster. Les points très éloignés de tout centroïde (au-delà d’un seuil défini) sont des signaux d’alarme : défaillance d’un capteur, comportement anormal d’une machine, ou fraude dans des transactions financières.

# Détection d'anomalies basée sur la distance au centroïde
distances_centroides = kmeans.transform(X_standardise).min(axis=1)
seuil = np.percentile(distances_centroides, 99)  # top 1% les plus éloignés
anomalies = X_standardise[distances_centroides > seuil]
print('Nombre d\'anomalies détectées :', len(anomalies))

Bonnes pratiques pour le K-Means en production

1. Toujours standardiser les données avec StandardScaler.
2. Exécuter K-Means plusieurs fois (n_init >= 10) pour éviter les minima locaux.
3. Combiner méthode du coude et score de silhouette pour choisir K.
4. Vérifier la distribution des tailles de clusters \u2014 un cluster trop petit ou vide est un signal d’alarme.
5. Visualiser les centroïdes \u2014 si les centroïdes n’ont pas de sens métier, le nombre de clusters est probablement mal choisi.
6. Considérer des alternatives quand les données ne sont pas sphériques : DBSCAN, clustering hiérarchique, ou Gaussian Mixture Models.

Tableau comparatif : K-Means vs alternatives

Ressources recommandées

• Livre : Pattern Recognition and Machine Learning de Christopher Bishop (chapitre 9 sur les modèles de mélange).
• Livre : Hands-On Machine Learning with Scikit-Learn, Keras & TensorFlow d’Aurélien Géron (chapitre 9 sur le clustering non supervisé).
• Article fondateur : Lloyd, S. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory.
• Article K-Means++ : Arthur, D. and Vassilvitskii, S. (2007). k-means++: The Advantages of Careful Seeding. SODA.
• Documentation scikit-learn : sklearn.cluster.KMeans.
• Documentation scikit-learn : Clustering \u2014 User Guide.

Voir aussi

• Maîtrisez le Calcul de la Somme des Diviseurs avec Python : Guide Complet et Astuces Efficaces
• Créer un Jeu de Glissement en Python : Guide Complet et Astuces pour les Développeurs