DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

Principes de la méthode DBSCAN

DBSCAN est l’acronyme de Density-based Spatial Clustering of Applications with Noise proposé par Ester, Kriegel, Sander et Xu en 1996. C'est la méthode d'apprentissage non supervisée la plus utilisée parmi les méthodes de classification par densité. Il y a plusieurs avantages au fait d'utiliser ce type de méthode, comme leur capacité à créer un nombre de classes non connu au préalable, à créer des classes non convexes et à reconnaître des anomalies.

Pour utiliser la méthode de DBSCAN, 2 paramètres sont attendus :

• ϵ > 0 ;
• le nombre minimum de points souvent appelé MinPts > 0

Plusieurs définitions permettent de comprendre la création d'une nouvelle classe. On commence par définir et compter les voisins que possèdent chaque point. On définit un voisin n'importe quel point p de notre jeu de données d'apprentissage qui a une distance inférieure ou égale à ϵ d'un point q.

Remarque : Par définition le point q est son propre voisin.

Chaque point peut être défini de 3 manières différentes avec l'algorithme DBSCAN :

• point central : si un point possède plus ou autant de voisins que le nombre minimum de points (entré en paramètre) alors il est considéré comme un point central ;
• point de frontière : si un point possède moins de voisins que le nombre minimum de points mais qu'il est voisin d'un point central alors il est considéré comme un point de frontière ;
• bruit : si un point n'est ni un point central ni un point de frontière, il s'agit alors d'un bruit.

On dit qu'un point p est atteignable directement par densité à partir d'un point q, si q est un point central et p est un voisin de q. Un point p est atteignable par densité lorsqu'il existe une chaîne de points qui sont chacun atteignables directement par densité à partir du point précédent. On dit aussi que deux points p et q sont connectés par densité s'il existe un point o à partir duquel p et q sont atteignables par densité.

Enfin, Ester et al. définissent une classe comme étant un sous-ensemble de notre jeu de données suivant deux conditions :

• dans le cas où p appartient à une classe C, si un point q est atteignable par densité à partir du point p, alors q appartient à la classe C ;
• la classe C doit respecter la condition que tous ses points doivent être mutuellement connectés par densité.

L'algorithme DBSCAN

L'algorithme DBSCAN va parcourir tous les points de notre jeu de données et va les marquer comme visités au fur et à mesure.

Dès qu'un premier point central est visité, une première classe est créée (nommée classe 1) ce point est alors affecté à la classe 1.

Par la suite, il va parcourir les voisins du point central en les affectant à la classe 1. Si l'algorithme trouve dans les voisins un autre point central, il va à son tour parcourir ses propres voisins et les affecter à la classe 1. Cette étape permet d'étendre la classe (Expand Cluster). L'algorithme arrête d'étendre la classe 1 lorsque tous les points atteignables par densité ont été parcourus.

L'algorithme continue de parcourir les points non visités du jeu de données, à la recherche d'un point central qui permettra de créer la classe 2, il pourra l'étendre si possible et ainsi de suite...

Enfin, tous les points qui ont été visités mais qui n'ont pas été affectés à une classe sont alors considérés comme des bruits.

Options de la fonctionnalité DBSCAN dans XLSTAT

Prédiction avec DBSCAN

La méthode de DBSCAN permet de prédire la classe de nouvelles observations.

Cela nécessite tout d'abord de trouver les voisins de chaque nouvelle observation dans le jeu de données d'apprentissage. Si la nouvelle observation possède un voisin qui a été considéré comme un point central lors de l'apprentissage, on affecte alors la nouvelle observation à la même classe que ce point central.

Si la nouvelle observation ne possède aucun point central dans ses voisins alors elle est considérée comme un bruit.

Remarque importante : l'ordre de visite des points peut influencer sur le résultat de l'affectation des points de frontière lors de l'apprentissage et de la prédiction.

L'arbre k-dimensionnel

XLSTAT vous propose d'utiliser un arbre k-dimensionnel lorsque vous ne possédez que des données quantitatives (Bentley, 1975). L'arbre va permettre de ne pas calculer toutes les distances pour trouver tous les voisins dans un rayon de taille epsilon.

L'arbre k-dimensionnel est un arbre binaire qui est construit en triant les points à partir d'une dimension et va diviser l'espace en 2 à partir de la médiane. Les points qui ont une valeur inférieure ou égale à la médiane dans cette dimension seront stockés dans le nœud fils gauche tandis que les points qui ont une valeur supérieure à la médiane seront stockés dans le nœud fils droit. La construction de l'arbre s'arrête lorsqu'il ne reste qu'un point dans un nœud.

Les formules de distance

XLSTAT propose différentes manières de calculer les distances pour pouvoir utiliser tout type de données.

Lorsque seulement des variables quantitatives sont en entrée, 5 formules de distance peuvent être utilisées :

• distance euclidienne ;
• distance de Minkowski ;
• distance de Manhattan ;
• distance de Chebychev ;
• distance de Canberra.

Lorsque seulement des variables qualitatives sont entrées, la distance d'intersection est utilisée.

Si les deux types de variables sont utilisées, la distance HEOM (Heterogeneous Euclidean Overlap Metric) est considérée.

Résultats de la fonctionnalité DBSCAN dans XLSTAT

Statistiques descriptives : le tableau des statistiques descriptives présente des statistiques simples pour toutes les variables sélectionnées. Le nombre de valeurs manquantes, le nombre de valeurs non manquantes, la moyenne, l'écart-type sont affichés pour les variables quantitatives. Pour les variables qualitatives, les catégories avec leur fréquence respective et pourcentage sont affichées.

Matrice de corrélation : ce tableau est affiché afin de vous permettre d'avoir un aperçu des corrélations entre les différentes variables sélectionnées.

Nombre d'objets par classe : ce tableau est affiché pour avoir un aperçu de la taille de chaque classe et du nombre de bruits.

Résultats associés aux matrices de distance : une ou deux matrices de distance seront affichées si l'option de prédiction est activée. La première matrice de distance correspond aux distances entre chaque point de l'échantillon d'apprentissage. La seconde matrice de distance correspond aux distances entre les nouvelles observations et les observations de l'échantillon d'apprentissage.

Résultats associés aux objets : les classes qui ont été associées à chaque observation en utilisant l'algorithme DBSCAN sont affichées pour les échantillons d'apprentissage et de prédiction. Si la classe est 00 cela signifie que l'observation est considérée comme un bruit. De plus, le coefficient de silhouette de chaque observation est affiché dans la deuxième colonne (si l'option est activée).

Un graphique des coefficients de silhouette est affiché si l'option est activée. Les observations sont regroupées par classes dans l'ordre décroissant par rapport au coefficient de silhouette.

Résultats associés aux objets triés par classe : ce tableau affiche les observations rangées par classe.