Regroupement des trajectoires (données GPS des points (x, y)) et exploration des données

14

Encore un jour au bureau du boulet de canon humain.

J'ai 2 questions sur l'analyse d'un jeu de données GPS.

1) Extraction de trajectoires J'ai une énorme base de données de coordonnées GPS enregistrées du formulaire (latitude, longitude, date-time). En fonction des valeurs date-heure des enregistrements consécutifs, j'essaie d'extraire toutes les trajectoires / chemins suivis par la personne. Par exemple; disons à partir du temps M, les (x,y)paires changent continuellement jusqu'au temps N. Après N, le changement par (x,y)paires diminue, à quel point je conclus que le chemin emprunté de temps MàNpeut être appelé une trajectoire. Est-ce une approche décente à suivre lors de l'extraction de trajectoires? Y a-t-il des approches / méthodes / algorithmes bien connus que vous pouvez suggérer? Y a-t-il des structures ou des formats de données que vous souhaiteriez me suggérer pour maintenir ces points de manière efficace? Peut-être que pour chaque trajectoire, déterminer la vitesse et l'accélération serait utile?

2) Exploration des trajectoires Une fois que j'ai toutes les trajectoires suivies / chemins empruntés, comment puis-je les comparer / les regrouper? Je voudrais savoir si les points de début ou de fin sont similaires, alors comment les chemins intermédiaires se comparent-ils?

Comment comparer les 2 chemins / routes et conclure s'ils sont similaires ou non. En outre; comment regrouper des chemins similaires?

Je vous serais très reconnaissant de bien vouloir me signaler une recherche ou quelque chose de similaire à ce sujet.

Le développement sera en Python, mais toutes sortes de suggestions de bibliothèques sont les bienvenues.

J'ouvre exactement la même question /programming/4910510/comparing-clustering-trajectories-gps-data-of-xy-points-and-mining-the-data dans StackOverflow. Je pensais avoir plus de réponses ici ...

Murat
la source
1
Une bonne réponse portera attention à la raison pour laquelle vous effectuez cette analyse. Quelles activités font vos «personnes»? Qu'entendez-vous, dans ce contexte, par une "trajectoire"? Pourquoi vous intéressez-vous aux trajectoires? Qu'est-ce que cela signifie que les trajectoires soient "similaires"? Vos clarifications suggéreront des réponses appropriées; sans clarification, obtenir une réponse appropriée sera une question de chance et de conjectures.
whuber
Eh bien, je suis intéressé à comprendre la routine quotidienne de la personne; où va-t-elle sur une base quotidienne / hebdomadaire / mensuelle et quels chemins / itinéraires suit-elle habituellement lorsqu'elle s'y rend? Quels chemins suit-elle rarement?
Murat
La base de données contient les points GPS enregistrés par les utilisateurs pendant plus d'un mois, avec une fréquence de 1 à 2 secondes. Je ne sais pas ce qu'ils font; en fait, c'est ce que je voudrais savoir.
Murat
1
@Murat OK, c'est bien. Soyons plus précis. Lorsqu'une personne se déplace dans une maison ou un bureau, considérez-vous que c'est immobile ou essayez-vous de suivre ces trajectoires aussi? Lorsque vous dites que deux trajectoires sont "similaires", voulez-vous dire qu'elles semblent suivre le même chemin entre les points A et B, ou qu'elles vont toutes les deux du point A au point B (peut-être par des itinéraires différents, mais sans s'arrêter), ou autre chose? BTW, vos données sont-elles complètes ou - comme on pourrait s'y attendre - y a-t-il des périodes où les données sont manquantes ou connues pour être erronées?
whuber
1
@ user5013 - Jetez un œil à ce que Microsoft Research a publié. Il "contient 17 621 trajectoires avec une distance totale d'environ 1,2 million de kilomètres et une durée totale de plus de 48 000 heures". research.microsoft.com/en-us/downloads/…
Murat

Réponses:

2

Deux articles qui pourraient vous intéresser, car ils ont des motivations similaires aux vôtres:

Limits of Predictability in Human Mobility par: Chaoming Song, Zehui Qu, Nicholas Blumm, Albert-László Barabási. Science , vol. 327, no 5968. (19 février 2010), p. 1018-1021.

Comprendre les schémas de mobilité humaine individuelle par: Marta C. Gonzalez, Cesar A. Hidalgo, Albert-Laszlo Barabasi. Nature , vol. 453, n ° 7196. (5 juin 2008), p. 779-782.

Notez que les deux études utilisent les mêmes données, qui sont similaires aux vôtres mais pas au niveau de précision dans l'espace ou dans le temps. Je ne pense pas que je décrirais ce que vous voulez trouver comme trajectoire, mais je ne sais pas trop comment je l'appellerais. Pourquoi voulez-vous exactement regrouper les nœuds de début / fin de vos "trajectoires"?

Andy W
la source
2

PySAL - la bibliothèque d'analyse spatiale Python peut être un bon début - http://code.google.com/p/pysal/

En particulier la section d'autocorrélation:

L'autocorrélation spatiale se rapporte au modèle non aléatoire de valeurs d'attribut sur un ensemble d'unités spatiales. Cela peut prendre deux formes générales: l'autocorrélation positive qui reflète la similitude des valeurs dans l'espace, et l'autocorrélation négative ou la dissimilarité des valeurs dans l'espace. Dans les deux cas, l'autocorrélation se produit lorsque le motif spatial observé est différent de ce qui serait attendu dans le cadre d'un processus aléatoire opérant dans l'espace.

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

Vous pouvez également envisager d'utiliser les bibliothèques R http://cran.r-project.org/web/views/Spatial.html pour l' analyse de modèle de point .

