基于LDTW的动态时间规整改进算法

doi:10.19678/j.issn.1000-3428.0059468

摘要/Abstract

摘要： 限制对齐路径长度的动态时间规整（LDTW）算法存在时间复杂度高和计算量大的问题。基于LDTW算法提出固定对齐路径长度的动态时间规整（FDTW）算法。通过调整LDTW算法中对齐路径长度的控制策略，由控制在某个区间改为固定到某个具体值，相应缩减累计代价矩阵中元素的计算范围。在UCR时间序列数据集上的实验结果表明，FDTW与LDTW算法的分类准确率持平，但FDTW算法在分类过程中的时间开销更小，并且能有效降低累计代价矩阵元素的计算量，提高计算效率。

关键词: 动态时间规整, 时间序列, 相似性度量, 对齐路径, 最近邻分类

Abstract: Dynamic Time Warping Under Limited Warping Path Length(LDTW) is an algorithm constructed based on the Dynamic Time Warping(DTW) algorithm,and solves the problem of matching points without similarity in DTW,but it tends to be computationally heavy due to the high time complexity.To address the problem,an algorithm called Dynamic Time Warping Under Fixed Warping Path Length(FDTW) is proposed.The strategy of controlling the alignment path length in the LDTW algorithm is adjusted,making the length fixed to a certain value rather than vary in an interval.Then the computing range of the elements in the cumulative cost matrix is narrowed accordingly.Experimental results on a time series data set,UCR,show that the classification accuracy of FDTW is equal to that of LDTW,but the time required by the classification process of FDTW is lower.FDTW can significantly reduce the calculations of elements in the cumulative cost matrix,and improve the computational efficiency.

Key words: Dynamic Time Warping(DTW), time series, similarity measurement, alignment path, nearest neighbor classification

中图分类号:

TP311

夏寒松, 张力生, 桑春艳. 基于LDTW的动态时间规整改进算法[J]. 计算机工程, 2021, 47(11): 108-120.

XIA Hansong, ZHANG Lisheng, SANG Chunyan. Improved Algorithm of Dynamic Time Warping Based on LDTW[J]. Computer Engineering, 2021, 47(11): 108-120.

https://www.ecice06.com/CN/Y2021/V47/I11/108

图/表 15

20211113143752

20211113143756

20211113143800

20211113143834

20211113143837

20211113143840

20211113143843

20211113143846

20211113143848

20211113143851

20211113143855

20211113143858

20211113143902

20211113143907

20211113143910

参考文献

[1] SEZER O B,GUDELEK M U,OZBAYOGLU A M.Financial time series forecasting with deep learning:a systematic literature review:2005-2019[J].Applied Soft Computing,2020,90:106181-106192.
[2] 张乔夫,何文明.基于指数平滑和WKNN的金融时间序列相似性搜索[J].现代计算机,2019(29):21-25. ZHANG Q F,HE W M.Financial time series similarity search based on exponential smoothing and WKNN[J].Modern Computer,2019(29):21-25.(in Chinese)
[3] 王敏,朱明.基于复杂网络理论的空中交通流时间序列分析[J].航空计算技术,2020,50(5):61-65. WANG M,ZHU M.Time series analysis of air traffic flow based on complex network theory[J].Aeronautical Computing Technique,2020,50(5):61-65.(in Chinese)
[4] 叶建鑫.基于社交网络用户影响力和时间序列的旅游服务推荐研究与应用[D].重庆:重庆大学,2019. YE J X.Research and application of tourism service recommendation based on social network user influence and time series[D].Chongqing:Chongqing University,2019.(in Chinese)
[5] 狄瑞彤,王红,房有丽.融合时间序列与多尺度特征的虚假评论识别方法[J].计算机工程,2019,45(3):278-285,292. DI R T,WANG H,FANG Y L.Fake reviews identification method fusing time series and multi-scale features[J].Computer Engineering,2019,45(3):278-285,292.(in Chinese)
[6] 许爱东,李锦涛,张宇南,等.基于动态时间规整的智能电网边缘用电数据去重技术[J].南方电网技术,2020,14(1):74-79. XU A D,LI J T,ZHANG Y N,et al.Edge power data de duplication technology of smart grid based on dynamic time warping[J].Southern Power System Technology,2020,14(1):74-79.(in Chinese)
[7] 李海林,梁叶,王少春.时间序列数据挖掘中的动态时间弯曲研究综述[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.(in Chinese)
[8] FU T C.A review on time series data mining[J].Engineering Applications of Artificial Intelligence,2011,24(1):164-181.
[9] BERNDT D J,CLIFFORD J.Using dynamic time warping to find patterns in time series[C]//Proceedings of the 31rd International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,1994,10(16):359-370.
[10] KEOGH E J,PAZZANI M J.Derivative dynamic time warping[C]//Proceedings of 2001 Society for Industrial & Applied Mathematics international conference on data mining.Philadelphia,USA:Society for Industrial & Applied Mathematics,2001:1-11.
[11] ZHANG Z,TAVENARD R,BAILLY A,et al.Dynamic time warping under limited warping path length[J].Information Sciences,2017,393:91-107.
[12] ANANTASECH P,RATANAMAHATANA C A.Enhanced weighted dynamic time warping for time series classification[C]//Proceedings of the 3rd International Congress on Information and Communication Technology.Berlin,Germany:Springer,2019:655-664.
[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.
[14] 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.
[15] ITAKURA F.Minimum prediction residual principle applied to speech recognition[J].IEEE Transactions on Acoustics,Speech,and Signal Processing,1975,23(1):67-72.
[16] RATANAMAHATANA C A,KEOGH E.Making time-series classification more accurate using learned constraints[C]//Proceedings of 2004 Society for Industrial & Applied Mathematics International Conference on Data Mining.Philadelphia,USA:Society for Industrial & Applied Mathematics,2004:11-22.
[17] MYERS C,RABINER L,ROSENBERG A.Performance tradeoffs in dynamic time warping algorithms for isolated word recognition[J].IEEE Transactions on Acoustics,Speech,and Signal Processing,1980,28(6):623-635.
[18] 常炳国,臧虹颖.基于分段降维和路径修正DTW的时序特征分类器设计[J].计算机应用,2018,38(7):1910-1915. CHANG B G,ZANG H Y,Time series classifier design based on piecewise dimensionality reduction and updated dynamic time warping[J].Journal of Computer Applications,2018,38(7):1910-915.
[19] HOANG A D,ANTHONY B,KAVEH K,et al.The UCR time series classification archive[J].IEEE/CAA Journal of Automatica Sinica,2019,6(6):1293-1305.
[20] BATISTA G E,WANG X,KEOGH E J.A complexity-invariant distance measure for time series[C]//Proceedings of 2011 Society for Industrial & Applied Mathematics International Conference on Data Mining.Philadelphia,USA:Society for Industrial & Applied Mathematics,2011:699-710.

选择文件类型/文献管理软件名称

选择包含的内容