Dynamiczne dopasowanie czasu — Dynamic time warping

Dynamiczne zakrzywienie czasu
Dwa powtórzenia sekwencji chodzenia nagranej za pomocą systemu przechwytywania ruchu. Chociaż istnieją różnice w szybkości chodzenia między powtórzeniami, tory przestrzenne kończyn pozostają bardzo podobne.

W analizie szeregów czasowych , odkształcanie dynamiczny czas ( DTW ) jest jednym z algorytmami do pomiaru podobieństwa dwóch sekwencji czasowych, które mogą różnić się szybkością. Na przykład podobieństwa w chodzeniu można wykryć za pomocą DTW, nawet jeśli jedna osoba szła szybciej niż druga lub jeśli w trakcie obserwacji występowały przyspieszenia i opóźnienia. DTW zastosowano do czasowych sekwencji danych wideo, audio i graficznych — w rzeczywistości wszelkie dane, które można przekształcić w sekwencję liniową, można analizować za pomocą DTW. Dobrze znaną aplikacją jest automatyczne rozpoznawanie mowy , aby radzić sobie z różnymi prędkościami mówienia. Inne aplikacje obejmują rozpoznawanie mówców i rozpoznawanie podpisów online . Może być również używany w aplikacjach do częściowego dopasowania kształtu .

Ogólnie rzecz biorąc, DTW jest metodą obliczającą optymalne dopasowanie między dwoma podanymi ciągami (np. szeregami czasowymi ) z pewnymi ograniczeniami i regułami:

  • Każdy indeks z pierwszego ciągu musi być dopasowany do jednego lub więcej indeksów z drugiego ciągu i odwrotnie
  • Pierwszy indeks z pierwszego ciągu musi być dopasowany do pierwszego indeksu z drugiego ciągu (ale nie musi to być jego jedyne dopasowanie)
  • Ostatni indeks z pierwszego ciągu musi być dopasowany do ostatniego indeksu z drugiego ciągu (ale nie musi to być jego jedyne dopasowanie)
  • Odwzorowanie indeksów z pierwszego ciągu na indeksy z drugiego ciągu musi być monotonicznie rosnące i odwrotnie, tzn. jeśli są indeksy z pierwszego ciągu, to w drugim ciągu nie mogą być dwa indeksy , tak aby indeks był dopasowany z indeksem i indeks jest dopasowywany do indeksu i na odwrót

Optymalny mecz oznaczamy meczu, który spełnia wszystkie ograniczenia i zasady i że ma minimalne koszty, gdzie koszt jest obliczany jako suma różnic bezwzględnych, dla każdego dopasowane pary indeksów, między ich wartościami.

Sekwencje są „wypaczane” nieliniowo w wymiarze czasu, aby określić miarę ich podobieństwa niezależnie od pewnych nieliniowych zmian w wymiarze czasu. Ta metoda dopasowywania sekwencji jest często stosowana w klasyfikacji szeregów czasowych. Chociaż DTW mierzy wielkość podobną do odległości między dwiema podanymi sekwencjami, nie gwarantuje utrzymania nierówności trójkąta .

Oprócz miary podobieństwa między dwiema sekwencjami wytwarzana jest tak zwana „ścieżka dopasowująca”, przez dopasowanie zgodnie z tą ścieżką dwa sygnały mogą być wyrównane w czasie. Sygnał z oryginalnym zestawem punktów X (oryginalny), Y (oryginalny) jest przekształcany na X (wypaczony), Y (wypaczony). Znajduje to zastosowanie w sekwencji genetycznej i synchronizacji dźwięku. W pokrewnej technice sekwencje o różnej prędkości mogą być uśredniane przy użyciu tej techniki, patrz sekcja o średniej sekwencji .

Jest to koncepcyjnie bardzo podobne do algorytmu Needlemana-Wunscha .

Realizacja

