Die Funktionsweise des Werkzeugs Dichte-basierte Cluster-Bildung besteht in der Erkennung von Flächen, auf denen Punkte konzentriert auftreten und auf denen sie durch leere und Flächen mit geringer Dichte getrennt sind. Punkte, die nicht Teil eines Clusters sind, werden als Rauschen gekennzeichnet. Die Zeit der Punkte kann optional verwendet werden, um Gruppen von Punkten zu finden, die räumlich und zeitlich ein Cluster bilden.
Dieses Werkzeug verwendet unüberwachte Cluster-Bildungs-Algorithmen für maschinelles Lernen, die Muster automatisch basierend auf rein räumlichen Positionen und der Entfernung zu einer angegebenen Anzahl von Nachbarn erkennen. Diese Algorithmen werden als unüberwacht betrachtet, da sie nicht für die Erkennung von Clustern trainiert werden müssen.
Tipp:
Cluster-Bildungs-, Gruppierungs- und Klassifizierungsverfahren zählen zu den am häufigsten verwendeten Methoden beim maschinellen Lernen. Die Werkzeuge Multivariate Cluster-Bildung und Räumlich eingeschränkte multivariate Cluster-Bildung nutzen ebenfalls Methoden für unüberwachtes Maschinenlernen, um natürliche Cluster in Ihren Daten zu ermitteln. Diese Klassifizierungsmethoden gelten als unüberwacht, da keine vorklassifizierten Features angeleitet oder trainiert werden müssen, um die Cluster in Ihren Daten zu suchen.
Potenzielle Anwendungsbereiche
Mögliche Anwendungsbereiche des Werkzeugs lauten wie folgt:
- Städtische Wasserversorgungsnetze sind wichtige unterirdische Assets. Die Cluster-Bildung von Rohrbrüchen- und rissen kann auf bevorstehende Probleme hinweisen: Mithilfe des Werkzeugs Dichte-basierte Cluster-Bildung können Ingenieure ermitteln, wo sich diese Cluster befinden, und vorbeugende Maßnahmen in Zonen mit hohem Gefahrenpotenzial in Wasserversorgungsnetzen ergreifen.
- Angenommen, Sie verfügen über Positionsdaten für alle erfolgreichen und nicht erfolgreichen Schüsse von NBA-Spielern. Mit dem Werkzeug Dichte-basierte Cluster-Bildung können Sie die verschiedenen Muster erfolgreicher und nicht erfolgreicher Positionen der einzelnen Spieler im Vergleich anzeigen. Diese Informationen können dann der Spielstrategie zugrunde gelegt werden.
- Angenommen, Sie untersuchen eine bestimmte durch Schädlinge übertragene Krankheit und verfügen über ein Punkt-Dataset, das Haushalte in Ihrem Untersuchungsgebiet darstellt, von denen einige betroffen sind und andere nicht. Mithilfe des Werkzeugs Dichte-basierter Cluster-Bildung können Sie die größten Cluster betroffener Haushalte ermitteln, um einen Bereich besser aufzeigen und mit der Behandlung und Vernichtung krankheitsübertragender Erreger beginnen zu können.
- Das Verorten von Tweets infolge von Naturgefahren oder Terroranschlägen kann geclustert und notwendige Rettungsmaßnahmen und Evakuierungen können basierend auf der Größe und Position des identifizierten Clusters vermittelt werden.
Methode der Cluster-Bildung
Der Parameter Methode der Cluster-Bildung des Werkzeugs Dichte-basierte Cluster-Bildung bietet drei Optionen, um Cluster in Ihren Punktdaten zu suchen:
- Definierte Entfernung (DBSCAN): Verwendet eine angegebene Entfernung, um dichte Cluster vom schwächeren Rauschen zu trennen. Der DBSCAN-Algorithmus stellt die schnellste Methode der Cluster-Bildung dar, ist jedoch nur dann geeignet, wenn eine sehr klare Suchentfernung verwendet werden muss und dies für alle potenziellen Cluster gut funktioniert. Dazu müssen alle sinnvollen Cluster eine ähnliche Dichte aufweisen. Diese Methode ermöglicht es Ihnen ebenfalls, mithilfe der Parameter Zeitfeld und Suchzeitintervall nach räumlichen und zeitlichen Clustern aus Punkten zu suchen.
- Automatische Anpassung (HDBSCAN): Verwendet einen Entfernungsbereich, um Cluster variierender Dichten vom schwächeren Rauschen zu trennen. Der HDBSCAN-Algorithmus ist die datenabhängigste Methode der Cluster-Bildung und erfordert somit die wenigsten Benutzereingaben.
- Mehrere Maßstäbe (OPTICS): Verwendet die Entfernung zwischen benachbarten Features, um einen Erreichbarkeitsplot zu erstellen, der anschließend dazu verwendet wird, die Cluster variierender Dichten vom Rauschen zu trennen. Der OPTICS-Algorithmus bietet die größte Flexibilität in der Optimierung der gefundenen Cluster, ist aber rechenintensiv, vor allem bei einer großen Suchentfernung. Diese Methode ermöglicht es Ihnen ebenfalls, mithilfe der Parameter Zeitfeld und Suchzeitintervall nach räumlichen und zeitlichen Clustern aus Punkten zu suchen.
Dieses Werkzeug verwendet Eingabe-Punkt-Features, einen Pfad für die Ausgabe-Features und einen Wert, der die minimale Anzahl von Features darstellt, die erforderlich ist, um als Cluster zu gelten. Je nach ausgewählter Methode der Cluster-Bildung müssen möglicherweise zusätzliche Parameter angegeben werden, wie nachfolgend beschrieben.
Minimale Anzahl Features pro Cluster
Mit diesem Parameter wird festgelegt, wie viele Features mindestens erforderlich sind, damit eine Gruppierung von Punkten als Cluster betrachtet wird. Wenn Sie beispielsweise über eine Reihe unterschiedlicher Cluster mit einer Größe von 10 bis 100 Punkten verfügen und für Minimale Anzahl Features pro Cluster den Wert 20 auswählen, werden alle Cluster mit weniger als 20 Punkten als Rauschen betrachtet (da sie keine Gruppierung bilden, die groß genug ist, um als Cluster zu gelten), oder sie werden mit benachbarten Clustern zusammengeführt, um der erforderlichen minimalen Anzahl von Features zu entsprechen. Wenn Sie im Gegensatz dazu einen Wert für Minimale Anzahl Features pro Cluster auswählen, der kleiner ist als das für Sie kleinste sinnvolle Cluster, kann dies dazu führen, dass sinnvolle Cluster in kleinere Cluster unterteilt werden. Dies bedeutet, je kleiner der Wert für Minimale Anzahl Features pro Cluster ist, desto mehr Cluster werden erkannt. Je größer der Wert für Minimale Anzahl Features pro Cluster ist, desto weniger Cluster werden erkannt.
Tipp:
Der ideale Wert für Minimale Anzahl Features pro Cluster hängt von den zu erfassenden Elementen und von der Analysefrage ab. Er sollte auf die kleinste Gruppierung festgelegt werden, die nach Ihrem Ermessen als sinnvolles Cluster gelten soll. Die Erhöhung des Wertes für Minimale Anzahl Features pro Cluster führt möglicherweise zu einer Zusammenführung der kleineren Cluster.
Der Parameter Minimale Anzahl Features pro Cluster ist auch für die Berechnung der Kernentfernung wichtig, bei der es sich um eine Messung handelt, die von allen Methoden zum Suchen von Clustern verwendet wird. Konzeptuell gesehen ist die Kernentfernung für jeden Punkt eine Messung der Entfernung, die von jedem einzelnen Punkt zur definierten minimalen Anzahl von Features zurückgelegt werden muss. Wenn also ein hoher Wert für Minimale Anzahl Features pro Cluster ausgewählt wird, ist die entsprechende Kernentfernung größer. Wird ein kleiner Wert für Minimale Anzahl Features pro Cluster ausgewählt, ist die entsprechende Kernentfernung kleiner. Die Kernentfernung bezieht sich auf den Parameter Suchentfernung, der sowohl von der Methode Definierte Entfernung (DBSCAN) als auch von der Methode Mehrere Maßstäbe (OPTICS) verwendet wird.
Suchentfernung (DBSCAN und OPTICS)
Wenn für Definierte Entfernung (DBSCAN) die Minimale Anzahl Features pro Cluster innerhalb der Suchentfernung von einem bestimmten Punkt aus gefunden werden kann, wird dieser Punkt als Kernpunkt markiert und zusammen mit allen Punkten innerhalb der Kernentfernung in ein Cluster aufgenommen. Bei einem Grenzpunkt handelt es sich um einen Punkt, der innerhalb der Suchentfernung eines Kernpunktes liegt, aber selbst nicht die minimale Anzahl der Features innerhalb der Suchentfernung aufweist. Jeder resultierende Cluster besteht aus Kern- und Grenzpunkten, wobei die Kernpunkte eher in der Mitte des Clusters liegen und die Grenzpunkte eher in den äußeren Bereichen. Weist ein Punkt nicht die minimale Anzahl der Features innerhalb der Suchentfernung auf und liegt er nicht innerhalb der Suchentfernung eines anderen Kernpunktes (ist er also weder ein Kernpunkt noch ein Grenzpunkt), wird er als Rauschpunkt markiert und in kein Cluster aufgenommen.
Für Mehrere Maßstäbe (OPTICS) wird der Wert Suchentfernung als maximale Entfernung behandelt, die mit der Kernentfernung verglichen wird. Mehrere Maßstäbe (OPTICS) basiert auf dem Konzept der minimalen Erreichbarkeitsentfernung, bei der es sich um die Entfernung von einem Punkt zu seinem nächsten Nachbarn handelt, der von der Suche noch nicht überprüft wurde (Hinweis: OPTICS ist ein Sortieralgorithmus, der mit dem Feature mit der kleinsten ID beginnt und von diesem Punkt zum nächsten geht, um einen Plot zu erstellen. Die Reihenfolge der Punkte ist für die Ergebnisse entscheidend.) Mehrere Maßstäbe (OPTICS) sucht alle Nachbarentfernungen innerhalb der angegebenen Suchentfernung und vergleicht diese jeweils mit der Kernentfernung. Wenn eine Entfernung kleiner ist als die Kernentfernung, wird diesem Feature diese Kernentfernung als seine Erreichbarkeitsentfernung zugewiesen. Sind alle Entfernungen größer als die Kernentfernung, wird die kleinste dieser Entfernungen als Erreichbarkeitsentfernung zugewiesen. Wenn sich innerhalb der Suchentfernung keine weiteren Punkte befinden, wird der Prozess an einem neuen Punkt neu gestartet, der zuvor noch nicht überprüft wurde. Bei jeder Iteration werden Erreichbarkeitsentfernungen neu berechnet und sortiert. Die kürzesten Entfernungen werden für die endgültige Erreichbarkeitsentfernung jedes Punktes verwendet. Anhand dieser Erreichbarkeitsentfernungen wird dann der Erreichbarkeitsplot erstellt, bei dem es sich um einen sortierten Plot der Erreichbarkeitsentfernungen handelt, der zum Erkennen von Clustern herangezogen wird.
Wenn weder für Definierte Entfernung (DBSCAN) noch für Mehrere Maßstäbe (OPTICS) eine Entfernung angegeben ist, ist die Standard-Suchentfernung die größte Kernentfernung, die im Dataset gefunden wurde, wobei die Kernentfernungen in den obersten 1 % (d. h. die extremsten Kernentfernungen) ausgeschlossen werden.
Bildung von Raum-Zeit-Clustern (DBSCAN und OPTICS)
Bei zwei Methoden der Cluster-Bildung kann die Zeit der einzelnen Punkte im Parameter Zeitfeld angegeben werden. Wenn sie angegeben wird, findet das Werkzeug Cluster aus Punkten, die zeitlich und räumlich nah beieinander liegen. Der Parameter Suchzeitintervall ist analog zur Suchentfernung und wird verwendet, um die Kernpunkte, Grenzpunkte und Rauschpunkte des Raum-Zeit-Clusters zu ermitteln.
Bei der Suche nach Cluster-Mitgliedern muss für die Option Definierte Entfernung (DBSCAN) die minimale Anzahl Features pro Cluster innerhalb der Werte von Suchentfernung und Suchzeitintervall gefunden werden, damit es sich um den Kernpunkt eines Raum-Zeit-Clusters handelt.
In der folgenden Abbildung beträgt die Suchentfernung 1 Meile, das Suchzeitintervall 3 Tage und die minimale Anzahl der Features 4. Der Punkt P ist ein Kernpunkt, da vier Punkte innerhalb der Suchentfernung und des Zeitintervalls liegen (einschließlich des Punktes selbst). Bei dem Punkt Q handelt es sich um einen Grenzpunkt, da es nur drei Punkte innerhalb der Suchentfernung und des Zeitintervalls gibt, der Punkt jedoch innerhalb der Suchentfernung und des Zeitintervalls eines Kernpunktes des Clusters liegt (der Punkt mit dem Zeitstempel 1/5/2021). Die Punkte C und D sind Rauschpunkte, da sie weder Kern- noch Grenzpunkte des Clusters sind. Alle anderen Punkte (einschließlich P und Q) bilden einen einzelnen Cluster.
Für Mehrere Maßstäbe (OPTICS) werden alle Punkte außerhalb des Bereichs Suchzeitintervall eines Punktes ausgeschlossen, wenn der Punkt seine Kernentfernung berechnet, nach allen Nachbarentfernungen innerhalb des angegebenen Wertes Suchentfernung sucht und die Erreichbarkeitsentfernung berechnet.
In der folgenden Abbildung beträgt die Suchentfernung 2 Meilen, das Suchzeitintervall 3 Tage und die minimale Anzahl der Features 4. Die Kernentfernung für den Punkt P wird berechnet, indem der Punkt q3 übersprungen wird, da er außerhalb des Suchzeitintervalls liegt. In diesem Fall entspricht die Kernentfernung von P der Erreichbarkeitsentfernung von P.
In der nächsten Abbildung wird die Berechnung der Erreichbarkeitsentfernung dargestellt, wenn einige benachbarte Punkte bereits überprüft wurden. Die Punkte q1, q2 und q4 wurden übersprungen, da sie bereits zuvor überprüft wurden. Die Punkte q3 und q5 wurden übersprungen, weil sie außerhalb des Suchzeitfensters liegen.
Erreichbarkeitsplot (OPTICS)
Nachdem die Erreichbarkeitsentfernungen für das gesamte Dataset berechnet wurden, wird ein Erreichbarkeitsplot erstellt, der die Entfernungen sortiert und die Struktur der Cluster-Bildung der Punkte sichtbar macht.
Die Täler im Erreichbarkeitsplot implizieren, dass zwischen den einzelnen Punkten eine kurze Entfernung liegt. Täler stellen somit eindeutige Cluster in diesem Punktmuster dar. Je dichter ein Cluster ist, desto niedriger sind die Erreichbarkeitsentfernungen und desto niedriger ist das Tal im Plot (im Beispiel oben hat das rosafarbene Cluster beispielsweise die größte Dichte) Cluster mit geringerer Dichte weisen größere Erreichbarkeitsentfernungen und höhere Täler im Plot auf (im Beispiel oben hat das dunkelgrüne Cluster beispielsweise die geringste Dichte). Je nach Konfiguration der Gruppe von Punkten stellen die Spitzen die erforderlichen Entfernungen von Cluster zu Cluster bzw. von Cluster zum Rauschen und wieder zum Cluster zurück dar.
Plateaus können in einem Erreichbarkeitsplot auftreten, wenn die Suchentfernung kleiner als die größte Kernentfernung ist. Ein wichtiger Aspekt der Verwendung der OPTICS-Methode bei der Cluster-Bildung ist die Festlegung der Erkennung von Clustern über den Erreichbarkeitsplot, die mithilfe des Parameters Cluster-Empfindlichkeit erfolgt.
Cluster-Empfindlichkeit (OPTICS)
Mit dem Parameter Cluster-Empfindlichkeit wird festgelegt, wie Cluster anhand der Form (Neigung und Höhe) von Spitzen innerhalb des Erreichbarkeitsplots getrennt werden. Bei einer sehr hohen Cluster-Empfindlichkeit (nahe 100) wird selbst die kleinste Spitze als Trennung zwischen Clustern behandelt, wodurch die Anzahl der Cluster erhöht wird. Bei einer sehr geringen Cluster-Empfindlichkeit (nahe 0) werden nur die steilsten, höchsten Spitzen als Trennung zwischen Clustern behandelt, was zu einer niedrigeren Anzahl der Cluster führt.
Die Standard-Cluster-Empfindlichkeit wird als Schwellenwert berechnet, bei dem durch das Hinzufügen weiterer Cluster keine zusätzlichen Informationen hinzugefügt werden. Dies erfolgt anhand der Kullback-Leibler-Divergenz zwischen dem ursprünglichen Erreichbarkeitsplot und dem geglätteten Erreichbarkeitsplot, der nach der Cluster-Bildung abgerufen wird.
Vergleich der Methoden
Während der Erreichbarkeitsplot zum Erkennen von Clustern nur von Mehrere Maßstäbe (OPTICS) verwendet wird, kann anhand des Plots konzeptuell besser verdeutlicht werden, wie diese Methoden sich voneinander unterscheiden. Zur Veranschaulichung werden die Unterschiede der drei Methoden anhand des nachfolgenden Erreichbarkeitsplots erläutert. Der Plot zeigt Cluster mit unterschiedlicher Dichte und Trennungsentfernungen an. Wir untersuchen die Ergebnisse der Verwendung der jeweiligen Methode der Cluster-Bildung für diese illustrativen Daten.
Für Definierte Entfernung (DBSCAN) kann eine durch den Erreichbarkeitsplot verlaufende Linie mit der angegebenen Suchentfernung dargestellt werden. Flächen unterhalb der Suchentfernung stellen Cluster dar, während es sich bei den über der Suchentfernung liegenden Spitzen um Rauschpunkte handelt. Die Definierte Entfernung (DBSCAN) ist die schnellste Methode der Cluster-Bildung, jedoch ist sie nur dann geeignet, wenn eine sehr klare Suchentfernung als Grenzwert verwendet werden soll und diese Suchentfernung für alle Cluster gut funktioniert. Dazu müssen alle sinnvollen Cluster eine ähnliche Dichte aufweisen.
Bei Automatische Anpassung (HDBSCAN) können die Erreichbarkeitsentfernungen als geschachtelte Cluster-Ebenen aufgefasst werden. Jede Ebene der Cluster-Bildung würde zur Erkennung einer anderen Cluster-Gruppe führen. Mit Automatische Anpassung (HDBSCAN) wird festgelegt, welche Cluster-Ebenen in jeder Reihe von geschachtelten Clustern die stabilsten Cluster mit möglichst vielen Mitgliedern und ohne Einbeziehung von Rauschen optimal erstellen. Weitere Informationen zum Algorithmus finden Sie in der hervorragenden Dokumentation der Ersteller von HDBSCAN. Automatische Anpassung (HDBSCAN) ist die datenabhängigste dieser Methoden der Cluster-Bildung und erfordert somit nur einen geringen Aufwand an Benutzereingaben.
Bei Mehrere Maßstäbe (OPTICS) basiert die Erkennung von Clustern nicht auf einer bestimmten Entfernung, sondern auf den Spitzen und Täler innerhalb des Plots. Angenommen, dass die jeweilige Spitze eine Ebene mit dem Wert "Klein", "Mittel" oder "Groß" aufweist.
Die Auswahl einer sehr hohen Cluster-Empfindlichkeit bedeutet im Grunde, dass alle Spitzen, von klein bis groß, als Trennungen zwischen Clustern fungieren (was zu mehr Clustern führt).
Die Auswahl einer mäßigen Cluster-Empfindlichkeit führt dazu, dass mittlere und große Spitzen, jedoch keine kleinen Spitzen verwendet werden.
Die Auswahl einer sehr niedrigen Cluster-Empfindlichkeit führt dazu, dass nur große Spitzen verwendet werden, wodurch die niedrigste Anzahl von Clustern erkannt wird.
Mehrere Maßstäbe (OPTICS) bietet die größte Flexibilität bei der Feineinstellung der erkannten Cluster, obwohl sie die langsamste der drei Methoden zur Cluster-Bildung darstellt.
Ergebnisse
Dieses Werkzeug generiert eine Ausgabe-Feature-Class mit dem neuen ganzzahligen Feld CLUSTER_ID, das angibt, zu welchem Cluster das jeweilige Feature gehört. Das Standard-Rendering basiert auf dem Feld COLOR_ID. Dabei wird jede Farbe mehreren Clustern zugewiesen. Durch wiederholtes Zuweisen der Farben lässt sich jeder Cluster visuell von seinen benachbarten Clustern unterscheiden.
Wenn als Methode der Cluster-Bildung die Option Automatische Anpassung (HDBSCAN) ausgewählt wurde, enthält die Ausgabe-Feature-Class auch folgende Felder: PROB, das die Wahrscheinlichkeit angibt, mit der das Feature in die zugewiesene Gruppe gehört, OUTLIER, das das Feature angibt, das ein Ausreißer im eigenen Cluster sein könnte (je höher der Wert, desto wahrscheinlicher ist das Feature ein Ausreißer), und EXEMPLAR, das die prototypischsten bzw. repräsentativsten Features für jeden Cluster angibt.
Mit diesem Werkzeug werden auch Meldungen und Schemas erstellt, mit denen Sie die Merkmale der identifizierten Cluster leichter verstehen. Sie können auf die Meldungen zugreifen, indem Sie mit der Maus auf die Fortschrittsleiste zeigen, auf die Pop-out-Schaltfläche klicken und den Abschnitt Meldungen im Bereich Geoverarbeitung erweitern. Sie können auch auf die Meldungen für eine frühere Ausführung des Werkzeugs Dichte-basierte Cluster-Bildung über den Geoverarbeitungsverlauf zugreifen. Die erstellten Schemas können über den Bereich Inhalt aufgerufen werden.
Neben dem Erreichbarkeitsschema, das bei Auswahl von Mehrere Maßstäbe (OPTICS) erstellt wird, wird bei allen Methoden der Cluster-Bildung auch ein Balkendiagramm erstellt, das alle eindeutigen Cluster-IDs anzeigt. Anhand dieses Diagramms können alle Features, die innerhalb eines bestimmten Cluster liegen, problemlos ausgewählt werden und lässt sich die Größe der jeweiligen Cluster erkunden.
Zusätzliche Quellen
Weitere Informationen zu DBSCAN:
- Birant, D. & Kut, A. (2007, January). "ST-DBSCAN: An algorithm for clustering spatial–temporal data." In Data & Knowledge Engineering (Vol 60, No. 1, S. 208–221). https://doi.org/10.1016/j.datak.2006.01.013
- Ester, M., Kriegel, H. P., Sander, J., & Xu, X. (1996, August). "A density-based algorithm for discovering clusters in large spatial databases with noise." In Kdd (Vol. 96, No. 34, S. 226–231).
Weitere Informationen zu HDBSCAN:
- Campello, R. J., Moulavi, D., & Sander, J. (2013, April). "Density-based clustering based on hierarchical density estimates." In Pacific-Asia Conference on Knowledge Discovery and Data Mining (S. 160–172). Springer, Berlin, Heidelberg.
Weitere Informationen zu OPTICS:
- Agrawal, K. P., Garg, S., Sharma, S., & Patel, P. (2016, November). "Development and validation of OPTICS based spatio-temporal clustering technique." In Information Sciences (Vol 369, S. 388–401). https://doi.org/10.1016/j.ins.2016.06.048.
- Ankerst, M., Breunig, M. M., Kriegel, H. P., & Sander, J. (1999, June). "OPTICS: ordering points to identify the clustering structure." In ACM Sigmod record (Vol. 28, No. 2, S. 49–60). ACM.