Time Warp Edit Distance
# Time Warp Edit Distance

Bei Time Warp Edit Distance (TWED) handelt es sich um ein Abstandsmaß zwischen diskreten Zeitreihen. Im Vergleich zu anderen Abstandsmaßen (z. B. DTW, LCS) ist TWED eine Metrik. Die in den gemessenen Zeitreihen vorliegenden Datenpunkte müssen außerdem nicht notwendigerweise mit derselben Frequenz abgetastet sein, also nicht zwingend zu äquidistanten Abtastzeitpunkten vorliegen, was bei anderen Abstandsmaßen jedoch implizit angenommen wird. Der TWED-Algorithmus wurde im Februar 2009 von P.-F. Marteau veröffentlicht.

Ein typisches Problem bei der Verarbeitung von Zeitreihen ist die Bestimmung der Ähnlichkeit von Zeitreihen zueinander, beispielsweise im Rahmen des Clusterings oder der Klassifikation.

Ähnliche Zeitreihen können durch den Menschen bereits per Anschauung erkannt werden. Der Mensch erkennt beispielsweise, dass zwei Zeitreihen, die er miteinander vergleicht, beliebig ähnlich sein können, selbst wenn diese gestaucht, zeitlich versetzt oder ähnlich einfach erkennbare Unterschiede aufweisen.

Als Beispiel für ähnliche Zeitreihen, die bezüglich der Zeitachse gegeneinander verschoben sind, betrachte man zwei Fußgänger. Beide Fußgänger legen dieselbe Strecke zurück und haben die gleiche Geschwindigkeit. Ein Fußgänger startet jedoch später als der andere. Während beide diese Strecke zurücklegen, soll an jeweils denselben Wegpunkten der Wert der Höhenmeter ü.N.N., an dem sich die Fußgänger befinden, gemessen werden. Nachdem beide die Strecke zurückgelegt haben, können die gemessenen Werte der Höhenmeter gegen einen Zeitstrahl abgetragen werden – damit entstehen zwei Zeitreihen. Die Zeitreihe des später gestarteten Fußgänger ist gegenüber der Zeitreihe des anderen Fußgängers verschoben.

Als Beispiel für ähnliche Zeitreihen, von denen eine im Vergleich zur anderen gestreckt bzw. die andere im Vergleich zur einen gestaucht ist, betrachte man einen Fußgänger und einen Radfahrer. Beide legen dieselbe Strecke zurück, wobei sich der Radfahrer schneller als der Fußgänger bewegt. Während beide diese Strecke zurücklegen, wird an jeweils denselben Wegpunkten der Wert der Höhenmeter ü.N.N., an dem sich Fußgänger bzw. Radfahrer befinden, gemessen. Nachdem beide die Strecke zurückgelegt haben, können die gemessenen Werte der Höhenmeter gegen einen Zeitstrahl abgetragen werden – damit entstehen zwei Zeitreihen, wobei die Zeitreihe des Fußgängers gegenüber der Zeitreihe des Radfahrers gestaucht ist.

Weitere Beispiele für Zeitreihen, die sich, abgesehen vom Zeitbezug, ähneln können, sind beispielsweise Druckverläufe bei der Aufzeichnung des Schreibdrucks wenn ein (beliebiges, aber festes) Wort geschrieben wird. Der Schreibende kann hierbei unterschiedlich zügig schreiben, die Charakteristik seiner Handschrift bleibt effektiv aber die gleiche. Die geschriebenen Wörter sind damit zwar ähnlich, aber bezogen auf den Schreibdruck zeitlich verzerrt. Anwendungsbeispiele finden sich hierfür unter anderem im Bereich der Biometrie mittels sog. Unterschriftenpads.

Ein menschlicher Betrachter würde eine große Ähnlichkeit zwischen Zeitreihen sehr wahrscheinlich erkennen, ein Rechner jedoch nicht unmittelbar. Ein Rechner ist zur Abstandsbestimmung (und damit zur Aussage über eine Ähnlichkeit, wobei "wenig Abstand" mit hoher Ähnlichkeit einhergeht) auf ein Abstandsmaß angewiesen. Dieses Abstandsmaß kann dabei starr oder elastisch sein. Ein starres Abstandsmaß, wie beispielsweise der euklidische Abstand oder der Manhattan-Abstand könnte die Unterschiede zwischen Zeitreihen, die sich nur aus Streckung oder Verschiebung bezüglich der Zeitachse ergeben, nicht unberücksichtigt lassen – damit ist gemeint, dass entlang eines Zeitstrahls Datenpunkte der jeweiligen Zeitreihe zu jedem Zeitpunkt einen Datenpunkt zum selben Zeitpunkt in der jeweils anderen Zeitreihe zur Abstandsberechnung voraussetzen. Sollte eine der Zeitreihen gestaucht sein, sind diese starre Abstandsmaße zur Abstandsberechnung ungeeignet. Aus diesem Grund existieren elastische Abstandsmaße wie beispielsweise TWED. Informell beschrieben, löscht TWED Datenpunkte aus einer der Zeitreihen, um sie abschnittsweise der jeweils anderen anzugleichen. Je höher die Kosten für das Löschen oder je weiter entfernt vermeintlich passende Datenpunkte (gemessen entlang der Zeitachse) sind, desto unähnlicher sind die Zeitreihen. Während zur Angleichung unterschiedlich langer Zeitreihen entlang des Zeitstrahls auch Techniken wie Re-Sampling genutzt werden können, entfällt dieser zusätzliche Arbeitsaufwand bei der Nutzung elastischer Abstandsmaße.

