A Comparison Study of Dynamic Time Warping’s Variants for Time Series Classification

Yıl 2021, Cilt: 4 Sayı: 1, 56 - 71, 05.06.2021

Abdelmadjid Lahreche Bachir Boucheham

Öz

The similarity measure is a key operation in the analysis and mining of time-series data. One of the most popular and effective measures is Dynamic Time Warping (DTW). Particularly, in the time-series classification (TSC) domain, DTW has been extensively studied over the past two decades. Consequently, several improved versions have been proposed in the literature. A critical observation is that most of these variants have never been evaluated together in the context of TSC. In our opinion, we believe that there is a need to compare DTW’s variants under a unified framework. Moreover, we also believe that such a study is of fundamental importance and could drive meaningful conclusions for both researchers and practitioners. Our objective is to provide a comprehensive comparison in which we show which variant is the most suitable for a particular problem. In this paper, we conduct an extensive evaluation to compare the classical DTW and its most popular variations for TSC. We evaluate these methods in terms of classification accuracy using a large variety of data-sets from the UCR time-series archive. The results show that no variant outperforms the others for all problems. Results also show that there is no statistically significant difference between virtually all variants.

Anahtar Kelimeler

Time series, Similarity measures, Classification, DTW, Variants of DTW

Kaynakça

