#dbscan — Apprentissage non supervisé

Regrouper par densité : epsilon, MinPts, points cœur, bordure et bruit — l'algorithme qui trouve des formes quelconques et ignore les intrus.

Ce que tu vas manipuler

Bienvenue dans #dbscan. Sur le plan, 240 points gris : deux croissants entrelacés et une vingtaine d'intrus semés au hasard. Un k-means à deux centres couperait ce nuage en deux moitiés par une droite, et donnerait un cluster à chaque intrus, coûte que coûte. DBSCAN raisonne autrement : il regarde la densité. Un point qui compte au moins MinPts voisins (lui compris) dans un rayon eps est un cœur ; les cœurs voisins se rejoignent en un même cluster, quelle que soit sa forme ; ce qui reste isolé est du bruit. Réglages actuels, dans le panneau de droite : eps = 0.25, MinPts = 5.
Lance l'algorithme : /lancer. Regarde bien l'ordre d'apparition : DBSCAN part d'un point, trouve ses voisins dans le rayon eps (l'anneau jaune), puis les voisins de ses voisins… le cluster s'étend de proche en proche, comme une tache qui s'élargit.
Rétrécis le rayon : /eps 0.1. Avec un anneau aussi petit, rares sont les points qui comptent encore 5 voisins.
L'inverse maintenant : /eps 0.5. Un rayon trop grand relie tout ce qui se trouve à moins de 0.5, y compris ce qui ne devrait pas l'être.
Reviens au bon réglage : /eps 0.25. Comment le choisir sans tâtonner ? Le panneau de droite affiche la 4-distance médiane : la distance typique d'un point à son quatrième voisin (≈ 0.13 avec ce jeu). Un eps un peu au-dessus fait des cœurs partout dans les lunes sans franchir le vide qui les sépare.
Second bouton : /minpts 12. Être cœur exige maintenant 12 voisins dans le même rayon.
Le même jeu vu par k-means : /comparer. k-means cherche autant de centres que DBSCAN a trouvé de clusters (2 ici) et coupe le plan par la médiatrice des deux centres (droite pointillée) : chaque lune est tranchée en deux, et les intrus reçoivent un cluster comme tout le monde.
Pour finir, rejoue l'algorithme au ralenti : /pas. Tout redevient gris, puis un seul point se révèle, avec son anneau eps et des segments vers ses voisins.
À toi de jouer : /minpts 5 pour revenir au réglage souple, puis /dataset anneaux (deux cercles concentriques : k-means ne peut pas, DBSCAN oui), /dataset bruit (rien que des intrus : DBSCAN ne trouve rien, ou presque), /bruit 0.3 (30 % d'intrus), /voisins 0 0 (pose l'anneau sur le point le plus proche du centre), /reinit pour repartir. Limite à connaître : DBSCAN n'a qu'un seul eps, des clusters de densités très différentes lui échappent — c'est le problème que résout HDBSCAN. Prochaines étapes : #detection-anomalies (le bruit de DBSCAN comme détecteur d'intrus) et #clustering-hierarchique.

Commandes du canal

/eps <rayon=0.05..1> — Rayon de voisinage epsilon (relance DBSCAN si déjà lancé).
/minpts <2..20> — Nombre minimal de voisins (soi inclus) pour être un cœur.
/lancer — Calcule DBSCAN et rejoue l'expansion des clusters.
/pas — Révèle le point suivant dans l'ordre de visite (mode pas à pas).
/voisins <x=-2..2> <y=-2..2> — Pose l'anneau eps sur le point le plus proche de (x, y) et relie ses voisins.
/comparer — Bascule la coloration vers le résultat k-means (et retour).
/dataset <lunes|blobs|anneaux|bruit> — Change le jeu de points (lunes, blobs, anneaux ou bruit pur).
/bruit <proportion=0..0.3> — Proportion d'intrus uniformes ajoutés au jeu (0 à 0.3).
/graine <1..99> — Nouveau tirage aléatoire des points (déterministe).
/reinit — Revient aux lunes, 10 % de bruit, eps 0.25, MinPts 5, rien lancé.

Glossaire

DBSCAN: Algorithme de clustering par densité (Ester, Kriegel, Sander, Xu, 1996) : deux paramètres, eps et MinPts, aucun nombre de clusters à fixer. Il trouve des clusters de forme quelconque et étiquette explicitement les points isolés comme bruit.
epsilon (rayon de voisinage): Rayon eps du disque tracé autour de chaque point : tout point à distance ≤ eps est un voisin. Trop petit, tout devient bruit ; trop grand, tout fusionne.
MinPts: Nombre minimal de voisins (le point lui-même compris) qu'un point doit compter dans son rayon eps pour être un cœur. Valeur usuelle : 2 × dimension, soit 4 ou 5 en 2D ; l'augmenter rend l'algorithme plus exigeant et plus robuste au bruit.
point cœur: Point qui possède au moins MinPts voisins dans son rayon eps : il fait partie de l'intérieur dense d'un cluster et a le droit de l'étendre à ses voisins.
point bordure: Point qui n'a pas assez de voisins pour être cœur, mais qui se trouve dans le rayon eps d'un cœur : il rejoint le cluster de ce cœur sans pouvoir l'étendre. C'est la lisière du cluster.
bruit / valeur aberrante: Point ni cœur ni bordure : aucun cœur ne l'atteint. DBSCAN lui donne l'étiquette −1 au lieu de le forcer dans un cluster, ce qui en fait aussi un détecteur d'anomalies rudimentaire.
densité: Nombre de points par unité de surface. DBSCAN la mesure localement, en comptant les voisins dans un disque de rayon eps : un cluster est une région où cette densité dépasse le seuil MinPts, séparée des autres par des zones creuses.
expansion de cluster: Mécanisme central : partant d'un cœur, on ajoute ses voisins à une file ; chaque voisin qui est lui-même cœur y ajoute les siens, et ainsi de suite jusqu'à épuisement. Le cluster est l'ensemble des points atteignables par densité depuis la graine, d'où des formes quelconques.
graphe des k-distances: Pour chaque point, distance à son k-ième voisin (k = MinPts − 1, souvent 4), le tout trié. La courbe monte doucement pour les points des clusters puis décolle pour les intrus : le coude indique un bon eps.
densités variables (limite de DBSCAN): Avec un seul eps, DBSCAN ne peut pas distinguer un cluster compact d'un cluster diffus : l'un est fragmenté ou l'autre fusionné. HDBSCAN lève cette limite en explorant tous les eps à la fois et en gardant les clusters les plus stables.

Autres canaux du thème Apprentissage non supervisé

#k-means — Regrouper sans étiquettes : des centroïdes qui se déplacent, l'inertie qui baisse, le choix de k — et les formes où k-means échoue.
#pca — Analyse en composantes principales : trouver les axes où les données varient le plus, projeter, compresser — et mesurer ce qu'on perd.
#clustering-hierarchique — Fusionner les points deux à deux jusqu'à n'en faire qu'un : le dendrogramme, les critères de lien, et la hauteur de coupe qui décide du nombre de clusters.
#dbscan — Regrouper par densité : epsilon, MinPts, points cœur, bordure et bruit — l'algorithme qui trouve des formes quelconques et ignore les intrus.
#detection-anomalies — Repérer ce qui ne ressemble à rien : score z / Mahalanobis, Isolation Forest, LOF — trois façons de dire « ce point est bizarre ».
#t-sne-umap — Cartographier la haute dimension : t-SNE et UMAP déplient des données à 10 dimensions en une carte 2D lisible — perplexité, voisins, et pièges de lecture.