DBSCAN

Un point du jeu de données est dit central si :

1. Son voisinage est dense

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

Un point du jeu de données est dit frontière si :

1. Ce n'est pas un point central
2. 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.

Un point du jeu de données est dit aberrant si :

1. Ce n'est pas un point central
2. 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.

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.

En mathématiques, on appelle distance sur un ensemble E toute application d définie sur le produit E² = E×E et à valeurs dans l'ensemble ℝ⁺ des réels positifs,

${\displaystyle d:E\times E\to \mathbb {R} ^{+}}$

vérifiant les propriétés suivantes

Nom	Propriété
symétrie	${\displaystyle \forall (a,b)\in E^{2},\ d(a,b)=d(b,a)}$
séparation	${\displaystyle \forall (a,b)\in E^{2},\ d(a,b)=0\Leftrightarrow a=b}$
inégalité triangulaire	${\displaystyle \forall (a,b,c)\in E^{3},\ d(a,c)\leq d(a,b)+d(b,c)}$

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 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 ${\displaystyle (E,d)}$ :

La boule ouverte est l'ensemble ${\displaystyle B(p,\epsilon )\,}$ des points ${\displaystyle M}$ de l'espace ${\displaystyle E}$ dont la distance au point ${\displaystyle p}$ est strictement inférieure à ${\displaystyle \epsilon }$ :

${\displaystyle B(p,\epsilon )=\left\{M\in E\,\mid \,d(M,p)<\epsilon \right\}}$

Le point ${\displaystyle p}$ est alors appelé centre de la boule ouverte ${\displaystyle B(p,\epsilon )\,}$et ${\displaystyle \epsilon }$ est appelé le rayon de la boule ouverte ${\displaystyle B(p,\epsilon )\,}$.

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

1. La forme des boules est liée à la distance ${\displaystyle d}$ (paramètre implicite à DBSCAN).
2. L'espace couvert dépend du rayon ${\displaystyle \epsilon }$ choisie (paramètre explicite à DBSCAN).

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

Epsilon-Voisinage du point p, pour une distance euclidienne en dimension 2

L'${\displaystyle \epsilon }$-voisinage ${\displaystyle V_{\epsilon }(p)}$ d'un point ${\displaystyle p}$, est l'ensemble des points ${\displaystyle q}$ du jeu de données ${\displaystyle D}$ situés dans la boule ouverte centrée en ${\displaystyle p}$ et de rayon ${\displaystyle \epsilon }$ :

${\displaystyle V_{\epsilon }(p)=\left\{q\in D\,\mid \,d(q,p)<\epsilon \right\}}$

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

1. La distance ${\displaystyle d}$ entre les points ${\displaystyle p}$ et ${\displaystyle q}$
2. Le rayon de recherche ${\displaystyle \epsilon }$ autour du point ${\displaystyle p}$

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

Un ${\displaystyle \epsilon }$-voisinage ${\displaystyle V_{\epsilon }(p)}$ est dit dense si son cardinal est supérieur ou égal à ${\displaystyle minPts}$.

${\displaystyle \mid V_{\epsilon }(p)\mid \geqslant minPts}$

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

1. Le nombre minimum de points ${\displaystyle minPts}$ pour qu'un voisinage soit désigné dense.
2. Le rayon du voisinage ${\displaystyle \epsilon }$ autour du point ${\displaystyle p}$ considéré.
3. La distance ${\displaystyle d}$ entre points.

En reprenant l'illustration précédente, ${\displaystyle \epsilon }$ est fixé. Si ${\displaystyle minPts}$ est fixé à 3 points alors le voisinage considéré est clairement dense. À l’inverse si ${\displaystyle minPts}$ est fixé à 50 points alors le voisinage n'est clairement pas dense.

Les 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é.

Un point ${\displaystyle q}$ du jeu de données ${\displaystyle D}$ est directement accessible par densité depuis un autre point ${\displaystyle p}$ si :

1. ${\displaystyle V_{\epsilon }(p)}$ est dense
2. ${\displaystyle q\in V_{\epsilon }(p)}$

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 ${\displaystyle p}$ vers le point ${\displaystyle q}$.

Un point ${\displaystyle q}$ du jeu de données ${\displaystyle D}$ est accessible par densité depuis un autre point ${\displaystyle p}$ s'il existe une séquence ordonnée de points ${\displaystyle (p_{1},p_{2},...,p_{n})}$ tel que :

1. ${\displaystyle p_{1}=p}$
2. ${\displaystyle p_{i+1}}$ est directement accessible par densité depuis ${\displaystyle p_{i}}$
3. ${\displaystyle p_{n}=q}$

Un point ${\displaystyle q}$ est accessible par densité depuis un autre points ${\displaystyle p}$ s'il existe un chemin fléché vers de ${\displaystyle p}$ vers ${\displaystyle q}$.

Un point ${\displaystyle q}$ du jeu de données ${\displaystyle D}$ est densément connecté à un autre point ${\displaystyle p}$ si :

1. ${\displaystyle o\in D}$
2. ${\displaystyle p}$ est accessible par densité depuis ${\displaystyle o}$
3. ${\displaystyle q}$ est accessible par densité depuis ${\displaystyle o}$

Un point ${\displaystyle q}$ et un point ${\displaystyle p}$ sont densément connecté s'il existe deux chemins fléché qui partent d'un même point ${\displaystyle o}$ pour aller respectivement vers les points ${\displaystyle p}$ et ${\displaystyle q}$.