Time Warp Upravit vzdálenost - Time Warp Edit Distance

Tento článek má několik problémů. Prosím pomozte zlepšit to nebo diskutovat o těchto otázkách na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) tento článek poskytuje nedostatečný kontext pro ty, kteří danému tématu nejsou obeznámeni. Prosím pomozte vylepšit článek podle poskytuje čtenáři více kontextu. (Listopad 2016) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) tento článek může být pro většinu čtenářů příliš technická na to, aby tomu rozuměli. Prosím pomozte to vylepšit na aby to bylo srozumitelné pro neodborníky, aniž by byly odstraněny technické podrobnosti. (Listopad 2016) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) tento článek potřebuje víc odkazy na další články pomoci integrovat to do encyklopedie. Prosím pomozte vylepšit tento článek přidáním odkazů které jsou relevantní pro kontext v rámci stávajícího textu. (Září 2016) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) tento článek je sirotek, jako žádné další články odkaz na to. Prosím zavést odkazy na tuto stránku z související články; zkuste Najít odkaz nástroj pro návrhy. (Září 2016) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Time Warp Upravit vzdálenost (TWED) je míra vzdálenosti pro diskrétní časové řady shoda s časovou „pružností“. Ve srovnání s jinými měřiči vzdálenosti (např.Dynamic Time Warping ) nebo LCS (Nejdelší běžný problém s následností )), TWED je a metrický. Jeho výpočetní časová složitost je ${ displaystyle O (n ^ {2})}$, ale lze jej drasticky snížit v určité konkrétní situaci pomocí koridoru ke zmenšení vyhledávacího prostoru. Složitost jeho paměťového prostoru lze snížit na ${ displaystyle O (n)}$. Poprvé to navrhl v roce 2009 P.-F. Marteau.

Definice

