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:

function [ distance, DP ] = twed( A, timeSA, B, timeSB, lambda, nu )
% [distance, DP] = TWED( A, timeSA, B, timeSB, lambda, nu )
% Berechne Time Warp Edit Distance (TWED) für die Zeitreihen A und B
%
% A      := Werte der Zeitreihe A (e.g. [ 10 2 30 4])
% timeSA := Zeitstempel der Werte von Zeitreihe A (e.g. 1:4)
% B      := Werte der Zeitreihe B
% timeSB := Zeitstempel der Werte von Zeitreihe B
% lambda := Bestrafung für Abstände bei Löschoperationen
% nu     := Bestimmt die Elastizität; nu >=0 erforderlich für Distanzmaß.


    %Überprüfe, ob für jeden Zeitpunkt ein Zeitstempel existiert
    if length(A) ~= length(timeSA)
        warning('Die Länge von A ist ungleich der Länge timeSA')
        return
    end

    if length(B) ~= length(timeSB)
        warning('Die Länge von B ist ungleich der Länge timeSB')
        return
    end

    if nu<0
        warning('nu ist negativ')
        return
    end
    % Padding hinzufügen (Matlab unterstützt keine 0 Indizierung)
    A  = [ 0 A ];
    timeSA = [ 0 timeSA ];
    B  = [ 0 B ];
    timeSB = [ 0 timeSB ];

    % Dieser Algorithmus verwendet dynamische Programmierung
    DP = zeros(length(A),length(B));

    % Initialisiere die DP Matrix, setze die erste Zeile und Spalte auf
    % unendlich
    DP(1,:) = inf;
    DP(:,1) = inf;
    DP(1,1) = 0;

    % Die Länge der Zeitreihe A
    n = length(timeSA);
    % Die Länge der Zeitreihe B
    m = length(timeSB);
    % Berechnung der minimalen Kosten
    for i = 2:n
        for j = 2:m
            cost = Dlp(A(i), B(j));

            % Berechnen und Zwischenspeichern der Kosten der verschiedenen Operationen
            C = ones(3,1) * inf;

            % Löschen in A
            C(1) = DP(i-1,j) +  Dlp(A(i-1),A(i)) + nu * (timeSA(i) - timeSA(i-1)) + lambda;
            % Löschen in B
            C(2) = DP(i,j-1) + Dlp(B(j-1),B(j)) + nu * (timeSB(j) - timeSB(j-1)) + lambda;
            % Belassen von Datenpunkten in beiden Zeitreihen
            C(3) = DP(i-1,j-1) + Dlp(A(i),B(j)) + Dlp(A(i-1),B(j-1)) + ...
                   nu * ( abs( timeSA(i) - timeSB(j) ) + abs( timeSA(i-1) - timeSB(j-1) ) );

            % Wähle die Operation mit den minimalen Kosten und aktualisiere die DP Matrix
            DP(i,j) = min(C);
        end
    end

    % Die Distanz (die Kosten zur Anpassung der Zeitreihen aneinander) befindet sich im höchsten Matrixelement von DP
    distance = DP(n,m);

    % Funktion zur Berechnung des Euklidischen Abstands
    function [cost] = Dlp( A, B)
        cost = sqrt( sum( (A - B).^2 ,2));
    end

end

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

function [ path ] = backtracking( DP )
% [ path ] = BACKTRACKING ( DP )
% Berechnung des kostengünstigsten Pfades
% DP := DP Matrix aus der TWED Funktion

    x = size(DP);
    i = x(1);
    j = x(2);

    % In path werden die Indizes des Pfades in umgekehrter Reihenfolge gespeichert
    path = ones(i + j, 2 ) * Inf;

    steps = 1;
    while( i ~= 1 || j ~= 1 )
        path(steps,:) = [i; j];

        C = ones(3,1) * inf;

        % Belassen von Datenpunkten in beiden Zeitreihen
        C(1) = DP(i-1,j-1);
        % Löschen in A
        C(2) = DP(i-1,j);
        % Löschen in B
        C(3) = DP(i,j-1);

        % Berechnung des Indexes mit den geringsten Kosten
        [~,idx] = min(C);

        switch idx
            case 1
                % Belassen von Datenpunkten in beiden Zeitreihen
                i = i-1;
                j = j-1;
            case 2
                % Löschen in A
                i = i-1;
                j = j;
            case 3
                % Löschen in B
                i = i;
                j = j-1;
        end
        steps = steps +1;
    end
    path(steps,:) = [i j];

    % Der Pfad wurde in umgekehrter Reihenfolge berechnet, deswegen muss er umgedreht werden
    path = path(1:steps,:);
    path = path(end:-1:1,:);

end

Literatur

• P.-F. Marteau: Time Warp Edit Distance with Stiffness Adjustment for Time Series Matching. In: IEEE Transactions on Pattern Analysis and Machine Intelligence. Band 31, Nr. 2, Februar 2009, S. 306–318, doi:10.1109/TPAMI.2008.76.