Clustering von Trajektorien (GPS-Daten von (x, y) Punkten) und Mining der Daten

14

Nur ein weiterer Tag im Büro für die menschliche Kanonenkugel.

Ich habe zwei Fragen zur Analyse eines GPS-Datensatzes.

1) Trajektorien extrahieren Ich habe eine riesige Datenbank mit aufgezeichneten GPS-Koordinaten des Formulars (latitude, longitude, date-time). Entsprechend den Datums- / Uhrzeitwerten aufeinanderfolgender Datensätze versuche ich, alle Trajektorien / Pfade zu extrahieren, denen die Person folgt. Zum Beispiel; sagen wir mal M, die (x,y)paare verändern sich bis zur zeit kontinuierlich N. Danach Nnimmt die Veränderung in (x,y)Paaren ab, woraus ich schließe, dass der Weg von Zeit Mzu Zeit genommen wirdNkann eine Flugbahn genannt werden. Ist das ein vernünftiger Ansatz, um Trajektorien zu extrahieren? Gibt es bekannte Ansätze / Methoden / Algorithmen, die Sie vorschlagen können? Gibt es Datenstrukturen oder -formate, die Sie mir vorschlagen möchten, um diese Punkte effizient zu verwalten? Vielleicht wäre es nützlich, für jede Flugbahn die Geschwindigkeit und die Beschleunigung herauszufinden?

2) Trajektorien abbauen Wenn ich alle Trajektorien verfolgt / Pfade genommen habe, wie kann ich sie vergleichen / gruppieren? Ich möchte wissen, ob die Start- oder Endpunkte ähnlich sind. Wie vergleichen sich dann die Zwischenpfade?

Wie vergleiche ich die beiden Pfade / Routen und schließe daraus, ob sie ähnlich sind oder nicht? Außerdem; Wie gruppiere ich ähnliche Pfade zusammen?

Ich würde es sehr begrüßen, wenn Sie mich auf eine Untersuchung oder ähnliches in dieser Angelegenheit hinweisen könnten.

Die Entwicklung wird in Python sein, aber alle Arten von Bibliotheksvorschlägen sind willkommen.

Ich öffne die exakt gleiche Frage /programming/4910510/comparing-clustering-trajectories-gps-data-of-xy-points-and-mining-the-data in StackOverflow. Ich dachte, ich bekomme hier mehr Antworten ...

Murat
quelle
1
Bei einer guten Antwort wird darauf geachtet, warum Sie diese Analyse durchführen. Welche Aktivitäten machen Ihre "Personen"? Was meinen Sie in diesem Zusammenhang mit einer "Flugbahn"? Warum interessieren Sie sich für die Flugbahnen? Was bedeutet es bedeutet für Bahnen „ähnlich“ sein? Ihre Klarstellungen werden geeignete Antworten vorschlagen; Ohne Klärung ist es eine Frage des Glücks und der Vermutung, eine passende Antwort zu erhalten.
whuber
Nun, ich bin daran interessiert, den Tagesablauf der Person herauszufinden. Wohin fährt sie täglich / wöchentlich / monatlich und welchen Wegen / Routen folgt sie normalerweise, wenn sie dorthin geht? Welchen Wegen folgt sie selten?
Murat
Die Datenbank enthält die aufgezeichneten GPS-Punkte der Personen für mehr als einen Monat mit einer Frequenz von 1-2 Sekunden. Ich weiß nicht, was sie tun. Eigentlich ist es das, woran ich interessiert bin.
Murat
1
@ Murat OK, das ist gut. Lassen Sie uns genauer werden. Wenn sich eine Person zu Hause oder im Büro bewegt, halten Sie das für stationär, oder versuchen Sie auch, diese Flugbahnen zu verfolgen? Wenn Sie sagen, dass zwei Trajektorien "ähnlich" sind, meinen Sie damit, dass sie den gleichen Weg zwischen den Punkten A und B zu verfolgen scheinen, oder beide von Punkt A nach Punkt B (möglicherweise auf verschiedenen Wegen, aber ohne anzuhalten) oder etwas anderes? Übrigens, sind Ihre Daten vollständig oder gibt es - wie zu erwarten - Perioden, in denen Daten fehlen oder bekanntermaßen fehlerhaft sind?
whuber
1
@ user5013 - Sehen Sie sich an, was Microsoft Research veröffentlicht hat. Es "enthält 17.621 Flugbahnen mit einer Gesamtstrecke von etwa 1,2 Millionen Kilometern und einer Gesamtdauer von 48.000 Stunden und mehr." research.microsoft.com/en-us/downloads/…
Murat

