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.​

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.​ Aunque el nombre implica series temporales, puede usarse para todo tipo de datos, como reconocimiento facial,​ firmas biométricas​ e incluso clasificación de señales genómicas.​ 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.​

Funcionamiento

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:​

• 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 $j>i$ son elementos de la primera secuencia, entonces no debe haber dos elementos $l>k$ en la otra secuencia, tales que el elemento $i$ coincida con el elemento $l$ y el elemento $j$ coincida con el elemento $k$, 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.​

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.​ 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.​ 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.​
• 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.​
• 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.​

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(N²) 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.

Bibliografía

• Vintsyuk, T. K. (1968). «Speech discrimination by dynamic programming». Kibernetika 4: 81-88. 
• Sakoe, H.; Chiba (1978). «Dynamic programming algorithm optimization for spoken word recognition». IEEE Transactions on Acoustics, Speech, and Signal Processing 26 (1): 43-49. doi:10.1109/tassp.1978.1163055. 
• Myers, C. S.; Rabiner, L. R. (1981). «A Comparative Study of Several Dynamic Time-Warping Algorithms for Connected-Word Recognition». Bell System Technical Journal 60 (7): 1389-1409. ISSN 0005-8580. doi:10.1002/j.1538-7305.1981.tb00272.x. 
• Rabiner, Lawrence; Juang, Biing-Hwang (1993). «Chapter 4: Pattern-Comparison Techniques». Fundamentals of speech recognition. Englewood Cliffs, N.J.: PTR Prentice Hall. ISBN 978-0-13-015157-5. 
• Müller, Meinard (2007). Dynamic Time Warping. In Information Retrieval for Music and Motion, chapter 4, pages 69-84. Springer. ISBN 978-3-540-74047-6. doi:10.1007/978-3-540-74048-3. 
• Rakthanmanon, Thanawin (September 2013). «Addressing Big Data Time Series: Mining Trillions of Time Series Subsequences Under Dynamic Time Warping». ACM Transactions on Knowledge Discovery from Data 7 (3): 10:1-10:31. PMC 6790126. PMID 31607834. doi:10.1145/2513092.2500489. 

• Datos: Q1268863
• Multimedia: Dynamic time warping / Q1268863