Je vous présente ici un algorithme de partitionnement de données (clustering) utilisé en data-science : L’algorithme HDBSCAN. Il propose une approche différente de l’algorithme de DBSCAN . Il permet notamment de traiter des datasets de forme quelconque et il permet de séparer les clusters du bruit éventuel.
Présentation
Cet algorithme est une version améliorée de l’algorithme de DBSCAN qui ne nécessite plus de préciser un seuil de distance minimale de proximité mais uniquement une taille minimale des clusters à former. En effet, l’algorithme réalise plusieurs fois la procédure de DBSCAN en faisant varier les valeurs d’epsilon afin d’obtenir des clusters avec la meilleure stabilité sur epsilon. Il permet ainsi de trouver des clusters de densités variables. HDBSCAN est un algorithme de clustering développé par Ricardo CAM- PELLO, Davoud MOULAVI et Joerg SANDER du département des sciences informatiques de l’Université de l’Alberta, Edmonton au Canada. Il trans- forme DBSCAN en un algorithme de clustering hiérarchique dont il est en- suite extrait des clusters plats selon un critère de stabilité. Pour y parvenir, HDBSCAN suit un processus en 5 grandes étape.
Etapes de l’algorithmes
Etape 1 : Construction d’une nouvelle métrique d’évaluation des zones denses.
On définit sur nouvelle mesure de distance appelée distance d’accessibilité mutuelle (dacc(.,.)) et a pour but d’accentuer l’écart dans l’espace entre les points appartenant à une zone dense et ceux appartenant à une zone clairse- mée. elle se construit à partir de la distance centrale (dcent(.)) correspondant à la distance maximale entre un point et les MinPts points qui l’entoure. Ainsi, pour deux points a et b, la distance d’accessibilité mutuelle se traduit par :
dacc(a, b) = max(dcent(a), dcent(b), d(a, b)) .
Nous pouvons illustrer avec ce schéma ci dessous :
Etape 2 : Construction d’arbres minimums couvrants
Il utilise généralement la distance euclidienne comme mesure de dissimilarité et nécessite essentiellement 2 paramètres :
La seconde étape consiste à créer des groupes de points minimisant le che- min les reliant. Des grappes de connectivité sont alors construites illustrant les différentes possibilités de liaisons. Pour y parvenir, l’algorithme utilise la théorie des graphes pour obtenir des arbres couvrants minimums de chaque grappe mère préalablement constituées. Il existe plusieurs algorithmes permettent de réaliser l’arbre minimum couvrant, mais nous nous contenterons de présenter uniquement l’algorithme de Kruskal voir figure suivante.
Etape 3 : Hiérarchisation des Clusters
Cette étape consiste à créer une arborescence à partie de la longueur des branches reliant les points des arbres minimums couvrants en construisant une hiérarchie dans les clusters sous forme de dendrogramme (Figure 11).
Etape 4 : Condensation de l’arborescence des clusters
On introduit un nouveau paramètre mclSize, qui correspond au nombre mi- nimal d’éléments dans un cluster. L’idée ici va être de lisser les clusters, en considérant que les clusters créés lors d’une séparation sont du bruit s’ils n’ont pas mclSize points, et donc ils ne constituent pas un vrai split. A chaque nouvelle proposition de sépara- tion du dendrogramme , si le nouveau cluster proposé ne correspond pas à la taille minimale exigée, la segmentation est supprimée et le cluster à former est considéré comme une partie du cluster précédent. A contrario, la segmentation est retenue et un nouveau cluster est créé si celui-ci contient au moins mclSize points.
Etape 5 : Extraction des clusters plats
Lorsque vous utilisez une faible valeur de mclSize pour regrouper des ensembles de données avec des densités variables, il peut arriver que la méthode basée sur la stabilité de HDBSCAN extrait un grand nombre de petits clusters dans des régions avec des points de données denses. Pour résoudre le problème de la sélection de clusters non souhaitée à des niveaux hiérarchiques bas, on introduit l’application d’un seuil de distance ε1 comme paramètre supplémentaire pour HDBSCAN. Ainsi Pour formaliser le processus de sélection de clusters basé sur ε1, nous utilisons les termes ε1 stable. Un Cluster Ci avec i ∈ [2, k] est dit stable si le niveau auquel cluster Ci apparaît soit supérieur à notre seuil ε1 choisit. Ainsi, pour un cluster donné, s’il présente une stabilité supérieur à notre seuil ε1, la segmentation est retenue en l’état , dans le cas contraire les clusters fils ne sont pas considérés comme de nouveaux clusters à retenir Les clusters plats recherchés sont ainsi obtenus et tout point n’appartenant pas à un cluster sélectionné est considéré comme un bruit.
Illustration
Nous avons programmé cet algorithme sous R et Rshiny, pour obtenir l'ensemble des codes veuillez nous contacter.
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/
Comentarios