Разные результаты и выступления с разными библиотеками

Question

Я сравниваю библиотеки dtaidistance , fastdtw и cdtw для вычислений DTW.Это мой код:

from fastdtw import fastdtw
from cdtw import pydtw
import fastdtw
import array
from timeit import default_timer as timer
from dtaidistance import dtw, dtw_visualisation as dtwvis

s1 = mySampleSequences[0] # first sample sequence consisting of 3000 samples
s2 = mySampleSequences[1] # second sample sequence consisting of 3000 samples

start = timer()
distance1 = dtw.distance(s1, s2)
end = timer()
start2 = timer()
distance2 = dtw.distance_fast(array.array('d',s1),array.array('d',s2))
end2 = timer()
start3 = timer()
distance3, path3 = fastdtw(s1,s2)
end3 = timer()
start4 = timer()
distance4 = pydtw.dtw(s1,s2).get_dist()
end4 = timer()

print("dtw.distance(x,y) time: "+ str(end - start))
print("dtw.distance(x,y) distance: "+str(distance1))
print("dtw.distance_fast(x,y) time: "+ str(end2 - start2))
print("dtw.distance_fast(x,y) distance: " + str(distance2))
print("fastdtw(x,y) time: "+ str(end3 - start3))
print("fastdtw(x,y) distance: " + str(distance3))
print("pydtw.dtw(x,y) time: "+ str(end4 - start4))
print("pydtw.dtw(x,y) distance: " + str(distance4))

Это вывод, который я получаю:

• dtw.distance (x, y) время: 22.16925272245262
• dtw.distance(x, y) расстояние: 1888.8583853746156
• dtw.distance_fast (x, y) время: 0.3889036471839056
• dtw.distance_fast (x, y) расстояние: 1888.8583853746156
• fastdtw (x, y) время: 0,23296659641047412
• fastdtw (x, y) расстояние: 27238,0
• pydtw.dtw (x, y) время: 0,13706478039556558
• pydtw.dtw (x, у) расстояние: 17330,0

Мой вопрос: почему я получаю разные выступления и разные расстояния?Большое спасибо за ваши комментарии.

// edit: единица измерения времени - секунды.

Answer 1

Некоторая дополнительная информация поверх информационного ответа Фелипе Мелло (отказ от ответственности: автор DTAIDistance здесь).

Для результатов дистанции:

• DTAIDistance использует только евклидово расстояние (или L2норма), это жестко закодировано.Этот выбор был сделан для ускорения выполнения C-кода (без вызовов функций).«Быстрый» относится к использованию реализации на основе языка Си вместо чистой версии Python, и оба метода, таким образом, дают одинаковые результаты.
• FastDTW - это алгоритм, отличный от DTW.Это линейное приближение.«Быстрый» означает меньшую сложность.
• cDTW.Я не очень знаком с этим набором инструментов, но, похоже, он реализует норму L1.

Для получения скоростных результатов:

В целом, алгоритмы на чистом C работают примерно в 100 раз быстреечем чисто Python (в DTAIDistance это разница между distance () и distance_fast ()).Для методов на основе C различия главным образом обусловлены гибкостью методов.Например, передача пользовательской нормы замедлит метод (больше вызовов функций).Кроме того, разные методы имеют разные опции, которые вызывают более или менее операторы переключения в алгоритме.Например, DTAIDistance предлагает целый ряд опций для настройки метода, потому что он предпочитает раннюю остановку вычислений по сравнению с дальнейшей оптимизацией (также наблюдал Фелипе Мелло).Кроме того, разные методы хранят разные объемы данных.Метод расстояния DTAIDistance не сохраняет всю матрицу, чтобы также предложить линейную пространственную сложность (полная матрица получается с использованием метода warping_paths, который имеет квадратичную пространственную сложность).В общем случае для DTW рекомендуется использовать окно, чтобы немного уменьшить временную сложность.

Для DTAIDistance все варианты проектирования были сделаны с учетом приложений кластеризации временных рядов (метод distance_matrix_fast).Это еще одна причина, чтобы не допустить пользовательских норм.Код DTW должен быть чистым C для поддержки распараллеливания на уровне C-кода и иметь минимальные издержки (он использует OpenMP) для вычисления всех парных расстояний между рядами.

Answer 2

Редактировать: Какие единицы измерения времени?Я считаю, что вы сравнили их, поскольку они все были в одном блоке.Возможно, dtw.distance, например, в микросекундах, а остальные ответы - в миллисекундах, и вы подумали, что dtw.distance работает медленнее, когда на самом деле все наоборот.

Существуют разныеметодики измерения расстояния между двумя точками.Это может быть основано на стандартном отклонении или просто евклидовом расстоянии.Вот список многих из этих расстояний.

Некоторые из них могут быть более вычислительными, чем другие, и также имеют разные значения.Fast dtw, например, использует в качестве третьего входа желаемый тип расстояния, как описано на их github

distance3, path3 = fastdtw(s1, s2, dist = euclidean)

Другая причина разницы в скорости - это основной код.Некоторые из них в чистом Python, а другие в C, что может быть легко в 100 раз быстрее.Способ ускорить ваше расстояние - установить максимальный порог расстояния.Алгоритм остановит вычисление, если поймет, что общее расстояние будет выше определенного значения:

distance2 = dtw.distance_fast(array.array('d',s1),array.array('d',s2), max_dist = your_threshold)

Также важно отметить, что некоторые из них могут быть оптимизированы для более длинных или более коротких массивов.Глядя на приведенный ниже пример и запустив его на своем компьютере, я нахожу разные результаты:

from cdtw import pydtw
from dtaidistance import dtw
from fastdtw import fastdtw
from scipy.spatial.distance import euclidean
s1=np.array([1,2,3,4],dtype=np.double)
s2=np.array([4,3,2,1],dtype=np.double)

%timeit dtw.distance_fast(s1, s2)
4.1 µs ± 28.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
%timeit d2 = pydtw.dtw(s1,s2,pydtw.Settings(step = 'p0sym', window = 'palival', param = 2.0, norm = False, compute_path = True)).get_dist()
45.6 µs ± 3.39 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
%timeit d3,_=fastdtw(s1, s2, dist=euclidean)
901 µs ± 9.95 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

fastdtw в 219 раз медленнее, чем dtaidistance lib, и в 20 раз медленнее, чем cdtw