Dynamic time warping: cómo funciona el algoritmo DTW

El algoritmo dynamic time warping (DTW), también conocido como alineamiento temporal dinámico, se utiliza para comprobar las coincidencias en secuencias de valores de diferentes longitudes mediante la comparación con patrones. Para ello, sin importar el desfase del tiempo, el algoritmo crea rutas de alineamiento en las que pueden reconocerse coincidencias mediante backtracking y medidas diferenciales. Este algoritmo se utiliza, entre otros, en el reconocimiento de voz, en el reconocimiento de firmas digitales o en el análisis de mercados financieros.

¿Qué significa dynamic time warping?

Dynamic time warping (DTW) se puede traducir como “alineamiento temporal dinámico”. Aunque en un principio se puede considerar una tecnología sacada de Star Trek, no es más que un algoritmo que permite comparar secuencias temporales o series de valores. Aunque las secuencias cuenten con longitudes o velocidades diferentes, el “alineamiento” permite encontrar patrones de coincidencias entre las secuencias.

Por ejemplo, si se comparan varias firmas de una misma persona, el algoritmo permite identificar coincidencias a pesar de que cada firma tenga un tamaño diferente. Lo mismo ocurre al usar el dynamic time warping al analizar dos secuencias de marchas; aunque cada marcha se produzca a una velocidad diferente o la distancia recorrida varíe, el algoritmo es capaz de reconocer patrones de coincidencia.

¿Para qué se usa el dynamic time warping?

Aunque en un primer momento el algoritmo DTW pueda parecer un concepto abstracto sin mucha utilidad, lo cierto es que cumple con una importante función de análisis en distintos ámbitos. Es especialmente útil en el análisis de secuencias de vídeo y audio, gráficos o modelos estadísticos, esto es, con aquellas secuencias que se pueden comparar de forma lineal. Si se detectan determinadas coincidencias, el algoritmo DTW puede poner en marcha determinadas acciones, señales o funciones.

Además, gracias a la medición de patrones y al reconocimiento de pautas en series de valores, también se pueden analizar desarrollos similares de sistemas en distintos periodos de tiempo. Por este motivo, el algoritmo DTW también se usa en tecnologías como el machine learning, el supervised learning o la neural networks. Con este algoritmo, las distintas tecnologías presentadas entrenan sus capacidades de análisis y reacción y, en consecuencia, pueden evaluar conjuntos de datos con mayor eficiencia.

¿Cómo funciona el dynamic time warping?

Para identificar patrones y coincidencias en distintas series de valores, DTW busca coincidencias óptimas, para lo que resulta útil los principios “one-to-many” o “many-to-one”. Se aplican diversas normas y condiciones:

• Cada valor de una secuencia debe compararse con uno o varios valores de la segunda secuencia (y viceversa).
• El primer valor de una secuencia debe compararse con el primer valor de la segunda secuencia.
• El último valor de una secuencia debe compararse con el último valor de la segunda secuencia.
• El mapeo de la serie de valores de la primera secuencia con la serie de valores de la segunda secuencia debe aumentar de forma monotónica. Por lo tanto, los valores al principio y al final de las secuencias deben coincidir en sus posiciones, sin omisiones ni solapamientos.

Si se cumplen todos los puntos antes expuestos se habla de una coincidencia óptima. Aquí entra en juego la llamada función de costo, con la que se puede crear una medida diferencial entre los valores de las secuencias. Una coincidencia óptima depende de una función de costo lo más baja posible.

Además, el algoritmo genera una ruta de alineamiento capaz también de reconocer coincidencias óptimas en secuencias de diferente longitud. La ruta de alineamiento se crea mediante backtracking: el algoritmo relaciona uno o más valores de una secuencia con puntos de la segunda secuencia. De este modo, se pueden encontrar coincidencias incluso en secuencias temporales de distinta longitud, sin importar la deformación temporal.

¿Dónde se utiliza el dynamic time warping?

Se puede usar el algoritmo DTW siempre que los conjuntos de datos puedan proyectarse y compararse en secuencias lineales. Por ejemplo, el algoritmo DTW se utiliza a menudo como análisis previo o posterior del análisis de datos, ya sean datos de audio, de vídeo, alfanuméricos o conjuntos de datos basados en Big Data.

Otros ámbitos de aplicación del DTW son:

