Voir la source de DBSCAN

{{ébauche|informatique}}{{Infobox Méthode scientifique
| image = DBSCAN-Illustration.svg
| légende = Les points A sont les points déjà dans le cluster. Les points B et C sont atteignables depuis A et appartiennent donc au même cluster. Le point N est une donnée aberrante puisque son epsilon voisinage ne contient pas de points dont l'epsilon voisinage contient MinPts points ou plus.
}}'''DBSCAN''' (''density-based spatial clustering of applications with noise'') est un [[algorithme]] de [[partitionnement de données]] proposé en 1996 par  Martin Ester, Hans-Peter Kriegel, Jörg Sander et Xiaowei Xu<ref name=":0">M. Ester, H.-P. Kriegel, J. Sander, and X. Xu, “A density-based algorithm for discovering clusters in large spatial databases with noise,” in Proceedings of the 2nd International Conference on Knowledge Discovery and Data mining, 1996, pp. 226–231.</ref>. Il s'agit d'un algorithme fondé sur la densité dans la mesure qui s’appuie sur la densité estimée des clusters pour effectuer le partitionnement.

== Principe général ==
L'algorithme DBSCAN utilise 2 paramètres : la distance <math>\epsilon</math> et le nombre minimum de points <math>MinPts</math> devant se trouver dans un rayon <math>\epsilon</math> pour que ces points soient considérés comme un cluster. Les paramètres d'entrées sont donc une estimation de la densité de points des clusters. L'idée de base de l'algorithme est, pour un point donné, de récupérer son <math>\epsilon</math>-voisinage et de vérifier qu'il contient bien <math>MinPts</math> points ou plus. Ce point est alors considéré comme faisant partie d'un cluster. On parcourt ensuite l'<math>\epsilon</math>-voisinage de proche en proche afin de trouver l'ensemble des points du cluster.