Antworten:

2

Zwei Artikel, an denen Sie wahrscheinlich interessiert sind, da sie ähnliche Motivationen haben wie Ihre:

Grenzen der Vorhersagbarkeit in der menschlichen Mobilität von: Chaoming Song, Zehui Qu, Nicholas Blumm, Albert-László Barabási. Science , Bd. 327, Nr. 5968 (19. Februar 2010), S. 1018-1021.

Verständnis der individuellen menschlichen Mobilitätsmuster durch Marta C. Gonzalez, Cesar A. Hidalgo und Albert-Laszlo Barabasi. Nature . 453, Nr. 7196 (5. Juni 2008), S. 779-782.

Beachten Sie, dass in den beiden Studien dieselben Daten verwendet werden, die Ihren Daten ähnlich sind, jedoch keine räumliche oder zeitliche Genauigkeit aufweisen. Ich denke nicht, was ich beschreiben würde, was Sie als Flugbahn finden möchten, aber ich bin nicht sicher, wie ich es auch nennen würde. Warum genau möchten Sie die Anfangs- / Endknoten Ihrer "Trajektorien" gruppieren?

Andy W
quelle
2

PySAL - Die Python Spatial Analysis Library ist möglicherweise ein guter Anfang - http://code.google.com/p/pysal/

Insbesondere der Autokorrelationsabschnitt:

Die räumliche Autokorrelation bezieht sich auf das nicht zufällige Muster von Attributwerten über einen Satz räumlicher Einheiten. Dies kann zwei allgemeine Formen annehmen: eine positive Autokorrelation, die die Wertähnlichkeit im Raum widerspiegelt, und eine negative Autokorrelation oder Wertunterschiedlichkeit im Raum. In beiden Fällen entsteht die Autokorrelation, wenn sich das beobachtete räumliche Muster von dem unterscheidet, was bei einem zufälligen Prozess im Weltraum zu erwarten wäre.

http://pysal.org/1.2/users/tutorials/autocorrelation.html

Sie können auch die Verwendung von R-Bibliotheken http://cran.r-project.org/web/views/Spatial.html für die Punktmusteranalyse in Betracht ziehen .

Andere R-Pakete:

Funktionen für den Zugriff auf und die Bearbeitung von Geodaten zur Verfolgung von Tieren. Filtern Sie nach Geschwindigkeit und erstellen Sie Zeitplots aus Tierdaten.

Dies kann die Analyse auch vereinfachen, wenn Sie die Punkte an vorhandenen linearen Verkehrsnetzen (Straße / Schiene) ausrichten, die von OSM bereitgestellt werden. Dann können Sie anhand dieser Zeilen symbolisieren, wie viele Personen sie zu bestimmten Tageszeiten verwenden.

geographika
quelle
Angesichts des Zusammenhangs der Frage ergibt der Vorschlag, die Autokorrelation zu untersuchen, keinen Sinn. Autokorrelation welcher Attribute?
Andy W
Der Zeitstempel für die GPS-Messwerte kann verwendet werden, um festzustellen, welche Bereiche einer Stadt zu verschiedenen Tageszeiten verwendet werden. Obwohl es nicht klar ist, ob die primäre Forschung darin besteht, herauszufinden, was Menschen tun oder wie sie dorthin gelangen.
Geographika
Es konnte auch ein abgeleiteter Punktdatensatz mit eng verwandten Punkten für gruppierte Personen und einem "Dauer" -Parameter analysiert werden
geographika
Ihr erster Kommentar ändert die Analyseeinheit von Personen zu Orten. Obwohl ich der Meinung bin, dass die Frage etwas mehrdeutig ist, gibt es nichts, was die OP unterstellen könnte, Orte zu gruppieren. Ich kann ein Argument für den zweiten Kommentar sehen (ein Punkt hat ein Attribut der Geschwindigkeit). Obwohl es sich um eine interessante Vorstellung handelt, ist sie ziemlich abstrakt und neuartig, daher halte ich es nicht für sinnvoll, die Untersuchung der räumlichen Autokorrelation vorzuschlagen, und sie ist wahrscheinlich verwirrend (Sie können Punkte in diesem Rahmen gruppieren, nicht ganze Pfade). Ich bin damit einverstanden, dass pysal und R-Bibliotheken von Interesse sein werden.
Andy W
2

