Una medida de similitud de trayectoria. Frontera tecnológica
Basándose en datos de trayectoria a gran escala, se desarrollan funciones relevantes de consulta colectiva y se proporcionan para problemas que son difíciles de detectar para grupos susceptibles. Mediante la comparación y extracción de trayectorias, se pueden encontrar rápidamente personas que han tenido "contacto" con la trayectoria de la persona diagnosticada en el tiempo y el espacio. Entre ellas, una de las tareas más importantes para implementar esta función es cómo medir la similitud de dos trayectorias. A continuación se presentarán brevemente algunos métodos comunes de medición de similitud de trayectorias.
La trayectoria, como un tipo de datos espacio-temporales [1], se refiere a la trayectoria de movimiento de un objeto en el espacio, generalmente expresada como una secuencia de puntos GPS, como tr=, donde el punto pi= (lat, lng, t) indica que el objeto está ubicado en la posición de coordenadas geográficas (lat, lng) en el momento t, donde lat y lng representan la latitud y la longitud respectivamente.
En la era del big data, con la popularización de los sistemas de navegación de vehículos, se genera constantemente una gran cantidad de datos de trayectoria. Estas trayectorias contienen un valor enorme [2]. flujo de tráfico, que puede proporcionar información gubernamental. Proporciona sugerencias para la planificación urbana. También puede realizar agrupaciones de trayectorias para encontrar carreteras atravesadas por múltiples trayectorias, que pueden usarse para guiar la planificación de carriles para bicicletas; también puede detectar puntos estacionarios y encontrar; áreas donde las trayectorias a menudo permanecen.
El análisis y procesamiento de datos de trayectoria es extremadamente desafiante e incluye principalmente tres aspectos: 1) la cantidad de datos de trayectoria es grande; 2) los datos de trayectoria son ruidosos; 3) hay varias formas de obtener la trayectoria; datos. Entre ellos, la similitud de trayectorias sirve como un servicio de algoritmo básico, que mide la distancia entre dos trayectorias, lo que puede respaldar sus aplicaciones de capa superior y también es uno de los puntos calientes de la investigación actual.
En comparación con la medición de distancia punto a punto o punto a trayectoria, la medición de distancia entre trayectorias es más compleja y requiere que se consideren muchos factores, como la frecuencia de muestreo de la trayectoria, la información del tiempo de la trayectoria y la trayectoria misma. Ruido, etc. Los métodos comunes de medición de similitud de trayectorias se clasifican aproximadamente como se muestra en la siguiente figura.
Definimos las siguientes dos trayectorias con longitudes n y m respectivamente, y luego:
Distancia euclidiana La distancia euclidiana requiere que las dos trayectorias sean iguales en longitud y correspondan uno a uno. su definición matemática es:
La definición de distancia euclidiana es simple y clara, es decir, la distancia espacial promedio entre los puntos correspondientes de dos trayectorias, pero la desventaja también es obvia, es decir, la similitud de trayectorias de diferentes longitudes no se pueden medir y es sensible a puntos de ruido.
Dynamic Time Warping (DTW)
Como se mencionó anteriormente, una limitación obvia de la distancia euclidiana es que se requiere que la longitud de las dos trayectorias sea igual, lo cual no es muy práctico. en la práctica. Idealmente, debería haber cierta flexibilidad en la longitud de las pistas.
La idea del time warping dinámico DTW [3] es deformar automáticamente dos secuencias, escalarlas localmente y alinearlas en la línea de tiempo, para que sus formas sean lo más consistentes posible, obteniendo así la mayor coherencia posible. semejanza. DTW mapea los puntos de dos trayectorias en muchos a muchos, resolviendo así efectivamente el problema de los datos desiguales. Su algoritmo de programación dinámica es el siguiente:
Entre ellos, head(tr)= 1
El algoritmo de normalización de tiempo dinámico es flexible, tiene una longitud de trayectoria ilimitada y es efectivo, pero no No abordar los puntos de ruido también puede tener un gran impacto en los resultados.
Subsecuencia común más larga (LCSS)
Existe un problema de algoritmo clásico: resolver la subsecuencia común más larga de dos secuencias, que no requiere que dos subsecuencias comunes consecutivas estén conectadas, por ejemplo. Por ejemplo, la subsecuencia común más grande de BDCABA y ABCBDAB es BCBA. Sobre esta base, es natural proponer un método de medición de similitud de trayectorias basado en la subsecuencia * * * común más larga, es decir, LCSS, cuyo valor representa el número de puntos que pueden considerarse como el mismo punto como máximo, es decir, los dos las trayectorias satisfacen el mínimo El logaritmo de los puntos de trayectoria que están distanciados del límite umbral. El algoritmo basado en programación dinámica es el siguiente:
Entre ellos, el parámetro es el umbral de distancia mínima. Cuando la distancia entre dos puntos sea menor que este valor, se considerarán el mismo punto. Además, el algoritmo no tiene restricciones en cuanto a la longitud de la trayectoria.
La distancia de subcadena común más larga se ocupa de los puntos de ruido, es decir, debido a que la desviación del punto de ruido no está cerca de su punto de seguimiento, no se incluirá en el resultado final. Este paso funciona muy bien para el ruido.
Pero al mismo tiempo, el umbral de distancia mínima del algoritmo es difícil de definir y puede devolver trayectorias diferentes.
Editar la distancia de la secuencia real (EDR)
Dadas dos trayectorias tr1 y tr2 de longitud n y m respectivamente, y el umbral coincidente de la distancia mínima, entre las dos trayectorias La distancia EDR [4] es el número de operaciones necesarias para insertar, eliminar o reemplazar tr1 y convertirlo en tr2. El algoritmo basado en programación dinámica es el siguiente.
Entre ellos,
la distancia de edición de la trayectoria proporciona una nueva idea para la nueva medición de similitud de trayectoria, pero su defecto también es obvio, es decir, es sensible a los puntos de ruido. .
Distancia de Hausdorff
Simplemente hablando, la distancia de Hausdorff [5] es la distancia máxima entre los puntos más cercanos de dos trayectorias.
Donde h(tr1, tr2) se llama distancia de Hausdorff unidireccional de tr1 a tr2, la cual se define de la siguiente manera:
Distancia de Frechet (distancia de Frechet)
Intuitivamente hablando, la distancia de Flecher [6] es la distancia de la correa del perro, es decir, la longitud de correa más corta requerida para que el dueño camine por el camino A y el perro camine por el camino B, respectivamente.
El algoritmo de distancia de Flecher basado en ideas de programación dinámica es el siguiente:
donde d(p, q) es la distancia euclidiana entre dos puntos GPS, tr(n-1 )= es la subtrayectoria de la trayectoria tr de longitud n-1.
La distancia de Frecher nos proporciona un método simple e intuitivo para medir la similitud, que también puede lograr buenos resultados, aunque desafortunadamente no trata los puntos de ruido; Por ejemplo, si el punto de seguimiento del perro se desvía mucho debido al ruido, la distancia de Flecher también aumentará, lo que obviamente no es razonable.
Distancia unidireccional (OWD)
La distancia unidireccional OWD[7] se define de la siguiente manera:
donde |tr1 representa la longitud de la trayectoria| tr1, d(p, tr2) representa la distancia desde el punto GPS p a tr2. Para simetría, simplemente modifique la fórmula anterior:
Figura 11: Diagrama esquemático de la distancia unidireccional, que es la relación entre la suma de las áreas del polígono y la longitud de la polilínea.
El concepto básico de distancia OWD se basa en el área rodeada por dos pistas. Un área grande indica que la distancia entre trayectorias es larga y la similitud es baja. Por el contrario, si el área cerrada es 0, significa que las dos trayectorias se superponen y tienen la mayor similitud.
Posición entre polilíneas (LIP)
La distancia de posición multilínea LIP[8] se define de la siguiente manera:
donde Ii representa el I-ésimo de las dos trayectorias El punto de intersección y el peso wi se definen de la siguiente manera:
El método LIP es fácil de entender. Cuando la proporción del perímetro de un área determinada con respecto a la longitud total es grande, el peso es naturalmente. grande; cuando el área es 0, significa que no hay espacio entre las dos trayectorias. Cuando la distancia entre los labios es 0, la suma ponderada de las áreas es mayor, lo que significa que la distancia entre las dos trayectorias es mayor; la distancia entre los labios también es mayor. Además, el peso está determinado por la relación entre el perímetro de la superficie y la longitud total, que también resiste en cierta medida la interferencia de puntos de ruido.
Actualmente, el motor de datos espaciotemporal JUST (JD Urban Spatiotemporal Data Engine) desarrollado por JD.COM City ha implementado varios cálculos de similitud de trayectorias, como la deformación dinámica del tiempo, la distancia de Hausdorff y el método de distancia de Fleisher. Los usuarios solo necesitan un SQL para implementarlo y no se requiere codificación. Solo proporciona una función de visualización de trayectoria para que los usuarios la observen. Bienvenido a visitar/experimentar. Envíe un correo electrónico a just@jd.com para buscar cooperación.
Referencias:
[1] Zheng, y, et al. Computación urbana: conceptos, métodos y aplicaciones. ACM.
[2]Zheng Yu. Minería de datos de trayectoria: una revisión. Transacciones ACM sobre tecnología y sistemas inteligentes. 2015 Volumen 6 Número 3.
[3] Yi B K, Jagadish H V, Faloutsos C. Recuperación eficiente de series temporales similares bajo distorsión del tiempo[C]//Actas de la 14ª Conferencia Internacional sobre Ingeniería de Datos. IEEE, 1998: 201-208.
[4] Chen Sheng,? Búsqueda de similitudes rápida y robusta para trayectorias de objetos en movimiento[C]//Actas de la Conferencia Internacional ACM SIGMOD de 2005 sobre Gestión de Datos. 2005: 491-502.
[5] Alt H. Geometría computacional para comparar formas[M]//Algoritmo eficiente. Springer, Berlín, Heidelberg, 2009: 235-248.
[6] Eiter T, Mannila H. Cálculo de la distancia de Frecher discreta [R]. Informe técnico CD-TR 94/64, Laboratorio de sistemas expertos Christian Doppler, Universidad de Viena, Austria, Código postal: 1994.
[7] Artículo: Lin B, Su J. Distancia unidireccional: utilizada para la búsqueda de similitud de artefactos de objetos en movimiento basada en formas [J]. .
[8] Artículo LIP: Pelekis N, Kopanakis I, Marketos G, et al. Búsqueda de similitudes en la base de datos de trayectorias[C]//14º Taller Internacional sobre Representación y Razonamiento Temporal (TIME '07). , 2007: 129-140.