Une routine pour choisir eps et minPts pour DBSCAN

14

DBSCAN est l'algorithme de clustering le plus cité selon certaines publications et il peut trouver des clusters de formes arbitraires en fonction de la densité. Il a deux paramètres eps (comme rayon de voisinage) et minPts (comme voisins minimum pour considérer un point comme point central) dont je crois que cela dépend fortement.

Existe-t-il une méthode de routine ou couramment utilisée pour choisir ces paramètres?

clustering dbscan Mehraban
la source
1
Notez qu'il y a une question similaire sur Stack Overflow : Choisir eps et minpts pour DBSCAN (R)?
gung - Rétablir Monica

Réponses:

11

Il existe de nombreuses publications qui proposent des méthodes pour choisir ces paramètres.

Le plus notable est OPTICS, une variation DBSCAN qui supprime le paramètre epsilon; il produit un résultat hiérarchique qui peut être considéré comme "exécutant DBSCAN avec tous les epsilon possibles".

Pour minPts, je suggère de ne pas compter sur une méthode automatique, mais sur votre connaissance du domaine .

Un bon algorithme de clustering a des paramètres qui vous permettent de le personnaliser selon vos besoins.

Un paramètre que vous avez négligé est la fonction de distance. La première chose à faire pour DBSCAN est de trouver une bonne fonction de distance pour votre application . Ne comptez pas sur la distance euclidienne comme étant la meilleure pour chaque application!

A QUIT - Anony-Mousse
la source
Bien que l'utilisateur puisse choisir la fonction de distance, je doute que ce soit un paramètre.
Mehraban
1
Bien sûr que oui. C'est autant un paramètre que la fonction noyau pour toute autre méthode noyauée (vous pouvez en fait noyauer DBSCAN de cette manière), et d'après mon expérience, d'autres distances telles que Canberra ou Clark peuvent améliorer considérablement les résultats .
A QUIT - Anony-Mousse
Je ne sous-estime pas l'influence de la fonction de distance sur le clustering, mais je pense que c'est en quelque sorte général, non spécifique à dbscan ou à tout autre algorithme de clustering; tandis que eps et minPts sont explicitement des paramètres dbscan.
Mehraban
1
Il existe également de nombreux algorithmes non basés sur la distance. Et lorsque vous considérez que minPts est le même que, par exemple, kpour la classification du plus proche voisin, vous pouvez dire la même chose pour le paramètre minPts. Je suppose que la principale différence est que pour la distance, il y a un défaut "souvent" sensible: la distance euclidienne; alors que pour minPts, la valeur sera spécifique aux données.
A QUIT - Anony-Mousse
1
OPTICS lui-même ne vous donnera pas de partitions, mais un ordre de cluster. Pour obtenir des partitions, utilisez l'extraction xi décrite dans le document OPTICS. Voir chaque article sur les variantes pour comprendre les différences.
A QUIT - Anony-Mousse