## TWED und andere Abstandsmaße

TWED nutzt Bestandteile beziehungsweise Konzepte, die sich so oder ähnlich in anderen Abstandsmaßen, vor allem in der Levenshtein-Distanz, die jedoch nicht primär für die Ähnlichkeitsmessung von Zeitreihen gedacht ist, wiederfinden. Über die Levenshtein-Distanz hat TWED auch Ähnlichkeiten zu DTW.

## Erweiterungen und Anwendungen von TWED

### GTWED-Kernel

Gaussian TWED ist, auch wenn der Name es anders vermuten lässt, keine "Erweiterung" der TWED, sondern GTWED ist eine Anwendung von TWED als Abstandsmaß in Support Vector Machines. Hier wird das im Gaußkernel häufig verwendete euklidische Abstandsmaß durch TWED ersetzt.

### Medizinische Anwendungen

Es existieren Arbeiten, in denen vorgestellt wird, wie TWED zum Vergleich von durch Pulsmessung aufgezeichneten Zeitreihen verwendet werden kann.

## Definition, Pseudocode, Implementierung in unterschiedlichen Programmiersprachen

### Definition

$\delta _{\lambda ,\nu }(A_{1}^{p},B_{1}^{q})=Min{\begin{cases}\delta _{\lambda ,\nu }(A_{1}^{p-1},B_{1}^{q})+\Gamma (a_{p}^{'}\to \Lambda )&{\rm {L{\ddot {o}}schen\ in\ A}}\\\delta _{\lambda ,\nu }(A_{1}^{p-1},B_{1}^{q-1})+\Gamma (a_{p}^{'}\to b_{q}^{'})&{\rm {{\ddot {U}}bereinstimmung}}\\\delta _{\lambda ,\nu }(A_{1}^{p},B_{1}^{q-1})+\Gamma (\Lambda \to b_{q}^{'})&{\rm {L{\ddot {o}}schen\ in\ B}}\end{cases}}$ wobei

$\Gamma (\alpha _{p}^{'}\to \Lambda )=d_{LP}(a_{p}^{'},a_{p-1}^{'})+\nu \cdot (t_{a_{p}}-t_{a_{p-1}})+\lambda$ $\Gamma (\alpha _{p}^{'}\to b_{q}^{'})=d_{LP}(a_{p}^{'},b_{q}^{'})+d_{LP}(a_{p-1}^{'},b_{q-1}^{'})+\nu \cdot (|t_{a_{p}}-t_{b_{q}}|+|t_{a_{p-1}}-t_{b_{q-1}}|)$ $\Gamma (\Lambda \to b_{q}^{'})=d_{LP}(b_{p}^{'},b_{p-1}^{'})+\nu \cdot (t_{b_{q}}-t_{b_{q-1}})+\lambda$

Wobei die Rekursion $\delta _{\lambda ,\nu }$ wie folgt initialisiert wird: $\delta _{\lambda ,\nu }(A_{1}^{0},B_{1}^{0})=0,$ $\delta _{\lambda ,\nu }(A_{1}^{0},B_{1}^{j})=\infty \ {\rm {{f{\ddot {u}}r\ }j\geq 1}}$ $\delta _{\lambda ,\nu }(A_{1}^{i},B_{1}^{0})=\infty \ {\rm {{f{\ddot {u}}r\ }i\geq 1}}$ mit $a'_{0}=b'_{0}=0$ nach Konvention.

### Implementierung in C

Eine Implementierung des TWED-Algorithmus in der Programmiersprache C kann von der Homepage des Autors heruntergeladen werden.

### Implementierung in Matlab

TWED Algorithmus:

Backtracking, um den kostengünstigsten Pfad zurückzuverfolgen:

