不同库的不同结果和性能

Question

我正在比较用于 DTW 计算的库dtaidistance、fastdtw和cdtw。这是我的代码：

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,y) 距离：17330.0

我的问题是：为什么我得到不同的表现和不同的距离？非常感谢您的评论。

// 编辑：时间测量的单位是秒。

Answer 1

在 Felipe Mello 的信息丰富的答案之上还有一些附加信息（免责声明：DTAIDistance 的作者）。

对于距离结果：

• DTAIDistance 仅使用欧几里德距离（或 L2 范数），这是硬编码的。做出此选择是为了加快 C 代码的执行速度（无函数调用）。“快速”是指使用基于 C 的实现而不是纯 Python 版本，因此两种方法都会给出完全相同的结果。
• FastDTW 是一种与 DTW 不同的算法。这是一个线性近似。“快”是指较低的复杂性。
• cDTW。我对这个工具箱不是很熟悉，但它似乎实现了 L1 规范。

对于速度结果：

一般来说，纯基于 C 的算法比纯 Python 算法快约 100 倍（在 DTAIDistance 中，这是 distance() 和 distance_fast() 之间的差异）。对于基于 C 的方法，差异主要是由于方法的灵活性。例如，传递自定义规范会减慢方法速度（更多函数调用）。此外，不同的方法有不同的选项，这会导致算法中或多或少的 switch 语句。例如，DTAIDistance 提供了相当多的选项来调整方法，因为它更喜欢提前停止计算而不是进一步优化（Felipe Mello 也观察到）。此外，不同的方法存储不同数量的数据。DTAIDistance 距离方法不存储整个矩阵，也提供线性空间复杂度（完整矩阵是使用具有二次空间复杂度的 warping_paths 方法获得的）。一般来说，对于 DTW，建议使用窗口来稍微降低时间复杂度。

对于 DTAIDistance，所有设计选择都是考虑到时间序列聚类应用程序（distance_matrix_fast 方法）。这是不允许自定义规范的另一个原因。DTW 代码需要是纯 C 代码，以支持 C 代码级别的并行化，并以最小的开销（它使用 OpenMP）来计算系列之间的所有成对距离。