Algoritmo de transformación dinámica de línea de tiempo

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 12 de diciembre de 2014; las comprobaciones requieren 11 ediciones .

El algoritmo para la transformación dinámica de la escala de tiempo ( algoritmo DTW , del inglés dynamic time warping ) es un algoritmo que le permite encontrar la coincidencia óptima entre secuencias de tiempo. Se aplicó por primera vez en el reconocimiento de voz , donde se usa para determinar cómo dos señales de voz representan la misma frase hablada original. Posteriormente, se encontraron aplicaciones en otras áreas [1] .

Las series temporales son un tipo de datos muy utilizado[ aclarar ] que ocurre en prácticamente cualquier campo científico, y comparar dos secuencias es una tarea estándar. Para calcular la desviación, es suficiente una simple medición de la distancia entre los componentes de dos secuencias (distancia euclidiana). Sin embargo, a menudo dos secuencias tienen aproximadamente las mismas formas generales, pero estas formas no están alineadas en el eje X. Para determinar la similitud entre dichas secuencias, debemos "deformar" el eje de tiempo de una (o ambas) de la secuencia para lograr una mejor alineación. [2]

Algoritmo

Es necesario medir la distancia entre dos series de tiempo para determinar su similitud y clasificación. Una medida tan efectiva es la métrica euclidiana . Para dos secuencias de tiempo, esto es simplemente la suma de las distancias al cuadrado desde cada punto n de una secuencia hasta el punto n de la otra. Sin embargo, el uso de la distancia euclidiana tiene un inconveniente importante: si dos series temporales son iguales, pero una de ellas se desplaza ligeramente en el tiempo (a lo largo del eje temporal), entonces la métrica euclidiana puede considerar que las series difieren entre sí. . El algoritmo DTW se introdujo para superar esta deficiencia y proporcionar una medición visual de la distancia entre las filas, sin prestar atención a los cambios globales y locales en la escala de tiempo . [3]

Algoritmo clásico

Considere dos series temporales: longitudes y longitudes [4] : $q$ $norte$ $C$ $metro$

Q=q_{1},q_{2},\ldots,q_{i},\ldots,q_{n};\qquad \qquad (1)

C=c_{1},c_{2},\ldots,c_{j},\ldots,c_{m}.\qquad \qquad (2)

La primera etapa del algoritmo es la siguiente. Construimos una matriz de orden ( matriz de distancia ) en la que el elemento es la distancia entre dos puntos y . Normalmente se utiliza la distancia euclidiana: , o . Cada elemento de la matriz corresponde a la alineación entre los puntos y . $d$ $n\veces m$ ${\displaystyle d_{i\;j))$ ${\ estilo de visualización d (q_ {i}, c_ {j})}$ ${\ Displaystyle q_ {i}}$ ${\ Displaystyle c_ {j}}$ $d(q_{i},c_{j})=(q_{i}-c_{j})^{2}\quad$ $d(q_{i},c_{j})=|q_{i}-c_{j}|$ $(yo, j)$ ${\ Displaystyle q_ {i}}$ ${\ Displaystyle c_ {j}}$

En la segunda etapa, construimos una matriz de transformación (deformación) , cada elemento del cual se calcula en función de la siguiente relación: $D$

D_{i\;j}=d_{i\;j}+min({D_{i-1\;j},D_{i-1\;j-1},D_{i\;j -1}}).\qquad(3)

Después de completar la matriz de transformación, pasamos al paso final, que es construir una ruta de transformación óptima (deformación) y una distancia DTW ( costo de la ruta ).
Una ruta de transformación es un conjunto de elementos de matriz adyacentes que se asignan entre y . Representa el camino que minimiza la distancia total entre y . El elemento th de la ruta se define como . De este modo: $W$ $q$ $C$ $q$ $C$ $k$ $W$ $w_{k}=(i,j)_{k},\quad d(w_{k})=d(q_{i},c_{j})=(q_{i}-c_{j })^{2}$

W=w_{1},w_{2},\ldots,w_{k},\ldots,w_{K};\qquad max(m,n)\leqslant K<m+n,

donde es la longitud del camino. $k$

La ruta de transformación debe satisfacer las siguientes condiciones de restricción:

Condiciones de contorno : el comienzo del camino , su final - . Esta restricción garantiza que la ruta de transformación contenga todos los puntos de ambas series temporales. ${\ estilo de visualización w_ {1} = (1,1)}$ ${\ estilo de visualización w_ {K} = (n, m)}$
Continuidad (condición sobre la longitud del paso): dos elementos cualesquiera adyacentes del camino , y , satisfacen las siguientes desigualdades: , . Esta restricción asegura que la ruta de transformación avance un paso a la vez. Es decir, ambos índices y solo pueden aumentar en 1 en cada paso de la ruta. $W$ $w_{k}=(w_{i},w_{j})$ ${\ estilo de visualización w_{k+1}=(w_{i+1},w_{j+1})}$ $w_{i}-w_{i+1}\leqslant 1$ $w_{j}-w_{j+1}\leqslant 1$ $i$ $j$
Monotonicidad : dos elementos cualesquiera adyacentes del camino , y , satisfacen las siguientes desigualdades: , . Esta restricción garantiza que la ruta de transformación no vuelva al punto por el que ha pasado. Es decir, ambos índices y permanecen igual o aumentan (pero nunca disminuyen). $W$ $w_{k}=(w_{i},w_{j})$ $w_{k-1}=(w_{i-1},w_{j-1})$ $w_{i}-w_{i-1}\geqslant 0$ $w_{j}-w_{j-1}\geqslant 0$ $i$ $j$