Ten przykład ilustruje implementację algorytmu dynamicznego dopasowania czasu, gdy dwie sekwencje s i t są ciągami symboli dyskretnych. Przez dwa symbole X i Y , d(x, y)to odległość między symbolami, np d(x, y)= . 

int DTWDistance(s: array [1..n], t: array [1..m]) {
    DTW := array [0..n, 0..m]
    
    for i := 0 to n
        for j := 0 to m
            DTW[i, j] := infinity
    DTW[0, 0] := 0
    
    for i := 1 to n
        for j := 1 to m
            cost := d(s[i], t[j])
            DTW[i, j] := cost + minimum(DTW[i-1, j  ],    // insertion
                                        DTW[i  , j-1],    // deletion
                                        DTW[i-1, j-1])    // match
    
    return DTW[n, m]
}

gdzie DTW[i, j]jest odległość między s[1:i]i t[1:j]z najlepszym wyrównaniem.

Czasami chcemy dodać ograniczenie lokalizacji. Oznacza to, że jeśli s[i]jest dopasowane z t[j], then nie jest większe niż w , parametr okna.

Możemy łatwo zmodyfikować powyższy algorytm, aby dodać ograniczenie lokalności (różnice wyraźny). Jednak powyższa modyfikacja działa tylko wtedy, gdy nie jest większa niż w , czyli punkt końcowy znajduje się na długości okna od przekątnej. Aby algorytm działał, parametr okna w musi być tak dostosowany (patrz linia oznaczona (*) w kodzie). 

int DTWDistance(s: array [1..n], t: array [1..m], w: int) {
    DTW := array [0..n, 0..m]

    w := max(w, abs(n-m)) // adapt window size (*)

    for i := 0 to n
        for j:= 0 to m
            DTW[i, j] := infinity
    DTW[0, 0] := 0
    for i := 1 to n
        for j := max(1, i-w) to min(m, i+w)
            DTW[i, j] := 0

    for i := 1 to n
        for j := max(1, i-w) to min(m, i+w)
            cost := d(s[i], t[j])
            DTW[i, j] := cost + minimum(DTW[i-1, j  ],    // insertion
                                        DTW[i  , j-1],    // deletion
                                        DTW[i-1, j-1])    // match

    return DTW[n, m]
}

Wypaczanie właściwości

Algorytm DTW tworzy dyskretne dopasowanie między istniejącymi elementami jednej serii do drugiej. Innymi słowy, nie pozwala na skalowanie czasowe segmentów w sekwencji. Inne metody umożliwiają ciągłe wypaczanie. Na przykład, Correlation Optimized Warping (COW) dzieli sekwencję na jednolite segmenty, które są skalowane w czasie przy użyciu interpolacji liniowej, aby uzyskać najlepiej dopasowane wypaczenie. Skalowanie segmentów powoduje potencjalne tworzenie nowych elementów poprzez skalowanie segmentów w dół lub w górę iw ten sposób daje bardziej czułe wypaczenie niż dyskretne dopasowanie surowych elementów przez DTW.

Złożoność

Złożoność czasowa algorytmu DTW wynosi , gdzie i są długościami dwóch sekwencji wejściowych. 50-letnia kwadratowa granica czasu została niedawno złamana, algorytm Golda i Sharira umożliwia obliczenie DTW w czasie i przestrzeni dla dwóch wejściowych sekwencji długości . Algorytm ten można również dostosować do sekwencji o różnej długości. Pomimo tej poprawy, wykazano, że silnie podkwadratowy czas przebiegu formy dla niektórych nie może istnieć, chyba że zawiedzie hipoteza Silnego czasu wykładniczego .

Podczas gdy algorytm programowania dynamicznego dla DTW wymaga miejsca w naiwnej implementacji, zużycie przestrzeni można zredukować do zastosowania algorytmu Hirschberga .

Szybkie obliczenia

