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

14

Solo otro día en la oficina para la bala de cañón humana.

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

1) Extracción de trayectorias Tengo una gran base de datos de coordenadas GPS registradas de la forma (latitude, longitude, date-time). De acuerdo con los valores de fecha y hora de registros consecutivos, estoy tratando de extraer todas las trayectorias / caminos seguidos por la persona. Por ejemplo; De vez en cuando M, las (x,y)parejas cambian continuamente hasta el tiempo N. Después N, el cambio en (x,y)pares disminuye, en cuyo punto concluyo que el camino tomado de tiempo MaNse le puede llamar una trayectoria. ¿Es un enfoque decente a seguir al extraer trayectorias? ¿Existen enfoques / métodos / algoritmos bien conocidos que pueda sugerir? ¿Hay alguna estructura o formato de datos que quisiera sugerirme para mantener esos puntos de manera eficiente? Quizás, para cada trayectoria, ¿sería útil calcular la velocidad y la aceleración?

2) Minería de las trayectorias Una vez que tengo todas las trayectorias seguidas / rutas tomadas, ¿cómo puedo compararlas / agruparlas? Me gustaría saber si los puntos de inicio o final son similares, entonces, ¿cómo se comparan las rutas intermedias?

¿Cómo comparo los 2 caminos / rutas y concluyo si son similares o no? Además; ¿Cómo agrupo rutas similares?

Le agradecería mucho si me puede señalar 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 /programming/4910510/comparing-clustering-trajectories-gps-data-of-xy-points-and-mining-the-data en StackOverflow. Pensé que obtendría más respuestas aquí ...

python gps algorithm clustering Murat
fuente
1
Una buena respuesta prestará atención a por qué está haciendo este análisis. ¿Qué actividades están haciendo sus "personas"? ¿Qué quiere decir, en este contexto, con una "trayectoria"? ¿Por qué estás interesado en las trayectorias? ¿Qué significa que las trayectorias sean "similares"? Sus aclaraciones sugerirán respuestas apropiadas; sin aclaraciones, obtener una respuesta adecuada será cuestión de suerte y conjeturas.
whuber
Bueno, estoy interesado en descubrir la rutina diaria de la persona; ¿A dónde va a diario / semanalmente / mensualmente y qué caminos / rutas suele seguir cuando va allí? ¿Qué caminos raramente sigue?
Murat
La base de datos contiene los puntos GPS registrados de las personas durante más de un mes, con una frecuencia de 1-2 segundos. No sé lo que están haciendo. en realidad, eso es lo que me interesa descubrir.
Murat
1
@Murat OK, eso es bueno. Seamos más precisos. Cuando una persona se mueve por una casa u oficina, ¿consideraría que es estacionaria o está tratando de rastrear esas trayectorias también? Cuando dice que dos trayectorias son "similares", ¿quiere decir que parecen seguir el mismo camino entre los puntos A y B, o ambos van del punto A al punto B (quizás por diferentes rutas, pero sin detenerse), o algo más? Por cierto, ¿están completos sus datos o, como cabría esperar, hay períodos en los que faltan datos o se sabe que son erróneos?
whuber
1
@ user5013 - Echa un vistazo a lo que ha publicado Microsoft Research. "Contiene 17,621 trayectorias con una distancia total de aproximadamente 1.2 millones de kilómetros y una duración total de más de 48,000 horas". research.microsoft.com/en-us/downloads/…
Murat

Respuestas:

2

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

Límites de previsibilidad en la movilidad humana por: Chaoming Song, Zehui Qu, Nicholas Blumm, Albert-László Barabási. Science , vol. 327, núm. 5968. (19 de febrero de 2010), págs. 1018-1021.

Comprensión de los patrones individuales de movilidad humana por: Marta C.González, César A. Hidalgo, Albert-Laszlo Barabasi. Nature , vol. 453, núm. 7196. (05 de junio de 2008), págs. 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 quieres encontrar como trayectoria, pero tampoco estoy seguro de cómo lo llamaría. ¿Por qué exactamente quiere agrupar los nodos de inicio / final de sus "trayectorias"?

Andy W
fuente
2

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

Particularmente la sección de autocorrelación:

La autocorrelación espacial pertenece al patrón no aleatorio de valores de atributo sobre un conjunto de unidades espaciales. Esto puede tomar dos formas generales: autocorrelación positiva que refleja similitud de valor en el espacio, y autocorrelación negativa o disparidad de valor en el espacio. En cualquier caso, la autocorrelación surge cuando el patrón espacial observado es diferente de lo que cabría esperar en un proceso aleatorio que opera en el espacio.

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

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

