Agrupación de trayectorias (datos GPS de puntos (x,y)) y extracción de datos

Question

Tengo 2 preguntas sobre el análisis de un conjunto de datos GPS.

1) Extracción de trayectorias Tengo una enorme base de datos de coordenadas GPS registradas de la forma (latitude, longitude, date-time) . Según los valores de fecha-hora de los registros consecutivos, estoy intentando extraer todas las trayectorias/caminos seguidos por la persona. Por ejemplo; digamos que desde la hora M El (x,y) pares cambian continuamente hasta el momento N . Después de N el cambio en (x,y) pares disminuyen, momento en el que concluyo que el camino recorrido desde el tiempo M a N puede llamarse trayectoria. ¿Es éste un enfoque decente a seguir cuando se extraen trayectorias? ¿Hay algún enfoque/método/algoritmo conocido que puedas sugerir? ¿Hay alguna estructura de datos o formato que me puedas sugerir para mantener esos puntos de manera eficiente? ¿Tal vez, para cada trayectoria, sería útil calcular la velocidad y la aceleración?

2) Extracción de las trayectorias Una vez que tengo todas las trayectorias seguidas/recorridas, ¿cómo puedo compararlas/agruparlas? Me gustaría saber si los puntos iniciales o finales son similares, entonces ¿cómo se comparan las trayectorias intermedias?

¿Cómo puedo comparar los dos caminos/rutas y concluir si son similares o no? Además, ¿cómo puedo agrupar las rutas similares?

Te agradecería mucho que me indicaras una investigación o algo similar sobre este asunto.

El desarrollo será en Python, pero todo tipo de sugerencias de bibliotecas son bienvenidas.

Estoy abriendo exactamente la misma pregunta https://stackoverflow.com/questions/4910510/comparing-clustering-trajectories-gps-data-of-x-y-points-and-mining-the-data en StackOverflow. Pensé que obtendría más respuestas aquí...

Answer 1

PySAL - la biblioteca de análisis espacial de Python puede ser un buen comienzo - http://code.google.com/p/pysal/

Especialmente la sección de autocorrelación:

La autocorrelación espacial se refiere a el patrón no aleatorio de los valores de los atributos en un conjunto de unidades espaciales. Puede adoptar dos formas generales autocorrelación positiva, que refleja la similitud de los valores en el espacio, y autocorrelación negativa o disimilitud de valores o disimilitud de valores en el espacio. En ambos casos la autocorrelación surge cuando el patrón espacial observado es diferente de lo que cabría esperar en un proceso proceso aleatorio que opera en el espacio.

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

También puede considerar el uso de las bibliotecas de R http://cran.r-project.org/web/views/Spatial.html para Análisis de patrones de puntos .

Otros paquetes de R:

• clases y métodos para datos espacio-temporales
• Análisis espacial de datos de seguimiento de animales :

Funciones de acceso y manipular los datos espaciales para el seguimiento de animales. Filtrar por velocidad y crear gráficos de tiempo transcurrido a partir de los datos de de animales.

También puede simplificar el análisis si ajusta los puntos a las redes de transporte lineal existentes (carreteras/ferrocarril) disponibles en OSM. A continuación, puede simbolizar en base a estas líneas y la cantidad de personas que las utilizan en determinados momentos del día.

Answer 2

Dos artículos que probablemente le interesen, ya que tienen motivaciones similares a las suyas:

Límites de la previsibilidad en la movilidad humana por: Chaoming Song, Zehui Qu, Nicholas Blumm, Albert-László Barabási. Ciencia , Vol. 327, No. 5968. (19 de febrero de 2010), pp. 1018-1021.

Comprender los patrones de movilidad humana individual por: Marta C. González, César A. Hidalgo, Albert-Laszlo Barabasi. Naturaleza , vol. 453, nº 7196. (5 de junio de 2008), pp. 779-782.

Tenga en cuenta que los dos estudios utilizan los mismos datos, que son similares a los suyos, pero no al nivel de precisión en el espacio o el tiempo. No creo que describa lo que quiere encontrar como una trayectoria, pero tampoco estoy seguro de cómo lo llamaría. ¿Por qué exactamente quieres agrupar los nodos de inicio/fin de tus "trayectorias"?

Answer 3

Aunque no puedo comentar mucho sobre las trayectorias o caminos de los tuyos, creo que vas por buen camino con el enfoque de la agrupación y el tiempo.

El año pasado preparé una demostración para la UC de Esri mientras trabajaba con algunas personas de la Snow Leopard Conservancy, disponible en: http://resources.arcgis.com/gallery/file/geoprocessing/details?entryID=1F9F376F-1422-2418-7FBC-C359E9644702

Examina los "lugares de alimentación" (agrupaciones) de los leopardos de las nieves en función de unos criterios determinados:

• el grado de agrupación de esos puntos (distancia entre ellos)
• un umbral mínimo de puntos (mi análisis requería más de 4 puntos, ya que las lecturas se realizaban aproximadamente cada 12 horas)
• los puntos deben ser secuenciales (parte fácil del análisis, ya que deben recogerse en un orden lineal)

Aunque utiliza las herramientas de Esri para hacer el análisis de la distancia, el script de python que hay dentro podría ayudarte con la idea de la agrupación una vez que sepas qué puntos están cerca unos de otros. (Utiliza la teoría de los grafos: http://en.wikipedia.org/wiki/Graph_theory )

Como se ha mencionado en las otras respuestas, existen documentos para determinar los atributos que se necesitan para tomar las decisiones.

El análisis se basó vagamente en los conceptos de: Knopff, K.H., A. R. A. Knopff, M. B. Warren y M. S. Boyce. 2009. Evaluación de las técnicas de telemetría del Sistema de Posicionamiento Global para estimar los parámetros de depredación del puma. Journal of Wildlife Management73:586-597.

Answer 4

Para llevar a cabo cualquier tipo de agrupación en el conjunto de trayectorias, es necesario contar con una forma de calcular la similitud o la distancia de los pares de trayectorias. Existen varios métodos para ello, y se están desarrollando otros nuevos para casos especiales o para solucionar alguna deficiencia de los tradicionales (yo personalmente estoy trabajando en uno nuevo para mi tesis doctoral). Los algoritmos más conocidos son los siguientes:

• Distancia del par más cercano: simplemente define la distancia de 2 trayectorias por la distancia del par de puntos más cercano. Las trayectorias deben estar formadas por el mismo número de puntos.
• Suma de la distancia de los pares: Calcula las distancias de cada par de puntos y las suma. También funciona sólo si las trayectorias son de la misma longitud
• Distancia de deformación temporal dinámica (DTW): Este algoritmo fue desarrollado para manejar trayectorias de diferente cantidad de puntos medidos. Funciona con pares de puntos y permite que un punto de una trayectoria se utilice varias veces en los cálculos de la distancia del par, si el otro se mueve "demasiado rápido". (Imagen de Wikipedia )
• Subsecuencia común más larga: como su nombre indica, define la similitud de dos trayectorias por la longitud de la subtrayectoria más larga en la que las trayectorias originales viajan cerca la una de la otra.
• La distancia de edición en la secuencia real (EDR) y la distancia de edición con penalización real (ERP) definen la similitud por el número de operaciones de edición (añadir, eliminar o sustituir) que se necesitan para transformar una de las trayectorias en la otra.

Si te dedicas a este campo, te recomiendo encarecidamente el libro "Computing with Spatial Trajectories" de varios investigadores de Microsoft Asia.

Answer 5

Esto también puede ser de ayuda para usted:

Orellana D, Wachowicz M. Exploración de los patrones de suspensión del movimiento en la movilidad de los peatones. Geogr Anal. 2011;43(3):241-60. PubMed PMID: 22073410.

También puedes consultar este blog:

ideasonmovement.wordpress.com/