algorithm
Time Warping dinámico
Buscar..
Introducción a la distorsión de tiempo dinámico
Dynamic Time Warping (DTW) es un algoritmo para medir la similitud entre dos secuencias temporales que pueden variar en velocidad. Por ejemplo, las similitudes en la marcha se pueden detectar utilizando DTW, incluso si una persona caminaba más rápido que la otra, o si hubo aceleraciones y desaceleraciones durante el curso de una observación. Se puede usar para hacer coincidir un comando de voz de muestra con el comando de otros, incluso si la persona habla más rápido o más lento que la voz de muestra pregrabada. DTW puede aplicarse a secuencias temporales de datos de video, audio y gráficos; de hecho, cualquier información que pueda convertirse en una secuencia lineal puede analizarse con DTW.
En general, DTW es un método que calcula una coincidencia óptima entre dos secuencias dadas con ciertas restricciones. Pero sigamos con los puntos más simples aquí. Digamos, tenemos dos secuencias de voces Muestra y Prueba , y queremos comprobar si estas dos secuencias coinciden o no. Aquí la secuencia de voz se refiere a la señal digital convertida de su voz. Podría ser la amplitud o frecuencia de su voz que denota las palabras que dice. Asumamos:
Sample = {1, 2, 3, 5, 5, 5, 6}
Test = {1, 1, 2, 2, 3, 5}
Queremos encontrar la coincidencia óptima entre estas dos secuencias.
Al principio, definimos la distancia entre dos puntos, d (x, y) donde x e y representan los dos puntos. Dejar,
d(x, y) = |x - y| //absolute difference
Vamos a crear una tabla de matriz 2D utilizando estas dos secuencias. Calcularemos las distancias entre cada punto de muestra con cada punto de prueba y encontraremos la coincidencia óptima entre ellos.
+------+------+------+------+------+------+------+------+
| | 0 | 1 | 1 | 2 | 2 | 3 | 5 |
+------+------+------+------+------+------+------+------+
| 0 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 1 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 2 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 3 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 5 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 5 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 5 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 6 | | | | | | | |
+------+------+------+------+------+------+------+------+
Aquí, la Tabla [i] [j] representa la distancia óptima entre dos secuencias si consideramos la secuencia hasta la Muestra [i] y la Prueba [j] , considerando todas las distancias óptimas que observamos antes.
Para la primera fila, si no tomamos valores de Muestra , la distancia entre esto y Prueba será infinita . Así que ponemos infinito en la primera fila. Lo mismo ocurre con la primera columna. Si no tomamos valores de Test , la distancia entre éste y Sample también será infinita. Y la distancia entre 0 y 0 será simplemente 0 . Obtenemos,
+------+------+------+------+------+------+------+------+
| | 0 | 1 | 1 | 2 | 2 | 3 | 5 |
+------+------+------+------+------+------+------+------+
| 0 | 0 | inf | inf | inf | inf | inf | inf |
+------+------+------+------+------+------+------+------+
| 1 | inf | | | | | | |
+------+------+------+------+------+------+------+------+
| 2 | inf | | | | | | |
+------+------+------+------+------+------+------+------+
| 3 | inf | | | | | | |
+------+------+------+------+------+------+------+------+
| 5 | inf | | | | | | |
+------+------+------+------+------+------+------+------+
| 5 | inf | | | | | | |
+------+------+------+------+------+------+------+------+
| 5 | inf | | | | | | |
+------+------+------+------+------+------+------+------+
| 6 | inf | | | | | | |
+------+------+------+------+------+------+------+------+
Ahora, para cada paso, consideraremos la distancia entre cada punto en cuestión y la agregaremos con la distancia mínima que encontramos hasta ahora. Esto nos dará la distancia óptima de dos secuencias hasta esa posición. Nuestra fórmula será,
Table[i][j] := d(i, j) + min(Table[i-1][j], Table[i-1][j-1], Table[i][j-1])
Para el primero, d (1, 1) = 0 , la Tabla [0] [0] representa el mínimo. Entonces el valor de la Tabla [1] [1] será 0 + 0 = 0 . Para el segundo, d (1, 2) = 0 . La tabla [1] [1] representa el mínimo. El valor será: Tabla [1] [2] = 0 + 0 = 0 . Si continuamos de esta manera, después de terminar, la tabla se verá así:
+------+------+------+------+------+------+------+------+
| | 0 | 1 | 1 | 2 | 2 | 3 | 5 |
+------+------+------+------+------+------+------+------+
| 0 | 0 | inf | inf | inf | inf | inf | inf |
+------+------+------+------+------+------+------+------+
| 1 | inf | 0 | 0 | 1 | 2 | 4 | 8 |
+------+------+------+------+------+------+------+------+
| 2 | inf | 1 | 1 | 0 | 0 | 1 | 4 |
+------+------+------+------+------+------+------+------+
| 3 | inf | 3 | 3 | 1 | 1 | 0 | 2 |
+------+------+------+------+------+------+------+------+
| 5 | inf | 7 | 7 | 4 | 4 | 2 | 0 |
+------+------+------+------+------+------+------+------+
| 5 | inf | 11 | 11 | 7 | 7 | 4 | 0 |
+------+------+------+------+------+------+------+------+
| 5 | inf | 15 | 15 | 10 | 10 | 6 | 0 |
+------+------+------+------+------+------+------+------+
| 6 | inf | 20 | 20 | 14 | 14 | 9 | 1 |
+------+------+------+------+------+------+------+------+
El valor en la Tabla [7] [6] representa la distancia máxima entre estas dos secuencias dadas. Aquí 1 representa la distancia máxima entre la muestra y la prueba es 1 .
Ahora, si retrocedemos desde el último punto, hacia el punto de inicio (0, 0) , obtendremos una línea larga que se mueve horizontal, vertical y diagonalmente. Nuestro procedimiento de backtracking será:
if Table[i-1][j-1] <= Table[i-1][j] and Table[i-1][j-1] <= Table[i][j-1]
i := i - 1
j := j - 1
else if Table[i-1][j] <= Table[i-1][j-1] and Table[i-1][j] <= Table[i][j-1]
i := i - 1
else
j := j - 1
end if
Continuaremos esto hasta llegar a (0, 0) . Cada movimiento tiene su propio significado:
- Un movimiento horizontal representa la eliminación. Eso significa que nuestra secuencia de prueba se aceleró durante este intervalo.
- Un movimiento vertical representa la inserción. Eso significa que la secuencia de prueba se desaceleró durante este intervalo.
- Un movimiento diagonal representa un partido. Durante este periodo la prueba y la muestra fueron iguales.
Nuestro pseudo-código será:
Procedure DTW(Sample, Test):
n := Sample.length
m := Test.length
Create Table[n + 1][m + 1]
for i from 1 to n
Table[i][0] := infinity
end for
for i from 1 to m
Table[0][i] := infinity
end for
Table[0][0] := 0
for i from 1 to n
for j from 1 to m
Table[i][j] := d(Sample[i], Test[j])
+ minimum(Table[i-1][j-1], //match
Table[i][j-1], //insertion
Table[i-1][j]) //deletion
end for
end for
Return Table[n + 1][m + 1]
También podemos agregar una restricción de localidad. Es decir, requerimos que si la Sample[i] coincide con la Test[j] , entonces |i - j| no es más grande que w , un parámetro de ventana.
Complejidad:
La complejidad de calcular el DTW es O (m * n) donde m y n representan la longitud de cada secuencia. Las técnicas más rápidas para computar DTW incluyen PrunedDTW, SparseDTW y FastDTW.
Aplicaciones:
- Reconocimiento de palabras habladas
- Análisis de poder de correlación
