不同的库会导致不同的结果和性能表现。

Question

不同的库会导致不同的结果和性能表现。

7

我正在比较库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,y) 距离：17330.0

我的问题是：为什么我会得到不同的性能和不同的距离？非常感谢您的意见。

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

- Hagbard

2个回答

4

编辑：时间测量的单位是什么？我认为您将它们比较了，因为它们都是以同一单位表示的。可能dtw.distance是以微秒为单位的，而其他答案则是以毫秒为单位的，您认为dtw.distance执行速度较慢，而实际上正好相反。

有不同的方法来衡量两点之间的距离。可以基于标准差或欧几里得距离。这里是许多距离的列表。

其中一些可能比其他距离更耗费计算资源，并且具有不同的意义。例如，Fast dtw使用作为第三个输入的距离类型，如其GitHub描述。

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

速度差异的另一个原因是底层代码。其中一些是纯Python编写的，而另一些是C语言编写的，速度可以轻松提高100倍。加快dtaidistance速度的方法是设置最大距离阈值。如果算法意识到总距离将超过某个值，则计算将停止：

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的速度比dtaidistance库慢219倍，比cdtw慢20倍。

- Felipe Mello

首先：很抱歉回复晚了，非常感谢您的答复。在fastdtw调用中添加参数“dist = euclidean”并没有改变距离值。我是否还缺少其他附加参数？ - Hagbard

@Hagbard，可能欧几里得距离是标准使用的距离，因为它是最简单和最快的之一，这就是为什么你不会注意到任何差异的原因。 - Felipe Mello

@Hagbard，我在想，我认为你在计时时犯了一个错误。时间单位是什么？我100%确定dtw.distance不需要22秒。我刚刚在这里创建了两个随机向量，每个向量有3000个点，只用了50毫秒。可能它显示的是22，但是使用的是不同的时间单位，例如微秒而不是毫秒，所以你认为它比其他操作花费更长的时间。 - Felipe Mello

这个答案可能有些出人意料，但时间测量单位确实是秒。为了再次验证这一点，我使用 s1 = np.random.rand(3000)和s2 = np.random.rand(3000)创建的两个序列运行了上面的代码，并获得了类似的结果。我在这里做错了什么吗？关于距离度量：为了使所有函数调用的度量（例如欧几里得距离）获得相同的结果，我应该使用哪些参数？ - Hagbard

@Hagbard，我不确定你如何在它们每个人中都有相同的“距离度量”。如果你在他们的文档或其他地方找到了，请也告诉我。现在，关于你花费的22秒，你能做最后一个测试吗？你能否请指定numpy数组的类型为np.double？只需执行以下操作： s1 = np.array(s1, dtype=np.double); s2 = np.array(s2, dtype=np.double)并在控制台上运行：％timeit dtw.distance_fast（s1，s2） - Felipe Mello

2

非常感谢您在这个问题上一直与我保持联系。不幸的是，将输入序列转换为双精度数组只会产生（大致）相同的输出。 :-( - Hagbard

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- wannesm · Accepted Answer

Felipe Mello的信息性答案之外，这里还有一些额外的信息：

对于距离结果： - DTAIDistance仅使用欧几里得距离（或L2范数），这是硬编码的。为了加快C代码的执行速度，做出了这个选择（不需要函数调用）。'fast'指的是使用基于C语言的实现而不是纯Python版本，因此两种方法给出的结果完全相同。 - FastDTW是不同于DTW的算法。它是线性逼近。'fast'指的是较低的复杂度。 - cDTW。我不太熟悉这个工具箱，但看起来它似乎实现了L1范数。

对于速度结果： - 一般来说，纯C语言的算法比纯Python语言的算法快大约100倍（在DTAIDistance中，distance()和distance_fast()之间的差异就是这样）。对于基于C的方法，不同之处主要是由于方法的灵活性。例如，传递自定义范数将会降低方法的速度（需要更多的函数调用）。此外，不同的方法具有不同的选项，在算法中会引入更多或更少的开关语句。例如，DTAIDistance提供了相当多的选项来调整方法，因为它更喜欢停止计算而不是进一步优化（Felipe Mello也观察到了这一点）。此外，不同的方法存储不同数量的数据。DTAIDistance距离方法不需要存储整个矩阵，以提供线性空间复杂度（完整矩阵可通过具有二次空间复杂度的warping_paths方法获得）。一般来说，对于DTW，建议使用窗口来稍微降低时间复杂度。 - 对于DTAIDistance，所有设计选择都是针对时间序列聚类应用程序而做出的（distance_matrix_fast()方法）。这是不允许自定义范数的另一个原因。 - DTW代码需要是纯C的，以支持在C代码层面上的并行化，并且具有最小的开销（它使用OpenMP）来计算序列之间的所有成对距离。