摘要：

针对现有动态时间规整(DTW)算法普遍计算量大、时间复杂度高的问题，提出极值点自适应加权的动态时间规整算法(EWDTW)。局部极值的波动可反映序列变化趋势和整体形状特征，在提取局部极值点后按其原有位置分布近似表示原始时间序列，降低原始序列维数。在计算极值序列最佳动态弯曲路径的过程中，基于极值点的相位差、大小、类型等特征量为每个点设置自适应代价权重。利用权重参数调整距离矩阵的加权结构以适应不同特征的数据，并在降低计算复杂度的同时有效改善序列的病态对齐现象。实验结果表明，相比于DTW及其衍生算法，EWDTW算法在15个UCR数据集上的运算效率提升了10倍以上，尤其是在长时间序列和极值点占比低的序列上表现突出，并且对于大部分不同类型的时间序列具有良好度量性能，分类准确率更高。

关键词: 动态时间规整, 相似性度量, 局部极值, 自适应代价权重, 时间序列

Abstract:

To solve the problem of large computation and high time complexity of the Dynamic Time Warping(DTW) algorithm, a novel DTW algorithm with adaptive weighting of extreme points, called EWDTW, is proposed.The fluctuation of local extreme points reflects the trend of sequence change and the overall shape. After extracting the local extreme points, the original time series can be approximately represented based on their original position distribution, and the dimensions of the original sequence can be reduced.While calculating the best dynamic warping path of the extrema sequence, the adaptive cost weights for each point based on the phase difference, value, and type are set. The weight parameters can adjust the weighted structure of the distance matrix for application to datasets with different features, which improves the pathological alignment of the sequences and reduces the computational complexity.The experimental results show that, compared with DTW and its derived algorithms, the EWDTW algorithm improves performance efficiency on the 15 UCR datasets at least 10 fold, especially for long time series and series with a low extremum point proportion. Moreover, EWDTW algorithm has good measurement performance and higher classification accuracy for most types of time series.

Key words: Dynamic Time Warping(DTW), similarity measurement, local extrema, adaptive cost weight, time series