FastDTW与dtaidistance的DTW计算结果差异原因及选型咨询

问题背景 #

我刚开始学习DTW（动态时间规整），尝试了fastdtw和dtaidistance两个Python包。在多分类时间序列分类任务中（类别为0、1、3、4，1、3、4类样本基于0类生成），样本生成代码如下：

import numpy as np
from fastdtw import fastdtw
from dtaidistance import dtw

np.random.seed(42)
# Original Class 0 samples (10 samples with 48 half-hourly measurements each)
class_0_samples = np.random.rand(10, 48)
# Generate Class 1 samples (multiply each sample by a random value between [0, 0.8])
class_1_samples = class_0_samples * np.random.uniform(0, 0.8, size=(10, 1))
# Generate Class 3 samples (multiply each half-hourly measurement by a different random value between [0, 0.8])
class_3_samples = class_0_samples * np.random.uniform(0, 0.8, size=(10, 48))
# Generate Class 4 samples (multiply specific columns by a random value between [0, 0.8])
class_4_samples = class_0_samples.copy()
start_cols = np.random.randint(7, 15, size=(10,))
for i in range(10):
    start_col = start_cols[i]
    class_4_samples[i, start_col:start_col+4] = class_4_samples[i, start_col:start_col+4]*np.random.uniform(0, 0.8)

分别用fastdtw和dtaidistance计算0类样本到1、3、4类对应样本的DTW距离，发现部分结果一致，部分存在差异甚至显著差异。

fastdtw计算代码 #

# 注意：需补充导入euclidean函数：from scipy.spatial.distance import euclidean
# Calculate DTW distances between Class 0 samples and original Class 0 samples
fastdtw_distances_class_0 = []
fastdtw_distances_class_1 = []
fastdtw_distances_class_3 = []
fastdtw_distances_class_4 = []
for i in range(10):
    distance0, _ = fastdtw(class_0_samples[i].reshape(1, -1), class_0_samples[i].reshape(1, -1), dist=euclidean)
    fastdtw_distances_class_0.append(distance0)
    distance1, _ = fastdtw(class_0_samples[i].reshape(1, -1), class_1_samples[i].reshape(1, -1), dist=euclidean)
    fastdtw_distances_class_1.append(distance1)
    distance3, _ = fastdtw(class_0_samples[i].reshape(1, -1), class_3_samples[i].reshape(1, -1), dist=euclidean)
    fastdtw_distances_class_3.append(distance3)
    distance4, _ = fastdtw(class_0_samples[i].reshape(1, -1), class_4_samples[i].reshape(1, -1), dist=euclidean)
    fastdtw_distances_class_4.append(distance4)

# Convert distances to a numpy array
fastdtw_distances_class_0 = np.array(fastdtw_distances_class_0).reshape(-1, 1)
fastdtw_distances_class_1 = np.array(fastdtw_distances_class_1).reshape(-1, 1)
fastdtw_distances_class_3 = np.array(fastdtw_distances_class_3).reshape(-1, 1)
fastdtw_distances_class_4 = np.array(fastdtw_distances_class_4).reshape(-1, 1)

dtaidistance计算代码 #

# Calculate DTW distances between Class 0 samples and original Class 0 samples
dtaidtw_distances_class_0 = []
dtaidtw_distances_class_1 = []
dtaidtw_distances_class_3 = []
dtaidtw_distances_class_4 = []
for i in range(10):
    distance0 = dtw.distance_fast(class_0_samples[i], class_0_samples[i])
    dtaidtw_distances_class_0.append(distance0)
    distance1 = dtw.distance_fast(class_0_samples[i], class_1_samples[i])
    dtaidtw_distances_class_1.append(distance1)
    distance3 = dtw.distance_fast(class_0_samples[i], class_3_samples[i])
    dtaidtw_distances_class_3.append(distance3)
    distance4 = dtw.distance_fast(class_0_samples[i], class_4_samples[i])
    dtaidtw_distances_class_4.append(distance4)

# Convert distances to a numpy array
dtaidtw_distances_class_0 = np.array(dtaidtw_distances_class_0).reshape(-1, 1)
dtaidtw_distances_class_1 = np.array(dtaidtw_distances_class_1).reshape(-1, 1)
dtaidtw_distances_class_3 = np.array(dtaidtw_distances_class_3).reshape(-1, 1)
dtaidtw_distances_class_4 = np.array(dtaidtw_distances_class_4).reshape(-1, 1)

差异原因与代码问题 #

1. 代码本身的小问题 #

• fastdtw代码中未导入euclidean函数，需补充from scipy.spatial.distance import euclidean才能正常运行。
• fastdtw中对样本做reshape(1, -1)是多余的，直接传入一维数组class_0_samples[i]即可，不影响结果但没必要。

2. 核心差异：DTW的距离定义与算法类型不同 #

（1）距离度量的定义差异

• fastdtw使用指定的euclidean函数时，计算的是路径上所有对应点的欧氏距离之和（逐点计算sqrt((x-y)^2)后求和）。
• dtaidistance的dtw.distance_fast默认计算的是路径上所有对应点的平方欧氏距离之和（逐点计算(x-y)^2后求和），且默认不开根号。这是导致结果数值差异最直接的原因。

（2）算法的精确性差异

• fastdtw是近似DTW算法：通过对时间序列降采样、递归计算来加速，得到的是近似距离，序列越长，近似误差越明显；短序列下近似度高，结果可能和精确DTW接近。
• dtaidistance的dtw.distance_fast是精确DTW算法：基于动态规划的C优化实现，计算的是完全精确的DTW距离，无近似误差。

两个包的DTW实现核心区别 #

如何选择合适的包 #

1. 优先选dtaidistance的场景：

   • 需要精确DTW距离结果，且时间序列长度适中（比如长度在1000以内）。
   • 对计算速度有要求，同时需要精度保证，其C优化的精确DTW速度足够快。
   • 可通过参数调整匹配不同距离定义：比如要欧氏距离求和，可自定义距离函数配合dtw.distance使用；要平方和开根号的结果，可调用dtw.distance(..., sqrt=True)。

2. 优先选fastdtw的场景：

   • 处理超长时间序列（比如长度上万），此时精确DTW计算量过大，fastdtw的近似计算能大幅减少耗时，且误差在可接受范围内。
   • 对精度要求不高，只需要相对距离用于分类、聚类等任务。

3. 结果对齐的方法：

   • 若要让两个包结果一致，需统一距离定义：
     • 方法1：让fastdtw使用平方欧氏距离，将dist=euclidean改为dist=lambda x,y: (x-y)**2，此时结果会和dtaidistance的distance_fast一致。
     • 方法2：让dtaidistance计算欧氏距离求和，使用dtw.distance并传入自定义距离函数：dtw.distance(class_0_samples[i], class_1_samples[i], dist=lambda x,y: np.abs(x-y))。

内容的提问来源于stack exchange，提问作者Murilo