Utilisateur:Bouftoubleu/Brouillon

Structure des solutions

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 :

1. Son voisinage est dense

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

Les points frontières

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épendantes de l'ordre d'exploration du jeu de données.

Les points aberrants

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 point 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é pour la localisation des points centraux et l'expansion des clusters.

Distance entre points

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,

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

vérifiant les propriétés suivantes

Nom	Propriété
symétrie	$\forall (a,b)\in E^{2},\ d(a,b)=d(b,a)$
séparation	$\forall (a,b)\in E^{2},\ d(a,b)=0\Leftrightarrow a=b$
inégalité triangulaire	$\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 rayon de epsilon

Dans l'espace usuel comme dans n'importe quel espace métrique $(E,d)$ :

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

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

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

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

Epsilon-voisinage

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

$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 $d$ entre les points $p$ et $q$
2. Le rayon de recherche $\epsilon$ autour du point $p$

Epsilon-voisinage dense

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

$\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 $minPts$ pour qu'un voisinage soit désigné dense.
2. Le rayon du voisinage $\epsilon$ autour du point $p$ considéré.
3. La distance $d$ entre points.

Relations basées sur la densité

Les relations binaires qui suivent sont utilisés 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 $q$ du jeu de données $D$ est directement accessible par densité depuis un autre point $p$ si :

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

Accessible par densité

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

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

Densément connecté

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

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

Avantages et inconvénients