Comment les groupes de dbscan parfois non convexe?

Question

J'utilise le regroupement dans mon sac de techniques ML pour un certain temps maintenant, et je ne l'ai jamais trouvé une réponse satisfaisante à cette question.

dbscan, on définit un rayon maximal avec lequel pour former des amas. L'algorithme va scanner les points ensemble et l'espace de groupe qui sont tous accessibles les uns des autres. Cependant, on peut parfois se retrouver avec un groupe non-convexe.

Ma confusion est autour de la façon dont la notion d'un « rayon », qui décrit un objet convexe, peut être une entrée à un algorithme qui se traduit par un objet non-convexe?

Answer 1

Une grappe en dbscan consiste en multiple points de base.

Le rayon est la zone couverte par un seul point de base, mais en même temps que les points de base voisine la forme sera beaucoup plus complexe. En particulier, ils peuvent être beaucoup plus grande que epsilon, donc vous devez choisir une petite valeur, et de compter sur cette fonctionnalité « de couverture ».

Wikipédia a un exemple de non -convex groupe

Answer 2

Je pense qu'il est non-convexe, car l'affectation de groupe particulier que vous obtenez lors de l'application dbscan dépend de l'ordre que vous traverserez les données.

L'essai Let pour illustrer avec un exemple. Considérez cet ensemble de données:

Vous voulez exécuter dbscan avec un rayon $ r = 3 $ et le texte $ \ {} = min_pts de 4 $, vous obtenez ceci:

Le point au centre n'est pas un point de base, car il n'a que 3 points, pas 4, et nous avons seulement deux points de base. Et selon la façon dont vous traversez les points de données, vous pouvez obtenir différentes affectations de cluster:

La photo du haut montre le résultat que nous obtiendrions en traversant de gauche à droite, et l'image de fond -. En traversant de droite à gauche

Apparemment, ces deux résultats correspondrait à la même valeur de la fonction de coût, donc la fonction de coût a plusieurs minima et il n'est pas convexe.