Beginnen wir mit DBSCAN.
Density-based spatial clustering of applications with noise (DBSCAN) ist ein bekannter Datencluster-Algorithmus, der häufig im Data Mining und beim maschinellen Lernen eingesetzt wird.
Ausgehend von einer Menge von Punkten (denken wir uns einen zweidimensionalen Raum, wie in der Abbildung dargestellt), gruppiert DBSCAN Punkte, die einander nahe sind, auf der Grundlage eines Abstandsmaßes (normalerweise euklidischer Abstand) und einer Mindestanzahl von Punkten. Außerdem werden Punkte, die sich in Regionen mit geringer Dichte befinden, als Ausreißer markiert.
Parameter:
Der DBSCAN-Algorithmus benötigt im Wesentlichen 2 Parameter:
eps: gibt an, wie nahe Punkte beieinander liegen müssen, um als Teil eines Clusters zu gelten. Das heißt, wenn der Abstand zwischen zwei Punkten kleiner oder gleich diesem Wert (eps) ist, werden diese Punkte als Nachbarn betrachtet.
minPoints: die Mindestanzahl von Punkten, um eine dichte Region zu bilden. Wenn wir zum Beispiel den minPoints-Parameter auf 5 setzen, dann brauchen wir mindestens 5 Punkte, um eine dichte Region zu bilden.
Parameterschätzung:
Die Parameterschätzung ist ein Problem für jede Data-Mining-Aufgabe. Um gute Parameter zu wählen, müssen wir verstehen, wie sie verwendet werden, und zumindest ein grundlegendes Vorwissen über den zu verwendenden Datensatz haben.
eps: Wenn der eps-Wert zu klein gewählt wird, wird ein großer Teil der Daten nicht geclustert. Er wird als Ausreißer betrachtet, da die Anzahl der Punkte nicht ausreicht, um eine dichte Region zu bilden. Ist der gewählte Wert hingegen zu hoch, verschmelzen die Cluster und die meisten Objekte befinden sich im selben Cluster. Der eps-Wert sollte auf der Grundlage des Abstands des Datensatzes gewählt werden (wir können ein k-Abstandsdiagramm verwenden, um ihn zu finden), aber im Allgemeinen sind kleine eps-Werte vorzuziehen.
minPoints: In der Regel lässt sich ein Minimum von minPoints aus der Anzahl der Dimensionen (D) des Datensatzes ableiten, als minPoints ≥ D + 1. Größere Werte sind in der Regel besser für Datensätze mit Rauschen geeignet und führen zur Bildung signifikanterer Cluster. Der Mindestwert für minPoints muss 3 sein, aber je größer der Datensatz ist, desto größer sollte der minPoints-Wert gewählt werden.
Mehr zur Parameterschätzung finden Sie hier.
Warum sollten wir DBSCAN verwenden?
Der DBSCAN-Algorithmus sollte verwendet werden, um Assoziationen und Strukturen in Daten zu finden, die manuell schwer zu finden sind, aber relevant und nützlich sein können, um Muster zu finden und Trends vorherzusagen.
Clustering-Methoden werden normalerweise in der Biologie, der Medizin, den Sozialwissenschaften, der Archäologie, dem Marketing, der Zeichenerkennung, den Managementsystemen und so weiter eingesetzt.
Lassen Sie uns an eine praktische Anwendung von DBSCAN denken. Nehmen wir an, wir haben ein E-Commerce-Unternehmen und wollen unseren Umsatz steigern, indem wir unseren Kunden relevante Produkte empfehlen. Wir wissen nicht genau, wonach unsere Kunden suchen, aber wir können auf der Grundlage eines Datensatzes ein relevantes Produkt für einen bestimmten Kunden vorhersagen und empfehlen. Wir können DBSCAN auf unseren Datensatz (basierend auf der E-Commerce-Datenbank) anwenden und Cluster auf der Grundlage der Produkte finden, die die Benutzer gekauft haben. Mit Hilfe dieser Cluster können wir Ähnlichkeiten zwischen Kunden finden, z. B. wenn Kunde A einen Stift, ein Buch und eine Schere gekauft hat und Kunde B ein Buch und eine Schere, dann können wir Kunde B einen Stift empfehlen. Dies ist nur ein kleines Beispiel für die Verwendung von DBSCAN, aber es kann in vielen Anwendungen in verschiedenen Bereichen eingesetzt werden.
Wie können wir es einfach implementieren?
Wie ich bereits geschrieben habe (Tipp: Glauben Sie nicht alles, was ich schreibe), ist DBSCAN ein bekannter Algorithmus, daher müssen Sie sich nicht selbst um die Implementierung kümmern. Sie können eine der Bibliotheken/Pakete verwenden, die im Internet zu finden sind. Hier ist eine Liste von Links, unter denen Sie die DBSCAN-Implementierung finden können: Matlab, R, R, Python, Python.
Ich habe auch eine Anwendung (auf Portugiesisch) entwickelt, um die Funktionsweise von DBSCAN auf didaktische Weise zu erklären. Die Anwendung wurde in C++ geschrieben und Sie können sie auf Github finden.