• Abanda, A., Mori, U., Lozano, J.A.: A review on distance based time series classi cation. Data Min. Knowl. Discov. 33(2), 378412 (2019)
• Bagnall, A., Lines, J.: An experimental evaluation of nearest neighbour time series classication (2014)
• Bagnall, A., Lines, J., Bostrom, A., Large, J., Keogh, E.: The great time series classication bake o: A review and experimental evaluation of recent algorithmic advances. Data Min. Knowl. Discov. 31(3), 606660 (2017)
• Batista, G.E., Keogh, E.J., Tataw, O.M., Souza, V.M.: CID: An ecient complexity-invariant distance for time series. Data Min. Knowl. Discov. 28(3), 634669 (2014)
• Berndt, D., Cliord, J.: Using dynamic time warping to nd patterns in time series. In: KDD Workshop (1994)
• Boulnemour, I., Boucheham, B.: QP-DTW: Upgrading dynamic time warping to handle quasi periodic time series alignment. J. Inf. Process. Syst. 14, 851{876 (2018)
• Cassisi, C., Montalto, P., Aliotta, M., Cannata, A., Pulvirenti, A.: Similarity Measures and Dimensionality Reduction Techniques for Time Series Data Mining (2012)
• Chen, L.,  Ozsu, M.T., Oria, V.: Robust and fast similarity search for moving object trajectories. In: Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. p. 491502. Association for Computing Machinery, New York, NY, USA (2005)
• Chen, Y., Keogh, E., Hu, B., Begum, N., Bagball, A., Mueen, A., Batista, G.: The UCR time series classication archive (2015), www.cs.ucr.edu/ eamonn/time series data/
• Demsar, J.: Statistical comparisons of classiers over multiple data sets. The Journal of Machine Learning Research 7, 1{30 (2006)
• Esling, P., Agon, C.: Time-series data mining. ACM Comput. Surv. 45(1) (2012)
• Fu, T.C.: A review on time series data mining. Engineering Applications of Arti- cial Intelligence 24(1), 164{181 (2011)
• Giusti, R., Batista, G.E.: An empirical comparison of dissimilarity measures for time series classication. In: 2013 Brazilian Conference on Intelligent Systems. pp. 82{88 (2013)
• Gorecki, T., Luczak, M.: Using derivatives in time series classication. Data Min. Knowl. Discov. 26(2), 310331 (2013)
• Itakura, F.: Minimum prediction residual principle applied to speech recognition. IEEE Transactions on Acoustics, Speech, and Signal Processing 23(1), 67{72 (1975)
• Jeong, Y.S., Jeong, M.K., Omitaomu, O.A.: Weighted dynamic time warping for time series classication. Pattern recognition. 44(9), 22312240 (2011)
• Keogh, E.J., Pazzani, M.: Derivative dynamic time warping. In: the 2001 SIAM international conference on data mining (2001)
• Lahreche, A., Boucheham, B.: FastSEA: A very fast and very eective matching technique for very complex time series. In: 2017 International Conference on Mathematics and Information Technology (ICMIT). pp. 286{293 (2017)
• Lahreche, A., Boucheham, B.: LMDS-SEA: Upgrading the shape exchange algorithm (sea) to handle general time series classication by local matching and distance selection. In: 2018 3rd International Conference on Pattern Analysis and Intelligent Systems (PAIS). pp. 1{6 (2018) A comparison study of DTW's variants for TSC 71
• Lahreche, A., Boucheham, B.: A fast and accurate similarity measure for long time series classication based on local extrema and dynamic time warping. Expert Systems with Applications 168, 114374 (2021). https://doi.org/https://doi.org/10.1016/j.eswa.2020.114374
• Lin, J., Williamson, S., Borne, K.D., DeBarr, D.: Pattern Recognition in Time Series, pp. 617{645 (2012)
• Marteau, P.: Time warp edit distance with stiness adjustment for time series matching. IEEE Transactions on Pattern Analysis and Machine Intelligence 31, 306{318 (2009)
• Mondal, T., Ragot, N., Ramel, J., Pal, U.: Performance evaluation of DTW and its variants for word spotting in degraded documents. In: 2015 13th International Conference on Document Analysis and Recognition (ICDAR). pp. 1141{1145 (2015)
• Mueen, A., Keogh, E.: Extracting optimal performance from dynamic time warping. In: the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. p. 21292130. Association for Computing Machinery, New York, NY, USA (2016)
• Ratanamahatana, C., Keogh, E.J.: Three myths about dynamic time warping data mining. In: the 2005 SIAM International Conference on Data Mining (2005)
• Ratanamahatana, C.A., Lin, J., Gunopulos, D., Keogh, E.J., Vlachos, M., Das, G.: Mining time series data. In: Maimon, O., Rokach, L. (eds.) Data Mining and Knowledge Discovery Handbook, 2nd ed, pp. 1049{1077. Springer (2010)
• Sakoe, H., Chiba, S.: Dynamic programming algorithm optimization for spoken word recognition. IEEE Transactions on Acoustics, Speech, and Signal Processing 26(1), 43{49 (1978)
• Schafer, P.: The BOSS is concerned with time series classication in the presence of noise. Data Min. Knowl. Discov. 29(6), 15051530 (2015)
• Schafer, P.: Scalable time series classication. Data Min. Knowl. Discov. 30(5), 12731298 (2016)
• Stefan, A., Athitsos, V., Das, G.: The move-split-merge metric for time series. IEEE Transactions on Knowledge and Data Engineering 25(6), 1425{1438 (2013)
• Vlachos, M., Kollios, G., Gunopulos, D.: Discovering similar multidimensional trajectories. In: Proceedings 18th International Conference on Data Engineering. pp. 673{684 (2002)
• Xing, Z., Pei, J., Keogh, E.: A brief survey on sequence classication. SIGKDD Explor. Newsl. 12(1), 4048 (2010)
• Yuan, J., Chouakria, A.D., Yazdi, S.V., Wang, Z.: A large margin time series nearest neighbour classication under locally weighted time warps. Knowl. Inf. Syst. 59(1), 117{135 (2019)
• Yuan, J., Lin, Q., Zhang, W., Wang, Z.: Locally slope-based dynamic time warping for time series classication. In: Proceedings of the 28th ACM International Conference on Information and Knowledge Management. p. 17131722. Association for Computing Machinery, New York, NY, USA (2019)
• Zhang, Z., Tang, P., Duan, R.: Dynamic time warping under pointwise shape context. Inf. Sci. 315, 88101 (2015)
• Zhang, Z., Tavenard, R., Bailly, A., Tang, X., Tang, P., Corpetti, T.: Dynamic time warping under limited warping path length. Inf. Sci. 393, 91107 (2017)
• Zhao, J., Itti, L.: shapeDTW: Shape dynamic time warping. Pattern Recogn. 74, 171184 (2018)