Ich kann zwar nicht viel zu den Trajektorien oder Pfaden Ihrer Leute sagen, aber ich denke, Sie sind mit dem Cluster- und Zeitansatz auf dem richtigen Weg.

Ich habe eine Demo für die Esri UC im vergangenen Jahr , während mit einigen Leuten auf dem Snow Leopard Conservancy arbeiten, abrufbar unter: http://resources.arcgis.com/gallery/file/geoprocessing/details?entryID=1F9F376F-1422-2418 -7FBC-C359E9644702

Es untersucht "Fütterungsstandorte" (Cluster) von Schneeleoparden anhand vorgegebener Kriterien:

  • wie gruppiert diese Punkte waren (Abstand voneinander)
  • eine Mindestpunktzahl (meine Analyse erforderte 4+ Punkte, da die Ablesungen etwa alle 12 Stunden erfolgten)
  • Punkte müssen sequentiell sein (einfacher Teil der Analyse, da sie in einer linearen Reihenfolge gesammelt werden sollten)

Während für die Entfernungsanalyse Esri-Tools verwendet werden, kann das darin enthaltene Python-Skript Sie bei der Clustering-Idee unterstützen, sobald Sie wissen, welche Punkte nahe beieinander liegen. (Es verwendet die Graphentheorie: http://en.wikipedia.org/wiki/Graph_theory )

Wie in den anderen Antworten erwähnt, gibt es Papiere, um die Attribute zu bestimmen, die Sie benötigen, um die Entscheidungen zu treffen.

Die Analyse basierte lose auf den Konzepten von: Knopff, KH, ARA Knopff, MB Warren und MS Boyce. 2009. Evaluierung der Telemetrietechniken des Global Positioning System zur Schätzung der Puma-Prädationsparameter. Journal of Wildlife Management73: 586-597.

KHibma
quelle
2

Wenn Sie eine beliebige Art von Clustering für Ihre Trajektorien ausführen möchten, müssen Sie die Ähnlichkeit oder den Abstand der Trajektorienpaare berechnen können. Hierfür gibt es verschiedene Methoden, und für Sonderfälle oder zur Behebung eines Mangels an den herkömmlichen Methoden werden neue entwickelt (ich arbeite persönlich an einer neuen Methode für meine Doktorarbeit). Die bekannten Algorithmen sind die folgenden:

  • Abstand des nächstgelegenen Paares: Definieren Sie einfach den Abstand von 2 Trajektorien durch den Abstand des Punktepaares, das am nächsten zueinander liegt. Die Trajektorien müssen aus der gleichen Anzahl von Punkten bestehen.
  • Summe der Paardistanzen: Berechnen Sie die Distanzen für jedes Punktepaar und addieren Sie sie. Funktioniert auch nur, wenn die Flugbahnen gleich lang sind
  • Dynamic Time Warping (DTW) -Distanz: Dieser Algorithmus wurde entwickelt, um Trajektorien unterschiedlicher Anzahl gemessener Punkte zu verarbeiten. Es funktioniert mit Punktpaaren und ermöglicht die mehrfache Verwendung eines Punktes einer Trajektorie bei der Paardistanzberechnung, wenn sich der andere "zu schnell" bewegt. DTW-Darstellung(Bild aus Wikipedia )
  • Längste gemeinsame Subsequenz: Wie der Name schon sagt, definiert er die Ähnlichkeit zweier Trajektorien durch die Länge der längsten Subtrajektorie, auf der sich die ursprünglichen Pfade nahe beieinander befinden.
  • Die Bearbeitungsentfernung für reale Sequenz (EDR) und die Bearbeitungsentfernung mit realer Strafe (ERP) definieren die Ähnlichkeit durch die Anzahl der Bearbeitungsvorgänge (Hinzufügen, Entfernen oder Ersetzen), die erforderlich sind, um eine der Trajektorien in die andere zu transformieren.

Wenn Sie in diesem Bereich tätig sind, empfehle ich das Buch "Computing with Spatial Trajectories" von einer Reihe von Microsoft Asia-Forschern.

sw0rdf1sh
quelle
0

Dies kann auch für Sie hilfreich sein:

Orellana D, Wachowicz M. Erforschung von Bewegungsmustern in der Mobilität von Fußgängern. Geogr Anal. 2011; 43 (3): 241 & ndash; 60. PubMed PMID: 22073410.

Schauen Sie sich auch diesen Blog an:

ideasonmovement.wordpress.com/

David
quelle