Eine Routine zur Auswahl von eps und minPts für DBSCAN

13

DBSCAN ist laut einiger Literatur der am häufigsten zitierte Cluster-Algorithmus und kann beliebige Formcluster basierend auf der Dichte finden. Es hat zwei Parameter eps (als Nachbarschaftsradius) und minPts (als minimale Nachbarn, um einen Punkt als Kernpunkt zu betrachten), von denen ich glaube, dass sie in hohem Maße davon abhängen.

Gibt es eine Routine oder eine allgemein verwendete Methode, um diese Parameter auszuwählen?

clustering dbscan Mehraban
quelle
1
Beachten Sie, dass es eine ähnliche Frage an ist Stack - Überlauf : Die Wahl eps und MinPts für DBSCAN (R)?
gung - Wiedereinsetzung von Monica

Antworten:

11

Es gibt zahlreiche Veröffentlichungen, in denen Methoden zur Auswahl dieser Parameter vorgeschlagen werden.

Am bemerkenswertesten ist OPTICS, eine DBSCAN-Variante, die den Parameter epsilon überflüssig macht. Es wird ein hierarchisches Ergebnis erzeugt, das grob als "Ausführen von DBSCAN mit jedem möglichen epsilon" angesehen werden kann.

Für MinPts, ich schlage nicht auf einem automatischen Verfahren verlassen, sondern auf Ihrem Domain - Wissen .

Ein guter Clustering-Algorithmus verfügt über Parameter, mit denen Sie ihn an Ihre Bedürfnisse anpassen können.

Ein Parameter, den Sie übersehen haben, ist die Distanzfunktion. Das erste, was Sie für DBSCAN tun müssen, ist, eine gute Distanzfunktion für Ihre Anwendung zu finden . Verlassen Sie sich nicht darauf, dass der euklidische Abstand für jede Anwendung der beste ist!

Hat aufgehört - Anony-Mousse
quelle
Obwohl der Benutzer die Distanzfunktion auswählen kann, bezweifle ich, dass es sich um einen Parameter handelt.
Mehraban
1
Natürlich ist es das. Es ist genauso ein Parameter wie die Kernelfunktion für jede andere kernelisierte Methode (Sie können DBSCAN tatsächlich auf diese Weise kernelisieren), und meiner Erfahrung nach können andere Entfernungen wie Canberra oder Clark die Ergebnisse erheblich verbessern .
Hat aufgehört - Anony-Mousse
Ich unterschätze den Einfluss der Distanzfunktion auf das Clustering nicht, aber ich denke, es ist irgendwie allgemein, nicht spezifisch für dbscan oder jeden anderen Clustering-Algorithmus. während eps und minPts explizit dbscan-Parameter sind.
Mehraban
1
Es gibt auch viele nicht entfernungsbasierte Algorithmen. Und wenn Sie minPts als identisch mit z. B. der kKlassifizierung des nächsten Nachbarn ansehen, können Sie dies auch für den minPts-Parameter sagen. Ich denke, der Hauptunterschied ist, dass es für die Entfernung eine "oft" sinnvolle Voreinstellung gibt: Euklidische Entfernung; wohingegen für minPts der Wert datenspezifisch ist.
Hat aufgehört - Anony-Mousse
1
OPTICS selbst gibt Ihnen keine Partitionen, sondern eine Clusterreihenfolge. Verwenden Sie zum Abrufen von Partitionen die im OPTICS-Dokument beschriebene xi-Extraktion. Sehen Sie sich die einzelnen Varianten an, um die Unterschiede zu verstehen.
Hat aufgehört - Anony-Mousse