== Algorithme ==
 DBSCAN(D, ε, MinPts)
    C = 0
    pour chaque point P non visité des données D
       marquer P comme visité
       PtsVoisins = epsilonVoisinage(D, P, ε)
       si tailleDe(PtsVoisins) < MinPts
          marquer P comme BRUIT
       sinon
          C++
          étendreCluster(D, P, PtsVoisins, C, ε, MinPts)
           
 étendreCluster(D, P, PtsVoisins, C, ε, MinPts)
    ajouter P au cluster C
    pour chaque point P' de PtsVoisins 
       si P' n'a pas été visité
          marquer P' comme visité
          PtsVoisins' = epsilonVoisinage(D, P', ε)
          si tailleDe(PtsVoisins') >= MinPts
             PtsVoisins = PtsVoisins U PtsVoisins'
       si P' n'est membre d'aucun cluster
          ajouter P' au cluster C
           
 epsilonVoisinage(D, P, ε)
    retourner tous les points de D qui sont à une distance inférieure à ε de P

== Structure des solutions<ref>{{Article |langue=en |prénom1=Michael |nom1=Hahsler |prénom2=Matthew |nom2=Piekenbrock |prénom3=Derek |nom3=Doran |titre=dbscan : Fast Density-Based Clustering with R |périodique=Journal of Statistical Software |volume=91 |numéro=1 |date=2019 |issn=1548-7660 |doi=10.18637/jss.v091.i01 |lire en ligne=http://www.jstatsoft.org/v91/i01/ |consulté le=2020-03-09 }}</ref>==
Les points du [[jeu de données]] sont séparés en 3 types :

* Les points centraux (''core points'')
* Les points frontières (''border points'')
*Les points aberrants (''noise points'')

=== Les points centraux ===
Un point du jeu de données est dit central si :

# Son voisinage est dense

Ces points forment des composantes connexes indépendantes de l'ordre d'exploration du jeu de données.

=== Les points frontières ===
Un point du jeu de données est dit frontière si :

# Ce n'est pas un point central
# Il appartient au voisinage d'un point central

Ces points viennent s'agréger autour des composantes connexes pour former des groupes. Ces groupes sont couramment appelées par leur nom anglais : ''Clusters''.

Contrairement aux composantes connexes, la formation des clusters est dépendante de l'ordre d'exploration du jeu de données. En effet un point frontière est assigné au premier cluster rencontré lors de l'étape d'expansion. En plus de l'ordre d'exploration, ces points sont sensibles aux différentes implémentations de l'algorithme DBSCAN. 

=== Les points aberrants ===
Un point du jeu de données est dit aberrant si :

# Ce n'est pas un point central
# Ce n'est pas un point frontière

Ces points sont donc tous les autres points du jeu de données.

Attention, le nom donné à ces points peut être trompeur car leur désignation dépend des paramètres choisis.

== Concepts mathématiques sous-jacent ==

=== Voisinage d'un point ===
La notion de voisinage est le concept élémentaire à la base de la méthode DBSCAN. Il permet de définir mathématiquement les voisinages denses qui sont utilisés pour la localisation des points centraux et l'expansion des clusters.  

==== Distance entre points ====
{{article détaillé|Distance_(mathématiques)}}En [[mathématiques]], on appelle '''distance''' sur un [[ensemble]] {{Formule|''E''}} toute application {{Formule|''d''}} définie sur le [[produit cartésien|produit]] {{Formule|1=''E''{{2}} = ''E''×''E''}} et à valeurs dans l'ensemble ℝ{{exp|+}} des [[Nombre réel|réels]] [[Nombre positif|positifs]],
<center><math>d :E\times E\to\R^+</math></center>
vérifiant les propriétés suivantes
{| class="wikitable centre"
! Nom
! Propriété
|-----
| '''symétrie'''
| <math>\forall (a,b)\in E^2,\ d(a,b)=d(b,a)</math>
|-----
| '''séparation'''
| <math>\forall (a,b)\in E^2,\ d(a,b)=0 \Leftrightarrow a=b</math>
|-----
| '''[[inégalité triangulaire]]'''
| <math>\forall (a,b,c)\in E^3,\ d(a,c)\leq d(a,b)+d(b,c)</math>
|}
Le choix de la distance entre points est un paramètre implicite à la méthode DBSCAN.

Dans le cas de DBSCAN, c'est communément la distance euclidienne qui est utilisée.
==== Boule ouverte de rayon de epsilon ====
{{article détaillé|Boule_(topologie)}}
[[Fichier:Boule centre p rayon epsilon.svg|vignette|Boule ouverte de centre le point p et de rayon ε, pour une distance euclidienne en dimension 2]]
Dans l'espace usuel comme dans n'importe quel [[espace métrique]] <math>(E,d)</math> :

La '''boule ouverte''' est l'ensemble <math>B(p,\epsilon)\,</math> des points <math>M</math> de l'espace <math>E</math> dont la distance au point <math>p</math> est strictement inférieure à <math>\epsilon</math> :

:<math>B(p,\epsilon)=\left\{M\in E\,\mid\,d(M,p)<\epsilon\right\}</math>

Le point <math>p</math> est alors appelé centre de la boule ouverte <math>B(p,\epsilon)\,</math>et <math>\epsilon</math> est appelé le rayon de la boule ouverte <math>B(p,\epsilon)\,</math>.

Les caractéristiques des boules dépendent de deux éléments :

# La forme des boules est liée à la distance <math>d</math> (paramètre implicite à DBSCAN).
# L'espace couvert dépend du rayon <math>\epsilon</math> choisie (paramètre explicite à DBSCAN).

Ci contre une boule ouverte de centre le point <math>p</math> et de rayon <math>\epsilon</math> est représentée dans un espace à deux dimensions pour une distance <math>d</math> euclidienne. La surface bleu représente la boule ouverte <math>B(p,\epsilon)\,</math>: Celle-ci correspond à la zone de recherche des voisins pour l'algorithme DBSCAN.

==== Epsilon-voisinage  ====
[[Fichier:Boule points.svg|vignette|Epsilon-Voisinage du point p, pour une distance euclidienne en dimension 2]]
L'<math>\epsilon</math>-voisinage <math>V_{\epsilon}(p)</math> d'un point <math>p</math>, est l'ensemble des points <math>q</math> du jeu de données <math>D</math> situés dans la boule ouverte centrée en <math>p</math> et de rayon <math>\epsilon</math> :

:<math>V_{\epsilon}(p)=\left\{q\in D\,\mid\,d(q,p)<\epsilon\right\}</math>

Les points du jeu de données sélectionnés reposent sur les boules ouvertes et sont donc dépendants des paramètres suivants :

# La distance <math>d</math> entre les points <math>p</math> et <math>q</math>
# Le rayon de recherche <math>\epsilon</math> autour du point <math>p</math>

Ci-contre un <math>\epsilon</math>-voisinage du point <math>p</math> a été représenté dans un espace de dimension 2 avec une distance euclidienne. Les points rouges sont les points <math>q</math> du jeu de données <math>D</math> qui appartiennent à l' <math>\epsilon</math>-voisinage du point <math>p</math>, et les points de couleur indigo représentent les points  <math>q</math> du jeu de données <math>D</math> qui n'appartiennent pas à l' <math>\epsilon</math>-voisinage du point <math>p</math>. Pour l'algorithme DBSCAN, c'est le nombre de points rouges qui est important.

==== Epsilon-voisinage dense ====
Un <math>\epsilon</math>-voisinage <math>V_{\epsilon}(p)</math> est dit dense si son cardinal est supérieur ou égal à <math>minPts</math>.

:<math>\mid V_{\epsilon}(p)\mid \geqslant minPts</math>

Cette définition est la première qui dépend des 3 paramètres de DBSCAN :

# Le nombre minimum de points <math>minPts</math> pour qu'un voisinage soit désigné dense.
# Le rayon du voisinage <math>\epsilon</math> autour du point <math>p</math> considéré.
# La distance <math>d</math> entre points.

En reprenant [[L'Illustration|l'illustration]] précédente, <math>\epsilon</math> est fixé. Si <math>minPts</math> est fixé à 3 points alors le voisinage considéré est clairement dense. À l’inverse si <math>minPts</math> est fixé à 50 points alors le voisinage n'est clairement pas dense.

=== Relations basées sur la densité ===
Les [[Relation binaire|relations binaires]] qui suivent sont utilisées pour effectuer des démonstrations sur la méthode DBSCAN, et plus généralement en [[apprentissage non supervisé]] basé sur la densité.

==== Directement accessible par densité ====
Un point <math>q</math> du jeu de données <math>D</math> est directement accessible par densité depuis un autre point <math>p</math>  si :

# <math>V_{\epsilon}(p)</math> est dense
# <math>q \in V_{\epsilon}(p)</math>

Autrement dit, les points directement accessible par densité sont les points d'un voisinage dense.

Une telle relation est graphiquement représentée par un flèche qui part du point <math>p</math> vers le point <math>q</math>.

==== Accessible par densité ====
Un point <math>q</math> du jeu de données <math>D</math> est accessible par densité depuis un autre point <math>p</math> s'il existe une séquence ordonnée de points <math>(p_1,p_2,...,p_n)</math> tel que :

# <math>p_1=p</math>
# <math>p_{i+1}</math> est directement accessible par densité depuis <math>p_{i}</math>
# <math>p_n = q</math>

Un point <math>q</math> est accessible par densité depuis un autre points <math>p</math> s'il existe un chemin fléché vers de <math>p</math> vers <math>q</math>.

==== Densément connecté ====
Un point <math>q</math> du jeu de données <math>D</math> est densément connecté à un autre point <math>p</math> si :

# <math>o \in D</math>
# <math>p</math> est accessible par densité depuis <math>o</math>
# <math>q</math> est accessible par densité depuis <math>o</math>

Un point <math>q</math> et un point <math>p</math> sont densément connecté s'il existe deux chemins fléché qui partent d'un même point <math>o</math> pour aller respectivement vers les points <math>p</math> et <math>q</math>.

== Estimation des paramètres ==
L'estimation des paramètres <math>\epsilon</math> et <math>MinPts</math> n'est pas un problème facile, car ces deux valeurs sont intrinsèquement liées à la [[topologie]] de l'espace à partitionner. Une trop faible valeur de <math>\epsilon</math> et/ou une trop grande valeur de <math>MinPts</math> peuvent empêcher l'algorithme de propager les clusters. À l'inverse, une trop grande valeur pour  <math>\epsilon</math> et/ou une trop faible valeur pour <math>MinPts</math> peuvent conduire l'algorithme à ne renvoyer que du bruit. Une heuristique<ref>{{Ouvrage|nom1=alitouka|titre=spark_dbscan: DBSCAN clustering algorithm on top of Apache Spark|date=2017-08-18|lire en ligne=https://github.com/alitouka/spark_dbscan|consulté le=2017-08-21}}</ref> permettant de déterminer conjointement  <math>\epsilon</math> et <math>MinPts</math> pour un certain espace pourrait être donnée par :
* <math>\epsilon</math> : calculer pour chaque point de l'espace la distance à son plus proche voisin. Prendre <math>\epsilon</math> tel qu'une part « suffisamment grande » des points aient une distance à son plus proche voisin inférieure à <math>\epsilon</math>;
* <math>MinPts</math> : calculer pour chaque point le nombre de ses voisins dans un rayon de taille <math>\epsilon</math> (la taille de son <math>\epsilon</math>-voisinage). Prendre <math>MinPts</math> tel qu'une part « suffisamment grande » des points aient plus de <math>MinPts</math> points dans leur <math>\epsilon</math>-voisinage.

Par « suffisamment grand » on entend, par exemple, <math>95</math>% ou <math>90</math>% des points.


Une autre heuristique pour les cas en 2D (définie dans l'article original de DBSCAN<ref name=":0" />) consiste à fixer la valeur de <math>MinPts</math> à 4, et à tracer la courbe (triée dans l'ordre décroissant) des distances de chaque point à leur 4<sup>ème</sup> plus proche voisin. On fixe alors <math>\epsilon</math> à la valeur du "point seuil" repéré sur le graphe. Si ce seuil n'est pas clairement identifiable, l'utilisateur peut le fixer en estimant le pourcentage de bruit dans le jeu de données : <math>\epsilon</math> est donc tel que seuls les termes de bruit ont une distance à leur 4<sup>ème</sup> plus proche voisin plus grande que <math>\epsilon</math>. 

== Avantages et inconvénients ==
L'algorithme est très simple et ne nécessite pas qu'on lui précise le nombre de clusters à trouver. Il est capable de gérer les [[Donnée aberrante|données aberrantes]] en les éliminant du processus de partitionnement. Les clusters n'ont pas pour obligation d'être linéairement séparables (tout comme pour l'[[algorithme des k-moyennes]] par exemple). Cependant, il n'est pas capable de gérer des clusters de densités différentes.

== Articles connexes ==
* [[OPTICS]]

== Références ==
{{références}}

{{Palette |Apprentissage automatique}}
{{portail|Informatique}}

[[Catégorie:Algorithme de partitionnement de données]]
[[Catégorie:Exploration de données]]