Distorção dinâmica do tempo (DTW, na sigla em inglês) é um algoritmo para comparar e alinhar duas séries temporais. A DTW é utilizada para encontrar o alinhamento não-linear ótimo entre duas sequências de valores numéricos. Dessa maneira, é possível encontrar padrões entre medições de eventos com diferentes ritmos. Por exemplo, é possível casar a série temporal obtida por acelerômetros (ou outros sensores) de duas pessoas andando em diferentes velocidades.

DTW pode ser utilizada para alinhar qualquer tipo de dado que obedeça uma ordem temporal, como vídeo, áudio e imagens. Entre as diversas aplicações da DTW, encontra-se o reconhecimento de fala e de assinatura, bem como o alinhamento de gravações musicais com suas respectivas partituras.

Apesar do algoritmo que calcula a DTW fornecer um valor numérico relacionado a uma medida de distância, ele deve ser utilizado com cautela. Por não obedecer a desigualdade triangular, a DTW não pode ser considerada uma métrica. Consequentemente, métodos de indexação em espaço métrico não são aplicáveis.

Implementação A DTW é implementado por um algoritmo de programação dinâmica. O exemplo a seguir ilustra a implementação da DTW para alinhar duas séries temporais s e t, em que d(x, y) é a distância entre os valores x e y. Especificamente, d(x, y) geralmente é calculado como o quadro da distância euclidiana entre eles, ou seja, d(x, y) = (x-y)². int DTWDistance(s: array [1..n], t: array [1..m]) { DTW := array [0..n, 0..m]

for i := 1 to n DTW[i, 0] := infinity for i := 1 to m DTW[0, i] := infinity DTW[0, 0] := 0

for i := 1 to n for j := 1 to m cost := d(s[i], t[j<nowiki>])</nowiki> 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] }

Comumente, a DTW é associada a uma janela de restrição.Zoltan Geler, Vladimir Kurbalija, Miloš Radovanović, Mirjana Ivanović (2014). Impact of the Sakoe-Chiba Band on the DTW Time Series Distance Measure for kNN Classification Basicamente, essa técnica limita a distância no eixo do tempo do alinhamento entre valores das séries temporais sendo comparadas.

Cálculo Eficiente Por ser calculado por um algoritmo de programação dinâmica bi-dimensional, o cálculo da DTW tem complexidade . Isso torna seu uso inviável em grandes conjuntos de dados. Por isso, diversas técnicas de indexação específicas para essa medida foram propostas para a tarefa de busca por similaridade, tais como lower bound e early abandoning.Eamonn Keogh, Chotirat Ann Ratanamahatana (2004). Exact indexing of dynamic time warping Com essas técnicas, é possível encontrar os vizinhos mais próximos de uma dada subsequência em uma quantidade massiva de séries temporais em poucos segundos utilizando a DTW.Thanawin Rakthanmanon, Bilson Campana, Abdullah Mueen, Gustavo Batista,Brandon Westover, Qiang Zhu, Jesin Zakaria, Eamonn Keogh (2012). Searching and Mining Trillions of Time Series Subsequences under Dynamic Time Warping Quando a tarefa em execução não pode ser reduzida à busca por similaridade, as únicas alternativas para acelerar o cálculo da DTW são a poda de etapas do seu algoritmoDiego Furtado Silva, Gustavo Batista (2015). Speeding Up All-Pairwise Dynamic Time Warping Matrix Calculation ou aproximações da medida de distância.Stan Salvador, Philip K. Chan (2007). Toward accurate dynamic time warping in linear time and space

Categoria:Inteligência artificial Categoria:Algoritmos de aprendizado de máquina Categoria:Programação dinâmica