9.1. Medidas de Similaridade entre Séries Temporais

Existem diferentes medidas de similaridade para séries temporais [144], como mostrado na Figura 9.4. Essas medidas incluem Hausdorff, Modified Hausdorff (MODH), HMM-based distance, Dynamic Time Warping (DTW), Euclidean distance, Euclidean distance in a PCA subspace, and Longest Common Sub-Sequence (LCSS).

Figura 9.4 - Medidas de similaridades entre séries temporais baseadas na forma.
**Adaptado de:** [144].

A escolha de uma abordagem de distância adequada depende das características das séries temporais, da duração das séries, do método de representação e do objetivo do agrupamento (similaridade no tempo, na forma ou na mudança). As distâncias mais utilizadas para similaridade entre séries temporais são: Euclidiana e DTW (e suas variações). Figura 9.5 e Figura 9.6 ilustram a diferença entre as distâncias DTW e Euclidiana entre duas séries temporais.

Figura 9.5 - Distâncias DTW e Euclidiana entre duas séries temporais.
**Fonte:** [148].

9.1.1. Distância Euclidiana

A distância euclidiana e suas variações, como Manhattan, são amplamente utilizadas em métodos de agrupamento devido suas simplicidades e eficiência linear $O (n)$ . Baseada em comparações ponto a ponto (lock-step), em que assume que o i-ésimo ponto de uma série esteja alinhado com o i-ésimo ponto na outra série, como ilustrado nas figuras anteriores, a distância euclidiana é limitada a séries temporais com a mesma linha de base, escala e comprimento. Além disso, ela ignora os desalinhamentos nos eixos temporais.

Definição: Dado duas séries temporais $i = (x_{i 1}, x_{i 2}, . . ., x_{i n})$ e $j = (x_{j 1}, x_{j 2}, . . ., x_{j n})$ com n valores.

A distância euclidiana entre essas duas séries é definida como:

(9.1)

d (i, j) = \sqrt{(x_{i 1} - x_{j 1})^{2} + (x_{i 2} - x_{j 2})^{2} + . . . + (x_{i n} - x_{j n})^{2}}

A distância manhattan entre essas duas séries é definida como:

(9.2)

d (i, j) = | x_{i 1} - x_{j 1} | + | x_{i 2} - x_{j 2} | + . . . + | x_{i n} - x_{j n} |

9.1.2. Distância DTW (Dynamic Time Warping)

Dado duas séries temporais, a distância DTW (Dynamic Time Warping) as esticam ou comprimem localmente para fazer com que uma se pareça com a outra o máximo possível [150]. Por isso a distância DTW é chamada de elástica. Ela contorna o problema de desalinhamento temporal, pois permite uma mudança elástica no eixo do tempo, como ilustrado na Figura 9.7. A distância entre as duas séries é computada após o alongamento, somando as distâncias entre os elementos alinhados. Essa distância baseia-se em técnicas de programação dinâmica, sendo mais robusta que a distância euclidiana, no entanto, sem otimizações possui complexidade de $O (n^{2})$ [148].

Figura 9.7 - Distância DTW (Dynamic Time Warping) entre duas séries temporais.
**Adaptada de:** [148].

Definição: Dado duas séries temporais $Q = q_{1}, q_{2}, . . ., q_{n}$ e $C = c_{1}, c_{2}, . . ., c_{m}$ . Para alinhar ambas sequências, uma matriz $n$ x $m$ é construída, em que cada elemento $(i_{t h}, j_{t h})$ contém a distância entre $q_{i}$ e $c_{j}$ , como por exemplo $d (q_{i}, c_{j}) = (q_{i} - c_{j})^{2}$ . Cada elemento $(i, j)$ da matriz corresponde ao alinhamento entre os pontos $q_{i}$ e $c_{j}$ . Uma via de deformação (ou Warping Path) $W$ é um traçado de elementos contíguos na matriz, que define um mapeamento entre $Q$ e $C$ . O elemento $k^{t h}$ de $W$ é definido como $w_{k} = (i, j)_{k}$ . Assim, $W = w_{1}, w_{2}, . . ., w_{k}$ é obtido com $max (m, n) \leq K < m + n - 1$ . Geralmente, o caminho na matriz é diagonal, começando em extremos opostos da matriz, por exemplo $w_{1} = (1, 1)$ e $w_{k} = (m, n)$ . Desta forma, o objetivo é selecionar o caminho que minimize o custo da via de deformação:

(9.3)

D T W (Q, C) = min (\sqrt{\sum_{k = 1}^{K} w_{k}})

Para restringir o quanto a via de deformação (ou Warping Path) pode desviar da diagonal da matriz, é possível definir a janela de deformação (ou Warping Window). A Figura 9.8 ilustra dois tipos de janelas mais usadas como restrição global no DTW: Sakoe-Chiba Band and the Itakura Parallelogram.

Figura 9.8 - Janela de deformação (ou *Warping Window*) do DTW (Dynamic Time Warping).
**Fonte:** [148].