Inkrementeller räumlicher Clustering-Algorithmus

8

Ich bin auf der Suche nach einem inkrementellen räumlichen Clustering- Algorithmus. Hier ist mein Anwendungsfall:

  • Benutzer erstellen Einträge mit einer Anfangsposition
  • Benutzer können die Positionen vorhandener Einträge ändern

Ich möchte jetzt einen entkoppelten Dienst implementieren, der Clusterinformationen dieser Daten bereitstellt. Der Dienst wird jedes Mal benachrichtigt, wenn ein neuer Eintrag hinzugefügt oder ein vorhandener Eintrag verschoben wurde. Was ist daher ein guter Clustering-Algorithmus? Im Idealfall sollte es gut auf große Datenmengen skaliert werden können. Wenn ein Kompromiss zwischen Clusterqualität und Laufzeitkomplexität besteht, kann ich die Ergebnisse verschlechtern und schließlich konsistente Ergebnisse erzielen (veraltete Ergebnisse sind für einige Zeit in Ordnung).

Um meine Anforderungen zusammenzufassen:

  • räumliche Clusterbildung basierend auf Positionen
  • inkrementelle Änderungen an Änderungen
  • neue Positionen hinzufügen
  • Bestehende Positionen ändern
  • gute Laufzeitleistung

Danke im Voraus!

b_erb
quelle
1
Wofür werden die Cluster verwendet? Was meinen sie ? (Die Antworten auf diese Fragen bieten die grundlegendsten Möglichkeiten zur Auswahl eines Clustering-Algorithmus.)
whuber
Sind Ereignisse auch selten oder häufig? im Zusammenhang mit einer gefährdeten Bevölkerung? oder wird es in Ordnung sein, nur Bereiche hervorzuheben, in denen Menschen leben?
Ian Turton
@whuber: Die Cluster werden verwendet, um die Elemente auf einer Karte besser erforschbar zu machen (daher kann es unterschiedliche Cluster mit unterschiedlichen Zoomstufen geben). Sie bedeuten eine Konzentration verfügbarer Artikel in den angegebenen Bereichen.
b_erb
@iant: Die Erstellung neuer Elemente erfolgt sehr häufig, die Änderung der Position vorhandener Elemente erfolgt selten. Es sind keine detaillierten Muster zu erwarten, wie Ereignisse auftreten. Es ist jedoch weniger wahrscheinlich, dass mehrere Elemente gleichzeitig erstellt werden.
b_erb
@PartlyCloudy Ich habe die Idee, aber ich verstehe immer noch nicht, wie Clustering helfen wird. OK, nehmen wir an, Sie identifizieren intern bestimmte Punktcluster. Wie wirkt sich das auf die Benutzeroberfläche (oder allgemein auf die "Erkundbarkeit" der Daten) aus? Abhängig davon, wie Sie reagieren, gibt es möglicherweise Lösungen, die (a) extrem schnell und einfach zu implementieren sind, aber (b) im Allgemeinen nicht als "Clustering" -Algorithmen betrachtet werden.
whuber

Antworten:

4

Der Zweck dieser Gruppierung besteht darin, die Anzeige von Punktsymbolen zu vereinfachen: Wenn viele auf der Karte nahe beieinander liegen, werden sie durch ein einzelnes Symbol ersetzt, um eine Gruppe anzuzeigen.

Die Anforderungen weisen auf die Notwendigkeit einer einfachen, anpassungsfähigen Lösung hin: Die Punktsymbole können aktualisiert werden, und wenn der Benutzer zoomt, werden an verschiedenen Stellen auf der Karte (oder auf dem Bildschirm) verschiedene Symbole angezeigt.

Ein ausgezeichneter Kandidat ist eindeutig ein Region Quadtree .

Es gibt eine einfachere Methode, die sich wie ein Regionsquadtree verhält. Es erfordert weniger Codierung, keine vorherige Erstellung einer Datenstruktur, aber Sie zahlen einen (kleinen) Preis, indem Sie beim Zoomen und Schwenken einige Berechnungen im laufenden Betrieb durchführen müssen. Raster einfach die Karte . Angenommen , innerhalb der aktuellen Ausdehnung der Karte müssen n Punktsymbole gezeichnet werden, die eine Länge von dx und eine Höhe von dy haben . Bezogen auf den Ursprung der Karte müssen die Symbole an den Koordinaten ( x [i] , y [i] ) gezeichnet werden , i = 1, 2, ..., n . Durch Auswahl einer Rasterzellengröße von c wird die Karte in ein Raster von Zellen unterteilt. Die Zelle, in der sich der Ort befindet (x , y ) gehört in Zeile j ( y ) = Etage [ y / c ] und Spalte j ( x ) (Zählen von 0, wobei die Zeilen von unten nach oben und die Spalten von links nach rechts gehen). Sie können jede Zelle, die zwei oder mehr Punkte empfängt, als "Cluster" betrachten. Das Clustersymbol kann in der Mitte der Zelle gezeichnet werden, die Koordinaten hat ( j + c / 2, k + c / 2).

