Module 5 — DBSCAN et groupes de forme quelconque

Les deux modules précédents partageaient un présupposé : un groupe est un nuage ramassé autour d'un centre. DBSCAN abandonne complètement cette idée et la remplace par la densité : un groupe est une région où les points sont serrés, quelle que soit sa forme. Ce changement de définition règle d'un coup les deux principales faiblesses des k-moyennes — les formes non sphériques et les valeurs aberrantes.

Un groupe comme région dense

L'intuition est celle du contact de proche en proche. Si deux points sont voisins immédiats, ils appartiennent au même groupe ; si le voisin de mon voisin a lui-même des voisins, le groupe s'étend. En suivant ainsi les zones denses, le groupe prend la forme que les données lui donnent : un croissant, une spirale, un ruban.

Deux paramètres suffisent à formaliser cela, et tout DBSCAN tient dans leur bon réglage :

• eps : le rayon qui définit le voisinage d'un point ;
• min_samples : le nombre de voisins requis dans ce rayon pour parler de zone dense.

Trois statuts de points, dont un décisif

De ces deux paramètres découle une classification de chaque point, et c'est elle qui fait l'originalité de la méthode :

Statut	Définition	Rôle
point de cœur	au moins min_samples voisins dans eps	fait croître le groupe
point de bord	dans le voisinage d'un point de cœur, sans l'être lui-même	rattaché, mais ne propage pas
bruit	ni l'un ni l'autre	n'appartient à aucun groupe

La troisième ligne est l'apport majeur. Les k-moyennes affectaient tout point, y compris les aberrants qui tiraient les centroïdes ; DBSCAN les étiquette explicitement comme bruit, avec le label -1. Le partitionnement est ainsi assaini, et les points isolés deviennent au passage des candidats naturels à la détection d'anomalies du module 8.

from sklearn.cluster import DBSCAN
db = DBSCAN(eps=0.5, min_samples=5).fit(X_s)
db.labels_                              # -1 designe le bruit
(db.labels_ == -1).sum()                # volume de bruit : indicateur de reglage
len(set(db.labels_)) - (1 if -1 in db.labels_ else 0)   # nombre de groupes trouves

Notez qu'on ne fournit pas le nombre de groupes : DBSCAN le déduit de la structure. C'est un avantage réel, mais qui déplace la difficulté vers le réglage de eps.

Régler eps sans tâtonner : le graphe des k-distances

Un eps trop petit déclare presque tout comme bruit ; trop grand, il fusionne tous les groupes en un seul bloc. La méthode standard pour le calibrer est graphique et fiable : pour chaque point, on calcule la distance à son $k$-ième voisin le plus proche (avec $k$ = min_samples), puis on trace ces distances triées par ordre croissant. La courbe reste plate — les points denses ont tous un voisin proche — puis décolle brusquement quand on atteint les points isolés. Le coude de cette courbe est un excellent eps.

Pour min_samples, une heuristique répandue est de partir de deux fois le nombre de variables. Plus il est élevé, plus l'algorithme est exigeant et plus il déclare de bruit.

Ce que DBSCAN ne résout pas

L'honnêteté impose de nommer les limites, car elles sont réelles :

• densités variables : eps étant global, un jeu de données comportant un groupe dense et un groupe diffus est mal traité — un seul rayon ne peut convenir aux deux ;
• grande dimension : DBSCAN repose sur des distances, donc subit la malédiction de la dimension (module 4 du cours supervisé). En pratique, on réduit d'abord la dimension par ACP (module 6), puis on applique DBSCAN ;
• pas de profils types : sans centroïdes, l'interprétation demande de résumer soi-même chaque groupe, par exemple par ses moyennes.

HDBSCAN, la suite naturelle

La limite des densités variables a une réponse directe : HDBSCAN fait varier eps et retient les groupes stables sur une plage de densités. On n'a plus qu'un seul paramètre intuitif à fournir — la taille minimale d'un groupe — et les densités hétérogènes sont gérées. Quand DBSCAN donne un résultat correct sur une partie des données et absurde sur le reste, c'est le réflexe à avoir.

En résumé

• DBSCAN définit un groupe comme une région dense, ce qui lui permet de détecter des formes quelconques là où les k-moyennes échouent.
• Deux paramètres seulement : eps (rayon de voisinage) et min_samples (voisins requis) ; le nombre de groupes est déduit, non imposé.
• Points de cœur, de bord et bruit : le bruit est explicitement écarté (label -1), ce qui assainit le partitionnement.
• On règle eps par le coude du graphe des k-distances ; les densités variables appellent HDBSCAN, et la grande dimension une réduction préalable.

Module suivant : l'analyse en composantes principales, premier outil de réduction de dimension et complément indispensable de tout ce qui précède.