ALGORITHME DBSCAN

6️⃣ minutes de lecture 📗 📗 📗
Classification non supervisée

Je vous présente ici un algorithme de partitionnement de données (clustering) utilisé en data-science : L’algorithme DBSCAN (density-base spacial clustering of applications with noise). Il propose une approche différente de l’algorithme des $k-means$. Il permet notamment de traiter des datasets de forme quelconque et il permet de séparer les clusters du bruit éventuel.

Présentation

L’algorithme de DBSCAN ( density-bases spatial clustering of applications with noise) a été introduit en 1996 par Martin Ester, Hans-peter Kriegel, Jorg Sander et Xiaowei Xu et il a été reconnu pour sa contribution scientifique durable en 2014. Cet algorithme de partionnement de données se base sur la densité pour identifier les cluster et éliminer le bruit.

Déroulement de l’algorithme

Il utilise généralement la distance euclidienne comme mesure de dissimilarité et nécessite essentiellement 2 paramètres :

$ϵ$ : C’est la distance maximale séparant deux points pour qu’ils soient considérés comme proches et pouvoir appartenir au même cluster.
$Minpts$ : C’est le nombre minimum de points que doit contenir un regroupement pour être considéré comme un cluster.

Avec ces paramètres renseignés, l’algorithme part d’un point arbitrairement choisi et évalue tous les points à proximité : S’il y a au minimum $Minpts$ point(s) proche(s) de ce point au sens de $ϵ$ alors un cluster est formé, sinon, ce point est considéré comme du bruit pour l’instant. Un point initialement considéré comme du bruit par DBSCAN peut être ultérieurement rattaché à un autre cluster : il peut appartenir au voisinage d’un autre point, qui lui contient plus de $Minpts$ points, comme sur la figure suivante :

Dans l’image ci-dessus, si $Minpts=4$, le point orange n’est pas un point intérieur car son epsilon-voisinage ne contient pas suffisamment de points. Par contre, il appartient à l’epsilon-voisinage du point rose qui, lui contient plus de $Minpts$ points ; ainsi le point orange sera assigné au même cluster que le point rose, plutôt que d’être considéré comme du bruit.

DBSCAN fonction de la manière suivante :

Etape 1️⃣

DBSCAN commence par un point de départ choisi au hasard parmi les points de données qui n’a pas été visité. Le voisinage de ce point est extrait en utilisant une distance $ϵ$ .

Etape 2️⃣

S’il y a au moins $Minpts$ de point(s) dans son voisinage, le processus de mise en cluster démarre et le point de données actuel devient le premier point du nouveau cluster. Sinon, le point sera considéré pour le moment comme bruit. Dans les deux cas, ce point est marqué comme visité.

Etape 3️⃣

Pour ce premier point du nouveau cluster, les points situés dans son voisinage à distance se joignent également au même cluster. Cette procédure est ensuite répétée pour tous les nouveaux points qui viennent d’être ajoutés au groupe de cluster.

Etape 4️⃣

les étapes 2️⃣ et 3️⃣ sont répétées jusqu’à ce que tous les points du cluster soient déterminés, c’est-à-dire que tous les points à proximité du $ϵ$ voisinage du cluster ont été visités et étiquetés.

Etape 5️⃣

Une fois terminé avec le cluster actuel, un nouveau point non visité est récupéré et traité, ce qui permet de découvrir un nouveau cluster ou du bruit. Ce processus se répète jusqu’à ce que tous les points soient marqués comme étant visités. A la fin de tous les points visités, chaque points a été marqué comme appartenant à un cluster ou comme étant du bruit.

Estimations des paramètres

Le choix des paramètres $Minpts$ et $ϵ$ est crucial. En effet, si $ϵ$ a une petite valeur, de nombreux points seront considérés comme des points aberrants car ils ne seraient pas des points centraux ou des points frontières. Par contre, Une valeur élevée pour $ϵ$ peut entraîner la présence d’un grand nombre de points dans le même cluster.

On définit la fonction ($k-distance(p)$ ) : distance du point $p$ à son $k$-plus proche voisin (l’utilisateur choisit la valeur $k$).

Par exemple, si l’utilisateur choisit la valeur de $k=4$, la distance 4-plus proche du point $p$ est la distance de $p$ à son voisin 4-plus proche comme on peut le voir sur la figure ci-dessous :

La méthode proposée ici pour déternimer la valeur optimale de $ϵ$ consiste à calculer les ($k-dist$) voisins les plus proche dans une matrice de points.
L’ idée est de calculer la moyenne des distances de chaque point par rapport à ses $k$ voisins les plus proches. La valeur de $k$ sera spécifiée par l’utilisateur et correspond à $Minpts$ , ensuite ces ($k-dist$) sont tracées dans un ordre croissant.
Le but est de déterminer le « genou¹ », qui correspond au paramètre $ϵ$ optimal.

La valeur Optimale de $MinPts$ est déterminée de la manière suivante : $$Minpts=\frac{\sum _i^n{P}_i}{n}$$

$P_i$ est le nombre de points dans le voisinage $ϵ$ du point $i$, et $n$ est le nombre de points du données.

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é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 et le choix des valeurs de ces paramètres ($MinPts$ et $ϵ$) reste très complexes.

Illustration

CODES² R

Cliquez ici !!!
👇👇 👇👇

DBSCAN

APPLICATION RSHINY³

Cliquez ici !!!
👇👇 👇👇

BIBLIOGRAPHIE

1- Guillaume, Cleuziou, Une méthode de classification non-supervisée pour l’apprentissage de règles et la recherche d’information . Université d’Or- léans, 2004. Français. fftel-00084828

2- Lebarbier, T. Mary-Huard, Classification non supervisée

3- Ricco RAKOTOMALALA, Algorithmes des K-medoides, Université de lyon 2

4- AIME NDJENG, Implémentation sur R: Algorithme de pam, Dbscan et Hdbscan, Euria, brest

5- https://datascientest.com/machine-learning-clustering-dbscan

6- https://openclassrooms.com/fr/courses/4379436-explorez-vos-donnees-avec-des-algorithmes-non-

supervises/4379571-partitionnez-vos-donnees-avec-dbscan

7- https://miro.medium.com/v2/resize:fit:1000/1*

yDUZAvQb39vrf9apjrRU5A.gif

https://khayyam.developpez.com/articles/data-science/clustering/dbscan/

Footnotes

1. Un genou correspond est un seuil où un changement brusque se produit le long de la courbe de distance $k$.

2. C’est une implémentation très très très basique de l’algorithme de dbscan sous R. Le code peut etre optimisé en minimisant les boucle…….

3. L’application est adaptée pour un écran type ordinateur.