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.
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.
Methoden der Cluster-Bildung
Das Werkzeug Dichte-basierte Cluster-Bildung bietet drei verschiedene Methoden der Cluster-Bildung, 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.
- 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 ein Erreichbarkeitsplot zu erstellen, das anschließend dazu verwendet wird, die Cluster variierender Dichten vom schwächeren 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.
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.
Mindestanzahl der Features pro Cluster (für alle Methoden erforderlich)
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 Mindestanzahl der 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 Mindestanzahl der Features pro Cluster ist, desto mehr Cluster werden erkannt. Je größer der Wert für Mindestanzahl der 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 Mindestanzahl der Features pro Cluster führt möglicherweise zu einer Zusammenführung der kleineren Cluster.
Der Parameter Mindestanzahl der 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 oder jeder 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 Mindestanzahl der Features pro Cluster ausgewählt wird, ist die entsprechende Kernentfernung größer. Wird ein kleiner Wert für Mindestanzahl der Features pro Cluster ausgewählt, ist die entsprechende Kernentfernung kleiner. An den Grenzen von Clustern weisen Punkte große Kernentfernungen auf (und liegen wahrscheinlich nicht innerhalb eines Clusters). 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) der Wert für Mindestanzahl der Features pro Cluster nicht innerhalb der Suchentfernung von einem bestimmten Punkt gefunden werden kann, wird dieser Punkt als Rauschen gekennzeichnet. Wenn die Kernentfernung (die Entfernung, die zur Erreichung der minimalen Anzahl von Features erforderlich ist) für ein Feature also größer ist als die Suchentfernung, wird der Punkt als Rauschen gekennzeichnet. Die Suchentfernung wird bei Verwendung von Definierte Entfernung (DBSCAN) als Suchgrenzwert behandelt.
Für Mehrere Maßstäbe (OPTICS) wird die Suchentfernung als maximale Entfernung behandelt, die mit der Kernentfernung verglichen wird. Mehrere Maßstäbe (OPTICS) basiert auf dem Konzept einer maximal erreichbaren Entfernung, 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 bei OID 0 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. Wenn alle Entfernungen größer als die Kernentfernung sind, wird die kleinste dieser Entfernungen als Erreichbarkeitsentfernung zugewiesen. Anhand dieser Entfernungen wird dann der Erreichbarkeitsplot erstellt, bei dem es sich um einen sortierten Plot der Erreichbarkeitsentfernungen handelt, der zum Erkennen von Clustern dient.
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.
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 unter 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, ist jedoch 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 Diagramme 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 Ressourcen
Weitere Informationen zu DBSCAN:
- 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. (April 2013). 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:
- Ankerst, M., Breunig, M. M., Kriegel, H. P., & Sander, J. (Juni 1999). OPTICS: ordering points to identify the clustering structure. In ACM Sigmod record (Vol. 28, No. 2, S. 49-60). ACM.