Dies führt zu der folgenden Lösung, die im Pseudocode dargestellt wird:

m = Floor(dy/c)+1
n = Floor(dx/c)+1
Dimension a[m,n] = 0
For each (x[i], y[i]) to be displayed:
    Increment( a[ j(y[i]), j(x[i]) ] )
End for
For each (x[i], y[i]) to be displayed:
    row = j(y[i])
    col = j(x[i])
    If  a[row, col] > 1:
        Draw a symbol for a cluster of k points at (c*(col+0.5), c*(row+0.5))
        a[row, col] = 0
    Else
        Draw a point symbol at (x[i], y[i])
    End if
End for

Die Rechenlast des Algorithmus beträgt eindeutig O (Anzahl der Punkte) in der Zeit und O (dx * dy / c ^ 2) im Speicher. Die Kompromisse bei der Auswahl der Zellengröße c sind:

  1. c sollte so groß wie möglich sein: Der Speicher ist umgekehrt proportional zu c ^ 2: kleine Werte von c bedeuten große Mengen an RAM. (Der Speicher kann durch Verwendung von spärlichen Arrays oder Wörterbüchern auf O (Anzahl der Punkte) reduziert werden.)

  2. c sollte so groß wie möglich sein: Zwei Symbole (Punkte oder Cluster) werden niemals näher als c / 2 sein.

  3. c sollte so klein wie möglich sein: Jedes Clustersymbol repräsentiert Orte, die nicht weiter als c / sqrt (2) von ihm entfernt sind.

  4. c sollte so klein wie möglich sein: Große Werte von c erzeugen in der Regel viele Cluster und lassen nur wenige einzelne Punkte erscheinen.

Lassen Sie uns eine kurze Analyse von (4) durchführen. Nehmen wir als Ausgangspunkt an, dass die abzubildenden Orte gleichmäßig zufällig und unabhängig voneinander auftreten. Die Anzahl der Zellen ist N ( c ) = (Boden ( dx / c ) +1) * (Boden ( dy / c ) +1), was - zumindest für größere Werte von c - direkt proportional zu c ^ ist 2. Die Verteilung der Zellzahlen folgt ungefähr einem Poisson-Gesetz mit der Intensität Lambda = n / N ( c ) = n * c ^ 2 / ( dx * dy). Die erwartete Anzahl von Clustern ist gleich

e ( c ) = n (1 - exp (- Lambda ) (1 + Lambda )).

Dies wird kleiner, wenn Lambda auf 0 schrumpft; das heißt, wenn die Zellengröße c immer kleiner wird. Der Punkt dieser Analyse ist, dass Sie mit der vorhergehenden Formel vorhersehen können, wie viele Cluster es möglicherweise gibt, sodass Sie einen Anfangswert von c auswählen können, für den e ( c ) unter einem akzeptablen Wert liegt (während er immer noch groß genug ist, um den RAM zu begrenzen Anforderungen). Es gibt keine geschlossene Lösung, aber einige Newton-Raphson- Schritte konvergieren schnell zu einem.

Dieser Ansatz ist so dynamisch - er ist schnell genug, dass das Raster und das daraus resultierende Clustering mit jedem Zoom und Schwenken berechnet werden können und keine vorberechneten Datenstrukturen erforderlich sind -, dass die gewünschten "inkrementellen Änderungen" bei der Aktualisierung der Daten automatisch erfolgen.

whuber
quelle
Was ist, wenn Sie visuell eine Gruppe von Punkten in der Nähe des Bereichs mit 4 Ecken gruppiert haben? Würden Sie nicht mit 4 Clustern enden?
Kirk Kuykendall
@Kirk Tatsächlich kann diese Situation einen großen Cluster in zwei bis vier Cluster oder einzelne Punkte aufteilen. Es werden keine künstlichen Cluster erzeugt. Dies kann auch bei einem Regionsquadtree auftreten. Es gibt verschiedene Lösungen. Eine besteht darin, den Gitterursprung um einen zufälligen Betrag zwischen 0 und -c (in beiden Koordinaten) zu versetzen, damit solche Bedingungen nicht dauerhaft gelten. Eine andere Möglichkeit besteht darin, einen Quadtree dynamisch zu erstellen und ihn an die Punkte anzupassen (anstatt feste Schnittpunkte zu verwenden). Dies erfordert eindeutig mehr Codierung. Eine gute Lösung besteht darin, die Situation zu ignorieren: Ist das wirklich so ein Problem?
whuber