Research Article
BibTex RIS Cite
Year 2021, Volume: 4 Issue: 1, 56 - 71, 05.06.2021

Abstract

References

  • 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., Cli ord, 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 e ective 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 sti ness 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)

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

Year 2021, Volume: 4 Issue: 1, 56 - 71, 05.06.2021

Abstract

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.

References

  • 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., Cli ord, 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 e ective 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 sti ness 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)
There are 37 citations in total.

Details

Primary Language English
Subjects Software Engineering (Other)
Journal Section Articles
Authors

Abdelmadjid Lahreche

Bachir Boucheham This is me

Publication Date June 5, 2021
Acceptance Date December 16, 2020
Published in Issue Year 2021 Volume: 4 Issue: 1

Cite

APA Lahreche, A., & Boucheham, B. (2021). A Comparison Study of Dynamic Time Warping’s Variants for Time Series Classification. International Journal of Informatics and Applied Mathematics, 4(1), 56-71.
AMA Lahreche A, Boucheham B. A Comparison Study of Dynamic Time Warping’s Variants for Time Series Classification. IJIAM. June 2021;4(1):56-71.
Chicago Lahreche, Abdelmadjid, and Bachir Boucheham. “A Comparison Study of Dynamic Time Warping’s Variants for Time Series Classification”. International Journal of Informatics and Applied Mathematics 4, no. 1 (June 2021): 56-71.
EndNote Lahreche A, Boucheham B (June 1, 2021) A Comparison Study of Dynamic Time Warping’s Variants for Time Series Classification. International Journal of Informatics and Applied Mathematics 4 1 56–71.
IEEE A. Lahreche and B. Boucheham, “A Comparison Study of Dynamic Time Warping’s Variants for Time Series Classification”, IJIAM, vol. 4, no. 1, pp. 56–71, 2021.
ISNAD Lahreche, Abdelmadjid - Boucheham, Bachir. “A Comparison Study of Dynamic Time Warping’s Variants for Time Series Classification”. International Journal of Informatics and Applied Mathematics 4/1 (June 2021), 56-71.
JAMA Lahreche A, Boucheham B. A Comparison Study of Dynamic Time Warping’s Variants for Time Series Classification. IJIAM. 2021;4:56–71.
MLA Lahreche, Abdelmadjid and Bachir Boucheham. “A Comparison Study of Dynamic Time Warping’s Variants for Time Series Classification”. International Journal of Informatics and Applied Mathematics, vol. 4, no. 1, 2021, pp. 56-71.
Vancouver Lahreche A, Boucheham B. A Comparison Study of Dynamic Time Warping’s Variants for Time Series Classification. IJIAM. 2021;4(1):56-71.

International Journal of Informatics and Applied Mathematics