Otros paquetes R:

Funciones para acceder y manipular datos espaciales para el seguimiento de animales. Filtre por velocidad y cree tiempo dedicado a las parcelas a partir de datos de seguimiento 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. Luego, puede simbolizar según estas líneas y cuántas personas las usan en determinados momentos del día.

geographika
fuente
Dado el contexto de la pregunta que sugiere examinar la autocorrelación no tiene ningún sentido. ¿Correlación automática de qué atributos?
Andy W
La marca de tiempo para las lecturas de GPS se puede usar para ver qué áreas de un pueblo o ciudad se usan en diferentes momentos del día. Aunque no está claro si la investigación principal es encontrar lo que hace la gente o cómo la gente llega allí.
geographika
También un conjunto de datos punto derivada con puntos estrechamente relacionados para los individuos agrupados y dados un parámetro "duración" se podría analizar
geographika
Su primer comentario cambia la unidad de análisis de las personas a los lugares. Si bien estoy de acuerdo en que la pregunta es algo ambigua, no hay nada que insinúe que el OP quiere agrupar lugares. Puedo ver un argumento para el segundo comentario (un punto tiene un atributo de velocidad). Si bien es una noción interesante, es bastante abstracta y novedosa, por lo tanto, no creo que tenga mucho sentido sugerir examinar la autocorrelación espacial y es probable que sea confusa (puede agrupar puntos en ese marco, no rutas completas). Sin embargo, estoy de acuerdo en que las bibliotecas Pysal y R serán de interés.
Andy W
2

Si bien no puedo comentar mucho sobre las trayectorias o caminos de su gente, creo que está en el camino correcto con el enfoque de clúster y tiempo.

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

Analiza los "sitios de alimentación" (grupos) de leopardos de las nieves según los criterios dados:

  • qué tan agrupados estaban esos puntos (distancia entre sí)
  • un umbral mínimo de puntos (mi análisis requirió más de 4 puntos ya que las lecturas se tomaron aproximadamente cada 12 horas)
  • los puntos deben ser secuenciales (parte fácil del análisis, ya que deben recopilarse en un orden lineal)

Si bien utiliza las herramientas de Esri para hacer el análisis de distancia, el script de Python en el interior podría ayudarlo con la idea de agrupamiento una vez que sepa qué puntos están cerca uno del otro. (utiliza la teoría de gráficos: http://en.wikipedia.org/wiki/Graph_theory )

Como se menciona en las otras respuestas, hay documentos disponibles para determinar los atributos que necesitaría para tomar las decisiones.

El análisis se basó libremente en los conceptos de: Knopff, KH, ARA Knopff, MB Warren y MS 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.

KHibma
fuente
2

Para ejecutar cualquier tipo de agrupación en su conjunto de trayectorias, debe tener una forma de calcular la similitud o la distancia de los pares de trayectoria. Hay varios métodos existentes para esto, y se están desarrollando otros nuevos para casos especiales o para corregir una deficiencia de los tradicionales (estoy trabajando personalmente en uno nuevo para mi tesis doctoral). Los algoritmos bien conocidos son los siguientes:

  • Distancia de par más cercana: simplemente defina la distancia de 2 trayectorias por la distancia del par de puntos más cercano entre sí. Las trayectorias deben consistir en el mismo número de puntos.
  • Suma de distancia de pares: calcule las distancias para cada par de puntos y sume. También funciona solo si las trayectorias son de la misma longitud
  • Distancia de deformación dinámica del tiempo (DTW): este algoritmo fue desarrollado para manejar trayectorias de diferentes cantidades de puntos medidos. Funciona en pares de puntos y permite que un punto de una trayectoria se use varias veces en los cálculos de distancia de pares, si el otro se mueve "demasiado rápido". Ilustración DTW(Imagen de Wikipedia )
  • Subsecuencia común más larga: como su nombre lo indica, define la similitud de dos trayectorias por la longitud de la subtrayectoria más larga donde los caminos originales están viajando cerca el uno del otro.
  • Editar distancia en secuencia real (EDR) y Editar distancia con penalización real (ERP) definen la similitud por el número de operaciones de edición (agregar, eliminar o reemplazar) que se necesitan para transformar una de las trayectorias en la otra.

Si está en este campo, le recomiendo el libro llamado "Computación con trayectorias espaciales" de varios investigadores de Microsoft Asia.

sw0rdf1sh
fuente
0

Esto también puede ser de ayuda para usted:

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

También eche un vistazo a este blog:

ideasonmovement.wordpress.com/

David
fuente