Abstract:

The Dynamic Time Warping （DTW） algorithm measures the similarity between two time series by finding the best match between two time series. Aiming at the problem of excessive stretching and compression during time series matching due to noise existing in the sequence， a Noise robust Dynamic Time Warping （NoiseDTW） algorithm was proposed. Firstly， after introducing extra noise into the original signal， and the problem of one point aligning multiple points in sequence alignment was solved. Secondly， by finding an optimal matching path between two time series with multiple possible matching paths， the influence of randomness of noise on the time series similarity measure was reduced. Finally， the matching paths were mapped to the original sequence. Experimental results show that compared to Euclidean Distance （ED）， DTW， Sakoe-Chiba window DTW （Sakoe-Chiba DTW） and Weighted DTW （WDTW） algorithms， combined with K-Nearest Neighbors （KNN）， the proposed algorithm has the classification accuracy improved by 1 to 15 percentage points compared to the suboptimal algorithm on eight time series datasets， respectively， indicating that the proposed algorithm has good classification performance and is robust to noise.

Key words: Dynamic Time Warping (DTW), time series, pathological alignment, similarity measure, K-Nearest Neighbors (KNN)

摘要：

动态时间规整（DTW）算法通过寻找两个时间序列的最佳匹配衡量序列之间的相似性。针对序列中存在的噪声容易导致时间序列匹配时局部出现过度拉伸和压缩问题，提出了一种噪声鲁棒的动态时间规整（NoiseDTW）算法。首先，在原始的信号中引入额外噪声，解决序列对齐中存在的一个点对齐多个点的问题；然后，通过在两个时间序列之间多条可能的匹配路径中找到一条最优的匹配路径，减少噪声的随机性对时间序列相似性度量的影响；最后，将匹配路径映射到原始序列上。实验结果表明，相较于欧氏距离（ED）、DTW、Sakoe-Chiba窗口动态时间规整（Sakoe-Chiba DTW）和加权动态时间规整（WDTW）算法，所提算法结合K-近邻（KNN）分类器得到的分类准确率在8个时间序列数据集上分别比次优算法提高了1~15个百分点。可见所提算法具有较好的分类性能，且对噪声具有鲁棒性。

关键词: 动态时间规整, 时间序列, 病态对齐, 相似性度量, K-近邻