Autres packages R:

Fonctions d'accès et de manipulation des données spatiales pour le suivi des animaux. Filtrez la vitesse et créez des parcelles de temps passé à partir des données de la trace animale.

Cela peut également simplifier l'analyse si vous accrochez les points aux réseaux de transport linéaire existants (routes / rail) disponibles auprès d'OSM. Ensuite, vous pouvez symboliser en fonction de ces lignes et du nombre de personnes qui les utilisent à des moments particuliers de la journée.

geographika
la source
Compte tenu du contexte de la question suggérant d'examiner l'autocorrélation n'a aucun sens. Auto-corrélation de quels attributs?
Andy W
L'horodatage des lectures GPS peut être utilisé pour voir quelles zones d'une ville ou d'une ville sont utilisées à différents moments de la journée. Bien qu'il ne soit pas clair si la recherche principale consiste à trouver ce que les gens font ou comment les gens y arrivent.
geographika
Un ensemble de données ponctuelles dérivées avec des points étroitement liés pour les individus groupés et avec un paramètre de "durée" pourrait également être analysé
geographika
Votre premier commentaire modifie l'unité d'analyse des personnes aux lieux. Bien que je convienne que la question est quelque peu ambiguë, il n'y a rien en elle pour insinuer que le PO veut regrouper des lieux. Je peux voir un argument pour le deuxième commentaire (un point a un attribut de vitesse). Bien qu'il s'agisse d'une notion intéressante, elle est assez abstraite et nouvelle, donc je ne pense pas que cela ait beaucoup de sens de suggérer d'examiner l'autocorrélation spatiale et cela risque de prêter à confusion (vous pouvez regrouper des points dans ce cadre, pas des chemins entiers). Je suis d'accord cependant que les bibliothèques pysal et R seront intéressantes.
Andy W
2

Bien que je ne puisse pas beaucoup commenter les trajectoires ou les chemins de votre peuple, je pense que vous êtes sur la bonne voie avec l'approche cluster et temporelle.

J'ai monté une démo pour l'UC Esri l'année dernière en travaillant avec des gens au Snow Leopard Conservancy, disponible sur: http://resources.arcgis.com/gallery/file/geoprocessing/details?entryID=1F9F376F-1422-2418 -7FBC-C359E9644702

Il examine les «sites d'alimentation» (grappes) de léopards des neiges en fonction de critères donnés:

  • comment ces points étaient groupés (distance les uns des autres)
  • un seuil minimum de points (mon analyse a nécessité 4+ points car les lectures ont été prises toutes les 12 heures environ)
  • les points doivent être séquentiels (partie facile de l'analyse car ils doivent être collectés dans un ordre linéaire)

Bien qu'il utilise des outils Esri pour effectuer l'analyse de distance, le script python à l'intérieur peut vous aider avec l'idée de clustering une fois que vous savez quels points sont proches les uns des autres. (il utilise la théorie des graphes: http://en.wikipedia.org/wiki/Graph_theory )

Comme mentionné dans les autres réponses, il existe des documents pour déterminer les attributs dont vous auriez besoin pour prendre les décisions.

L'analyse était basée sur les concepts de Knopff, KH, ARA Knopff, MB Warren et MS Boyce. 2009. Évaluation des techniques de télémétrie du Global Positioning System pour estimer les paramètres de prédation des couguars. Journal of Wildlife Management73: 586-597.

KHibma
la source
2

Pour exécuter tout type de clustering sur votre ensemble de trajectoires, vous devez avoir un moyen de calculer la similitude ou la distance des paires de trajectoires. Il existe plusieurs méthodes pour cela, et de nouvelles sont en cours de développement pour des cas particuliers ou pour corriger une lacune des méthodes traditionnelles (je travaille personnellement sur une nouvelle pour ma thèse de doctorat). Les algorithmes bien connus sont les suivants:

  • Distance de la paire la plus proche: définissez simplement la distance de 2 trajectoires par la distance de la paire de points la plus proche l'une de l'autre. Les trajectoires doivent comporter le même nombre de points.
  • Somme de la distance des paires: calculez les distances pour chaque paire de points et additionnez-les. Fonctionne également uniquement si les trajectoires sont de même longueur
  • Distance de distorsion temporelle dynamique (DTW): cet algorithme a été développé pour gérer les trajectoires de différentes quantités de points mesurés. Il fonctionne sur des paires de points et permet d'utiliser un point d'une trajectoire plusieurs fois dans les calculs de distance de paire, si l'autre se déplace "trop ​​vite". Illustration DTW(Image de Wikipedia )
  • Conséquence commune la plus longue: comme son nom l'indique, elle définit la similitude de deux trajectoires par la longueur de la sous-trajectoire la plus longue où les trajectoires d'origine se rapprochent.
  • Modifier la distance sur séquence réelle (EDR) et Modifier la distance avec pénalité réelle (ERP) définissent la similitude par le nombre d'opérations d'édition (ajouter, supprimer ou remplacer) qui sont nécessaires pour transformer l'une des trajectoires en l'autre.

Si vous êtes dans ce domaine, je recommande fortement le livre intitulé "Computing with Spatial Trajectories" d'un certain nombre de reserachers Microsoft Asia.

sw0rdf1sh
la source
0

Cela peut aussi vous être utile:

Orellana D, Wachowicz M. Explorer les modèles de suspension de mouvement dans la mobilité des piétons. Geogr Anal. 2011; 43 (3): 241-60. PubMed PMID: 22073410.

Jetez également un œil à ce blog:

ideasonmovement.wordpress.com/

David
la source