Dynamic Time Warping

Literatur Iterative Deepening Dynamic Time Warping for Time Series

Normalisieren der Distanzen mit der Länge des Warping Path. (Siehe “Indexing Multi-Dimensional Time-Series”).

Dynamic Time Warping mit Piecewise Aggregate Approximation (PAA): Approximieren einer Zeitreihe durch Segmentierung in gleichlange Teile und Mittelwert der Datenpunkte innerhalb dieser Punkte.

Zuerst Normalisieren jeder Dimension von t und r.

$$d(i,j) = \sum_{k=1}^K(t(k,i)-r(k,j))^2$$

Gleichzeitiges Alignment mehrerer Zeitreihen

Quelle: Multiple Multidimensional Sequence Alignment Using Generalized Dynamic Time Warping

Ersetzen der Punkte durch globale charakteristische Measures.

Dynamic Time Warping (DTW) has been applied in time series mining to resolve the difficulty caused when clustering time series of varying lengths in Euclidean space or containing possible out-of-phase similarities (Berndt & Clifford, 1994; Keogh, 2002; Ratanamahatana & Keogh, 2004). […] but is not defined if a single data point is missing.

Vergleich einer Query mit allen anderen Trajektorien problematisch. Trajektorien, die weit entfernt für eine gegebene Anfrage liegen, sollten nicht untersucht werden.

Schema: 1. Segmentieren der ZR in MBRs, speichern in R-Baum 2. Gegeben Anfrage Q, Bereiche, die übereinstimmen können, werden durch die Konstruktion eines Minimum Bounding Envelopes erkannt. 3. Der MBE wird zerteilt in MBRs, die in Index gespeichert sind. 4. Basierend auf den MBR Überschneidungen werden Ähnlichkeitsschätzungne berechnet. Nur für hinreichend ähnliche ZR werden Distanzen berechnet.