Unter http://www.speech.zone/exercises/dtw-in-python/ heißt es

Obwohl es nicht mehr wirklich verwendet wird, ist Dynamic Time Warping (DTW) eine schöne Einführung in das Schlüsselkonzept der dynamischen Programmierung.

Ich verwende DTW für die Signalverarbeitung und bin etwas überrascht: Was wird stattdessen verwendet?

Ich würde DTW überhaupt nicht als veraltet betrachten. Im Jahr 2006 haben Xi et al. zeigte, dass

[...] Es wurden viele Algorithmen für das Problem der Zeitreihenklassifizierung vorgeschlagen. Es ist jedoch klar, dass ein nächster Nachbar mit DTW-Abstand (Dynamic Time Warping) außerordentlich schwer zu schlagen ist.

Die Ergebnisse dieses Papiers sind im Buch "Temporal Data Mining" von Theophano Mitsa wie folgt zusammengefasst:

• In [Che05a] ergibt ein statischer Minimierungs-Maximierungs-Ansatz einen maximalen Fehler von 7,2%. Bei 1NN-DTW beträgt der Fehler 0,33% bei demselben Datensatz wie im Originalartikel.
• In [Che05b] ergibt ein mehrskaliger Histogrammansatz einen maximalen Fehler von 6%. Bei 1NN-DTW beträgt der Fehler (im selben Datensatz) 0,33%.
• In [Ead05] ergibt ein grammatikalisch gesteuerter Merkmalsextraktionsalgorithmus einen maximalen Fehler von 13,22%. Bei 1NN-DTW betrug der Fehler 9,09%.
• In [Hay05] werden Zeitreihen mithilfe einer Laplace-Eigenkarte und DTW-Abständen in einen Raum mit niedrigeren Dimensionen eingebettet. Die Autoren erreichten eine beeindruckende Genauigkeit von 100%; Der 1NN-DTW erreichte jedoch auch eine Genauigkeit von 100%.
• In [Kim04] erreichen Hidden Markov-Modelle eine Genauigkeit von 98%, während 1NN-DTW eine Genauigkeit von 100% erreicht.
• In [Nan01] erzielt ein mehrschichtiges neuronales Perzeptron-Netzwerk die beste Leistung von 1,9% Fehlerrate. Bei demselben Datensatz betrug die Rate von 1NN-DTW 0,33%.
• In [Rod00] ergibt eine Logik erster Ordnung mit Boosting eine Fehlerrate von 3,6%. Im selben Datensatz betrug die Fehlerrate von 1NN-DTW 0,33%.
• In [Rod04] ergibt ein DTW-basierter Entscheidungsbaum eine Fehlerrate von 4,9%. Im selben Datensatz gibt 1NN-DTW einen Fehler von 0,0% aus. • In [Wu04] ergibt ein Super-Kernel-Fusionssatz eine Fehlerrate von 0,79%, während 1NN-DTW im selben Datensatz 0,33% ergibt.

Im Originalbuch finden Sie eine Liste der genannten Referenzen.

Ein wichtiger Punkt hierbei ist die Tatsache, dass Xi et al. Ich habe es sogar geschafft, die Leistung eines MLP im Jahr 2006 zu übertreffen. Auch wenn die Situation heutzutage etwas anders aussieht (da wir bessere und schnellere Deep-Learning-Algorithmen zur Hand haben), würde ich DTW dennoch als eine gültige Option betrachten, um zu prüfen, wann es kommt zu Signalklassifikationen.

Aktualisieren

Ich möchte auch einen Link zu einem neueren Artikel mit dem Titel "The Great Time Series Classification Bake Off: Eine experimentelle Bewertung kürzlich vorgeschlagener Algorithmen" aus dem Jahr 2016 hinzufügen . In diesem Artikel haben die Autoren "18 kürzlich vorgeschlagene Algorithmen gemeinsam implementiert Java Framework und verglich sie mit zwei Standard-Benchmark-Klassifikatoren (und untereinander) ". Die folgenden Zitate aus dem Papier betonen, dass DTW tatsächlich noch relevant ist (oder zumindest 2016 war):

1. Viele der Algorithmen sind in der Tat nicht besser als unsere beiden Benchmark-Klassifikatoren 1-NN DTW und Rotation Forest.
2. Für diejenigen, die ein Vorhersagemodell für ein neues Problem erstellen möchten, empfehlen wir, mit DTW, RandF und RotF als grundlegende Überprüfung und Benchmark der Gesundheit zu beginnen.
3. Die erhaltene Weisheit ist, dass DTW schwer zu schlagen ist.

