Inkrementeller räumlicher Clustering-Algorithmus

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!

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.

Suchen Sie etwas wie http://dev.openlayers.org/releases/OpenLayers-2.10/examples/strategy-cluster-threshold.html ? Wenn ja, sollte der Code nicht zu schwer zu befolgen sein.