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
editarA 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.[1] 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
editarPor 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.[2] 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.[3] 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 algoritmo[4] ou aproximações da medida de distância.[5]
Referências
- ↑ 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
- ↑ Eamonn Keogh, Chotirat Ann Ratanamahatana (2004). Exact indexing of dynamic time warping
- ↑ 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
- ↑ Diego Furtado Silva, Gustavo Batista (2015). Speeding Up All-Pairwise Dynamic Time Warping Matrix Calculation
- ↑ Stan Salvador, Philip K. Chan (2007). Toward accurate dynamic time warping in linear time and space
