Comparación de dos gráficos de cotización con distorsiones no lineales en el eje X - página 6

Nuevo comentario
 

Cómo se resuelve este problema mediante DTW (ejemplo):

  1. Tenemos que encontrar situaciones similares en el historial como las 100 barras extremas.
  2. El historial disponible es de 1 000 000 de barras.
  3. En primer lugar, tomamos 1.000.000 de secuencias de 50 barras y las comparamos con el patrón mediante DTW.
  4. A continuación, tomamos otro 1.000.000 de secuencias de 55 barras y las comparamos mediante DTW con la plantilla.
  5. Esta vez son 60 bares.
  6. .....
  7. A 100 bares.
  8. .....
  9. 300 bares. Y aquí es donde podemos parar.

En total hemos realizado 50.000.000 de comparaciones utilizando el algoritmo DTW que tiene una complejidad de O(N^2). Es decir, se realizaron aproximadamente 5 * 10^11 (500 mil millones) de operaciones de cálculo elementales.

Ahora ha llegado una nueva barra: hemos vuelto a hacer 500.000 millones de cálculos.

Decidimos ejecutarlo en la historia, a partir de 200.000 del último elemento. Aproximadamente, se necesitan 200.000 veces 500.000 millones de cálculos cada una para hacer una carrera. Son 10^17 cálculos en total.

Incluso si hay una optimización complicada, no producirá una ganancia de más de dos órdenes de magnitud. Es decir, tendrá que realizar 10^15 cálculos como máximo.

 
hrenfx:

Cómo se resuelve esta tarea mediante DTW (ejemplo):

Como ves, en este punto nos interesa más el DTW en sí que la forma de aplicarlo.
 
hrenfx: Cómo se resuelve esta tarea con DTW (ejemplo):

Si no te importa, por favor, muestra la solución de este problema en el código, no es tanto de interés práctico, sino más bien de interés deportivo.

 

Nadie en su sano juicio se comprometería a poner en práctica un algoritmo cuyo resultado simplemente no esperaría.

El mismo Pearson QC tampoco sería adecuado, al igual que DTW, ya que su complejidad computacional también es O(N^2). Pero existe una importante optimización algorítmica del cálculo de Pearson QC con una complejidad O(N * log(N)) que podría permitir resolver este problema en un tiempo razonable. La implementación de este algoritmo se ha publicado en Codebase. Para resolver el problema planteado, queda aplicar el mismo algoritmo al conjunto de ZVRs transformados en ZigZag.

 
hrenfx:

Nadie en su sano juicio se comprometería a poner en práctica un algoritmo cuyo resultado simplemente no esperaría.

El mismo Pearson QC tampoco sería adecuado, al igual que DTW, ya que su complejidad computacional también es O(N^2). Pero existe una importante optimización algorítmica del cálculo de Pearson QC con una complejidad O(N * log(N)) que podría permitir resolver este problema en un tiempo razonable. La implementación de este algoritmo se ha publicado en Codebase. Para resolver el problema planteado, queda aplicar el mismo algoritmo al conjunto de ZVRs transformados en ZigZag.


Primero debes leer el problema al que se enfrenta el autor y sus respuestas.
 
Integer:


Lo he probado. Yo tampoco entiendo cómo se usa. La salida debe ser una ruta de transformación o datos transformados.

El resultado del algoritmo es una "matriz de costes acumulados" (en lugar de la matriz de distancias locales mostrada en la figura), en la que el método devuelve el valor de la celda inferior derecha (por construcción, es el máximo de toda la matriz). Para encontrar el camino ahora, sólo tenemos que movernos desde la celda (n,m) hacia la celda (1,1), eligiendo cada vez la opción con el valor más bajo:

1: path[] <- new array
2: i =rows(dtw)
3: j =columns(dtw)
4: while(i>1) & (j>1)do
5:    if (i == 1) then
6:       j = j-1
7:    else if (j == 1) then
8:       i = i-1
9:    else
10:     if dtw(i-1;j) == min{dtw(i-1;j); dtw(i;j-1); dtw(i-1; j-1)} then 
11:        i = i-1
12:     else if dtw(i;j-1) == min{dtw(i-1;j); dtw(i;j-1); dtw(i-1;j-1)} then
13:        j = j-1
14:     else
15:     i = i-1; j = j-1
16:     end if
17:   path:add(i;j)
18:   end if
19: end while
20: return path
 
La matriz de trayectorias resultante contiene la trayectoria óptima para transformar una señal en otra. Esto puede hacerse en cualquier dirección.
 
El grado de similitud de las señales viene determinado por el valor de la celda inferior derecha de la matriz; cuanto mayor sea, más diferentes serán las señales.
 
alsu: El grado de similitud de las señales viene determinado por el valor de la celda inferior derecha de la matriz; cuanto mayor sea, más diferentes serán las señales.
Vale, gracias, lo has explicado bastante claro, una pregunta más: ¿es necesario normalizar o reducir los datos al mismo orden, afecta al resultado?
 
IgorM:
Vale, gracias, ha quedado bastante claro, una pregunta más: ¿es necesario normalizar o reordenar los datos, afecta al resultado?
dtw[n][m] depende de la escala, por lo que si hay muchas comparaciones por pares, debemos escalarlo y centrarlo preferentemente.
123456789101112
Nuevo comentario