Dynamic Time Warping (DTW) ist quadratisch komplex. Es gibt mehrere andere Versionen des Algorithmus, wie z. B. FastDTW (lineare Komplexität), die die Komplexität durch Berechnung von Näherungen verringern. FastDTW ist beispielsweise in diesem Python-Modul implementiert .

Soweit ich weiß, geht es hauptsächlich um den rechnerischen Aspekt, der verbessert wurde. Daher ist es immer noch eine geeignete Methode, um die Ähnlichkeit zwischen Sequenzen zu messen.

Ich empfehle dies als gute Referenz, insbesondere Abschnitt 4.3. Hier ist der kühne Teil dieses Abschnitts:

Ein Warping-Pfad W ist ein Satz zusammenhängender Matrixindizes, die eine Abbildung zwischen zwei Zeitreihen definieren. Selbst wenn es eine exponentielle Anzahl möglicher Warping-Pfade gibt, ist der optimale Pfad derjenige, der die globalen Warping-Kosten minimiert. DTW kann unter Verwendung dynamischer Programmierung mit Zeitkomplexität O (n2) berechnet werden [Ratanamahatana und Keogh 2004a]. Es wurden jedoch mehrere Maßnahmen mit niedrigerer Begrenzung eingeführt, um die Berechnung zu beschleunigen. Keogh und Ratanamahatana [2005] führten den Begriff der oberen und unteren Hüllkurve ein, der das maximal zulässige Verziehen darstellt. Mit dieser Technik wird die Komplexität zu O (n). Es ist auch möglich, die Größe des DTW-Warping-Fensters zeitlich zu beschränken. Es wurde gezeigt, dass diese nicht nur die Geschwindigkeit, sondern auch die Genauigkeit verbessern, da sie die durch ausgedehntes Verziehen verursachte pathologische Anpassung vermeiden [Ratanamahatana und Keogh 2004b]. Die beiden am häufigsten verwendeten globalen Einschränkungen sind das Sakoe-Chiba-Band und das Itakura-Parallelogramm. Salvador und Chan [2007] führten den FastDTW-Algorithmus ein, der eine lineare Zeitberechnung von DTW ermöglicht, indem ein Warp-Pfad rekursiv auf eine höhere Auflösung projiziert und anschließend verfeinert wird. Ein Nachteil dieses Algorithmus ist, dass er ungefähr ist und daher ACM Computing Surveys, Vol. 3, No. 45, Nr. 1, Artikel 12, Erscheinungsdatum: November 2012. 12:18 P. Esling und C. Agon bieten keine Garantie für die Suche nach der optimalen Lösung. Neben dem dynamischen Warping, Manchmal kann es nützlich sein, eine globale Skalierung von Zeitreihen zuzulassen, um aussagekräftige Ergebnisse zu erzielen. Diese Technik wird als Uniform Scaling (US) bezeichnet. Fu et al. [2008] schlugen das Ähnlichkeitsmaß Scaled and Warped Matching (SWM) vor, das es ermöglicht, die Vorteile von DTW mit denen der USA zu kombinieren. Andere formbasierte Maßnahmen wurden eingeführt, wie beispielsweise der Spatial Assembling Distance (SpADe) [Chen et al. 2007b]; Es ist ein musterbasiertes Ähnlichkeitsmaß. Dieser Algorithmus identifiziert übereinstimmende Muster, indem er das Verschieben und Skalieren sowohl auf der Zeitachse als auch auf der Amplitudenachse ermöglicht und somit robust skaliert. Das DISSIM [Frentzos et al. 2007] Abstand wurde eingeführt, um Ähnlichkeit bei verschiedenen Abtastraten zu behandeln. Es wird als Annäherung an das Integral der euklidischen Distanz definiert. Einer der interessantesten jüngsten Vorschläge basiert auf dem Konzept der elastischen Anpassung von Zeitreihen [Latecki et al. 2005]. Latecki et al. [2007] stellten eine OSB-Technik (Optimal SuBsequence Matching) vor, mit der automatisch die beste Teilsequenz und der beste Verzerrungsfaktor für die Entfernungsberechnung ermittelt werden können. Es enthält eine Strafe beim Überspringen von Elementen. Optimalität wird durch hohe Rechenkosten erreicht; Sie kann jedoch durch Begrenzen des Sprungbereichs verringert werden.