Dynamic time warping

Dynamic time warping (DTW) é 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. 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 $O(N^{2})$. 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. 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. 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 ou aproximações da medida de distância.