Clustering : K-Means & DBSCAN
“Trouver des groupes cachés dans des données non étiquetées — aucun enseignant requis”
Groupement non supervisé — K-Means (algorithme de Lloyd, inertie, sélection K), DBSCAN (points core/border/noise, voisinage ε, formes arbitraires) et clustering hiérarchique.
Prérequis
Concepts Couverts
∑Formules Clés
Objectif K-Means
Minimiser la somme totale des distances au carré intra-cluster aux centroïdes
Point Noyau DBSCAN
Un point est noyau s'il a ≥ MinPts voisins dans le rayon ε
Score de Silhouette
a = distance intra-cluster, b = distance au cluster le plus proche — plage [-1, 1], 1 = parfait
Inertie
Somme des distances au carré de chaque point à son centroïde le plus proche — l'objectif K-Means
▶Simulation Interactive
Pourquoi Regrouper des Données Non Étiquetées ?
La plupart des données du monde réel arrivent sans étiquettes — transactions clients, séquences génomiques, articles de presse, lectures de capteurs. Le clustering vous permet de découvrir une structure naturelle qu'aucun humain n'a annotée. Spotify segmente les auditeurs pour construire Discover Weekly. Les compagnies d'assurance regroupent les sinistres pour détecter les fraudes organisées. Les biologistes groupent les profils d'expression génique pour trouver des sous-types de maladies. L'objectif est toujours le même : trouver des groupes où les membres sont plus similaires entre eux qu'aux membres des autres groupes.
K-Means a été publié en 1967 et reste l'un des algorithmes les plus utilisés dans les systèmes ML en production. Sa simplicité est sa force.
K-Means : La Négociation Itérative
Imaginez poser K drapeaux aléatoirement sur une carte. Chaque personne marche vers son drapeau le plus proche. Chaque drapeau se déplace ensuite vers la position moyenne de toutes les personnes qui l'ont rejoint. On répète jusqu'à ce que personne ne change de drapeau. Cet algorithme de Lloyd converge vers un minimum local — il n'est pas garanti de trouver l'optimum global, c'est pourquoi l'initialisation K-Means++ (écarter les centroïdes initiaux) améliore dramatiquement les résultats en pratique.
K-Means converge toujours mais peut converger vers un mauvais minimum local. Toujours exécuter avec plusieurs initialisations aléatoires (n_init=10 dans scikit-learn) et garder le meilleur.
L'Objectif de K-Means
K-Means minimise la somme des distances euclidiennes au carré de chaque point à son centroïde assigné. L'étape E assigne chaque point à son centroïde le plus proche ; l'étape M déplace chaque centroïde vers la moyenne de ses points assignés. Chaque étape diminue monotoniquement l'objectif, garantissant la convergence.
Choisir K : La Méthode du Coude & Silhouette
K est un hyperparamètre — vous devez le choisir. La méthode du coude trace l'inertie vs K : l'inertie décroît toujours, mais le taux de décroissance fait un coude au « bon » K. Plus rigoureusement, le score de silhouette mesure à quel point chaque point correspond à son propre cluster vs le cluster le plus proche suivant. s=1 = séparation parfaite, s=0 = clusters qui se chevauchent, s<0 = le point est dans le mauvais cluster. La silhouette moyenne sur tous les points donne une métrique scalaire de qualité.
Essayer K = 2 à 10, tracer l'inertie — chercher le 'coude'
Calculer le score de silhouette pour chaque K — le pic = meilleur K
Utiliser la statistique d'écart (comparer aux données aléatoires) pour sélectionner K rigoureusement
La connaissance du domaine prime souvent : si vous savez qu'il y a 5 segments clients, utiliser K=5
K-Means vs DBSCAN vs Hiérarchique
K-Means suppose des clusters sphériques de taille égale et nécessite K à l'avance. Il échoue sur les données en forme de croissant ou à densité variable. DBSCAN trouve des clusters de forme arbitraire et identifie automatiquement les anomalies — points qui ne font partie d'aucun cluster. Il ne nécessite que ε (rayon de voisinage) et MinPts (points minimum pour former un noyau). Le clustering hiérarchique construit un dendrogramme qu'on coupe à n'importe quel niveau pour obtenir K clusters, donnant la structure complète en une seule passe.
Utiliser DBSCAN quand vous attendez du bruit/des anomalies ou des clusters non sphériques. K-Means quand les clusters sont grossièrement sphériques et K connu. Hiérarchique pour explorer plusieurs granularités simultanément.
DBSCAN Étape par Étape
Pour chaque point p non visité, trouver tous les points dans le rayon ε (ε-voisinage)
Si |N_ε(p)| ≥ MinPts → p est un point noyau ; démarrer un nouveau cluster
Expansion du cluster : ajouter tous les points accessibles en densité (voisins de points noyaux)
Si |N_ε(p)| < MinPts et p est accessible depuis un noyau → p est un point de bordure
Si p n'est accessible depuis aucun noyau → p est du bruit (anomalie, étiqueté -1)
Répéter jusqu'à ce que tous les points soient visités — O(n log n) avec index spatial
Implémentation scikit-learn
from sklearn.cluster import KMeans, DBSCAN, AgglomerativeClustering from sklearn.metrics import silhouette_score from sklearn.preprocessing import StandardScaler from sklearn.datasets import make_blobs import numpy as np class="tok-comment"># ── Données dclass="tok-str">'exemple ────────────────────────────────────────────────── X, _ = make_blobs(n_samples=class="tok-num">300, centers=class="tok-num">4, cluster_std=class="tok-num">0.8, random_state=class="tok-num">42) class="tok-comment"># ── K-Means avec sélection de K via silhouette ──────────────────── X_normalise = StandardScaler().fit_transform(X) meilleur_k, meilleur_score = class="tok-num">2, -class="tok-num">1 for k in range(class="tok-num">2, class="tok-num">11): km = KMeans(n_clusters=k, init='k-means++class="tok-str">', n_init=class="tok-num">10, random_state=class="tok-num">42) etiquettes = km.fit_predict(X_normalise) score = silhouette_score(X_normalise, etiquettes) if score > meilleur_score: meilleur_k, meilleur_score = k, score km_final = KMeans(n_clusters=meilleur_k, init='k-means++class="tok-str">', n_init=class="tok-num">10, random_state=class="tok-num">42) etiq_km = km_final.fit_predict(X_normalise) print(f"K={meilleur_k}, silhouette={meilleur_score:.3f}, inertie={km_final.inertia_:.1f}") class="tok-comment"># ── DBSCAN — détecte automatiquement clusters et anomalies ──────── db = DBSCAN(eps=class="tok-num">0.5, min_samples=class="tok-num">5) etiq_db = db.fit_predict(X_normalise) n_clusters = len(set(etiq_db)) - (class="tok-num">1 if -class="tok-num">1 in etiq_db else class="tok-num">0) n_bruit = list(etiq_db).count(-class="tok-num">1) print(f"DBSCAN: {n_clusters} clusters, {n_bruit} points de bruit") class="tok-comment"># ── Agglomératif — pas de K nécessaire à l'avance ───────────────── from scipy.cluster.hierarchy import dendrogram, linkage Z = linkage(X_normalise, method=class="tok-str">'ward') class="tok-comment"># Couper à K=class="tok-num">3 agg = AgglomerativeClustering(n_clusters=class="tok-num">3, linkage=class="tok-str">'ward') etiq_agg = agg.fit_predict(X_normalise)
Pièges Courants du Regroupement
Le clustering sans mise à l'échelle est l'erreur n°1 : les caractéristiques à grande échelle dominent la métrique de distance. Toujours mettre à l'échelle avant de regrouper. Deuxième piège : traiter les étiquettes de cluster comme vérité absolue — les clusters sont des hypothèses, pas des faits. Valider avec des experts du domaine et des métriques externes (si des étiquettes existent, utiliser l'Adjusted Rand Index). Troisième : supposer que les clusters sont significatifs — toujours vérifier en examinant les profils des clusters.
Les étiquettes de cluster sont des entiers arbitraires qui changent entre les exécutions. Ne jamais coder en dur 'cluster 0 = clients haute valeur' — toujours caractériser les clusters par leurs distributions de caractéristiques.
?Vérification des Connaissances
La progression est sauvegardée dans votre navigateur — aucun compte requis.
Besoin d'un ingénieur IA ou data scientist ?
Je conçois des modèles ML sur mesure, des agents IA, de la vision par ordinateur et de l'automatisation — de l'idée à la production.