Ok, commençons à parler de DBSCAN.
Le clustering spatial d’applications basé sur la densité avec bruit (DBSCAN) est un algorithme de clustering de données bien connu et couramment utilisé dans le domaine de l’exploration de données et de l’apprentissage automatique.
Sur la base d’un ensemble de points (pensons à un espace bidimensionnel comme illustré sur la figure), DBSCAN regroupe les points proches les uns des autres en fonction d’une mesure de distance (généralement la distance euclidienne) et d’un nombre minimum de points. Il marque également comme aberrants les points qui se trouvent dans des régions à faible densité.
Paramètres:
L’algorithme DBSCAN nécessite essentiellement 2 paramètres:
eps : spécifie la proximité des points entre eux pour être considérés comme faisant partie d’un cluster. Cela signifie que si la distance entre deux points est inférieure ou égale à cette valeur (eps), ces points sont considérés comme voisins.
minPoints : le nombre minimum de points pour former une région dense. Par exemple, si nous définissons le paramètre minPoints comme 5, alors nous avons besoin d’au moins 5 points pour former une région dense.
Estimation des paramètres:
L’estimation des paramètres est un problème pour chaque tâche de data mining. Pour choisir de bons paramètres, nous devons comprendre comment ils sont utilisés et avoir au moins une connaissance préalable de base sur le jeu de données qui sera utilisé.
eps : si la valeur eps choisie est trop petite, une grande partie des données ne seront pas regroupées. Elle sera considérée comme aberrante car ne satisfaisant pas le nombre de points pour créer une région dense. D’un autre côté, si la valeur choisie est trop élevée, les clusters fusionneront et la majorité des objets seront dans le même cluster. L’eps doit être choisi en fonction de la distance de l’ensemble de données (nous pouvons utiliser un graphique de k-distance pour la trouver), mais en général, les petites valeurs d’eps sont préférables.
minPoints : En règle générale, un minimum minPoints peut être dérivé d’un nombre de dimensions (D) dans l’ensemble de données, comme minPoints ≥ D + 1. Des valeurs plus grandes sont généralement meilleures pour les ensembles de données avec du bruit et formeront des clusters plus significatifs. La valeur minimale de minPoints doit être de 3, mais plus l’ensemble de données est grand, plus la valeur de minPoints qui doit être choisie est grande.
Vous pouvez trouver plus d’informations sur l’estimation des paramètres ici.
Pourquoi devrions-nous utiliser DBSCAN ?
L’algorithme DBSCAN doit être utilisé pour trouver des associations et des structures dans les données qui sont difficiles à trouver manuellement mais qui peuvent être pertinentes et utiles pour trouver des modèles et prédire des tendances.
Les méthodes de clustering sont généralement utilisées en biologie, en médecine, en sciences sociales, en archéologie, en marketing, en reconnaissance de caractères, en systèmes de gestion, etc.
Réfléchissons à une utilisation pratique de DBSCAN. Supposons que nous avons un e-commerce et que nous voulons améliorer nos ventes en recommandant des produits pertinents à nos clients. Nous ne savons pas exactement ce que nos clients recherchent, mais sur la base d’un ensemble de données, nous pouvons prédire et recommander un produit pertinent à un client spécifique. Nous pouvons appliquer le DBSCAN à notre ensemble de données (basé sur la base de données du commerce électronique) et trouver des clusters basés sur les produits que les utilisateurs ont achetés. En utilisant ces clusters, nous pouvons trouver des similitudes entre les clients, par exemple, le client A a acheté 1 stylo, 1 livre et 1 ciseau et le client B a acheté 1 livre et 1 ciseau, alors nous pouvons recommander 1 stylo au client B. Ceci n’est qu’un petit exemple d’utilisation de DBSCAN, mais il peut être utilisé dans de nombreuses applications dans plusieurs domaines.
Comment pouvons-nous facilement l’implémenter ?
Comme je l’ai déjà écrit (conseil : ne croyez pas à tout ce que j’écris) le DBSCAN est un algorithme bien connu, par conséquent, vous n’avez pas besoin de vous soucier de l’implémenter vous-même. Vous pouvez utiliser l’une des bibliothèques/packages que l’on trouve sur Internet. Voici une liste de liens où vous pouvez trouver l’implémentation de DBSCAN : Matlab, R, R, Python, Python.
J’ai également développé une application (en portugais) pour expliquer le fonctionnement de DBSCAN de manière didactique. L’application a été écrite en C++ et vous pouvez la trouver sur Github.
.