Research on Distance Measurement Method of Improved DTW Lower Bound Function

doi:10.3778/j.issn.1002-8331.2106-0036

Abstract

Abstract: As a common time series similarity measurement method, dynamic time warping algorithm（DTW） plays a crucial role in data mining. Aiming at the high time complexity and general measurement accuracy of existing DTW algorithms, an early termination algorithm（LB_ESDTW） for DTW lower bound function is proposed. First, stopping based on the idea of early stopping is proposed to measure the DTW distance and reduce the calculation cost of DTW algorithm. Then, based on the idea of early termination algorithm, this paper proposes an early termination algorithm based on the DTW lower bound distance function. The algorithm not only ensures the efficient running time efficiency, but also improves the measurement accuracy of the algorithm. The experimental results show that LB_ESDTW has good robustness in most time series data sets and has good measurement performance for different types of time series.

Key words: time series, dynamic time warping, early termination, lower bound distance, similarity measure

摘要： 动态时间弯曲算法（DTW）是一种常见的时间序列相似性度量方法，对数据挖掘任务起着至关重要的作用。针对现有DTW算法的时间复杂度高、度量精确度一般的特征，提出一种DTW下界函数的提前终止算法（LB_ESDTW）。引入提前终止思想，提高算法的执行效率；再在提前终止算法思想的基础上，与DTW下界函数相结合，提出一种基于提前终止DTW的下界函数算法（LB_ESDTW）。该算法在保证高效的运行时间效率的同时，也使得算法的度量准确率得到了提升。实验结果表明，LB_ESDTW在绝大部分时间序列数据集中，都表现出良好的适应性，针对不同类别的时间序列，都能有良好的度量性能。

关键词: 时间序列, 动态时间弯曲, 提前终止, 下界距离, 相似性度量

WANG Chao, LONG Yingwen, YIN Weihong, HUANG Bo. Research on Distance Measurement Method of Improved DTW Lower Bound Function[J]. Computer Engineering and Applications, 2022, 58(23): 316-326.

王超, 龙英文, 殷炜宏, 黄勃. 改进DTW下界函数的距离度量方法研究[J]. 计算机工程与应用, 2022, 58(23): 316-326.

References

