タイムワープ編集距離 – ウィキペディア

Posted on by
before-content-x4

で タイムワープ編集距離 （Twed）は、離散時系列間の距離です。他のスペーサー（DTW、LCSなど）と比較して、Twedはメトリックです。測定された時系列で利用可能なデータポイントは、必ずしも同じ周波数でスキャンする必要はありません。つまり、必ずしも他の距離で暗黙的に想定される等距離物が利用できるわけではありません。 Twedアルゴリズムは2009年2月にP.-Fによって行われました。 Marteauが公開しました。

時系列の処理に関する典型的な問題は、たとえばクラスタリングや分類のコンテキストなど、時系列の類似性の決定です。

同様の時系列は既に視野で認識されています。たとえば、男性は、たとえ圧縮されていても、時間内に混合されている、または同様に認識可能であっても、互いに比較する2つの時系列が同様であることを認識しています。

タイムラインに関して互いに反対する同様の時系列の例として、2人の歩行者が考慮されます。両方の歩行者は同じルートをカバーし、同じ速度を持っています。ただし、1つの歩行者は他の歩行者よりも遅く開始されます。どちらもこのルートをカバーしていますが、海面上の垂直メートルの値は、歩行者が配置されている同じウェイポイントで測定する必要があります。両方がルートをカバーした後、垂直メートルの測定値をタイムビームに対して削除できます。これにより、2つの時系列が作成されます。後に始まった歩行者の時系列は、他の歩行者の時系列と比較してシフトされます。

歩行者とサイクリストは、同様の時系列の例と見なされ、そのうちの1つは他の時系列と比較して伸びています。どちらも同じルートをカバーし、サイクリストは歩行者よりも速く動いています。どちらもこのルートをカバーしていますが、歩行者またはサイクリストが配置されているü.n.n.の値は同じ方法で測定されます。両方がルートをカバーした後、垂直メートルの測定値はタイムビームに対して削除できます。これにより、2つの時系列が作成され、歩行者のタイムラインはサイクリストのタイムケアと比較して浸されます。

時系列の他の例は、時間参照とは別に、類似している可能性があり、たとえば、（会社以外の）単語が書かれているときに書き込み圧力を記録するときの圧力曲線です。作家は迅速に別の方法で書くことができますが、彼の原稿の特徴は事実上同じままです。書かれた言葉は似ていますが、圧力を書くという点では、執筆の観点から歪められています。アプリケーションの例は、SO -Caled Signature Padsを使用して、バイオメトリーの領域にあります。

人間の視聴者は、時系列の間の大きな類似性を認識する可能性が非常に高いですが、コンピューターは直接ではありません。コンピューターは、距離までの距離に依存します（したがって、類似性について言うことは、「小さな距離」には高い類似性を伴います）。この距離は剛性または弾力性があります。ユークリッド距離やマンハッタンの距離などの剛​​性距離は、時系列の違いによって無視できません。これは、タイムラインの観点からの拡張またはシフトのみから生じることを意味します。時系列の1つが圧縮されている場合、この剛性距離の寸法は距離計算には不適切です。このため、Twedなどの弾性距離寸法があります。非公式に説明されているため、Twedは時系列の1つからデータポイントを削除して、他のセクションで補償します。削除のコストが高い、または遠く離れているほど、適切なデータポイント（タイムラインに沿って測定されている）は、時系列を消極的にします。再サンプリングなどの手法は、時間ビームに沿った異なる時間の長さの適応にも使用できますが、弾性距離寸法を使用する場合、この追加のワークロードは必要ありません。

Twedは、このまたは他のスペーサー、特にLevenshtein距離でこれまたは類似のコンポーネントまたは概念を使用します。これは、主に時系列の類似性測定を目的としていません。 Levenshtein距離を介して、TwedはDTWと類似しています。

gtwed-kernel [ 編集 | ソーステキストを編集します ]

Gaussian Twedは、たとえ名前がそれを示唆していても、Twedの「拡張」はありませんが、Gtwedはベクターマシンをサポートするための距離としてTwedの適用です。ここでは、ガウカネルで頻繁に使用されるユークリッドの距離測定値は、Twedに置き換えられます。 [初め]

医療アプリケーション [ 編集 | ソーステキストを編集します ]

after-content-x4

Twedを使用して、パルス測定によって記録された時系列を比較する方法が提示される作品があります。 [2]

定義、擬似コード、さまざまなプログラミング言語での実装 [ 編集 | ソーステキストを編集します ]

意味 [ 編集 | ソーステキストを編集します ]

