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

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]	夏进, 王正群, 朱世明. 基于时间序列分解的交通流量预测模型[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1129-1135.
[2]	陈容均, 严宣辉, 杨超城. 面向时间序列的混合图像化循环胶囊分类网络[J]. 《计算机应用》唯一官方网站, 2023, 43(3): 692-699.
[3]	尹春勇, 周立文. 基于再编码的无监督时间序列异常检测模型[J]. 《计算机应用》唯一官方网站, 2023, 43(3): 804-811.
[4]	郎祎平, 毛文涛, 罗铁军, 范黎林, 任颖莹, 刘侠. 间歇性时间序列的可预测性评估及联合预测方法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2722-2731.
[5]	吴明晖, 张广洁, 金苍宏. 基于多模态信息融合的时间序列预测模型[J]. 《计算机应用》唯一官方网站, 2022, 42(8): 2326-2332.
[6]	玄英律, 万源, 陈嘉慧. 基于多尺度卷积和注意力机制的LSTM时间序列分类[J]. 《计算机应用》唯一官方网站, 2022, 42(8): 2343-2352.
[7]	张瑛琪, 彭大卫, 李森, 孙莹, 牛强. 基于单标签射频识别的唇语识别算法[J]. 《计算机应用》唯一官方网站, 2022, 42(6): 1762-1769.
[8]	胡鹤轩, 隋华超, 胡强, 张晔, 胡震云, 马能武. 基于图注意力网络与双阶注意力机制的径流预报模型[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1607-1615.
[9]	王艺霏, 于雷, 滕飞, 宋佳玉, 袁玥. 基于长-短时序特征融合的资源负载预测模型[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1508-1515.
[10]	李晓杰, 崔超然, 宋广乐, 苏雅茜, 吴天泽, 张春云. 基于时序超图卷积神经网络的股票趋势预测方法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 797-803.
[11]	陈育丹, 高翠芳, 沈莞蔷, 殷萍. 迭代直觉模糊K-modes算法[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 375-381.
[12]	解伟凡, 郭岩, 匡广生, 余智华, 薛源海, 沈华伟. 基于演化模式的推特话题流行度预测方法[J]. 《计算机应用》唯一官方网站, 2022, 42(11): 3364-3370.
[13]	李洋莹, 陈智军, 张子豪, 游兰. 基于改进Elman神经网络的制糖企业原糖需求预测模型[J]. 计算机应用, 2021, 41(7): 2113-2120.
[14]	李国荣, 冶继民, 甄远婷. 基于新的鲁棒相似性度量的时间序列聚类[J]. 计算机应用, 2021, 41(5): 1343-1347.
[15]	杨蒙蒙, 张爱华. 基于灰度共生矩阵和同步正交匹配追踪的分形图像压缩[J]. 计算机应用, 2021, 41(5): 1445-1449.

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

Noise robust dynamic time warping algorithm

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 21

相关文章 15

编辑推荐

Metrics