Wie sind Cluster von DBSCAN manchmal nicht konvex?

Question

Ich benutze Clustering in meiner Tasche mit ML -Techniken seit einiger Zeit und habe noch nie eine befriedigende Antwort auf diese Frage gefunden.

In DBSCAN definieren wir einen maximalen Radius, mit dem Cluster gebildet werden können. Der Algorithmus scannt den Raum und die Gruppierung zusammen, die alle voneinander erreichbar sind. Wir können jedoch manchmal einen nicht konvexen Cluster haben.

Meine Verwirrung geht davon aus, wie der Begriff eines "Radius", der ein konvexes Objekt beschreibt, eine Eingabe in einen Algorithmus sein kann, der zu einem nicht konvexen Objekt führt?

Answer 1

Ein Cluster in dbscan besteht aus mehrere Kernpunkte.

Der Radius ist der Bereich, der von einem einzigen Kernpunkt bedeckt ist, aber zusammen mit Nachbarkernpunkten wird die Form viel komplexer. Insbesondere können sie viel größer sein als Epsilon, daher sollten Sie einen kleinen Wert auswählen und sich auf diese "Cover" -Funktionalität verlassen.

Wikipedia hat ein Beispiel für einen nicht konvexen Cluster

Answer 2

Ich denke, es ist nicht konvex, da die jeweilige Clusterzuweisung, die Sie bei der Anwendung von dbscan erhalten, von der Reihenfolge abhängt, die Sie durch die Daten durchqueren.

Versuchen wir es mit einem Beispiel zu veranschaulichen. Betrachten Sie diesen Datensatz:

Sie möchten DBSCAN mit Radius $ R = 3 $ und $ text {min_pts} = 4 $ ausführen, also erhalten Sie Folgendes:

Der Punkt in der Mitte ist kein Kernpunkt, da es nur 3 Punkte hat, nicht 4 und wir nur zwei Kernpunkte haben. Und je nachdem, wie Sie die Datenpunkte durchqueren, erhalten Sie möglicherweise unterschiedliche Clusterzuweisungen:

Das obere Bild zeigt das Ergebnis, das wir durch Überqueren von links nach rechts und das untere Bild erhalten haben-indem wir nach rechts nach links überqueren.

Anscheinend würden diese beiden Ergebnisse dem gleichen Wert der Kostenfunktion entsprechen, daher hat die Kostenfunktion mehrere Minima und sie ist nicht konvex.