🌌 DBSCAN — Regroupement basé sur la densité

Un point q est directement accessible par densité depuis le point p (étant donné epsilon et minPts) si q se trouve dans l'epsilon-voisinage de p et que p est un point central. Un point q est accessible par densité depuis p s'il existe une chaîne de points p1, p2, ..., pn où p1 = p, pn = q, et chaque pi+1 est directement accessible par densité depuis pi. Deux points sont connectés par densité s'il existe un point o à partir duquel les deux sont accessibles par densité. Une grappe est définie comme un ensemble maximal de points mutuellement connectés par densité. Les points de bruit sont ceux qui ne sont accessibles par densité depuis aucun point central.

DBSCAN est largement utilisé en analyse géospatiale pour trouver des grappes de coordonnées GPS telles que des points chauds de circulation, des scènes de crime ou des épicentres de tremblements de terre. Il est appliqué en astronomie pour regrouper les étoiles et les galaxies dans les données de relevés, en biologie pour regrouper les cellules en cytométrie en flux, dans le commerce électronique pour détecter des schémas d'achat inhabituels comme anomalies, et en vision par ordinateur pour regrouper les pixels en segmentation d'image. Sa capacité à ignorer les valeurs aberrantes en tant que bruit le rend particulièrement précieux dans les données de capteurs bruitées des appareils IoT et des véhicules autonomes.

Une idée reçue courante est que DBSCAN est simplement une version plus flexible de k-means qui produit toujours de meilleurs résultats. En réalité, DBSCAN peine avec les jeux de données ayant des grappes de densités très variables, car une seule valeur epsilon globale ne peut pas capturer simultanément une grappe dense compacte et une grappe éparse étalée. K-means, bien qu'il nécessite le nombre de grappes à l'avance, peut surpasser DBSCAN sur des amas sphériques bien séparés de tailles similaires. Les deux algorithmes sont complémentaires plutôt que l'un étant universellement supérieur.

DBSCAN a été introduit en 1996 par Martin Ester, Hans-Peter Kriegel, Jorg Sander et Xiaowei Xu lors de la deuxième conférence internationale sur la découverte de connaissances et la fouille de données (KDD-1996). L'article original, intitulé « A density-based algorithm for discovering clusters in large spatial databases with noise », est devenu l'un des articles les plus cités en fouille de données. En 2014, les auteurs ont reçu le prix SIGKDD Test of Time, reconnaissant l'influence durable de l'algorithme près de deux décennies après sa publication.

OPTICS (Ordering Points To Identify the Clustering Structure) est une extension directe de DBSCAN qui surmonte la limitation des densités variables en produisant un graphique d'accessibilité au lieu d'une partition fixe. HDBSCAN (DBSCAN hiérarchique) construit une hiérarchie de grappes à plusieurs niveaux de densité et sélectionne les plus stables, le rendant plus robuste sur les données du monde réel. Le regroupement par décalage de moyenne (mean-shift) est une autre méthode basée sur la densité qui trouve les centres de grappes en déplaçant itérativement les points vers des régions de densité plus élevée. La propagation d'affinité et le regroupement spectral partagent certaines idées sur la connectivité mais reposent sur des principes mathématiques différents.

Dans la conduite autonome, DBSCAN est utilisé pour regrouper les nuages de points 3D provenant des capteurs LiDAR, regroupant les retours appartenant au même objet physique tel qu'un piéton ou un autre véhicule. En sécurité réseau, il détecte l'activité de botnets en regroupant les adresses IP présentant des schémas de trafic similaires, signalant les adresses isolées comme des anomalies potentielles. Dans l'industrie manufacturière, il identifie les grappes de produits défectueux dans les flux de capteurs sur les lignes de production. Les plateformes cloud comme AWS et Google Cloud incluent DBSCAN dans leurs services d'apprentissage automatique gérés pour l'analyse spatiale à grande échelle.

Les directions de recherche actives incluent des variantes évolutives de DBSCAN pour les données distribuées et en flux continu, comme PDBSCAN (DBSCAN parallèle sur MapReduce/Spark) et des approximations basées sur STING qui réduisent le goulot d'étranglement de complexité O(n^2). Les chercheurs explorent également des méthodes de sélection adaptative des paramètres qui estiment automatiquement epsilon à partir de la distribution des données en utilisant des graphiques de distance aux k plus proches voisins ou des substituts d'apprentissage automatique. Le regroupement profond combine DBSCAN avec des plongements de réseaux de neurones afin que la métrique de distance elle-même soit apprise, rendant l'algorithme efficace sur les données d'images, de texte et de graphes où la distance euclidienne n'est pas significative.