Vergleich von zwei Kurstabellen mit nichtlinearen Verzerrungen auf der X-Achse - Seite 6

Neuer Kommentar
 

Wie wird dieses Problem über DTW gelöst (Beispiel):

  1. Wir müssen ähnliche Situationen in der Geschichte finden wie die extremen 100 Balken.
  2. Die verfügbare Historie beträgt 1 000 000 Takte.
  3. Zuerst haben wir 1.000.000 Sequenzen von 50 Takten genommen und sie mit dem Muster durch DTW verglichen.
  4. Dann nahmen wir weitere 1.000.000 Sequenzen von 55 Takten und verglichen sie mittels DTW mit der Vorlage.
  5. Diesmal sind es 60 Takte.
  6. .....
  7. Bei 100 bar.
  8. .....
  9. 300 bar. Und an dieser Stelle können wir aufhören.

Insgesamt haben wir 50.000.000 Vergleiche mit dem DTW-Algorithmus durchgeführt, der eine Komplexität von O(N^2) hat. Das bedeutet, dass sehr grob geschätzt 5 * 10^11 (500 Milliarden) elementare Rechenoperationen durchgeführt wurden.

Jetzt ist ein neuer Balken da - wir haben wieder 500 Milliarden Berechnungen gemacht.

Wir haben uns entschlossen, es auf der Grundlage der Historie laufen zu lassen, beginnend mit dem letzten Element 200 000. Für einen Durchlauf werden 200.000 mal 500 Milliarden Berechnungen benötigt. Das sind insgesamt 10^17 Berechnungen.

Selbst wenn es eine knifflige Optimierung gibt, wird sie nicht mehr als zwei Größenordnungen einbringen. D.h. es müssen höchstens 10^15 Berechnungen durchgeführt werden.

 
hrenfx:

Wie diese Aufgabe mittels DTW gelöst wird (Beispiel):

An diesem Punkt sind wir mehr an der DTW selbst interessiert als an ihrer Anwendung.
 
hrenfx: Wie diese Aufgabe mit DTW gelöst wird (Beispiel):

Wenn es Ihnen nichts ausmacht, zeigen Sie bitte die Lösung dieses Problems im Code, es ist nicht so sehr von praktischem Interesse, sondern eher von sportlichem Interesse.

 

Niemand, der bei klarem Verstand ist, würde einen Algorithmus implementieren, dessen Ergebnis einfach nicht warten kann.

Das gleiche Pearson QC wäre ebenfalls ungeeignet, ebenso wie DTW, da dessen Rechenaufwand ebenfalls O(N^2) ist. Es gibt jedoch eine bedeutende algorithmische Optimierung der Pearson QC-Berechnung mit der Komplexität O(N * log(N)), die es ermöglichen könnte, dieses Problem in einer angemessenen Zeit zu lösen. Die Implementierung dieses Algorithmus ist in Codebase veröffentlicht worden. Um das aufgeworfene Problem zu lösen, muss derselbe Algorithmus auf die Menge der ZigZag-transformierten ZVRs angewendet werden.

 
hrenfx:

Niemand, der bei klarem Verstand ist, würde einen Algorithmus implementieren, dessen Ergebnis einfach nicht warten kann.

Das gleiche Pearson QC wäre ebenfalls ungeeignet, ebenso wie DTW, da dessen Rechenaufwand ebenfalls O(N^2) ist. Es gibt jedoch eine bedeutende algorithmische Optimierung der Pearson QC-Berechnung mit der Komplexität O(N * log(N)), die es ermöglichen könnte, dieses Problem in einer angemessenen Zeit zu lösen. Die Implementierung dieses Algorithmus ist in Codebase veröffentlicht worden. Um das aufgeworfene Problem zu lösen, muss derselbe Algorithmus auf die Menge der ZigZag-transformierten ZVRs angewendet werden.


Sie sollten zunächst das Problem, mit dem der Autor konfrontiert ist, und seine Antworten lesen.
 
Integer:


Ich habe es versucht. Ich weiß auch nicht, wie man es benutzt. Die Ausgabe sollte entweder ein Transformationspfad oder transformierte Daten sein.

Die Ausgabe des Algorithmus ist eine "akkumulierte Kostenmatrix" (und nicht nur die in der Abbildung gezeigte lokale Abstandsmatrix), wobei die Methode den Wert der rechten unteren Zelle zurückgibt (konstruktionsbedingt ist dies das Maximum in der gesamten Matrix). Um den Weg zu finden, müssen wir uns nur von Zelle (n,m) zu Zelle (1,1) bewegen, wobei wir jedes Mal die Option mit dem niedrigsten Wert wählen:

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
 
Das resultierende Pfadfeld enthält den optimalen Pfad für die Umwandlung eines Signals in ein anderes. Dies kann in beide Richtungen geschehen.
 
Der Grad der Ähnlichkeit der Signale wird durch den Wert der rechten unteren Zelle der Matrix bestimmt, je größer er ist, desto unterschiedlicher sind die Signale.
 
alsu: Der Grad der Ähnlichkeit der Signale wird durch den Wert der rechten unteren Zelle der Matrix bestimmt, je größer er ist, desto unterschiedlicher sind die Signale.
OK, danke, Sie haben es ziemlich klar erklärt, eine Frage noch: Ist es notwendig, die Daten zu normalisieren oder auf die gleiche Reihenfolge zu reduzieren, hat das Auswirkungen auf das Ergebnis?
 
IgorM:
OK, danke, das war ziemlich klar. Eine Frage noch: Müssen die Daten normalisiert oder neu geordnet werden, hat das Auswirkungen auf das Ergebnis?
dtw[n][m] hängt von der Skalierung ab, d. h. wenn es viele paarweise Vergleiche gibt, sollten wir die Skalierung erhöhen und sie möglichst zentrieren.
123456789101112
Neuer Kommentar