噪声鲁棒的动态时间规整算法

doi:10.11772/j.issn.1001-9081.2022060885

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (6): 1855-1860.DOI: 10.11772/j.issn.1001-9081.2022060885

所属专题：数据科学与技术

噪声鲁棒的动态时间规整算法

邱莲鹏, 宋承云()

重庆理工大学计算机科学与工程学院，重庆 400054

收稿日期:2022-06-20 修回日期:2022-08-04 接受日期:2022-08-11 发布日期:2022-10-11 出版日期:2023-06-10
通讯作者: 宋承云
作者简介:邱莲鹏（1995—），女，甘肃定西人，硕士研究生，主要研究方向：大数据、智能信号处理
宋承云（1988—），男，甘肃白银人，副教授，博士，主要研究方向：大数据、智能信号处理Email：scyer123@163.com。

Noise robust dynamic time warping algorithm

Lianpeng QIU, Chengyun SONG()

College of Computer Science and Engineering，Chongqing University of Technology，Chongqing 400054，China

Received:2022-06-20 Revised:2022-08-04 Accepted:2022-08-11 Online:2022-10-11 Published:2023-06-10
Contact: Chengyun SONG
About author:QIU Lianpeng， born in 1995， M. S. candidate. Her research interests include big data， intelligent signal processing.
Supported by:
Graduate Innovation Project of Chongqing University of Technology(gzlcx20223195)

摘要/Abstract

摘要：

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

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

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)

中图分类号:

TP391.4

邱莲鹏, 宋承云. 噪声鲁棒的动态时间规整算法[J]. 计算机应用, 2023, 43(6): 1855-1860.

Lianpeng QIU, Chengyun SONG. Noise robust dynamic time warping algorithm[J]. Journal of Computer Applications, 2023, 43(6): 1855-1860.

图/表 12

图1 病态路径示意图

Fig. 1 Schematic diagram of pathological path

图2 DTW距离矩阵

Fig. 2 Distance matrix of DTW

图3 NoiseDTW算法的原理示意图

Fig. 3 Schematic diagram of principle of NoiseDTW algorithm

图4 5种步进模式

Fig. 4 Five stepping patterns

表1 数据集信息

Tab. 1 Information of datasets

数据集	类别数	训练集数	测试集数	序列长度
BeetleFly	2	20	20	512
BirdChicken	2	20	20	512
DistalPhalanxTW	6	139	400	80
Fish	7	175	175	463
Gun-Point	2	50	150	150
Symbols	6	25	995	398
ToeSegmentation1	2	40	228	277
ToeSegmentation2	2	36	130	343

图5 不同α下的分类准确率

Fig. 5 Classification accuracy under different α

图6 不同e下的分类准确率

Fig. 6 Classification accuracy under different e

图7 四种方法对齐效果与真实匹配路径的对比

Fig. 7 Comparison of alignment results between four methods and ground truth

表2 8个时间序列数据集上的分类正确率

Tab. 2 Classification accuracy on 8 time series datasets

数据集	ED	DTW	Sakoe-Chiba窗口DTW	WDTW	NoiseDTW
BeetleFly	0.750	0.700	0.700	0.700	0.800
BirdChicken	0.550	0.750	0.700	0.750	0.900
DistalPhalanxTW	0.727	0.710	0.728	0.604	0.758
Fish	0.783	0.823	0.846	0.851	0.874
Gun-Point	0.913	0.907	0.913	0.980	0.980
Symbols	0.900	0.950	0.938	0.950	0.960
ToeSegmentation1	0.680	0.772	0.750	0.794	0.829
ToeSegmentation2	0.808	0.838	0.908	0.892	0.920

图8 分类错误率

Fig. 8 Classification error rate

图9 多个数据集上的时滞对比

Fig. 9 Time lag comparison on multiple datasets

表3 3种算法的时间开销对比 (s)

Tab. 3 Comparison of time overhead of three algorithms

数据集	DTW/s	WDTW/s	NoiseDTW/s
BeetleFly	5	58	43
BirdChicken	4	60	42
DistalPhalanxTW	14	159	184
Fish	194	3 394	2 144
Gun-Point	6	76	72
Symbols	102	1 980	1 016
ToeSegmentation1	17	326	225
ToeSegmentation2	12	266	162

