terça-feira, 10 de dezembro de 2013
Inaugurando a minha primeira postagem no Blog Quase Mestre, irei comentar um pouco sobre uma distância bem conhecida na literatura (áreas de banco de dados, imagens, matemática e dentre outras) e também pela comunidade de reconhecimento de voz, chamada de DTW (Dynamic Time Warping) que traduzindo ao pé da letra, seria Deformação do Tempo Dinâmico.
Uma técnica que permite o mapeamento não linear entre duas séries temporais, de tal forma que realiza a similaridade entre elas para minimizar sua distância. É bastante utilizada em mineração de dados e várias outras tarefas e/ou problemas que podem envolver algum tipo de classificação, clusterização, detecção de anomalias, indexação de séries temporais, dentre outras.
Conhecendo mais sobre o DTW
Distância Euclidiana: Para fazer o cálculo utilizando a distância Euclidiana é bastante simples, imagine dois pontos em um plano cartesiano, ponto z1 e o ponto z2, cada ponto tem as coordenadas (x1, y1) e (x2, y2), respectivamente, ou seja, z1 = (x1, y1) e z2 = (x2, y2). A formula Euclidiana é dada a seguir:
Vamos um exemplo bem simples: x1 = 4, y1 = 3 e x2 = 5 e y2 = 7, então o resultado seria:
Claro que pode haver mais valores do que duas coordenadas para cada ponto, então podemos generalizar a formula Euclidiana entre os pontos P=(p1,p2, ..., pn) e Q = (q1, q2, ..., qn)para:
Vantagem de usar DTW em vez da distância Euclidiana: Como pode ser percebido, a distância Euclidiana deve utilizar vetores do mesmo tamanho, ou seja, deve ter a mesma quantidade de p's e q's, enquanto a DTW não têm essa restrição.
Para facilitar imagine como fazer o cálculo entre vetores de tamanhos diferentes utilizando a distância Euclidiana, uma solução seria completar o vetor de menor tamanho com valores 0's até alcançar e igualar ao tamanho do maior vetor. É uma das abordagens que pode ser realizada, mas será que é a mais eficiente?
Vamos dar uma olhada na distância DTW a seguir.
Como calcular a distância DTW
Suponha que exista duas séries temporais, uma sequência W de tamanho n, e uma sequência Q de tamanho m, onde:
W = w1, w2, ..., wi, ... , wn
Q = q1, q2, ..., qi, ..., qm
Exemplo prático:
W = [1,2,3,4] e n =4
Q = [4,5,6] e m =3
Para computar a matriz de distância, é computada a distância ao quadrado de todos os valores de W com todos os valores de Q. Então a matriz de distância d recebe (wi - qj)², ou seja, d(wi, qj) = (wi - qj)²,onde i inicia em 1 e vai até n, e j inicia em 1 e vai até m.
Exemplo prático seria:
formula dij = (wi - qj)²
d11 = (1 - 4)² = 3² = 9
d12 = (1 - 5)² = 4² = 16
d13 = (1 - 6)² = 5² = 25
d21 = (2 - 4)² = (-2)² = 4
d22 = (2 - 5)² = (-3)² = 9
d23 = (2 - 6)² = (-4)² = 16
d31 = (3 - 4)² = (-1)² = 1
d32 = (3 - 5)² = (-2)² = 4
d33 = (3 - 6)² = (-3)² = 9
d41 = (4 - 4)² = (0)² = 0
d42 = (4 - 5)² = (-1)² = 1
d43 = (4 - 6)² = (-2)² = 4
|9 16 25|
dij = |4 9 16 |
|1 4 9 |
|0 1 4 |
Após criar a matriz d, devemos encontrar o mapeamento entre W e Q, para encontrar o caminho chamado de caminho deformado (caminho na matriz d que determinar o menor custo total ao somar os elementos (i,j)) utiliza-se programação dinâmica para avaliar a seguinte recorrência:
Caminho deformado Y(i,j) = d(qi, wi) + min {Y( i - 1, j - 1), Y(i - 1, j), Y(i, j - 1)}
A programação dinâmica é baseada em algoritmos que tomam a melhor decisão a cada passo, ou seja, a partir de um determinado elemento da matriz, para encontrar a melhor decisão (no caso, o melhor elemento), devemos procurar o elemento mínimo (que é o menor elemento considerando as três posições Y(i-1, j - 1), Y(i - 1, j) e Y(i, j - 1)). Talvez não tenha ficado muito lógico ou até mesmo claro, então para resolver isso, nada melhor que um exemplo prático para terminar de sanar as dúvidas.
Ex: Seja a matriz dij
|9 16 25|
dij = |4 9 16 |
|1 4 9 |
|0 1 4 |
Inicialmente o i = n e j = m ou seja i = 4 e j = 3 então d(qi, wj) + min {Y( i - 1, j - 1), Y(i - 1, j), Y(i, j - 1)} = 4 + min(4, 9, 1) = 4 + 1 = 5
O valor 5 que acabou de ser calculado é a soma acumulada do caminho deformado. Seguindo com a explicação do exemplo, na matriz o nosso d(qi, wi) está de azul, e o min {Y( i - 1, j - 1), Y(i - 1, j), Y(i, j - 1) está de vermelho
|9 16 25|
dij = |4 9 16 | caminho deformado: 4
|1 4 9 |
|0 1 4 |
e nossa soma acumulada é 5, pois somamos os d(qi, wi) + min {Y( i - 1, j - 1), Y(i - 1, j), Y(i, j - 1)}.
Continuando os passos, refazemos novamente o passo anterior, mudando o i e o j:
d(qi, wj) + min {Y( i - 1, j - 1), Y(i - 1, j), Y(i, j - 1)} = 1 + min(1, 4, 0) = 1 + 0 = 1
Seguindo com a explicação do exemplo, na matriz o nosso d(qi, wi) está de azul, e o min {Y( i - 1, j - 1), Y(i - 1, j), Y(i, j - 1) está de vermelho, com a diferença agora que foi colocado com a cor verde, a representação do caminho deformado
|9 16 25|
dij = |4 9 16 | caminho deformado: 4-1
|1 4 9 |
|0 1 4 |
fazemos isso repetidas vezes até que i = 1 e j = 1, então:
|9 16 25|
dij = |4 9 16 | caminho deformado: 4-1-0
|1 4 9 |
|0 1 4 |
|9 16 25|
dij = |4 9 16 | caminho deformado: 4-1-0-1
|1 4 9 |
|0 1 4 |
|9 16 25|
dij = |4 9 16 | caminho deformado: 4-1-0-1-4
|1 4 9 |
|0 1 4 |
|9 16 25|
dij = |4 9 16 | caminho deformado: 4-1-0-1-4-9
|1 4 9 |
|0 1 4 |
|9 16 25|
dij = |4 9 16 | caminho deformado: 4-1-0-1-4-9
|1 4 9 |
|0 1 4 |
Obs: Não foi feita a soma acumulada para ser simples e didático, mas com o exemplo dado é possível entender o processo para o cálculo parcial do DTW, ressaltando que o resultado final será o mesmo que se fizesse a matriz acumulada, a diferença é que o elemento i = 1 e j =1 teria o valor 19.
Após ter achado o caminho deformado é necessário somar os elementos:
4 + 1+ 0 + 1+ 4 + 9 =19
O valor 19 é nossa distância entre as séries temporais
W = w1, w2, ..., wi, ... , wn
Q = q1, q2, ..., qi, ..., qm
Conclusão
Este artigo apresenta somente uma visão geral sobre a distância DTW, sendo aconselhável um aprofundamento maior por parte do leitor que gostou do assunto, porém, agora vocês já tem uma noção sobre o tema, sua importância e aplicabilidade. Esperamos que isso possa te ajudar a resolver algum problema.
