基于分段降维和路径修正DTW的时序特征分类器设计

Time series classifier design based on piecewise dimensionality reduction and updated dynamic time warping

针对传统的动态时间弯曲(DTW)度量方法易出现过度弯曲现象且计算复杂度高、算法效率低等问题,提出一种基于路径修正的动态时间弯曲(UDTW)度量方法。首先通过分段降维方法——分段局部最大值平滑法(PLM)有效提取序列特征信息,减少UDTW的计算代价;其次,考虑了时间序列形态特征的相似性要求,给过度弯曲路径设置动态惩罚系数,以此修正路径的弯曲程度;最后,在改进度量距离基础上,采用1-近邻分类算法对时序数据进行分类,以提高时间序列相似性度量的准确率和效率。实验结果表明,在15个UCR数据集上,UDTW度量方法与传统DTW度量方法相比具有更高的分类准确率,UDTW在其中3个数据集上能实现100%分类正确;与导数DTW(DDTW)度量方法相比,UDTW分类准确率最多提高了71.8%,而PLM-UDTW在不影响分类准确率的前提下执行时间减小了99%。

Since traditional Dynamic Time Warping （DTW） measurement method is prone to over-bending and has the shortcoming of high computation complexity and low efficiency, an Updated Dynamic Time Warping （UDTW） measurement method based on path correction was proposed. Firstly, the characteristic information of time series was extracted by Piecewise Local Max-smoothing （PLM） method （a dimensionality reduction method）, so that the computational cost of UDTW was reduced. Secondly, considering the sequence similarity requirements of morphological characteristics, a dynamic penalty factor was set to correct the bending degree of the excessive bending path. Finally, based on updated distance metric, 1-nearest neighbor classification algorithm was used to classify time series data, which improved the accuracy and efficiency of the time series similarity measurement. The experimental results show that UDTW measurement method outperforms the traditional DTW measurement method among 15 UCR datasets, and the accuracy rate achieved 100% in 3 of them. In the comparison experiments with Derivative DTW （DDTW） measurement method, UDTW increases the classification accuracy by 71.8% at most, and the execution time of PLM-UDTW is reduced by 99% without decreasing classification accuracy.