• Reconocimiento de patrones en secuencias de audio: el DTW se usa en el reconocimiento de voz. Los patrones de voz grabados y almacenados se comparan mediante DTW en la concordancia de patrones. Para secuencias de audio de distinta duración o velocidad, el DTW permite detectar coincidencias incluso en vocales y consonantes pronunciadas a distinta velocidad.
• Reconocimiento de patrones en secuencias de vídeo: para reconocer gestos y movimientos, DTW compara secuencias de vídeo. Se realiza una comparación y un reconocimiento de patrones en secuencias de movimientos, incluso si la duración temporal o la velocidad difieren en las secuencias.
• Reconocimiento de patrones en datos financieros: otro ámbito de uso importante se encuentra en los mercados financieros y en las finanzas empresariales. De hecho, el algoritmo DTW puede ser muy útil para generar pronósticos sobre ciclos financieros, volumen de ventas o tendencias en bolsa. Este algoritmo puede utilizarse para visualizar ciclos y tendencias similares o idénticos en datos de mercados y empresas en distintos periodos de tiempo. El análisis se basa en datos empresariales y financieros recopilados, así como en pronósticos.

¿Qué herramientas usan el algoritmo dynamic time warping?

El algoritmo DTW puede encontrarse en las bibliotecas de varios programas de código abierto. Por ejemplo, en:

• DTW Suite con paquetes de programación para Python y R.
• FastDTW, que ofrece una implementación Java para algoritmos DTW.
• MatchBox, que implementa DTW para señales de audio.
• mlpy y pydtw, que proporcionan funciones DTW como bibliotecas de Python para machine learning.
• Gesture Recognition, que ofrece algoritmos DTW para el reconocimiento gestual en tiempo real.

Para usar DTW de la forma más eficiente posible, también se utilizan las siguientes técnicas de fast computation:

• PruneDTW
• SparseDTW
• FastDTW
• MultiescalaDTW

Un ejemplo: algoritmo dynamic time warping en Python

Como muestra de la complejidad del algoritmo DTW, puedes encontrar un ejemplo de este algoritmo DTW en Python:

def dtw(s, t, window):
    n, m = len(s), len(t)
    w = np.max([window, abs(n-m)])
    dtw_matrix = np.zeros((n+1, m+1))
    
    for i in range(n+1):
        for j in range(m+1):
            dtw_matrix[i, j] = np.inf
    dtw_matrix[0, 0] = 0
    
    for i in range(1, n+1):
        for j in range(np.max([1, i-w]), np.min([m, i+w])+1):
            dtw_matrix[i, j] = 0
    
    for i in range(1, n+1):
        for j in range(np.max([1, i-w]), np.min([m, i+w])+1):
            cost = abs(s[i-1] - t[j-1])
            # take last min from a square box
            last_min = np.min([dtw_matrix[i-1, j], dtw_matrix[i, j-1], dtw_matrix[i-1, j-1]])
            dtw_matrix[i, j] = cost + last_min
    return dtw_matrix

En la función presentada en el ejemplo primero se incluyen tres parámetros: en primer lugar, se incluyen las dos señales que se van a analizar en los parámetros s y t. Normalmente, las señales son matrices o vectores. El parámetro* window* puede utilizarse para determinar con cuántos elementos puede producirse una coincidencia.

A continuación, se crea una matriz en la función y se inicializa con el valor infinito. El paso central del algoritmo DTW se produce en los dos últimos bucles for anidados: el valor de la variable last_min se añade a los costos anteriores de la variable costs, los cuales resultan de la distancia entre los dos valores de entrada en el índice respectivo.

El valor de la variable last_min resulta de valores calculados anteriormente gracias a la programación dinámica. Se escoge el mínimo de los valores calculados anteriormente y se añade a los costos calculados previamente. Con este paso se establece si dos elementos coinciden, si se añade un elemento o si se elimina un elemento.

Después de que la función se ejecute, se obtiene una matriz de distancia a partir de la cual se puede leer la ruta de alineamiento.

Alternativas al dynamic time warping

Algunas de las alternativas al algoritmo DTW para el reconocimiento de patrones en secuencias y secuencias temporales son:

• Correlation Optimized Warping (COW)
• Análisis de datos funcionales
• Modelo oculto de Márkov
• Algoritmo de Viterbi