python - 不同库的不同结果和性能
问题描述
我正在比较库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
我的问题是:为什么我会得到不同的表现和不同的距离?非常感谢您的意见。
// 编辑:时间测量的单位是秒。
解决方案
在 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)来计算系列之间的所有成对距离。
推荐阅读
- ios - 如何评估表达式以在 Xcode 中进行调试
- python - 如何使用 python 在 xlsx 文件中查找特定关键字?
- autocomplete - 为 MudBlazor 自动完成提供来自服务的内容
- r - 将重叠间隔与 lubridate 相结合
- emacs - 如何配置 org 模式来评估 J 代码块?
- pop3 - 邮件服务器如何在没有明文用户密码的情况下实现 POP3/APOP?
- python-3.x - 如何创建一个返回给定纬度和经度栅格值的函数?
- python - 无法在导入的图像上绘制形状
- iis - 使用 IIS 和反向代理为 SSL 设置 SonarQube 会引发 502 错误
- r - 如何将 2 列的所有组合放入 R 中的 1 个数据框中?