Le clustering : k-means, DBSCAN, hiérarchique
Prérequis : Encoder et mettre à l'échelle · Choisir un modèle
- expliquer l'algorithme des k-moyennes et sa sensibilité à l'initialisation ;
- choisir le nombre de groupes avec la méthode du coude et la silhouette ;
- expliquer le regroupement par densité (DBSCAN) et la classification hiérarchique ;
- évaluer un clustering, avec ou sans vraies classes.
Apprendre sans étiquettes
Section intitulée « Apprendre sans étiquettes »Jusqu’ici, chaque exemple venait avec sa réponse : un prix, une classe. En apprentissage non supervisé, il n’y a pas de réponse. On cherche une structure cachée dans les données. Le clustering (partitionnement, regroupement) forme des groupes d’exemples qui se ressemblent :
- segmenter des clients selon leurs habitudes d’achat ;
- regrouper des articles de presse par sujet ;
- découvrir des sous-types d’une maladie à partir de mesures biologiques ;
- réduire une image à quelques couleurs.
Sans réponse à prédire, il n’y a plus d’erreur de test évidente. Mesurer un clustering demande donc une réflexion propre, en fin de chapitre.
Les k-moyennes (k-means)
Section intitulée « Les k-moyennes (k-means) »L’algorithme le plus utilisé tient en deux étapes, répétées jusqu’à ce que plus rien ne bouge :
- affecter chaque point au centre le plus proche ;
- déplacer chaque centre au milieu (la moyenne) de ses points.
On choisit à l’avance le nombre de groupes , et on place les centres de départ au hasard.
Cliquez plusieurs fois sur Étape, puis sur 🎲 Autres centres de départ : selon le départ, l’algorithme converge parfois vers une mauvaise solution (deux centres dans un même nuage, un centre entre deux nuages). k-means ne trouve qu’un minimum local. Les remèdes :
- l’initialisation k-means++ : les centres de départ sont tirés loin les uns des autres ;
- plusieurs départs (
n_init) : on garde la solution de plus faible inertie.
Combien de groupes ?
Section intitulée « Combien de groupes ? »L’inertie est la somme des carrés des distances de chaque point à son centre. Elle baisse toujours quand augmente (avec , elle vaut 0) : la minimiser ne suffit pas, comme l’erreur d’entraînement en supervisé. Deux outils :
- la méthode du coude : on cherche le à partir duquel l’inertie ne baisse presque plus (le « coude » de la courbe bleue) ;
- la silhouette (courbe orange) : pour chaque point, compare la distance moyenne à son propre groupe () et au groupe voisin le plus proche () : . Proche de 1, le point est bien placé ; proche de 0, il est entre deux groupes ; négatif, il est sans doute dans le mauvais. On choisit le de silhouette moyenne maximale.
Ici, les deux critères désignent 3 ou 4 groupes : le petit nuage de droite est-il un groupe à part ? Les données seules ne tranchent pas toujours ; c’est alors l’usage qui décide.
Les limites de k-means
Section intitulée « Les limites de k-means »k-means suppose des groupes ronds, de tailles comparables, et il est sensible à l’échelle des variables (standardisez d’abord). Il échoue sur des formes allongées ou imbriquées, comme deux lunes.
k-means pas à pas dans le simulateurTrois nuages : regardez les itérations, la courbe du coude et la silhouette. Essayez ensuite le jeu « deux lunes » : k-means coupe chaque lune par une droite.
→DBSCAN : des groupes par densité
Section intitulée « DBSCAN : des groupes par densité »DBSCAN ne cherche pas des centres mais des zones denses. Deux réglages : un rayon , et un nombre minimal de voisins.
- un point qui a au moins ce nombre de voisins à moins de est un point cœur ;
- les points cœurs voisins sont reliés de proche en proche : chaque chaîne forme un groupe ;
- un point non cœur mais proche d’un cœur est un point de bord ;
- les autres sont du bruit : DBSCAN refuse de les classer.
DBSCAN trouve des groupes de forme quelconque, choisit seul leur nombre, et isole les points aberrants. En revanche, il peine quand les groupes ont des densités très différentes, et le choix de est délicat. Astuce : tracer, pour chaque point, la distance à son -ième voisin, triée ; le coude de cette courbe suggère (le simulateur l’affiche).
DBSCAN sur les deux lunesFaites varier ε : trop petit, tout devient du bruit ; trop grand, les lunes fusionnent. Le graphique des distances au k-ième voisin aide à choisir.
→La classification hiérarchique
Section intitulée « La classification hiérarchique »La classification ascendante hiérarchique part d’autant de groupes que de points, puis fusionne à chaque étape les deux groupes les plus proches, jusqu’à n’en avoir plus qu’un. L’historique des fusions forme un arbre : le dendrogramme. La hauteur de chaque fusion est la distance entre les deux groupes réunis.
On obtient groupes en coupant l’arbre à une hauteur donnée. Un grand saut de hauteur indique qu’on réunirait des groupes très différents : c’est là qu’il faut couper. Tout dépend de la distance entre groupes choisie :
- Ward : fusionne les groupes qui font le moins augmenter l’inertie (proche de k-means, le plus utilisé) ;
- lien complet : distance entre les deux points les plus éloignés ; groupes compacts ;
- lien moyen : moyenne des distances ;
- lien simple : distance entre les deux points les plus proches ; suit les formes allongées, mais crée des chaînes.
Avantages : pas besoin de fixer à l’avance, et le dendrogramme montre la structure à toutes les échelles. Inconvénient : le coût grandit comme (en mémoire) ; au-delà de quelques dizaines de milliers de points, il devient prohibitif.
Mesurer un clustering
Section intitulée « Mesurer un clustering »Trois types de mesures, à combiner :
| Type | Mesure | Quand |
|---|---|---|
| interne (les données seules) | inertie, silhouette, indice de Davies-Bouldin | toujours ; pour choisir ou comparer des méthodes |
| externe (de vraies classes connues) | indice de Rand ajusté (ARI), information mutuelle | pour tester une méthode sur des données étiquetées |
| utilité | stabilité, interprétation, effet sur une décision | toujours ; c’est le vrai critère |
L’ARI vaut 1 quand les groupes coïncident avec les classes (quels que soient leurs numéros), et environ 0 pour un regroupement au hasard. Attention : la silhouette favorise les groupes ronds ; elle jugera mal un excellent résultat de DBSCAN sur deux lunes. Une mesure interne n’est qu’un indice.
🎓 Pour aller plus loin : pourquoi k-means converge, et ce qu'il minimise
k-means minimise l’inertie
où est le groupe du point et le centre du groupe . Chaque étape fait baisser (ou la laisse égale) :
- à centres fixés, affecter chaque point au centre le plus proche minimise chaque terme ;
- à groupes fixés, la moyenne est le point qui minimise la somme des carrés des distances (c’est le même calcul que « la moyenne minimise la MSE »).
ne peut prendre qu’un nombre fini de valeurs (il y a un nombre fini de partitions) et décroît : l’algorithme s’arrête forcément. Mais rien ne garantit le minimum global : trouver la partition optimale est un problème NP-difficile.
Le modèle de mélange gaussien (GaussianMixture) généralise k-means : chaque groupe est une gaussienne avec sa propre forme (ellipse) et sa taille, et chaque point reçoit une probabilité d’appartenance à chaque groupe plutôt qu’une affectation stricte. Il s’ajuste par l’algorithme EM, une version « douce » des deux étapes de k-means.
from sklearn.pipeline import make_pipelinefrom sklearn.preprocessing import StandardScalerfrom sklearn.cluster import KMeans, DBSCAN, AgglomerativeClusteringfrom sklearn.metrics import silhouette_score, adjusted_rand_score
Xs = StandardScaler().fit_transform(X)for k in range(2, 9): km = KMeans(n_clusters=k, n_init=10, random_state=0).fit(Xs) print(k, km.inertia_, silhouette_score(Xs, km.labels_))
groupes = DBSCAN(eps=0.3, min_samples=5).fit_predict(Xs) # −1 = bruitgroupes_h = AgglomerativeClustering(n_clusters=3, linkage="ward").fit_predict(Xs)adjusted_rand_score(y_connu, groupes_h) # si de vraies classes existent✅ Vérifiez vos acquis