参考文献 21

1	KANGINEJAD A， MANI-VARNOSFADERANI A. Chemometrics advances on the challenges of the gas chromatography-mass spectrometry metabolomics data： a review［J］. Journal of the Iranian Chemical Society， 2018， 15（12）： 2733-2745. 10.1007/s13738-018-1461-5
2	PETITJEAN F， INGLADA J， GANCARSKI P. Satellite image time series analysis under time warping［J］. IEEE Transactions on Geoscience and Remote Sensing， 2012， 50（8）： 3081-3095. 10.1109/tgrs.2011.2179050
3	PERMANASARI Y， HARAHAP E H， ALI E P. Speech recognition using Dynamic Time Warping （DTW）［J］. Journal of Physics： Conference Series， 2019， 1366： No.012091. 10.1088/1742-6596/1366/1/012091
4	ZHOU Y W， ZHENG J B， HU H C， et al. Handwritten signature verification method based on improved combined features［J］. Applied Sciences， 2021， 11（13）： No.5867. 10.3390/app11135867
5	王敏，朱明. 基于复杂网络理论的空中交通流时间序列分析［J］. 航空计算技术， 2020， 50（5）：61-65. 10.3969/j.issn.1671-654X.2020.05.015
	WANG M， ZHU M. Analysis of air traffic flow time series based on complex network theory［J］. Aeronautical Computing Technique， 2020， 50（5）：61-65. 10.3969/j.issn.1671-654X.2020.05.015
6	王子一，商琳. 基于子段距离计算的时间序列分类方法［J］. 小型微型计算机系统， 2018， 39（7）：1386-1389. 10.3969/j.issn.1000-1220.2018.07.003
	WANG Z Y， SHANG L. New method of time series classification based on sub-sequence distance computation［J］. Journal of Chinese Computer Systems， 2018， 39（7）：1386-1389. 10.3969/j.issn.1000-1220.2018.07.003
7	LI M， ZHU Y， ZHAO T G， et al. Weighted dynamic time warping for traffic flow clustering［J］. Neurocomputing， 2022， 472： 266-279. 10.1016/j.neucom.2020.12.138
8	LEE D， YU S， JU H， et al. Weakly supervised temporal anomaly segmentation with dynamic time warping ［C］// Proceedings of the 2021 IEEE/CVF International Conference on Computer Vision. Piscataway： IEEE， 2021： 7335-7344. 10.1109/iccv48922.2021.00726
9	李海林，梁叶，王少春. 时间序列数据挖掘中的动态时间弯曲研究综述［J］. 控制与决策， 2018， 33（8）： 1345-1353.
	LI H L， LIANG Y， WANG S C. Review on dynamic time warping in time series data mining ［J］. Control and Decision， 2018， 33（8）： 1345-1353.
10	KEOGH E， RATANAMAHATANA C A. Exact indexing of dynamic time warping ［J］. Knowledge and Information Systems， 2005， 7（3）： 358-386. 10.1007/s10115-004-0154-9
11	KEOGH E J， PAZZANI M J. Derivative dynamic time warping［C］// Proceedings of the 2001 SIAM International Conference on Data Mining. Philadelphia， PA： SIAM， 2001： 1-11. 10.1137/1.9781611972719.1
12	王见，毛黎明，尹爱军. 结合形状特征及其上下文的多维DTW［J］. 计算机工程与应用， 2020， 56（22）： 42-47.
	WANG J， MAO L M， YIN A J. Multi-dimensional DTW combined with shape feature and context information ［J］. Computer Engineering and Applications， 2020， 56（22）： 42-47.
