Comparaison de deux graphiques de cotation avec des distorsions non linéaires sur l'axe des X - page 6

Nouveau commentaire
 

Comment ce problème est-il résolu via DTW (exemple) :

  1. Nous devons trouver des situations similaires sur l'historique comme les barres extrêmes de 100.
  2. L'historique disponible est de 1 000 000 de barres.
  3. Tout d'abord, nous avons pris 1 000 000 de séquences de 50 mesures et les avons comparées avec le modèle par DTW.
  4. Ensuite, nous avons pris 1 000 000 de séquences supplémentaires de 55 barres et les avons comparées au modèle par DTW.
  5. Cette fois, il s'agit de 60 bars.
  6. .....
  7. A 100 bars.
  8. .....
  9. 300 bars. Et c'est là que nous pouvons nous arrêter.

Au total, nous avons effectué 50 000 000 de comparaisons en utilisant l'algorithme DTW qui a une complexité de O(N^2). Cela signifie qu'environ 5 * 10^11 (500 milliards) d'opérations de calcul élémentaires ont été effectuées.

Maintenant, une nouvelle barre est arrivée - nous avons refait 500 milliards de calculs.

Nous avons décidé de l'exécuter sur l'historique, en partant de 200 000 de l'élément le plus extérieur. En gros, il faut 200 000 fois 500 milliards de calculs chacun pour faire une course. Cela fait 10^17 calculs au total.

Même s'il existe une optimisation délicate, elle ne permettra pas un gain de plus de deux ordres de grandeur. C'est-à-dire qu'il devra effectuer 10^15 calculs au maximum.

 
hrenfx:

Comment cette tâche est résolue par DTW (exemple) :

Vous voyez, à ce stade, nous sommes plus intéressés par le DTW lui-même que par la manière de l'appliquer.
 
hrenfx: Comment cette tâche est résolue avec DTW (exemple) :

Si vous le voulez bien, montrez la solution de ce problème dans le code, ce n'est pas tant un intérêt pratique, mais plutôt un intérêt sportif.

 

Aucune personne saine d'esprit n'entreprendrait de mettre en œuvre un algorithme dont le résultat n'attendrait tout simplement pas.

Le même Pearson QC serait également inadapté, tout comme DTW, puisque sa complexité de calcul est également O(N^2). Mais il existe une optimisation algorithmique significative du calcul du QC de Pearson avec une complexité O(N * log(N)) qui pourrait permettre de résoudre ce problème en un temps raisonnable. L'implémentation de cet algorithme a été publiée dans Codebase. Pour résoudre le problème soulevé, il reste à appliquer le même algorithme à l'ensemble des ZVR transformés en ZigZag.

 
hrenfx:

Aucune personne saine d'esprit n'entreprendrait de mettre en œuvre un algorithme dont le résultat n'attendrait tout simplement pas.

Le même Pearson QC serait également inadapté, tout comme DTW, puisque sa complexité de calcul est également O(N^2). Mais il existe une optimisation algorithmique significative du calcul du QC de Pearson avec une complexité O(N * log(N)) qui pourrait permettre de résoudre ce problème en un temps raisonnable. L'implémentation de cet algorithme a été publiée dans Codebase. Pour résoudre le problème soulevé, il reste à appliquer le même algorithme à l'ensemble des ZVR transformés en ZigZag.


Vous devez d'abord lire le problème auquel l'auteur est confronté et ses réponses.
 
Integer:


J'ai essayé. Je ne comprends pas non plus comment l'utiliser. La sortie doit être soit un chemin de transformation, soit des données transformées.

Le résultat de l'algorithme est une "matrice des coûts cumulés" (plutôt que la simple matrice des distances locales présentée dans la figure), la méthode renvoyant la valeur de la cellule inférieure droite (par construction, il s'agit du maximum de la matrice entière). Pour trouver le chemin maintenant, il suffit de se déplacer de la cellule (n,m) vers la cellule (1,1), en choisissant à chaque fois l'option ayant la valeur la plus faible :

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
 
Le réseau de chemins qui en résulte contient le chemin optimal pour transformer un signal en un autre. Cela peut se faire dans les deux sens.
 
Le degré de similarité des signaux est déterminé par la valeur de la cellule inférieure droite de la matrice, plus elle est grande, plus les signaux sont différents.
 
alsu: Le degré de similarité des signaux est déterminé par la valeur de la cellule inférieure droite de la matrice, plus elle est grande, plus les signaux sont différents.
OK, merci, vous l'avez expliqué très clairement, une dernière question : est-il nécessaire de normaliser ou de réduire les données au même ordre, cela affecte-t-il le résultat ?
 
IgorM:
OK, merci, c'était assez clair, une autre question : est-il nécessaire de normaliser ou de réordonner les données, cela affecte-t-il le résultat ?
dtw[n][m] dépend de l'échelle, donc s'il y a beaucoup de comparaisons par paires, nous devrions augmenter l'échelle et la centrer de préférence.
123456789101112
Nouveau commentaire