DBSCAN: Qu'est-ce que c'est? Quand l'utiliser? Comment l'utiliser.

DBSCAN (clustering spatial basé sur la densité des applications avec bruit) est une méthode d’apprentissage populaire non supervisée utilisée dans les algorithmes de construction de modèles et d’apprentissage automatique. Avant d'aller plus loin, nous devons définir ce qu'est une méthode d'apprentissage «non supervisée». Les méthodes d'apprentissage non supervisées existent lorsqu'il n'y a pas d'objectif ou de résultat clair que nous cherchons à trouver. Au lieu de cela, nous regroupons les données en fonction de la similarité des observations. Pour clarifier, prenons Netflix comme exemple. En fonction des émissions précédentes que vous avez regardées dans le passé, Netflix vous recommandera d’émettre des émissions. Quiconque a déjà regardé ou été sur Netflix a vu l’écran ci-dessous avec des recommandations (oui, cette image est prise directement à partir de mon compte Netflix et si vous n’avez jamais regardé Shameless auparavant, je vous suggère d’obtenir cette information dès que possible).

Parce que j’ai regardé ‘Shameless’, Netflix recommande plusieurs autres émissions similaires à regarder. Mais où Netflix rassemble-t-il ces recommandations? Considérant qu’il s’agit de tenter de prédire l’avenir avec ce que je vais regarder ensuite, Netflix n’a rien sur lequel fonder ses prédictions ou ses recommandations (pas d’objectif clair et définitif). Au lieu de cela, Netflix examine d’autres utilisateurs qui ont également regardé «Shameless» dans le passé et examine ce qu’ils ont regardé en plus de «Shameless». Ce faisant, Netflix regroupe ses utilisateurs en fonction de leurs intérêts communs. C'est exactement comme cela que l'apprentissage non supervisé fonctionne. Regrouper simplement les observations en fonction de la similarité, dans l’espoir de tirer des conclusions précises en fonction des grappes.

Retour à DBSCAN. DBSCAN est une méthode de regroupement utilisée dans l'apprentissage automatique pour séparer les regroupements de haute densité des regroupements de faible densité. Étant donné que DBSCAN est un algorithme de regroupement basé sur la densité, il permet de rechercher les zones dans lesquelles les données ont une densité élevée d'observations, par opposition aux zones de données qui ne sont pas très denses en observations. DBSCAN peut également trier les données en grappes de formes variées, un autre avantage non négligeable. DBSCAN fonctionne comme tel:

  • Divise le jeu de données en n dimensions
  • DBSCAN forme pour chaque point du jeu de données une forme à n dimensions autour de ce point de données, puis compte le nombre de points de données contenus dans cette forme.
  • DBSCAN compte cette forme comme un cluster. DBSCAN étend le cluster de manière itérative, en passant en revue chaque point individuel du cluster et en comptant le nombre d'autres points de données à proximité. Prenez le graphique ci-dessous pour un exemple:

En parcourant pas à pas le processus susmentionné, DBSCAN commencera par diviser les données en n dimensions. Une fois que DBSCAN l’a fait, il démarrera à un point aléatoire (dans ce cas, supposons qu’il s’agissait d’un des points rouges) et comptera le nombre de points proches. DBSCAN poursuivra ce processus jusqu'à ce qu'aucun autre point de données ne soit à proximité, puis il tentera de former un second cluster.

Comme vous l'avez peut-être remarqué dans le graphique, il est nécessaire de fournir à DBSCAN quelques paramètres et spécifications avant que celui-ci ne fonctionne. Les deux paramètres à spécifier sont les suivants:

Quel est le nombre minimum de points de données nécessaires pour déterminer un seul cluster?
À quelle distance un point peut-il être du point suivant dans le même cluster?

En revenant au graphique, epsilon est le rayon donné pour tester la distance entre les points de données. Si un point tombe dans la distance epsilon d'un autre point, ces deux points seront dans le même groupe.

En outre, le nombre minimal de points requis est défini sur 4 dans ce scénario. Lors de la lecture de chaque point de données, une grappe est formée tant que DBSCAN trouve 4 points à une distance égale à epsilon.

IMPORTANT: pour qu'un point soit considéré comme un point «principal», il doit contenir le nombre minimum de points dans la distance epsilon. Ainsi, la visualisation ne comporte en réalité que DEUX points essentiels. Consultez la documentation ici et examinez le paramètre min_samples en particulier.

Vous remarquerez également que le point bleu du graphique ne figure dans aucun cluster. DBSCAN NE catégorise pas nécessairement chaque point de données et est donc formidable pour la gestion des valeurs aberrantes dans l'ensemble de données. Permet d'examiner le graphique ci-dessous:

L'image de gauche décrit une méthode de classification plus traditionnelle qui ne prend pas en compte la multidimensionnalité. Alors que la bonne image montre comment DBSCAN peut contourner les données en différentes formes et dimensions afin de trouver des clusters similaires.

L'image de gauche décrit une méthode de classification plus traditionnelle, telle que K-Means, qui ne prend pas en compte la multidimensionnalité. Alors que la bonne image montre comment DBSCAN peut contourner les données en différentes formes et dimensions afin de trouver des clusters similaires. Nous remarquons également dans l'image de droite que les points situés le long du bord extérieur de l'ensemble de données ne sont pas classifiés, ce qui suggère qu'ils sont plus éloignés des données.

Avantages de DBSCAN:

  • Est excellent pour séparer les grappes de haute densité par rapport aux grappes de faible densité dans un jeu de données donné.
  • Est excellent avec la gestion des valeurs aberrantes au sein du jeu de données.

Inconvénients de DBSCAN:

  • Ne fonctionne pas bien lorsqu'il s'agit de grappes de densités différentes. Bien que DBSCAN permette de séparer les grappes à haute densité des grappes à faible densité, DBSCAN se débat avec des grappes de densité similaire.
  • Luttes avec des données de haute dimensionnalité. Je sais, dans tout cet article, j'ai expliqué à quel point DBSCAN est capable de tordre les données en différentes dimensions et formes. Toutefois, DBSCAN ne peut aller jusqu’à présent, si des données ayant trop de dimensions sont utilisées, DBSCAN en souffre.

Ci-dessous, j'ai expliqué comment implémenter DBSCAN en Python, dans lequel j'explique ensuite les métriques et évalue votre modèle DBSCAN.

Implémentation DBSCAN en Python

1. Affecter les données à nos valeurs X
N'oubliez pas que, puisqu'il s'agit d'un apprentissage non supervisé, nous n'avons aucune valeur claire à définir.
2. Instanciation de notre modèle DBSCAN. Dans le code ci-dessous, epsilon = 3 et min_samples sont le nombre minimum de points nécessaires pour constituer un cluster.
3. Stockage des étiquettes formées par le DBSCAN
4. Identifier les points qui constituent nos «points centraux»
5. Calcul du nombre de clusters
6. Calcul du score de la silhouette

Mesures pour mesurer les performances de DBSCAN:

Score de silhouette: Le score de silhouette est calculé en utilisant la distance moyenne intra-groupe entre les points ET la distance moyenne du groupe le plus proche. Par exemple, un cluster avec un grand nombre de points de données très proches les uns des autres (haute densité) ET loin du prochain cluster le plus proche (suggérant que le cluster est très unique par rapport au suivant), aura un score de silhouette élevé . Un score de silhouette va de -1 à 1, -1 étant le pire score possible et 1 le meilleur. Les scores en silhouette de 0 suggèrent des grappes qui se chevauchent.

Inertie: L’inertie mesure la somme des carrés du groupe interne (la somme des carrés est la somme de tous les résidus). L'inertie est utilisée pour mesurer la distance entre les groupes, plus le score d'inertie est bas, mieux c'est. TOUTEFOIS, il est important de noter que l'inertie repose fortement sur l'hypothèse que les grappes sont convexes (de forme sphérique). DBSCAN ne divise pas nécessairement les données en clusters sphériques. L'inertie n'est donc pas une métrique utile pour évaluer les modèles DBSCAN (c'est pourquoi je n'ai pas inclus l'inertie dans le code ci-dessus). L'inertie est plus souvent utilisée dans d'autres méthodes de classification, telles que la classification K-means.

Autres ressources:

Le blog de Naftali Harris est une formidable ressource supplémentaire pour plus d’informations.