${ displaystyle 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 {delete in A}} delta _ { lambda, nu} (A_ {1} ^ {p-1}, B_ {1} ^ {q-1}) + Gamma (a_ {p} ^ {'} až b_ {q} ^ {'}) & { rm {match or substitution}} delta _ { lambda, nu} (A_ {1} ^ {p}, B_ {1} ^ {q- 1}) + Gamma ( Lambda to b_ {q} ^ {'}) & { rm {delete in B}} end {cases}}}$
zatímco

${ displaystyle Gamma ( alpha _ {p} ^ {'} to Lambda) = d_ {LP} (a_ {p} ^ {'}, a_ {p-1} ^ {'}) + nu cdot (t_ {a_ {p}} - t_ {a_ {p-1}}) + lambda}$
${ displaystyle Gamma ( alpha _ {p} ^ {'} až 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}} |)}$
${ displaystyle Gamma ( Lambda až b_ {q} ^ {'}) = d_ {LP} (b_ {p} ^ {'}, b_ {p-1} ^ {'}) + nu cdot (t_ {b_ {q}} - t_ {b_ {q-1}}) + lambda}$

Zatímco rekurze${ displaystyle delta _ { lambda, nu}}$je inicializován jako:
${ displaystyle delta _ { lambda, nu} (A_ {1} ^ {0}, B_ {1} ^ {0}) = 0,}$
${ displaystyle delta _ { lambda, nu} (A_ {1} ^ {0}, B_ {1} ^ {j}) = infty { rm {{pro } j geq 1}} }$
${ displaystyle delta _ { lambda, nu} (A_ {1} ^ {i}, B_ {1} ^ {0}) = infty { rm {{pro } i geq 1}} }$
s${ displaystyle a '_ {0} = b' _ {0} = 0}$

Implementace

Implementaci algoritmu TWED v jazyce C nebo Matlab lze stáhnout z domovské stránky autorů^[1]

Implementace R TWED byla integrována do TraMineR, balíčku R pro těžbu, popisující a vizualizující sekvence stavů nebo událostí a obecněji diskrétní data sekvence^[2]

Dodatečně, škubání je CUDA akcelerovaná implementace TWED, která využívá vylepšený algoritmus díky G. Wrightovi (2020). Tato metoda je lineární v paměti a masivně paralelizovaná. cuTWED je napsán v CUDA C / C ++, je dodáván s vazbami pythonu a zahrnuje také vazby pythonu pro implementaci Marteauovy referenční C.

Krajta

import numpy tak jako npdef Dlp(A, B, p=2):    náklady = np.součet(np.Napájení(np.břišní svaly(A - B), p))    vrátit se np.Napájení(náklady, 1 / p)def twed(A, čas SA, B, časSB, nu, _lambda):    # [vzdálenost, DP] = TWED (A, timeSA, B, timeSB, lambda, nu)    # Vypočítat vzdálenost úprav časové osy (TWED) pro danou časovou řadu A a B    #    # A: = Časová řada A (např. [10 2 30 4])    # timeSA: = Časová známka časové řady A (např. 1: 4)    # B: = Časová řada B    # timeSB: = Časová známka časové řady B    # lambda: = Trest za operaci odstranění    # nu: = parametr pružnosti - nu> = 0 potřebné pro měření vzdálenosti    # Reference:    # Marteau, P .; F. (2009). Msgstr "Time Warp Edit Distance with Stiffness Adjustment for Time Series Matching".    # IEEE Transaction on Pattern Analysis and Machine Intelligence. 31 (2): 306–318. arXiv: cs / 0703033    # http://people.irisa.fr/Pierre-Francois.Marteau/    # Zkontrolujte, zda jsou zadány argumenty    -li len(A) != len(čas SA):        tisk("Délka A není stejná délka timeSA")        vrátit se Žádný, Žádný    -li len(B) != len(časSB):        tisk("Délka B není stejná délka timeSB")        vrátit se Žádný, Žádný    -li nu < 0:        tisk(„nu je negativní“)        vrátit se Žádný, Žádný    # Přidejte polstrování    A = np.pole([0] + seznam(A))    čas SA = np.pole([0] + seznam(čas SA))    B = np.pole([0] + seznam(B))    časSB = np.pole([0] + seznam(časSB))    n = len(A)    m = len(B)    # Dynamické programování    DP = np.nuly((n, m))    # Inicializujte DP Matrix a nastavte první řádek a sloupec na nekonečno    DP[0, :] = np.inf    DP[:, 0] = np.inf    DP[0, 0] = 0    # Vypočítejte minimální náklady    pro i v rozsah(1, n):        pro j v rozsah(1, m):            # Vypočítejte a ušetřete náklady na různé operace            C = np.ty((3, 1)) * np.inf            # Vymazání v A            C[0] = (                DP[i - 1, j]                + Dlp(A[i - 1], A[i])                + nu * (čas SA[i] - čas SA[i - 1])                + _lambda            )            # Vymazání v B            C[1] = (                DP[i, j - 1]                + Dlp(B[j - 1], B[j])                + nu * (časSB[j] - časSB[j - 1])                + _lambda            )            # Ponechat datové body v obou časových řadách            C[2] = (                DP[i - 1, j - 1]                + Dlp(A[i], B[j])                + Dlp(A[i - 1], B[j - 1])                + nu * (břišní svaly(čas SA[i] - časSB[j]) + břišní svaly(čas SA[i - 1] - časSB[j - 1]))            )            # Vyberte operaci s minimálními náklady a aktualizujte DP Matrix            DP[i, j] = np.min(C)    vzdálenost = DP[n - 1, m - 1]    vrátit se vzdálenost, DP

Backtracking, abyste našli nákladově nejefektivnější cestu:

def ustoupit(DP):    # [best_path] = BACKTRACKING (DP)    # Vypočítejte nákladově nejefektivnější cestu    # DP: = DP matice funkce TWED    X = np.tvar(DP)    i = X[0] - 1    j = X[1] - 1    # Indexy cest se ukládají v opačném směru    # path = np.ones ((i + j, 2)) * np.inf;    best_path = []    kroky = 0    zatímco i != 0 nebo j != 0:        best_path.připojit((i - 1, j - 1))        C = np.ty((3, 1)) * np.inf        # Ponechat datové body v obou časových řadách        C[0] = DP[i - 1, j - 1]        # Vymazání v A        C[1] = DP[i - 1, j]        # Vymazání v B        C[2] = DP[i, j - 1]        # Najděte index s nejnižšími náklady        idx = np.argmin(C)        -li idx == 0:            # Ponechat datové body v obou časových řadách            i = i - 1            j = j - 1        elif idx == 1:            # Vymazání v A            i = i - 1            j = j        jiný:            # Vymazání v B            i = i            j = j - 1        kroky = kroky + 1    best_path.připojit((i - 1, j - 1))    best_path.zvrátit()    vrátit se best_path[1:]

MATLAB

funkce[vzdálenost, DP] =twed(A, timeSA, B, timeSB, lambda, nu)% [vzdálenost, DP] = TWED (A, timeSA, B, timeSB, lambda, nu)    % Vypočítat vzdálenost pro úpravu časové osy (TWED) pro danou časovou řadu A a B    %    % A: = Časová řada A (např. [10 2 30 4])    % timeSA: = Časové razítko časové řady A (např. 1: 4)    % B: = Časová řada B    % timeSB: = Časová známka časové řady B    % lambda: = Penalizace za operaci odstranění    % nu: = parametr pružnosti - nu> = 0 potřebné pro měření vzdálenosti    %    % Kód od: P.-F. Marteau - http://people.irisa.fr/Pierre-Francois.Marteau/     % Zkontrolujte, zda jsou zadány argumenty    -li délka (A) ~ = délka (timeSA)        Varování(„Délka A není stejná délka timeSA“)        vrátit sekonec    -li délka (B) ~ = délka (timeSB)        Varování(„Délka B není stejná délka timeSB“)        vrátit sekonec    -li nu <0        Varování(‚nu je negativní ')        vrátit sekonec    % Přidat polstrování    A = [0 A];    čas SA = [0 čas SA];    B = [0 B];    časSB = [0 časSB];     % Dynamické programování    DP = nuly(délka(A), délka(B));     % Inicializujte DP Matrix a nastavte první řádek a sloupec na nekonečno    DP(1, :) = inf;    DP(:, 1) = inf;    DP(1, 1) = 0;     n = délka(čas SA);    m = délka(časSB);    % Vypočítat minimální náklady    pro i = 2: n        pro j = 2: m            náklady = Dlp(A(i), B(j));                     % Vypočítejte a ušetřete náklady na různé operace            C = ty(3, 1) * inf;                     % Vymazání v A            C(1) = DP(i - 1, j) + Dlp(A(i - 1), A(i)) + nu * (čas SA(i) - čas SA(i - 1)) + lambda;            % Vymazání v B            C(2) = DP(i, j - 1) + Dlp(B(j - 1), B(j)) + nu * (časSB(j) - časSB(j - 1)) + lambda;            % Udržujte datové body v obou časových řadách            C(3) = DP(i - 1, j - 1) + Dlp(A(i), B(j)) + Dlp(A(i - 1), B(j - 1)) + ...            nu * (břišní svaly(čas SA(i) - časSB(j)) + břišní svaly(čas SA(i - 1) - časSB(j - 1)));                     % Vyberte operaci s minimálními náklady a aktualizujte DP Matrix            DP(i, j) = min(C);        koneckonec     vzdálenost = DP(n, m);     % Funkce pro výpočet euklidovské vzdálenosti    funkce[náklady] =Dlp(A, B)náklady = čtv(součet((A - B) .^ 2, 2));    koneckonec

Backtracking, abyste našli nákladově nejefektivnější cestu:

funkce[cesta] =ustoupit(DP)% [cesta] = BACKTRACKING (DP)    % Vypočítejte nákladově nejefektivnější cestu    % DP: = DP matice funkce TWED     X = velikost(DP);    i = X(1);    j = X(2);     % Indexy cest se ukládají v opačném směru    cesta = ty(i + j, 2) * Inf;     kroky = 1;    zatímco (i ~= 1 || j ~= 1)        cesta(kroky, :) = [i; j];             C = ty(3, 1) * inf;             % Udržujte datové body v obou časových řadách        C(1) = DP(i - 1, j - 1);        % Vymazání v A        C(2) = DP(i - 1, j);        % Vymazání v B        C(3) = DP(i, j - 1);             % Najděte index s nejnižšími náklady        [~, idx] = min(C);             přepínač idx            případ 1                % Udržujte datové body v obou časových řadách                i = i - 1;                j = j - 1;            případ 2                % Vymazání v A                i = i - 1;                j = j;            případ 3                % Vymazání v B                i = i;                j = j - 1;        konec        kroky = kroky + 1;    konec    cesta (kroky, :) = [i j];     % Cesta byla vypočtena v opačném směru.    cesta = cesta(1:kroky, :);    cesta = cesta(konec: - 1:1, :); konec

Reference

• Marteau, P .; F. (2009). Msgstr "Time Warp Edit Distance with Stiffness Adjustment for Time Series Matching". Transakce IEEE na analýze vzorů a strojové inteligenci. 31 (2): 306–318. arXiv:cs / 0703033. doi:10.1109 / TPAMI.2008.76.