Deformación dinámica del tiempo

Dos repeticiones de una secuencia de marcha grabada con un sistema de captura de movimiento. Aunque hay diferencias en la velocidad de la marcha entre las repeticiones, las trayectorias espaciales de las extremidades siguen siendo muy similares.[1]​

En análisis de series temporales, la deformación dinámica del tiempo (en inglés, Dynamic Time Warping, DTW) es un algoritmo para medir la similitud entre dos secuencias temporales que permite obtener un buen ajuste incluso frente a un desfase en la velocidad o en el tiempo. Se trata de un algoritmo de aprendizaje no supervisado, puesto que no necesita ayuda externa para realizar inferencias sobre los datos, aunque puede combinarse con otros métodos para realizar aprendizaje supervisado.[2]​ Aunque el nombre implica series temporales, puede usarse para todo tipo de datos, como reconocimiento facial,[3]​ firmas biométricas[4]​ e incluso clasificación de señales genómicas.[5]​ Conceptualmente, es similar al algoritmo Needleman-Wunsch, en tanto a que ambos realizan una matriz de disimilitud, con las distancias entre todos los miembros de una relación, como manera de calcular la distancia óptima entre los miembros de un grupo.[6]​

Funcionamiento

Sobre una tabla que compara la distancia entre dos series de datos, unas flechas van iluminando el camino óptimo a seguir
Matriz de DTW y camino óptimo generado algorítmicamente

A diferencia del método euclídeo, que se basa en la comparación directa de cada punto de una serie con su equivalente en otra serie diferente, el DTW busca el "punto más cercano" entre cada punto de las dos series, permitiendo así discernir formas similares que pueden estar deformadas o desfasadas. Para ello, se genera una matriz de similitud, que compara las dos series y calcula las distancias entre todos los puntos de una y todos los puntos de la otra; y, sobre esa matriz, se selecciona el "camino más óptimo", es decir, la distancia más corta entre cada par de puntos. Para ello, sigue una serie de reglas:[7]​

  • Cada elemento de la primera secuencia debe coincidir con uno o más elementos de la otra secuencia, y viceversa.
  • El primer elemento de la primera secuencia debe coincidir, al menos, con el primer elemento de la otra secuencia (pero no tiene que ser la única coincidencia)
  • El último elemento de la primera secuencia debe coincidir, al menos, con el último elemento de la otra secuencia (pero no tiene que ser la única coincidencia)
  • El mapeo de los elementos de la primera secuencia a los elementos de la otra secuencia debe ser monotónicamente creciente, y viceversa, es decir si son elementos de la primera secuencia, entonces no debe haber dos elementos en la otra secuencia, tales que el elemento coincida con el elemento y el elemento coincida con el elemento , y viceversa.

El camino óptimo será, entonces, la ruta que satisfaga todas estas restricciones minimizando el coste, siendo este la suma de las diferencias absolutas entre los valores de cada par de elementos coincidentes, lo que puede llevar a la deformación no lineal de las secuencias respecto al tiempo, de manera que estas nuevas secuencias "deformadas" sí que estarían euclidianamente alineadas.[8]​

A diferencia de otros algoritmos, el DTW no genera nuevos elementos, sino que se limita a asociar los elementos existentes entre sí. Esto hace que el DTW sea menos sensible, al verse limitado por el número y la separación de los elementos discretos que forman cada serie temporal.

Aplicaciones

  • Reconocimiento automático del habla: Debido a los diferentes ritmos de habla, existen fluctuaciones no lineales en el patrón de habla frente al tiempo, que debe ser eliminadas.[9]​ Usando DTW, podemos capturar estas distancias, medirlas y cuantificar la similitud entre una muestra de audio y una señal maestra, lo que nos permite saber si se trata de la misma palabra o no.[10]​ También se puede usar para comparar la distancia entre la dicción de dos hablantes, lo que permite saber si se trata de la misma persona, lo que sirve de firma digital biométrica.[11]​
  • Clasificación de señales genómicas: Representando cadenas de ADN mediante símbolos, podemos comparar la posición y alineación de señales genómicas determinadas mediante agrupamiento.[5]​
  • Reconocimiento del paso: Si consideramos la situación del cuerpo con respecto al tiempo, obtenemos una serie temporal que puede ser procesada usando DTW para reconocer al sujeto.[4]​