[1] ARES J，LARA J A，LIZCANO D，et al.A soft computing framework for classifying time series based on fuzzy sets of events[J].Information Sciences，2016，330（10）：125-144.
[2] PADMAVATHI S，RAMANUJAM E.Naive bayes classifier for ECG abnormalities using multivariate maximal time series motif[J].Procedia Computer Science，2015，47：222-228.
[3] 张栗粽，王谨平，刘贵松，等.面向金融数据的神经网络时间序列预测模型[J].计算机应用研究，2018，35（9）：2632-2637.
ZHANG Lizong，WANG Jinping，LIU Guisong，et al.Neural network time series prediction model for financial data[J].Application Research of Computers，2018，35（9）：2632-2637.
[4] 于浩，贾清泉，李珍国，等.基于时间序列模式匹配的电能质量区域化治理[J].中国电机工程学报，2019，39（13）：3788-3799.
YU Hao，JIA Qingquan，LI Zhenguo，et al.Regionalization control for power quality based on time series pattern matching[J].Proceedings of the CSEE，2019，39（13）：3788-3799.
[5] 屈振新，王宏宇.流式时间序列的实时相似度研究[J].计算机工程与科学，2017，39（6）：1056-1062.
QU Zhenxin，WANG Hongyu.Real time similarity of streaming time sequence[J].Computer Engineering and Science，2017，39（6）：1056-1062.
[6] DAU H A，SILVA D F，PETITJEAN F，et al.Optimizing dynamic time warping’s window width for time series data mining applications[J].Data Mining and Knowledge Discovery，2018，32（5）：1-47.
[7] SILVA D F，GIUSTI R，KEOGH E，et al.Speeding up similarity search under dynamic time warping by pruning unpromising alignments[J].Data Mining & Knowledge Discovery，2018，32：988-1016.
[8] 陶洋，邓行，杨飞跃，等.基于DTW距离度量的层次聚类算法[J].计算机工程与设计，2019，40（1）：116-121.
TAO Yang，DENG Xing，YANG Feiyue，et al.Hierarchical clustering algorithm based on DTW distance measurement[J].Computer Engineering and Design，2019，40（1）：116-121.
[9] 李航.统计学习方法[M].北京：清华大学出版社，2012：37-45.
LI Hang.Statistical learning methods[M].Beijing：Tsinghua University Press，2012：37-45.
[10] 周驰，李智，徐灿.基于DTW算法的空间目标结构识别研究[J].计算机仿真，2019，36（9）：98-102.
ZHOU Chi，LI Zhi，XU Can.Research on spatial object structure recognition based on DTW algorithm[J].Computer Simulation，2019，36（9）：98-102.
[11] WONG T S F.Efficient subsequence matching for sequence database under time warping[C]//Database Engineering & Applications Symposium，2003.
[12] YI B K，JAGADISH H V，FALOUTSOS C.Efficient retrieval of similar time sequences under time warping[C]//14th International Conference on Data Engineering，1998.
[13] KIM S W，PARK S，CHU W W.An index-based approach for similarity search supporting time warping in large sequence databases[C]//17th International Conference on Data Engineering，2001：607-614.
[14] KEOGH E，RATANAMAHATANA C A.Exact indexing of dynamic time warping[J].Knowledge and Information Systems，2005，7（3）：358-386.
[15] 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.
[16] SAKURAI Y，YOSHIKAWA M，FALOUTSOS C.FTW：fast similarity search under the time warping distance[C]//Twenty-fourth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems，2005.
[17] GóRECKI T，?UCZAK M.Using derivatives in time series classification[J].Data Mining and Knowledge Discovery，2013，26（26）：310-331.
[18] GóRECKI T，?UCZAK M.First and second derivatives in time series classification using DTW[J].Communication in Statistics-Simulation and Computation，2014，43（9）：2081-2092.
[19] 晏臻，苏维均，于重重，等.一种改进的DTW相似性搜索方法[J].计算机仿真，2019，36（2）：232-236.
YAN Zhen，SU Weijun，YU Chongchong，et al.An Improved DTW similarity search method[J].Computer Simulation，2019，36（2）：232-236.
[20] 李正欣，张凤鸣，李克武，等.一种支持DTW 距离的多元时间序列索引结构[J].软件学报，2014，25（3）：560-575.
LI Zhengxin，ZHANG Fengming，LI Kewu，et al.Index structure for multivariate time series under DTW distance metric[J].Journal of Software，2014，25（3）：560-575.
[21] 谭章禄，王兆刚，胡翰.时间序列趋势相似性度量方法研究[J].计算机工程与应用，2020，56（10）：94-99.
TAN Zhanglu，WANG Zhaogang，HU Han.Research on trend similarity measurement method of time series[J].Computer Engineering and Applications，2020，56（10）：94-99.
[22] AMEUR S，KHALIFA A B，BOUHLEL M S.Chronological pattern indexing：an efficient feature extraction method for hand gesture recognition with leap motion[J].Journal of Visual Communication and Image Representation，2020，70：102842.
[23] 陈波，刘厚泉，赵志凯.时间序列多尺度异常检测方法[J].计算机工程与应用，2018，54（20）：122-127.
CHEN Bo，LIU Houquan，ZHAO Zhikai.Method of multi-scale anomaly detection in time series[J].Computer Engineering and Applications，2018，54（20）：122-127.
[24] ANANTASECH P，RATANAMAHATANA C A.Enhanced weighted dynamic time warping for time series classification[C]//Third International Congress on Information and Communication Technology.Singapore：Springer，2019：655-664.
[25] 李海林，梁叶，王少春.时间序列数据挖掘中的动态时间弯曲研究综述[J].控制与决策，2018，33（8）：1345-1353.
LI Hailin，LIANG Ye，WANG Shaochun.Review on dynamic time warping in time series data mining[J].Control and Decision，2018，33（8）：1345-1353.