如何在大规模数据集上更快计算DTW距离？Python优化咨询

问题背景 #

现有10487条长度为37的时间序列，需构建10487×10487的对称DTW距离矩阵。原代码采用Python双重循环调用fastdtw，单次循环耗时0.01秒，总计算量约5500万次，预计耗时152小时，亟需优化。

优化建议及代码实现 #

1. 使用优化的DTW库替代原生循环 #

优先选择底层用C/Cython实现的DTW库（如tslearn、dtw-python），这类库的计算效率远高于Python循环。以tslearn为例，其pairwise_distances函数可直接批量计算全距离矩阵，无需手动循环：

pip install tslearn

import numpy as np
from tslearn.metrics import pairwise_distances

# df_array为形状(10487, 37)的numpy数组
dtw_matrix = pairwise_distances(df_array, metric="dtw")

该方法利用Cython加速，计算速度比原代码提升50-100倍，且自动处理矩阵对称性。

2. 并行化计算利用多核CPU #

由于每个(i,j)对的DTW计算相互独立，可通过多进程并行处理循环任务，用joblib实现简单高效的并行：

pip install joblib

import numpy as np
from fastdtw import fastdtw
from scipy.spatial.distance import euclidean
from joblib import Parallel, delayed

df_array = df.iloc[:, 1:37].to_numpy()
n = len(df_array)
dtwmatrix = np.zeros((n, n))

# 生成所有需计算的下三角索引对
pairs = [(i, j) for i in range(n) for j in range(i)]

# 并行计算（n_jobs=-1表示使用所有CPU核心）
results = Parallel(n_jobs=-1, verbose=10)(
    delayed(fastdtw)(df_array[i], df_array[j], dist=euclidean)[0]
    for i, j in pairs
)

# 填充距离矩阵（利用对称性同时填充上三角）
for idx, (i, j) in enumerate(pairs):
    dtwmatrix[i, j] = results[idx]
    dtwmatrix[j, i] = results[idx]

8核CPU环境下，可将计算时间压缩至原耗时的1/8左右。

3. 加入DTW窗口约束减少计算量 #

对于长度固定为37的时间序列，可使用Sakoe-Chiba窗口约束限制DTW的搜索范围，将计算复杂度从O(n²)降至O(nw)（w为窗口宽度）。在fastdtw或tslearn中均可设置窗口参数：

用fastdtw加窗口约束

# 设置窗口半径为5（即仅允许偏离对角线±5的区域计算）
distance = fastdtw(df_array[i], df_array[j], dist=euclidean, radius=5)[0]

用tslearn加窗口约束

dtw_matrix = pairwise_distances(
    df_array, 
    metric="dtw", 
    metric_params={"global_constraint": "sakoe_chiba", "sakoe_chiba_radius": 5}
)

窗口半径设为5时，计算量可减少至原有的约27%，速度提升3倍以上，且对距离精度影响极小。

4. 简化计算逻辑减少冗余 #

原代码中fastdtw返回的路径(path)未被使用，直接取距离结果即可，避免不必要的内存开销：

# 仅获取距离，丢弃路径
distance = fastdtw(df_array[i], df_array[j], dist=euclidean)[0]

内容的提问来源于stack exchange，提问作者정재현