Abstract
Dynamic Time Warping (DTW) coupled with k Nearest Neighbour classification, where \(k=1\), is the most common classification algorithm in time series analysis. The fact that the complexity of DTW is quadratic, and therefore computationally expensive, is a disadvantage; although DTW has been shown to be more accurate than other distance measures such as Euclidean distance. This paper presents a hybrid, Euclidean and DTW time series analysis similarity metric approach to improve the performance of DTW coupled with a candidate reduction mechanism. The proposed approach results in better performance than alternative enhanced Sub-Sequence-Based DTW approaches, and the standard DTW algorithm, in terms of runtime, accuracy and F1 score.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Alshehri, M., Coenen, F., Dures, K.: Effective sub-sequence-based dynamic time warping. In: Bramer, M., Petridis, M. (eds.) SGAI 2019. LNCS (LNAI), vol. 11927, pp. 293–305. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34885-4_23
Alshehri, M., Coenen, F., Dures, K.: Sub-sequence-based dynamic time warping. In: KDIR, pp. 274–281 (2019)
Bagnall, A., Lines, J.: An experimental evaluation of nearest neighbour time series classification. arXiv preprint arXiv:1406.4757 (2014)
Bagnall, A., Lines, J., Bostrom, A., Large, J., Keogh, E.: The great time series classification bake off: a review and experimental evaluation of recent algorithmic advances. Data Min. Knowl. Disc. 31(3), 606–660 (2017). https://doi.org/10.1007/s10618-016-0483-9
Bringmann, K., Künnemann, M.: Quadratic conditional lower bounds for string problems and dynamic time warping. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 79–97. IEEE (2015)
Brunello, A., Marzano, E., Montanari, A., Sciavicco, G.: A novel decision tree approach for the handling of time series. In: Groza, A., Prasath, R. (eds.) MIKE 2018. LNCS (LNAI), vol. 11308, pp. 351–368. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-05918-7_32
Gamboa, J.C.B.: Deep learning for time-series analysis. arXiv preprint arXiv:1701.01887 (2017)
Huang, S.F., Guo, M., Chen, M.R.: Stock market trend prediction using a functional time series approach. Quant. Financ. 20(1), 69–79 (2020)
Itakura, F.: Minimum prediction residual principle applied to speech recognition. IEEE Trans. Acoust. Speech Signal Process. 23(1), 67–72 (1975)
Kocian, A., Chessa, S.: Auto regressive integrated moving average modeling and support vector machine classification of financial time series. In: Bucciarelli, E., Chen, S.-H., Corchado, J.M. (eds.) DCAI 2018. AISC, vol. 805, pp. 1–8. Springer, Cham (2019). https://doi.org/10.1007/978-3-319-99698-1_1
Kulkarni, N.: Effect of dynamic time warping using different distance measures on time series classification. Int. J. Comput. Appl. 975, 8887 (2017)
Liu, Z., Jiang, P., Zhang, L., Niu, X.: A combined forecasting model for time series: application to short-term wind speed forecasting. Appl. Energy 259, 114137 (2020)
Niennattrakul, V., Ratanamahatana, C.A.: Learning dtw global constraint for time series classification. arXiv preprint arXiv:0903.0041 (2009)
Rakthanmanon, T., et al.: Searching and mining trillions of time series subsequences under dynamic time warping. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 262–270. ACM (2012)
Sakoe, H., Chiba, S.: Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans. Acoust. Speech Signal Process. 26(1), 43–49 (1978)
Silva, D.F., Giusti, R., Keogh, E., Batista, G.E.: Speeding up similarity search under dynamic time warping by pruning unpromising alignments. Data Min. Knowl. Disc. 32, 1–29 (2018). https://doi.org/10.1007/s10618-018-0557-y
Tan, C.W., Herrmann, M., Forestier, G., Webb, G.I., Petitjean, F.: Efficient search of the best warping window for dynamic time warping. In: Proceedings of the 2018 SIAM International Conference on Data Mining, pp. 225–233. SIAM (2018)
Zhou, M., Wong, M.H.: Boundary-based lower-bound functions for dynamic time warping and their indexing. Inf. Sci. 181(19), 4175–4196 (2011)
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Alshehri, M., Coenen, F., Dures, K. (2020). Candidates Reduction and Enhanced Sub-Sequence-Based Dynamic Time Warping: A Hybrid Approach. In: Bramer, M., Ellis, R. (eds) Artificial Intelligence XXXVII. SGAI 2020. Lecture Notes in Computer Science(), vol 12498. Springer, Cham. https://doi.org/10.1007/978-3-030-63799-6_21
Download citation
DOI: https://doi.org/10.1007/978-3-030-63799-6_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-63798-9
Online ISBN: 978-3-030-63799-6
eBook Packages: Computer ScienceComputer Science (R0)