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”).

PDTW

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

Multidimensional DTW (MD-DTW)

Zuerst Normalisieren jeder Dimension von t und r.

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

Multiple Multidimensional DTW

Gleichzeitiges Alignment mehrerer Zeitreihen

Quelle: Multiple Multidimensional Sequence Alignment Using Generalized Dynamic Time Warping

Literatur

A Scalable Method for Time Series Clustering

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.

Indexing

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.