Algorithmus - Dynamic Time Warping

• Generalisierungen:
  • Dynamische Programmierung
  • Abstandsberechnung für Zeitreihen
• Involvierte Definitionen:
  • Zeitreihe
  • Metrik
  • siehe auch Levenshtein-Distanz
• Veranstaltung: DM
• Referenz: @valdes2024 (p. 38 f.)

⠀

Algorithmus : Dynamic Time Warping

Als Dynamische Zeitnormierung (en. Dynamic Time Warping, kurz DTW) bezeichnen wir eine Methode zur Synchronisierung und Abstandsberechnung zwischen zwei unterschiedlich langen Zeitreihen.

Sei der kleinstmögliche Abstand zwischen den ersten Elementen der Zeitreihe und den ersten Elementen der Zeitreihe .

Dabei steht es uns in jedem Schritt frei, nur den Index der Zeitreihe , nur den Index der Zeitreihe oder doch beide Indizes “weiterzuschieben”.

Rekursiv definieren wir durch

wobei eine beliebige Distanzmetrik sei.

---

Eingabe:

• Zeitreihen und
• Eine Metrik Ausgabe: der Abstand

% Base-Cases initialisieren

foreach do

foreach do

% Berechnungen durchführen
foreach do
foreach do

return

Anmerkung

Berechnung der DTW mittels Matrixdarstellung

Die Berechnung der DTW können wir ähnlich durchführen wie die Berechnung der Levenshtein-Distanz zwischen zwei Strings.

Für und erhalten wir beispielsweise:

	#	26	13	2	28	11	18
#	0
19
7

Die Distanz zwischen und beträgt mittels DTW also .