13	JEONG Y S， JEONG M K， OMITAOMU O A. Weighted dynamic time warping for time series classification［J］. Pattern Recognition， 2011， 44（9）： 2231-2240. 10.1016/j.patcog.2010.09.022
14	BATISTA G E A P A， WANG X Y， KEOGH E J. A complexity-invariant distance measure for time series ［C］// Proceedings of the 2011 SIAM International Conference on Data Mining. Philadelphia， PA： SIAM， 2011： 699-710. 10.1137/1.9781611972818.60
15	SAKOE H， CHIBA S. Dynamic programming algorithm optimization for spoken word recognition［J］. IEEE Transactions on Acoustics， Speech， and Signal Processing， 1978， 26（1）： 43-49. 10.1109/tassp.1978.1163055
16	ITAKURA F. Minimum prediction residual principle applied to speech recognition ［J］. IEEE Transactions on Acoustics， Speech， and Signal Processing， 1975， 23（1）： 67-72. 10.1109/tassp.1975.1162641
17	MOREL M， ACHARD C， KULPA R， et al. Time-series averaging using constrained dynamic time warping with tolerance ［J］. Pattern Recognition， 2018， 74： 77-89. 10.1016/j.patcog.2017.08.015
18	VINCENT P， LAROCHELLE H， BENGIO Y， et al. Extracting and composing robust features with denoising autoencoders ［C］// Proceedings of the 25th International Conference on Machine Learning. New York： ACM， 2008： 1096-1103. 10.1145/1390156.1390294
19	GIORGINO T. Computing and visualizing dynamic time warping alignments in R： the dtw package［J］. Journal of Statistical Software， 2009， 31（7）： 1-24. 10.18637/jss.v031.i07
20	GELER Z， KURBALIJA V， RADOVANOVIĆ M， et al. Impact of the Sakoe-Chiba band on the DTW time series distance measure for kNN classification ［C］// Proceedings of the 2014 International Conference on Knowledge Science， Engineering and Management， LNCS 8793. Cham： Springer， 2014： 105-114.
21	DAU H A， KEOGH， E， KAMGAR K， et al. The UCR time series classification archive ［EB/OL］. （2018-10）［2022-06-20］.. 10.1109/jas.2019.1911747

[1]	任烈弘, 黄铝文, 田旭, 段飞. 基于DFT的频率敏感双分支Transformer多变量长时间序列预测方法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2739-2746.
[2]	赵秦壮, 谭红叶. 基于自适应阈值学习的时序因果推断方法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2660-2666.
[3]	范黎林, 曹富康, 王琬婷, 杨凯, 宋钊瑜. 基于需求模式自适应匹配的间歇性需求预测方法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2747-2755.
[4]	徐泽鑫, 杨磊, 李康顺. 较短的长序列时间序列预测模型[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1824-1831.
[5]	王美, 苏雪松, 刘佳, 殷若南, 黄珊. 时频域多尺度交叉注意力融合的时间序列分类方法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1842-1847.
[6]	袁子璇, 翁小清, 戈宁振. 基于正交局部保持映射和成本优化的多变量时间序列早期分类模型[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1832-1841.
[7]	孟凡, 杨群力, 霍静, 王新宽. 基于边缘异常候选集的迭代式主动多元时序异常检测算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1458-1463.
[8]	王华华, 张旭, 李峰. 面向高速移动环境的二级信号检测算法[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1236-1241.
[9]	任帅, 纪元法, 孙希延, 韦照川, 林子安. 基于改进灰狼优化与支持向量回归的滑坡位移预测[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 972-982.
[10]	范艺扬, 张洋, 曾尚, 曾渝, 付茂栗. 基于分解和频域特征提取的多变量长时间序列预测模型[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3442-3448.
[11]	赵培, 乔焰, 胡荣耀, 袁新宇, 李敏悦, 张本初. 基于多域特征提取的多变量时间序列异常检测[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3419-3426.
[12]	曾渝, 张洋, 曾尚, 付茂栗, 何启学, 曾林隆. 基于多尺度门控膨胀卷积网络的时间序列预测算法[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3427-3434.
[13]	蒋辉, 闫秋艳, 姜竹郡. 面向多元时间序列异常检测的对称正定自编码器方法[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3294-3299.
[14]	叶力硕, 何志学. 融合小波分解的多尺度时间序列异常检测[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3300-3306.
[15]	徐凯, 高琦凯, 殷明, 谭京京. 基于三维空间面积划分的轨迹相似性度量算法[J]. 《计算机应用》唯一官方网站, 2024, 44(1): 318-323.

噪声鲁棒的动态时间规整算法

Noise robust dynamic time warping algorithm

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 21

相关文章 15

编辑推荐

Metrics