d l 、 n （ a 初め p 、 b 初め Q ）） = m 私 n { δλ,ν(A1p−1,B1q)+Γ(ap′→Λ)Lo¨schen in Aδλ,ν(A1p−1,B1q−1)+Γ(ap′→bq′)U¨bereinstimmungδλ,ν(A1p,B1q−1)+Γ(Λ→bq′)Lo¨schen in B{displaystyle delta _ {lambda、if}（e_ {1}^p}、b_ {1}^{q}）= MISEGININ {cass} delta}^{p-1}}、b __ {1} tol}） } ist {p}}^{p}} ag {p. enn in a} \ delta _ {lammbda、if}（a_ {1}^{p-1}、b_ {1}^}+gama（a_ {p}^to ‘} to b_ {{{{{{}}^{{{{{{{{{{{{{{{{{{u {{{u u） {lamba、}} …


したがって

c （ a p ′→ l ）） = d l p （ a p ′、 a p – 初め ′）） + n de （ t ap – t ap−1）） + l {displaystyle gamma（alpha _ {p}^{‘} to lambada）= d_ {lp}（a_p}^{‘}、a_ {p-1}^{‘}）+n+if cdot（t_ {p}}}} -t_ {a_ {p-1}}}}）+ashda


c （ a p ′→ b Q ′）） = d l p （ a p ′、 b Q ′）） + d l p （ a p – 初め ′、 b Q – 初め ′）） + n de （ | t ap – t bq| + | t ap−1 – t bq−1| ）） {displaystyle gamma（alpha _ {p}^{‘} to b_ {q}^{‘}）= d_ {lp}（a_ {p}^{‘}、b_ {q}^{‘}）+d_ {lp}}（a_ {p-1}^{{Q-1}} {Q-1} （| t_ {a_ {p}} -t_ {b_ {q}} |+| t_ {a_ {p-1}} – t_ {b_ {q-1}} |）}


c （ l → b Q ′）） = d l p （ b p ′、 b p – 初め ′）） + n de （ t bq – t bq−1）） + l {displaystyle gamma（lambda to b_ {q}^{‘}）= d_ {lp}（b_ {p}^{‘}、b_ {p-1}^{‘}）+nu cdot（t_ {{b_ {q}} – t_ {b_ {q-1}}+lambda

再帰

after-content-x4
d l 、 n {displaystyle delta _ {lambda、not}}

次のように初期化されています。

d l 、 n （ a 初め 0 、 b 初め 0 ）） = 0 、 {displaystyle delta _ {lambda、nu}（a_ {1}^{0}、b_ {1}^{0}）= 0、}


d l 、 n （ a 初め 0 、 b 初め j ）） = ∞ fu¨r j ≥ 初め {_ {lambda、nu}のdisplaystyle（a _ {1}、b_ {1}、b_ {1


d l 、 n （ a 初め 私 、 b 初め 0 ）） = ∞ fu¨r 私 ≥ 初め {delta delta _ {lambda、nu}（a_ {1}^{i}、b_ {1}^{0}）= inf {rm {{f {f {dot}} r} igeq 1}}}}


と

a 0 ‘ = b 0 ‘ = 0 {displaystyle a ‘_ {0} = b’ _ {0} = 0}

大会後。

cの実装 [ 編集 | ソーステキストを編集します ]

プログラミング言語CにおけるTwedアルゴリズムの実装は、著者のホームページからダウンロードできます。 [3]

MATLABでの実装 [ 編集 | ソーステキストを編集します ]

Twed Algorithmus： 

関数  [距離、dp] = twed （ A、Timesa、B、Timesb、Lambda、Nu ））  ％[距離、dp] = twed（a、timesa、b、timesb、lambda、nu）  ％時系列AおよびBのタイムワープ編集距離（TWED）を計算する  ％  ％a：=時系列Aの値（例：[10 2 30 4]）  ％タイム：=時系列Aの値のタイムテンプル（例：1：4）  ％B：=時系列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

最も費用対効果の高いパスを追跡するためのバックトラッキング： 

関数  [パス] =バックトラッキング （ DP ））  ％[PATH] =バックトラッキング（DP）  ％コスト効果の高いパスの計算  ％DP：= Twed関数のDPマトリックス   バツ  =  サイズ （ DP ）;   私  =  バツ （ 初め ）;   j  =  バツ （ 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
  • P.-F。ハンマー： 時系列のマッチングのための剛性調整でタイムワープ編集距離 。の： パターン分析とマシンインテリジェンスに関するIEEEトランザクション 。 バンド 最初に30 、 いいえ。 2 、2009年2月、 S. 306–318 、doi： 10.1109/tpami。2008.76 。
  1. ↑ 東の張力： ガウス弾性メトリックカーネルを使用したサポートベクターマシンを使用した時系列分類 。の： パターン認識（ICPR）、2010年20回目の国際会議 。 2010年8月、 S. 29–32 、doi： 10.1109/ICPR.2010.16 。
  2. ↑ Lei Liu、Wangmeng Zuo、Doongyu Zhang、Naimin Li、Hongzhi Zhang： タイムワープ編集距離を使用した手首パルス血流信号の分類 。の： ICMB 2010、LNCS 6165 。 S. 137–144 、doi： 10,1007/978-3-642-13923-9_14 。
  3. ↑ P.-F。ハンマー： IRISAサーバーのホームページ。 2014年8月26日にアクセス 。
after-content-x4