Confronto di due grafici di quotazione con distorsioni non lineari sull'asse X - pagina 6

Nuovo commento
 

Come si risolve questo problema tramite DTW (esempio):

  1. Abbiamo bisogno di trovare situazioni simili sulla storia come le 100 barre estreme.
  2. La cronologia disponibile è di 1 000 000 di barre.
  3. In primo luogo, abbiamo preso 1.000.000 di sequenze di 50 barre e le abbiamo confrontate con il modello attraverso DTW.
  4. Poi abbiamo preso altri 1.000.000 di sequenze di 55 barre e le abbiamo confrontate tramite DTW con il modello.
  5. Questa volta sono 60 barre.
  6. .....
  7. A 100 bar.
  8. .....
  9. 300 bar. Ed è qui che possiamo fermarci.

In totale abbiamo fatto 50.000.000 di confronti usando l'algoritmo DTW che ha una complessità di O(N^2). Cioè molto approssimativamente 5 * 10^11 (500 miliardi) di operazioni di calcolo elementari sono state eseguite.

Ora è arrivata una nuova barra - abbiamo fatto di nuovo 500 miliardi di calcoli.

Ha deciso di correre sulla storia, iniziando con 200.000 dell'elemento più esterno. Approssimativamente, ci vogliono 200.000 volte 500 miliardi di calcoli ciascuno per fare una corsa. Sono 10^17 calcoli in totale.

Anche se c'è un'ottimizzazione complicata, non darà un guadagno di più di due ordini di grandezza. Cioè dovrà eseguire al massimo 10^15 calcoli.

 
hrenfx:

Come questo compito viene risolto tramite DTW (esempio):

Vedete, a questo punto siamo più interessati al DTW stesso che a come applicarlo.
 
hrenfx: Come si risolve questo compito con DTW (esempio):

Se non ti dispiace, per favore mostra la soluzione di questo problema nel codice, non è tanto di interesse pratico, ma piuttosto di interesse sportivo.

 

Nessuno sano di mente si impegnerebbe ad implementare un algoritmo il cui risultato semplicemente non aspetterebbe.

Lo stesso Pearson QC sarebbe anche inadatto, così come DTW, poiché la sua complessità computazionale è anche O(N^2). Ma c'è una significativa ottimizzazione algoritmica del calcolo di Pearson QC con complessità O(N * log(N)) che potrebbe permettere di risolvere questo problema in un tempo ragionevole. L'implementazione di questo algoritmo è stata pubblicata in Codebase. Per risolvere il problema sollevato, resta da applicare lo stesso algoritmo all'insieme degli ZVR trasformati a ZigZag.

 
hrenfx:

Nessuno sano di mente si impegnerebbe ad implementare un algoritmo il cui risultato semplicemente non aspetterebbe.

Lo stesso Pearson QC sarebbe anche inadatto, così come DTW, poiché la sua complessità computazionale è anche O(N^2). Ma c'è una significativa ottimizzazione algoritmica del calcolo di Pearson QC con complessità O(N * log(N)) che potrebbe permettere di risolvere questo problema in un tempo ragionevole. L'implementazione di questo algoritmo è stata pubblicata in Codebase. Per risolvere il problema sollevato, resta da applicare lo stesso algoritmo all'insieme degli ZVR trasformati a ZigZag.


Dovresti prima leggere il problema che l'autore sta affrontando e le sue risposte.
 
Integer:


L'ho provato. Anch'io non capisco come usarlo. L'output dovrebbe essere un percorso di trasformazione o dati trasformati.

L'output dell'algoritmo è una "matrice dei costi accumulati" (piuttosto che solo la matrice della distanza locale mostrata nella figura), con il metodo che restituisce il valore della cella in basso a destra (per costruzione, è il massimo in tutta la matrice). Per trovare il percorso ora, dobbiamo solo muoverci dalla cella (n,m) verso la cella (1,1), scegliendo ogni volta l'opzione con il valore più basso:

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
 
L'array di percorsi risultante contiene il percorso ottimale per trasformare un segnale in un altro. Questo può essere fatto in entrambe le direzioni.
 
Il grado di somiglianza dei segnali è determinato dal valore della cella in basso a destra della matrice, più è grande, più i segnali sono diversi.
 
alsu: Il grado di somiglianza dei segnali è determinato dal valore della cella in basso a destra della matrice, più è grande, più i segnali sono diversi.
OK, grazie, l'hai spiegato abbastanza chiaramente, un'altra domanda: è necessario normalizzare o ridurre i dati allo stesso ordine, influenza il risultato?
 
IgorM:
OK, grazie, è stato abbastanza chiaro, un'altra domanda: c'è bisogno di normalizzare o riordinare i dati, influenza il risultato?
dtw[n][m] dipende dalla scala, quindi se ci sono molti confronti a coppie, dovremmo scalarlo e centrarlo preferibilmente.
123456789101112
Nuovo commento
Motivazione: