Dynamisches Time Warping und Normalisierung

9

Ich verwende Dynamic Time Warping, um eine "Abfrage" - und eine "Vorlagen" -Kurve abzugleichen, und habe bisher vernünftigen Erfolg, aber ich habe einige grundlegende Fragen:

  1. Ich bewerte eine "Übereinstimmung", indem ich bewerte, ob das DTW-Ergebnis unter einem von mir heuristisch ermittelten Schwellenwert liegt. Ist dies der allgemeine Ansatz zur Bestimmung einer "Übereinstimmung" mit DTW? Wenn nicht, erklären Sie bitte ...

    Angenommen, die Antwort auf (1) lautet "Ja", dann bin ich verwirrt, da das DTW-Ergebnis sehr empfindlich ist für a) den Unterschied in den Amplituden der Kurven und b) die Länge des Abfragevektors und die Länge des " Vorlage "Vektor.

    Ich verwende eine symmetrische Schrittfunktion, daher normalisiere ich für (b) mein DTW-Ergebnis durch Teilen durch M + N (Breite + Höhe der DTW-Matrix). Dies scheint etwas effektiv zu sein, aber es scheint, dass es DTW-Übereinstimmungen bestrafen würde, die weiter von der Diagonale entfernt sind (dh einen längeren Weg durch die DTW-Matrix haben). Was für einen "Normalisierungs" -Ansatz willkürlich erscheint. Das Teilen durch die Anzahl der Schritte durch die Matrix scheint intuitiv sinnvoll zu sein, aber dies scheint laut Literatur nicht der richtige Weg zu sein.

  2. Gibt es eine bessere Möglichkeit, das DTW-Ergebnis an die Größe der Abfrage- und Vorlagenvektoren anzupassen?

  3. Wie normalisiere ich schließlich das DTW-Ergebnis für den Amplitudenunterschied zwischen der Abfrage und den Vorlagenvektoren?

Angesichts des Mangels an zuverlässigen Normalisierungstechniken (oder meines Unverständnisses) scheint es viel manuellen Aufwand zu geben, mit den Beispieldaten zu arbeiten, um den besten Schwellenwert für die Definition einer "Übereinstimmung" zu ermitteln. Vermisse ich etwas

Herr blinky
quelle

Antworten:

8

Zumindest meines Wissens gibt es dafür keinen "allgemeinen Ansatz". Außerdem versuchen Sie trotzdem, eine Entfernungsmetrik zu minimieren. Zum Beispiel in dem Urvater DTW Papiere Sakoe & Chiba (1978) Verwendungals Messung der Differenz zwischen zwei Merkmalsvektoren.||einich- -bich||

Wie Sie richtig identifiziert haben, müssen Sie (normalerweise) die gleiche Anzahl von Punkten haben, damit dies sofort funktioniert. Ich würde vorschlagen, einen lowess () Smoother / Interpolator über Ihren Kurven zu verwenden, um sie zuerst gleich groß zu machen. Es ist ziemlich normal für "Kurvenstatistiken". Sie können eine Beispielanwendung in Chiou et al. (2003) ; Die Autoren interessieren sich in dieser Arbeit nicht für DTW als solches, aber es ist ein gutes Beispiel für den Umgang mit ungleich großen Messwerten.

Zusätzlich ist, wie Sie sagen, "Amplitude" ein Problem. Dies ist ein bisschen offener, um ehrlich zu sein. Sie können einen Area-Under-the-Curve-Ansatz wie den von Zhang und Mueller (2011) vorgeschlagenen versuchen , um dies zu beheben, aber tatsächlich, um selbst die Normalisierung über der Norm zu verzerren (dh durch zu ersetzen könnte wie in diesem von Tang und Mueller (2009) funktionieren . Ich würde dem zweiten folgen, aber auf jeden Fall, wie Sie auch bemerkt haben, ist die Normalisierung von Proben a Notwendigkeit.f(x)f(x)supy|f(x)|

Abhängig von der Art Ihrer Daten finden Sie weitere anwendungsspezifische Literatur. Ich persönlich finde den Ansatz mit dem Bezug auf eine Zielpaarweise Verzerrungsfunktion minimiert die intuitivste aller. Die zu minimierende Zielfunktion ist also: , wo das Ganze trotz seiner Unheimlichkeit eigentlich ganz einfach ist: Sie versuchen, die Verzerrungsfunktion zu finden , die die erwartete Summe der mit der minimiert Referenzkurve (der TermGC.λ(Y.ich,Y.k,G)=E.{T.(Y.ich(G(t))- -Y.k(t))2+λ(G(t)- -t)2dt|Y.ich,Y.k}}GY.ich(G(t))Y.k(t)Y.ich(G(t))- -Y.k(t)) vorbehaltlich einer gewissen Normalisierung der Zeitverzerrung, die Sie durch diese Verzerrung verursachen (der Term ). Dies ist, was das MATLAB-Paket PACE implementiert. Ich weiß, dass es ein R-Paket fda von JO Ramsay et al. Das könnte auch hilfreich sein, aber ich habe es nicht persönlich verwendet (ein bisschen ärgerlich ist die Standardreferenz für die Methoden dieses Pakets in vielen Fällen Ramsay und Silvermans ausgezeichnetes Buch Functional Data Analysis (2006), 2. Auflage , und Sie müssen a durchsuchen 400-seitiges Buch, um das zu bekommen, wonach Sie suchen; zumindest ist es trotzdem gut zu lesen)G(t)- -t

Das Problem, das Sie in der Statistikliteratur beschreiben, ist allgemein als " Kurvenregistrierung " bekannt (siehe beispielsweise Gasser und Kneip (1995) für eine frühzeitige Behandlung des Problems) und fällt unter das allgemeine Dach der Techniken zur Analyse funktionaler Daten .

(In Fällen, in denen ich das Originalpapier online finden konnte, verweist der Link dorthin; andernfalls verweist der Link auf eine allgemeine digitale Bibliothek. Fast alle genannten Papiere können kostenlos als Entwurfsversionen verwendet werden. Ich habe meinen ursprünglichen Kommentar so wie er ist gelöscht ersetzt durch diesen Beitrag.)

usεr11852
quelle
Dies ist eine ausgezeichnete und sehr sehr hilfreiche Antwort. Die Referenzen sind besonders hilfreich.
Mikko
Würdest du eine passende Referenz kennen, um zu sagen, dass "Amplitude ein Problem ist" in dtw? Dies ist wahrscheinlich so offensichtlich, dass ich Schwierigkeiten habe, eine Referenz zu finden, die klar darüber diskutiert.
Mikko
L.2
Aus den bereits erwähnten Quellen wird wahrscheinlich das FDA-Buch von Ramsay & Silverman, Kap. 7 zur "Registrierung und Anzeige von Funktionsdaten". Eine sehr gute Ressource ist auch das Buch: "Inferenz für funktionale Daten mit Anwendungen" von Horváth und Kokoszka; Teil III "Abhängige Funktionsdaten" berührt das Problem der Normalisierung hauptsächlich, weil man sich um die Erkennung von Änderungspunkten kümmert.
usεr11852