DBSCAN (Density-Based Spatial Clustering of Applications with Noise - Regroupement spatial d'applications basé sur la densité avec bruit)

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) est un algorithme d'apprentissage non supervisé populaire, utilisé pour regrouper les points de données qui sont étroitement liés, en marquant comme valeurs aberrantes les points isolés dans les régions de faible densité. Contrairement à d'autres méthodes de clustering, DBSCAN ne nécessite pas que le nombre de clusters soit spécifié à l'avance. Sa capacité à trouver des clusters de formes arbitraires et sa robustesse au bruit en font un outil puissant pour l'exploration de données et l'analyse de données. L'algorithme a été introduit pour la première fois dans un article de 1996 par Martin Ester, Hans-Peter Kriegel, Jörg Sander et Xiaowei Xu, qui est devenu un ouvrage fondamental dans le domaine.

Fonctionnement de DBSCAN

DBSCAN définit les clusters en fonction de la densité des points de données dans un espace donné. Il fonctionne sur deux paramètres clés :

• Epsilon (ε ou eps): Ce paramètre définit le rayon d'un voisinage autour d'un point de données. Tous les points situés à cette distance sont considérés comme des voisins.
• Nombre minimal de points (MinPts) : Il s'agit du nombre minimal de points de données (y compris le point lui-même) requis pour former une région dense ou un cluster.

Sur la base de ces paramètres, DBSCAN catégorise chaque point de données en l'un des trois types suivants :

1. Points centraux : Un point est un point central s’il a au moins MinPts dans son eps voisinage. Ces points sont l'intérieur d'un cluster.
2. Points frontières : Un point est un point frontière s'il se trouve dans le eps voisinage d'un point central, mais n'a pas assez de voisins pour être lui-même un point central. Ces points forment le bord d'un cluster.
3. Points de bruit (valeurs aberrantes) : Un point est considéré comme du bruit s’il n’est ni un point central ni un point limite. Ce sont les valeurs aberrantes qui n’appartiennent à aucun cluster.

L'algorithme commence par un point arbitraire et récupère son voisinage. S'il s'agit d'un point central, un nouveau cluster est créé. L'algorithme étend ensuite itérativement le cluster en ajoutant tous les voisins directement accessibles, un processus qui se poursuit jusqu'à ce qu'aucun autre point ne puisse être ajouté à un cluster. Vous pouvez voir une implémentation visuelle dans la documentation scikit-learn.

Applications réelles de l'IA/ML

La capacité de DBSCAN à identifier le bruit et à découvrir des clusters non linéaires le rend très précieux dans divers domaines :

• Analyse géospatiale : Les urbanistes et les géographes utilisent DBSCAN pour analyser les données spatiales. Par exemple, en regroupant les coordonnées GPS des incidents de circulation, ils peuvent identifier les points chauds d'accidents. De même, il peut être utilisé pour trouver des groupes de cas de maladies signalés, aidant ainsi les épidémiologistes à suivre les épidémies. Des organisations comme la Geospatial Information Authority of Japan utilisent des méthodes similaires basées sur la densité pour la cartographie.
• Détection d'anomalies dans la finance : Dans le secteur financier, DBSCAN peut être utilisé pour détecter les transactions frauduleuses. En regroupant les schémas de dépenses typiques d'un client, toute transaction qui se situe en dehors de ces clusters (c'est-à-dire, étiquetée comme bruit) peut être signalée pour une enquête plus approfondie. Cette approche est un élément clé des systèmes modernes de détection de fraude.

DBSCAN et Ultralytics

L'écosystème Ultralytics se concentre principalement sur les modèles d'apprentissage supervisé, tels que Ultralytics YOLO pour des tâches incluant la détection d'objets, la classification d'images et la segmentation d'instances. Bien que DBSCAN soit une méthode non supervisée, ses principes sont pertinents dans le contexte plus large de la vision par ordinateur (CV).

Par exemple, après avoir effectué une détection d'objets avec un modèle comme YOLO11 sur une vidéo d'une rue animée, DBSCAN pourrait être appliqué aux coordonnées centrales des boîtes englobantes détectées. Cette étape de post-traitement peut regrouper les détections de piétons individuels en foules distinctes, offrant ainsi une meilleure compréhension de la scène. La compréhension de la distribution des données est également cruciale lors de la préparation des jeux de données pour l'entraînement. L'analyse exploratoire des données à l'aide de DBSCAN peut révéler des schémas ou des anomalies dans le jeu de données, qui peuvent être gérés et visualisés à l'aide de plateformes comme Ultralytics HUB.

Distinguer des termes connexes

• Clustering K-Means : La différence la plus significative est que K-Means exige que l'utilisateur spécifie le nombre de clusters (k) au préalable, tandis que DBSCAN détermine automatiquement le nombre de clusters. K-Means est également confronté à des difficultés avec les clusters non sphériques et est sensible aux valeurs aberrantes, car il force chaque point dans un cluster. DBSCAN excelle dans la recherche de clusters de formes arbitraires et isole efficacement les valeurs aberrantes en tant que bruit.
• Clustering hiérarchique : Cette méthode crée un arbre de clusters, connu sous le nom de dendrogramme. Bien qu'utile pour visualiser les structures de clusters imbriquées, elle peut être plus coûteuse en calcul sur de grands ensembles de données par rapport à DBSCAN. Le choix entre les deux dépend souvent de la taille de l'ensemble de données et de la sortie souhaitée, comme indiqué dans les guides pour choisir le bon algorithme de clustering.