Implementaciones de Código abierto

  • La biblioteca de C++ lbimproved , bajo la GNU GPL, proporciona una implementación en C++ del DTW.
  • La librería FastDTW es una implementación en Java de DTW y una implementación de FastDTW que proporciona alineaciones óptimas o casi óptimas con una complejidad de tiempo y memoria O(N), en contraste con el requisito O(N2) del algoritmo DTW estándar.
  • FastDTW fork (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última). (Java) publicado en Maven Central.
  • time-series-classification (Java) un paquete para la clasificación de series temporales usando DTW en Weka.
  • DTW suite proporciona paquetes de Python (dtw-python) y R (dtw) con una amplia cobertura de los miembros de la familia de algoritmos DTW, incluyendo una variedad de reglas de recursión (también llamadas patrones de paso), restricciones y coincidencia de subcadenas.
  • Las bibliotecas mlpy y pydtw de python implementan DTW.
  • La biblioteca cudadtw de C++/CUDA implementa la alineación de subsecuencias DTW de forma similar a la serie UCR de CUDA.
  • La biblioteca de aprendizaje automático JavaML implementa DTW.
  • La biblioteca C# ndtw implementa DTW con varias opciones.
  • Sketch-a-Char utiliza Greedy DTW (implementado en JavaScript) como parte de LaTeX.
  • MatchBox implementa DTW para emparejar señales de audio.
  • Sequence averaging: una implementación Java GPL de DBA.
  • El Gesture Recognition Toolkit|GRT, un kit de herramientas de reconocimiento de gestos en tiempo real de C++, implementa DTW.
  • El paquete PyHubs implementa DTW y los clasificadores de vecino más cercano, así como sus extensiones.
  • La biblioteca de Python simpledtw implementa el clásico algoritmo DTW y se basa en Numpy. Está licenciado bajo la licencia MIT.
  • La biblioteca de Python tslearn implementa DTW en el contexto de "series temporales".
  • La librería cuTWED de Python implementa una versión mejorada de DTW, el Time Warp Edit Distance, lo que permite mejorar la eficiencia.
  • DynamicAxisWarping.jl Es una implementación en Julia de DTW y algoritmos relacionados como FastDTW, SoftDTW, GeneralDTW y DTW barycenters.
  • dtwParallel es un paquete (en Python) que incorpora las funcionalidades principales de bibliotecas DTW actuales y añade nuevas funcionalidades como paralelización, computación de valores de similitud (basado en kernels), y la consideración de datos de diferentes tipos (categóricos, valores reales, etc.).[12]​

Referencias

  1. ↑ Olsen, Niels Lundtorp; Markussen, Bo; Raket, Lars Lau (2018). «Simultaneous inference for misaligned multivariate functional data». Journal of the Royal Statistical Society: Series C (Applied Statistics) (en inglés) 67 (5): 1147-1176. ISSN 1467-9876. doi:10.1111/rssc.12276. Consultado el 8 de noviembre de 2021. 
  2. ↑ Ding, Hui; Trajcevski, Goce; Scheuermann, Peter; Wang, Xiaoyue; Keogh, Eamonn (1 de agosto de 2008). «Querying and mining of time series data: experimental comparison of representations and distance measures». Proceedings of the VLDB Endowment 1 (2): 1542-1552. ISSN 2150-8097. doi:10.14778/1454159.1454226. Consultado el 8 de noviembre de 2021. 
  3. ↑ Majed, Somaya (27 de julio de 2011). Robust Face Localization Using Dynamic Time Warping Algorithm (en inglés). IntechOpen. ISBN 978-953-307-368-2. Consultado el 8 de noviembre de 2021. 
  4. ↑ a b Lee, Hyun-Seob (28 de agosto de 2019). «Application of dynamic time warping algorithm for pattern similarity of gait». Journal of Exercise Rehabilitation 15 (4): 526-530. ISSN 2288-176X. PMC 6732547. PMID 31523672. doi:10.12965/jer.1938384.192. Consultado el 8 de noviembre de 2021. 
  5. ↑ a b Skutkova, Helena; Vitek, Martin; Babula, Petr; Kizek, Rene; Provaznik, Ivo (12 de agosto de 2013). «Classification of genomic signals using dynamic time warping». BMC Bioinformatics 14 (10): S1. ISSN 1471-2105. PMID 24267034. doi:10.1186/1471-2105-14-S10-S1. Consultado el 8 de noviembre de 2021. 
  6. ↑ «Dissimilarity Matrix». Statistics.com: Data Science, Analytics & Statistics Courses (en inglés estadounidense). Consultado el 11 de noviembre de 2021. 
  7. ↑ Zhang, Jeremy (14 de febrero de 2020). «Dynamic Time Warping». Medium (en inglés). Consultado el 11 de noviembre de 2021. 
  8. ↑ Brijnesh, J. Jain; Schultz, David (2 de marzo de 2018). «Optimal Warping Paths are unique for almost every Pair of Time Series». Technische Universit ̈at Berlin. Consultado el 11 de noviembre de 2021. 
  9. ↑ Sakoe, Hiroaki; Chiba, Seibi (1978). «Optimización del algoritmo de programación dinámica para el reconocimiento de palabras habladas». IEEE Transactions on Acoustics, Speech, and Signal Processing 26 (1): 43-49. 
  10. ↑ Alizadeh, Esmaeil (13 de octubre de 2020). «An Illustrative Explanation to Dynamic Time Warping». Medium (en inglés). Consultado el 8 de noviembre de 2021. 
  11. ↑ Permanasari, Yurika; Harahap, Erwin H.; Ali, Erwin Prayoga (2019-11). «Speech recognition using Dynamic Time Warping (DTW)». Journal of Physics: Conference Series (en inglés) 1366: 012091. ISSN 1742-6588. doi:10.1088/1742-6596/1366/1/012091. Consultado el 8 de noviembre de 2021. 
  12. ↑ Escudero-Arnanz, Óscar; Marques, Antonio G; Soguero-Ruiz, Cristina; Mora-Jiménez, Inmaculada; Robles, Gregorio (2023). «dtwParallel: A Python package to efficiently compute dynamic time warping between time series». SoftwareX 22 (101364). doi:10.1016/J.SOFTX.2023.101364. Consultado el 6 de diciembre de 2024. 

Bibliografía