Szybkie techniki obliczania DTW obejmują PrunedDTW, SparseDTW, FastDTW i MultiscaleDTW. Typowe zadanie, wyszukiwanie podobnych szeregów czasowych, można przyspieszyć, stosując dolne ograniczenia, takie jak LB_Keogh lub LB_Improved. W ankiecie Wang i in. odnotowali nieco lepsze wyniki z dolną granicą LB_Improved niż ograniczenie LB_Keogh i stwierdzili, że inne techniki były nieefektywne.

Średnia sekwencja

Uśrednianie dla dynamicznego dopasowania czasu to problem ze znalezieniem średniej sekwencji dla zestawu sekwencji. NLAAF to dokładna metoda uśredniania dwóch sekwencji przy użyciu DTW. W przypadku więcej niż dwóch sekwencji problem jest związany z wielokrotnym dopasowaniem i wymaga heurystyki. DBA jest obecnie metodą referencyjną do uśredniania zestawu sekwencji zgodnie z DTW. COMASA skutecznie randomizuje wyszukiwanie średniej sekwencji, wykorzystując DBA jako lokalny proces optymalizacji.

Nadzorowana nauka

Najbliższy sąsiad-klasyfikator może osiągnąć state-of-the-art wydajności podczas korzystania z dynamicznego dopasowania czasu jako miary odległości.

Alternatywne podejścia

W funkcjonalnej analizie danych szeregi czasowe są traktowane jako dyskretyzacje gładkich (różnicowalnych) funkcji czasu. Przeglądając obserwowane próbki w funkcjach gładkich, można wykorzystać matematykę ciągłą do analizy danych. Gładkość i monotoniczność funkcji dopasowania czasowego można uzyskać na przykład przez całkowanie zmiennej w czasie radialnej funkcji bazowej , będącej w ten sposób jednowymiarowym dyfeomorfizmem . Optymalne nieliniowe funkcje dopasowujące czas są obliczane przez minimalizację miary odległości zestawu funkcji do ich zakrzywionej średniej. Warunki kary za chropowatość dla funkcji wypaczania mogą być dodane, np. przez ograniczenie rozmiaru ich krzywizny. Wynikowe funkcje wypaczania są płynne, co ułatwia dalszą obróbkę. To podejście zostało z powodzeniem zastosowane do analizy wzorców i zmienności ruchów mowy.

Innym pokrewnym podejściem są ukryte modele Markowa (HMM) i wykazano, że algorytm Viterbiego używany do wyszukiwania najbardziej prawdopodobnej ścieżki przez HMM jest odpowiednikiem stochastycznego DTW.

DTW i powiązane metody wypaczania są zwykle używane jako etapy przetwarzania wstępnego lub końcowego w analizach danych. Jeżeli obserwowane sekwencje zawierają zarówno losową zmienność w obu ich wartościach, kształt obserwowanych sekwencji, jak i losowe niedopasowanie czasowe, zniekształcenie może nadmiernie pasować do szumu, prowadząc do zniekształconych wyników. Jednoczesne sformułowanie modelu z losową zmiennością zarówno wartości (w pionie), jak i parametryzacji czasowej (w poziomie) jest przykładem nieliniowego modelu efektów mieszanych . W analizie ruchu człowieka wykazano, że jednoczesne nieliniowe modelowanie efektów mieszanych daje lepsze wyniki w porównaniu z DTW.

