Comparação de dois gráficos de cotações com distorções não lineares no eixo X - página 6

Novo comentário
 

Como este problema é resolvido via DTW (exemplo):

  1. Precisamos encontrar situações similares na história como as 100 barras extremas.
  2. O histórico disponível é de 1.000.000 de barras.
  3. Primeiro, pegamos 1.000.000 de seqüências de 50 barras e as comparamos com o padrão através da DTW.
  4. Depois pegamos mais 1.000.000 de seqüências de 55 barras e as comparamos através da DTW com o modelo.
  5. Desta vez, são 60 barras.
  6. .....
  7. A 100 bares.
  8. .....
  9. 300 barras. E é aqui que podemos parar.

No total, fizemos 50.000.000 comparações usando o algoritmo DTW que tem complexidade de O(N^2). Foram realizadas cerca de 5 * 10 ^11 (500 bilhões) operações computacionais elementares.

Agora chegou uma nova barra - fizemos novamente 500 bilhões de cálculos.

Decidimos fazer um histórico, a partir de 200.000 últimos elementos. Grosso modo, são necessários 200.000 vezes 500 bilhões de cálculos cada um para fazer uma corrida. São 10 ^17 cálculos no total.

Mesmo que haja uma otimização complicada, ela não produzirá um ganho de mais de duas ordens de magnitude. Isto é, terá que realizar no máximo 10 ^15 cálculos.

 
hrenfx:

Como esta tarefa é resolvida via DTW (exemplo):

Vê, neste ponto estamos mais interessados na DTW em si do que em como aplicá-la.
 
hrenfx: Como esta tarefa é resolvida com DTW (exemplo):

Se você não se importa, por favor mostre a solução deste problema no código, não é tanto de interesse prático, mas sim de interesse esportivo.

 

Ninguém em seu perfeito juízo se comprometeria a implementar um algoritmo, cujo resultado simplesmente não esperaria.

O mesmo CQ Pearson também seria inadequado, assim como o DTW, uma vez que sua complexidade computacional também é O(N^2). Mas há uma otimização algorítmica significativa do cálculo de CQ Pearson com complexidade O(N * log(N)) que poderia permitir resolver este problema em um tempo razoável. A implementação deste algoritmo foi afixada no Codebase. Para resolver o problema levantado, resta aplicar o mesmo algoritmo ao conjunto de ZVRs transformadas em ZigZag.

 
hrenfx:

Ninguém em seu perfeito juízo se comprometeria a implementar um algoritmo, cujo resultado simplesmente não esperaria.

O mesmo CQ Pearson também seria inadequado, assim como o DTW, uma vez que sua complexidade computacional também é O(N^2). Mas há uma otimização algorítmica significativa do cálculo de CQ Pearson com complexidade O(N * log(N)) que poderia permitir resolver este problema em um tempo razoável. A implementação deste algoritmo foi afixada no Codebase. Para resolver o problema levantado, resta aplicar o mesmo algoritmo ao conjunto de ZVRs transformadas em ZigZag.


Você deve primeiro ler o problema que o autor está enfrentando e suas respostas.
 
Integer:


Eu tentei. Eu também não entendo como usá-lo. A saída deve ser ou um caminho de transformação ou dados transformados.

A saída do algoritmo é uma "matriz de custos acumulados" (em vez de apenas a matriz de distância local mostrada na figura), com o método retornando o valor da célula inferior direita (por construção, é o máximo em toda a matriz). Para encontrar o caminho agora, basta passar da célula (n,m) para a célula (1,1), escolhendo cada vez a opção com o valor mais baixo:

1: path[] <- new array
2: i =rows(dtw)
3: j =columns(dtw)
4: while(i>1) & (j>1)do
5:    if (i == 1) then
6:       j = j-1
7:    else if (j == 1) then
8:       i = i-1
9:    else
10:     if dtw(i-1;j) == min{dtw(i-1;j); dtw(i;j-1); dtw(i-1; j-1)} then 
11:        i = i-1
12:     else if dtw(i;j-1) == min{dtw(i-1;j); dtw(i;j-1); dtw(i-1;j-1)} then
13:        j = j-1
14:     else
15:     i = i-1; j = j-1
16:     end if
17:   path:add(i;j)
18:   end if
19: end while
20: return path
 
A matriz de caminhos resultante contém o caminho ideal para transformar um sinal em outro. Isto pode ser feito em qualquer direção.
 
O grau de similaridade dos sinais é determinado pelo valor da célula inferior direita da matriz, quanto maior ela for, mais diferentes serão os sinais.
 
alsu: O grau de similaridade dos sinais é determinado pelo valor da célula inferior direita da matriz, quanto maior ela for, mais diferentes serão os sinais.
OK, obrigado, você explicou muito claramente, mais uma pergunta: é necessário normalizar ou reduzir os dados para a mesma ordem, isso afeta o resultado?
 
IgorM:
OK, obrigado, isso ficou bem claro, mais uma pergunta: há necessidade de normalizar ou reordenar os dados, será que isso afeta o resultado?
dtw[n][m] depende da escala, portanto, se houver muitas comparações em pares, devemos escalá-la para cima e centralizá-la de preferência.
123456789101112
Novo comentário