Aunque existe un gran número de caminos de transformación que satisfacen todas las condiciones anteriores, sin embargo, solo nos interesa el camino que minimiza la distancia DTW ( costo del camino ).

La distancia DTW ( costo de la ruta ) entre dos secuencias se calcula en función de la ruta de transformación óptima mediante la fórmula:

DTW(Q,C)=min\left\{{\frac {\sum \limits _{k=1}^{K}{d(w_{k))))){K}}\right \ }.\qquad(4)

$k$ en el denominador se utiliza para tener en cuenta el hecho de que las rutas de transformación pueden tener diferentes longitudes.

La complejidad espacial y temporal del algoritmo es cuadrática, ya que el algoritmo DTW debe examinar cada celda de la matriz de transformación. $En M)$

Desventajas del algoritmo

Aunque el algoritmo se ha utilizado con éxito en muchas áreas, puede producir resultados incorrectos. El algoritmo puede tratar de explicar la volatilidad del eje con una transformación del eje . Esto puede dar lugar a una alineación en la que un punto de la primera secuencia se asigna a un gran subconjunto de puntos de la segunda secuencia. $y$ $X$

Otro problema es que el algoritmo puede no encontrar una alineación obvia de dos series debido al hecho de que el punto singular (pico, valle, meseta, punto de inflexión ) de una serie se encuentra ligeramente por encima o por debajo del punto singular correspondiente de la otra serie. [5] .

Variedades del algoritmo DTW

Varias mejoras del algoritmo DTW están destinadas a acelerar sus cálculos, así como a controlar mejor las posibles rutas de transformación.

Restricciones generales (globales)

Una de las variantes comunes del algoritmo DTW es la imposición de condiciones limitantes generales (globales) en las trayectorias de deformación admisibles [6] . Sea un subconjunto que defina el área de la restricción global. Ahora la ruta de transformación es la ruta contenida en el archivo . La ruta de transformación óptima es la ruta que pertenece y minimiza el costo de la ruta entre todas las rutas de transformación de . $R\subseteq [1:n]\times [1:m]$ $R$ $R$ $R$

Algoritmo DTW rápido

Este algoritmo tiene una complejidad espacial y temporal lineal . El algoritmo DTW rápido utiliza un enfoque en capas con tres operaciones clave [7] :

Disminuir en detalle: reducimos el tamaño de la serie temporal promediando pares de puntos adyacentes. La serie de tiempo resultante es una serie que tiene la mitad de puntos que la original. Ejecutamos esta operación varias veces para obtener muchas resoluciones de series de tiempo diferentes.
Planificación: tomamos la ruta de transformación con poco detalle y determinamos a través de qué celdas pasará la ruta de transformación en el siguiente detalle (un orden de magnitud más alto que el anterior). Dado que la resolución se duplica, un punto perteneciente a la ruta de transformación a baja resolución corresponderá a al menos cuatro puntos a mayor resolución. Esta ruta planificada se usa luego como una heurística durante el procesamiento para encontrar la ruta de alta resolución.
El procesamiento es la búsqueda de la ruta de deformación óptima en la vecindad de la ruta planificada.

Algoritmo DTW disperso

La idea principal de este método es utilizar dinámicamente la presencia de similitud y/o comparación de datos para dos secuencias de tiempo. Este algoritmo tiene tres ventajas específicas [8] :

La matriz de transformación se representa utilizando matrices dispersas , lo que resulta en una reducción de la complejidad espacial promedio en comparación con otros métodos.
El algoritmo DTW disperso siempre produce la ruta de transformación óptima.
Dado que el algoritmo produce una alineación óptima, se puede usar fácilmente en combinación con otros métodos.

Aplicaciones

reconocimiento de voz
procesamiento de datos
reconocimiento de gestos
robótica
la medicina
bioinformática
verificación de firma

Notas

↑ Ghazi Al-Naymat, Sanjay Chawla, Javid Taheri Sparse DTW: A novel approach to speed up Dynamic Time Warping Archivado el 13 de octubre de 2019 en Wayback Machine .
↑ Eamonn J. Keogh, Michael J. Pazzani Derivative Dynamic Time Warping, Sección 1 Archivado el 30 de julio de 2016 en Wayback Machine .
↑ Stan Salvador y Philip Chan Fast DTW: Toward Accurate Dynamic Time Warping in Linear Time and Space Archivado el 31 de octubre de 2014 en Wayback Machine .
↑ Eamonn J. Keogh, Michael J. Pazzani Derivative Dynamic Time Warping, Sección 2 Archivado el 30 de julio de 2016 en Wayback Machine .
↑ Eamonn J. Keogh, Michael J. Pazzani Derivative Dynamic Time Warping, Sección 1, página 2 Archivado el 30 de julio de 2016 . (Inglés)
↑ Revisión del algoritmo DTW. Sección 3.3 Archivado el 17 de diciembre de 2014 en Wayback Machine .
↑ Stan Salvador y Philip ChanFast DTW: Toward Accurate Dynamic Time Warping in Linear Time and Space Archivado el 31 de octubre de 2014 en Wayback Machine .
↑ Ghazi Al-Naymat, Sanjay Chawla, Javid Taheri Sparse DTW: A novel approach to speed up, Sección 1.1 Archivado el 13 de octubre de 2019 en Wayback Machine .