Aller au contenu
Data science

Le clustering : k-means, DBSCAN, hiérarchique

⏱ 1 h 15

Prérequis : Encoder et mettre à l'échelle · Choisir un modèle

À la fin de ce chapitre, vous saurez :
  • 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.

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.

L’algorithme le plus utilisé tient en deux étapes, répétées jusqu’à ce que plus rien ne bouge :

  1. affecter chaque point au centre le plus proche ;
  2. déplacer chaque centre au milieu (la moyenne) de ses points.

On choisit à l’avance le nombre de groupes kk, et on place les kk 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.

L’inertie est la somme des carrés des distances de chaque point à son centre. Elle baisse toujours quand kk augmente (avec k=nk = n, 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 kk à 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 (aa) et au groupe voisin le plus proche (bb) : s=b−amax⁡(a,b)s = \dfrac{b - a}{\max(a, b)}. 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 kk 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.

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 simulateur

Trois 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 ne cherche pas des centres mais des zones denses. Deux réglages : un rayon ε\varepsilon, et un nombre minimal de voisins.

  • un point qui a au moins ce nombre de voisins à moins de ε\varepsilon 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 ε\varepsilon est délicat. Astuce : tracer, pour chaque point, la distance à son kk-ième voisin, triée ; le coude de cette courbe suggère ε\varepsilon (le simulateur l’affiche).

🔬DBSCAN sur les deux lunes

Faites 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 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 kk 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 kk à l’avance, et le dendrogramme montre la structure à toutes les échelles. Inconvénient : le coût grandit comme n2n^2 (en mémoire) ; au-delà de quelques dizaines de milliers de points, il devient prohibitif.

Trois types de mesures, à combiner :

Type Mesure Quand
interne (les données seules) inertie, silhouette, indice de Davies-Bouldin toujours ; pour choisir kk 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

J=∑i=1n∥xi−μc(i)∥2,J = \sum_{i=1}^{n} \lVert x_i - \mu_{c(i)} \rVert^2 ,

où c(i)c(i) est le groupe du point ii et μj\mu_j le centre du groupe jj. Chaque étape fait baisser JJ (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 »).

JJ 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_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import KMeans, DBSCAN, AgglomerativeClustering
from 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 = bruit
groupes_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

1. Quelles sont les deux étapes répétées par k-means ?
2. Pourquoi ne choisit-on pas k en minimisant l'inertie ?
3. Deux lunes imbriquées : quelle méthode les sépare correctement ?
4. Un point a une silhouette de −0,4. Cela signifie qu'il…
5. On connaît les vraies espèces de fleurs. Quelle mesure compare un clustering à ces classes ?
6. Pourquoi standardiser les variables avant k-means ?