Utilisateur:Bouftoubleu/Brouillon

Structure des solutions^[1][modifier | modifier le code]

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[modifier | modifier le code]

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 données.

Les points frontières[modifier | modifier le code]

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

Les points aberrants[modifier | modifier le code]

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 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[modifier | modifier le code]

Voisinage d'un point[modifier | modifier le code]

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[modifier | modifier le code]

Article détaillé : Distance_(mathématiques).

En mathématiques, on appelle distance sur un ensemble $E$ toute application $d$ définie sur le produit $E 2 = E \times 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[modifier | modifier le code]

Article détaillé : Boule_(topologie).

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 :

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

Epsilon-voisinage[modifier | modifier le code]

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 :

La distance $d$ entre les points $p$ et $q$
Le rayon de recherche $\epsilon$ autour du point $p$

Epsilon-voisinage dense[modifier | modifier le code]

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 :

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

Relations basées sur la densité[modifier | modifier le code]

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é[modifier | modifier le code]

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

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

Accessible par densité[modifier | modifier le code]

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 :

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

Densément connecté[modifier | modifier le code]

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

$o\in D$
$p$ est accessible par densité depuis $o$
$q$ est accessible par densité depuis $o$

Classe et cluster[modifier | modifier le code]

Relation d'équivalence[modifier | modifier le code]

Classe d'équivalence[modifier | modifier le code]

Cluster[modifier | modifier le code]

Avantages et inconvénients[modifier | modifier le code]

Avantages[modifier | modifier le code]

Inconvénients[modifier | modifier le code]

↑ (en) Michael Hahsler, Matthew Piekenbrock et Derek Doran, « dbscan : Fast Density-Based Clustering with R », Journal of Statistical Software, vol. 91, n^o 1,‎ 2019 (ISSN 1548-7660, DOI 10.18637/jss.v091.i01, lire en ligne, consulté le 9 mars 2020)

[1] (en) Michael Hahsler, Matthew Piekenbrock et Derek Doran, « dbscan : Fast Density-Based Clustering with R », Journal of Statistical Software, vol. 91, n^o 1,‎ 2019 (ISSN 1548-7660, DOI 10.18637/jss.v091.i01, lire en ligne, consulté le 9 mars 2020)

[1]

Structure des solutions[1][modifier | modifier le code]