DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

DBSCAN (regroupement spatial basé sur la densité des applications avec bruit) est un algorithme d'apprentissage non supervisé qui regroupe en clusters les points très rapprochés et étiquette comme bruit ceux des zones peu denses. Martin Ester, Hans-Peter Kriegel, Jörg Sander et Xiaowei Xu l'ont présenté à la conférence KDD en 1996. Il n'exige pas de fixer à l'avance le nombre de clusters, détecte des clusters de toutes formes — anneaux, croissants ou routes sinueuses, par exemple — et son étiquette de bruit constitue une forme simple de détection d'anomalies. Deux paramètres contrôlent l'ensemble de l'algorithme : le rayon du voisinage et le nombre de points requis pour qu'un voisinage soit dense.

Points centraux, points frontières et bruit#

DBSCAN examine le voisinage de chaque point, soit l'ensemble des points situés à une distance eps, et en compte les membres :

• Point central : possède au moins min_samples points dans son voisinage, en se comptant lui-même dans l'implémentation de scikit-learn. Les points centraux forment le cœur dense d'un cluster.
• Point frontière : ne possède pas assez de voisins pour être un point central, mais se trouve à moins de eps d'un point central. Les points frontières forment les bords d'un cluster.
• Point de bruit : ne correspond à aucun des deux types précédents. Il n'appartient donc à aucun cluster et reçoit l'étiquette -1.

Un cluster se développe à partir de n'importe quel point central non visité. DBSCAN ajoute tous les points de son voisinage, puis recommence à partir de chaque nouveau point central ajouté jusqu'à ce qu'aucun autre point ne soit accessible. Une chaîne de voisinages denses qui se chevauchent forme ainsi un seul cluster, quelle que soit sa forme. Les points frontières rejoignent un cluster sans l'étendre. Le résultat est déterministe pour un ordre d'entrée donné, mais un point frontière accessible depuis deux clusters rejoint celui qui l'atteint en premier ; mélanger les données peut donc déplacer des points frontières d'un cluster à l'autre.

Choisir eps et min_samples#

Le rayon eps est le paramètre le plus important et dépend de l'échelle des données ; c'est pourquoi les caractéristiques sont généralement standardisées au préalable. Un rayon trop petit laisse la plupart des points dans le bruit, tandis qu'un rayon trop grand fusionne les clusters voisins. L'heuristique habituelle consiste à trier la distance entre chaque point et son k-ième voisin le plus proche, avec k égal à min_samples, puis à choisir eps au coude de la courbe, là où les distances commencent à augmenter fortement. Des valeurs de min_samples plus élevées rendent le regroupement plus tolérant au bruit et sont courantes sur les grands jeux de données ou ceux très bruités. Dans les espaces de grande dimension, comme les plongements d'images, les distances entre les points deviennent similaires ; les praticiens appliquent donc souvent une réduction de dimensionnalité, telle que l'analyse en composantes principales (PCA), avant d'exécuter DBSCAN.

DBSCAN, K-Means et HDBSCAN#

Le regroupement K-means exige de connaître à l'avance le nombre de clusters, affecte chaque point au centroïde le plus proche et favorise donc les clusters compacts et arrondis, tout en intégrant les valeurs aberrantes à un groupe. DBSCAN détermine le nombre de clusters à partir de la densité et laisse les valeurs aberrantes à l'écart. Son point faible est d'utiliser un unique eps global : lorsque les clusters ont des densités très différentes, aucun rayon ne permet de séparer à la fois les clusters clairsemés du bruit et les clusters denses les uns des autres. HDBSCAN contourne ce problème en exécutant en pratique DBSCAN pour toutes les valeurs de eps et en conservant les clusters les plus stables. Les deux algorithmes sont disponibles dans le module de regroupement de scikit-learn, avec l'algorithme OPTICS, qui leur est apparenté.

Cet exemple regroupe deux croissants entrelacés auxquels ont été ajoutées 20 valeurs aberrantes aléatoires, puis évalue chaque résultat par rapport aux groupes réels à l'aide de l'indice de Rand ajusté, où 1.0 correspond à une correspondance parfaite :

import numpy as np
from sklearn.cluster import DBSCAN, KMeans
from sklearn.datasets import make_moons
from sklearn.metrics import adjusted_rand_score

# Two interleaving crescents plus 20 scattered outliers (true label -1)
X, y = make_moons(n_samples=300, noise=0.05, random_state=0)
rng = np.random.default_rng(0)
X = np.vstack([X, rng.uniform(-1.5, 2.5, size=(20, 2))])
y = np.concatenate([y, np.full(20, -1)])

# DBSCAN infers clusters from density; k-means is told there are 2
db_labels = DBSCAN(eps=0.2, min_samples=5).fit_predict(X)
km_labels = KMeans(n_clusters=2, random_state=0).fit_predict(X)

print(f"DBSCAN: {db_labels.max() + 1} clusters, {(db_labels == -1).sum()} noise points")
print(f"ARI: DBSCAN {adjusted_rand_score(y, db_labels):.2f}, k-means {adjusted_rand_score(y, km_labels):.2f}")

Le script affiche 2 clusters et 15 points de bruit pour DBSCAN, ainsi que des indices de Rand ajustés de 0.97 pour DBSCAN et de 0.20 pour k-means. DBSCAN suit les deux croissants et met de côté les valeurs aberrantes qui en sont éloignées, tandis que k-means coupe les croissants par une frontière droite, même si le nombre correct de clusters lui a été fourni.

Applications concrètes#

• Perception LiDAR : les pipelines de véhicules autonomes et de robotique retirent les points du sol d'un balayage LiDAR, puis regroupent les points 3D restants en obstacles distincts. Le regroupement basé sur la densité est souvent choisi, car le nombre d'objets est inconnu.
• Post-traitement de détection : les centres des boîtes des détections YOLO26, disponibles sous la forme result.boxes.xywh, peuvent être regroupés avec DBSCAN pour repérer des groupes de personnes dans une foule ou des emplacements récurrents de défauts sur une chaîne de production ; les détections isolées sont alors considérées comme du bruit.
• Détection des fraudes et surveillance des capteurs : Les transactions ou relevés étiquetés -1 se trouvent loin de tout groupe dense de comportements normaux et deviennent des candidats à examiner.
• Analyse géospatiale : Les entreprises de livraison et de VTC regroupent les points GPS pour repérer les arrêts fréquents et les zones de prise en charge très fréquentées. DBSCAN de Scikit-learn accepte metric="haversine" pour la latitude et la longitude en radians ; dans ce cas, eps est un angle sur la sphère unité, si bien qu’un rayon de 100 mètres devient eps = 0.1 / 6371, en utilisant le rayon moyen de la Terre de 6 371 km.