Oprogramowanie open source

  • W lbimproved c ++ biblioteka implementuje Szybko najbliższych sąsiadów pobierania algorytmy na licencji GNU General Public License (GPL). Zapewnia również implementację C++ dynamicznego dopasowania czasu, a także różne dolne ograniczenia.
  • FastDTW Biblioteka jest implementacja Javy z Detroit i realizacji FastDTW który zapewnia optymalne lub prawie optymalne dopasowania z O ( N ) czasu i pamięci złożoności, w przeciwieństwie do O ( N 2 ) wymogu standardowego algorytmu DTW. FastDTW wykorzystuje podejście wielopoziomowe, które rekursywnie projektuje rozwiązanie z grubszej rozdzielczości i udoskonala projektowane rozwiązanie.
  • Widelec FastDTW (Java) opublikowany w Maven Central.
  • time-series-classification (Java) pakiet do klasyfikacji szeregów czasowych przy użyciu DTW w języku Weka.
  • Pakiet DTW zapewnia pakiety Python ( dtw-python ) i R ( dtw ) z kompleksowym omówieniem członków rodziny algorytmów DTW, w tym różnych reguł rekurencji (zwanych również wzorcami kroków), ograniczeń i dopasowywania podciągów.
  • Biblioteka mlpy Python implementuje DTW.
  • Biblioteka pydtw Python implementuje miary DTW o smaku Manhattanu i Euklidesa, w tym dolne granice LB_Keogh.
  • Cudadtw C ++ / narzędzia biblioteki CUDA podciąg wyrównanie euklidesowa smaku Detroit i Z -normalized odległość euklidesową podobny do popularnego UCR-Suite z obsługą CUDA akceleratorów.
  • JavaML machine learning narzędzi bibliotecznych DTW .
  • Biblioteka ndtw C# implementuje DTW z różnymi opcjami.
  • Sketch-a-Char wykorzystuje Greedy DTW (zaimplementowany w JavaScript) jako część programu klasyfikatora symboli LaTeX.
  • W zapałek narzędzia DTW dopasować Mel częstotliwości współczynników cepstralnych sygnałów audio.
  • Uśrednianie sekwencji : implementacja DBA na licencji GPL Java.
  • Gesture Recognition Toolkit | GRT C ++ w czasie rzeczywistym, narzędzia do rozpoznawania gest Toolkit DTW.
  • W PyHubs oprogramowanie wdraża pakiet DTW i klasyfikatorów najbliższych sąsiadów, a także ich rozszerzenia (hubness świadomy klasyfikatorów).
  • Biblioteka simpledtw Python implementuje klasyczny algorytm programowania dynamicznego O ( NM ) i bazuje na Numpy. Obsługuje wartości dowolnego wymiaru, a także wykorzystuje niestandardowe funkcje norm dla odległości. Jest licencjonowany na podstawie licencji MIT.
  • Biblioteka tslearn Python implementuje DTW w kontekście szeregów czasowych.
  • Biblioteka cuTWED CUDA Python implementuje najnowocześniejszą, ulepszoną odległość edycji z zakrzywieniem czasowym, używając tylko pamięci liniowej z fenomenalnymi przyspieszeniami.
  • DynamicAxisWarping.jl to implementacja Julii DTW i powiązanych algorytmów, takich jak FastDTW, SoftDTW, GeneralDTW i barycenters DTW.

Aplikacje

Rozpoznawanie słów mówionych

Ze względu na różne tempo mówienia występuje nieliniowa fluktuacja wzorca mowy względem osi czasu, którą należy wyeliminować. Dopasowanie DP to algorytm dopasowywania wzorców oparty na programowaniu dynamicznym (DP) , który wykorzystuje efekt normalizacji czasu, w którym fluktuacje na osi czasu są modelowane przy użyciu nieliniowej funkcji odkształcania czasu. Biorąc pod uwagę dowolne dwa wzorce mowy, możemy pozbyć się ich różnic czasowych, wypaczając oś czasu jednego, aby osiągnąć maksymalną zbieżność z drugim. Co więcej, jeśli funkcja wypaczania może przyjąć dowolną możliwą wartość, znacznie mniej rozróżnia się między słowami należącymi do różnych kategorii. Tak więc, aby wzmocnić rozróżnienie między słowami należącymi do różnych kategorii, nałożono ograniczenia na nachylenie funkcji wypaczania.

Analiza mocy korelacji

Niestabilne zegary są używane do pokonania naiwnej analizy mocy . W celu przeciwdziałania tej obronie stosuje się kilka technik, z których jedną jest dynamiczne zakrzywianie czasu.

Zobacz też

Bibliografia

Dalsza lektura