Сравнение двух графиков котировок с нелинейными искажениями по оси X - страница 6

Новый комментарий
 

Как решается данная задача через DTW (пример):

  1. Нам надо найти похожие ситуации на истории, как крайние 100 баров.
  2. Доступная история 1 000 000 баров.
  3. Сначала взяли 1 000 000 последовательностей по 50 баров и через DTW сравнили с шаблоном.
  4. Взяли еще 1 000 000 последовательностей уже по 55 баров и через DTW сравнили с шаблоном.
  5. Теперь уже по 60 баров.
  6. .....
  7. По 100 баров.
  8. .....
  9. По 300 баров. И на этом можно остановиться.

Итого выполнили 50 000 000 сравнений по DTW алгоритму, который имеет сложность O(N^2). Т.е. очень грубо совершили 5 * 10^11 (500 миллиардов) элементарных вычислительных операций.

Теперь пришел новый бар - сделали еще раз 500 млрд вычислений.

Решили прогнать на истории, начиная с 200 000 крайнего элемента. Грубо, для прогона нужно совершить 200 000 раз по 500 млрд каждый вычислений. Итого 10^17 вычислений.

Даже если будет хитрая оптимизация, то она не даст выигрыша больше, чем на два порядка. Т.е. в лучшем случае надо будет совершить каких-то 10^15 вычислений.

 
hrenfx:

Как решается данная задача через DTW (пример):

Понимаете ли, на данный момент нас больше интересует сам DTW, а не то, как его применять.
 
hrenfx:Как решается данная задача через DTW (пример):

если не сложно то покажите в коде решение этой задачи, тут уже не сколько практический, а скорее спортивный интерес

 

Никто в здравом уме не возьмется за реализацию алгоритма, результат работы которого будет просто не дождаться.

Тот же КК Пирсона также не подходил бы, как и DTW, т.к. его вычислительная сложность тоже O(N^2). Но есть значительная алгоритмическая оптимизация вычислений КК Пирсона со сложностью O(N * log(N)), которая может позволить решить данную задачу за приемлемое время. Реализацию этого алгоритма выложил в Codebase. Для решения поднятой задачи осталось этот же алгоритм применить к множеству преобразованных ЗигЗагом цВР.

 
hrenfx:

Никто в здравом уме не возьмется за реализацию алгоритма, результат работы которого будет просто не дождаться.

Тот же КК Пирсона также не подходил бы, как и DTW, т.к. его вычислительная сложность тоже O(N^2). Но есть значительная алгоритмическая оптимизация вычислений КК Пирсона со сложностью O(N * log(N)), которая может позволить решить данную задачу за приемлемое время. Реализацию этого алгоритма выложил в Codebase. Для решения поднятой задачи осталось этот же алгоритм применить к множеству преобразованных ЗигЗагом цВР.


Вы бы почитали для начала задачу которая стоит перед автором темы и его ответы.
 
Integer:


Пробовал его. Тоже не понятно как им пользоваться. На выходе должен быть или путь трансформации или трансформированные данные.

На выходе алгоритма мы получили "матрицу накопленных расстояний" - "accumulated cost matrix" (а не просто локальную матрицу расстояний, которая на рисунке), при этом метод вернул нам значение правой нижней ячейки (по построению оно максимальное во всей матрице). Чтобы теперь найти путь, надо просто двигаться от ячейки (n,m) в сторону ячейки (1,1), выбирая каждый раз вариант с наименьшим значением:

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
 
в результате в массиве path содержится оптимальный путь для трансформации одного сигнала в другой. Можно делать причем в любую сторону.
 
Степень похожести сигналов определяется по значению правой нижней ячейки матрицы, чем оно больше, тем сильнее отличаются друг от друга сигналы.
 
alsu:Степень похожести сигналов определяется по значению правой нижней ячейки матрицы, чем оно больше, тем сильнее отличаются друг от друга сигналы.
ОК, спасибо, довольно доходчиво разъяснили, еще вопросик: нормализовать или приводить к одному порядку данные есть необходимость, на результат влияет?
 
IgorM:
ОК, спасибо, довольно доходчиво разъяснили, еще вопросик: нормализовать или приводить к одному порядку данные есть необходимость, на результат влияет?
dtw[n][m] зависит от масштаба, поэтому если попарных сравнений много, то надо отмасштабировать и еще центрировать желательно.
123456789101112
Новый комментарий
Причина обращения: