改进DTW下界函数的距离度量方法研究

Research on Distance Measurement Method of Improved DTW Lower Bound Function

动态时间弯曲算法(DTW)是一种常见的时间序列相似性度量方法,对数据挖掘任务起着至关重要的作用。针对现有DTW算法的时间复杂度高、度量精确度一般的特征,提出一种DTW下界函数的提前终止算法(LB_ESDTW)。引入提前终止思想,提高算法的执行效率;再在提前终止算法思想的基础上,与DTW下界函数相结合,提出一种基于提前终止DTW的下界函数算法(LB_ESDTW)。该算法在保证高效的运行时间效率的同时,也使得算法的度量准确率得到了提升。实验结果表明,LB_ESDTW在绝大部分时间序列数据集中,都表现出良好的适应性,针对不同类别的时间序列,都能有良好的度量性能。

As a common time series similarity measurement method,dynamic time warping algorithm(DTW)plays a crucial role in data mining.Aiming at the high time complexity and general measurement accuracy of existing DTW algorithms,an early termination algorithm(LB_ESDTW)for DTW lower bound function is proposed.First,stopping based on the idea of early stopping is proposed to measure the DTW distance and reduce the calculation cost of DTW algorithm.Then,based on the idea of early termination algorithm,this paper proposes an early termination algorithm based on the DTW lower bound distance function.The algorithm not only ensures the efficient running time efficiency,but also improves the measurement accuracy of the algorithm.The experimental results show that LB_ESDTW has good robustness in most time series data sets and has good measurement performance for different types of time series.