Abstract: Dynamic Time Warping Under Limited Warping Path Length(LDTW) is an algorithm constructed based on the Dynamic Time Warping(DTW) algorithm,and solves the problem of matching points without similarity in DTW,but it tends to be computationally heavy due to the high time complexity.To address the problem,an algorithm called Dynamic Time Warping Under Fixed Warping Path Length(FDTW) is proposed.The strategy of controlling the alignment path length in the LDTW algorithm is adjusted,making the length fixed to a certain value rather than vary in an interval.Then the computing range of the elements in the cumulative cost matrix is narrowed accordingly.Experimental results on a time series data set,UCR,show that the classification accuracy of FDTW is equal to that of LDTW,but the time required by the classification process of FDTW is lower.FDTW can significantly reduce the calculations of elements in the cumulative cost matrix,and improve the computational efficiency.

Key words: Dynamic Time Warping(DTW), time series, similarity measurement, alignment path, nearest neighbor classification

摘要： 限制对齐路径长度的动态时间规整（LDTW）算法存在时间复杂度高和计算量大的问题。基于LDTW算法提出固定对齐路径长度的动态时间规整（FDTW）算法。通过调整LDTW算法中对齐路径长度的控制策略，由控制在某个区间改为固定到某个具体值，相应缩减累计代价矩阵中元素的计算范围。在UCR时间序列数据集上的实验结果表明，FDTW与LDTW算法的分类准确率持平，但FDTW算法在分类过程中的时间开销更小，并且能有效降低累计代价矩阵元素的计算量，提高计算效率。

关键词: 动态时间规整, 时间序列, 相似性度量, 对齐路径, 最近邻分类

CLC Number: 

• TP311