Time Series Classification Through Ordinal Pattern Transition Graphs

• Isadora Cardoso-Pereira Universidade Federal de Minas Gerais
• João B. Borges Universidade Federal do Rio Grande do Norte
• Pedro H. Barros Universidade Federal de Minas Gerais
• Antonio F. Loureiro Universidade Federal de Minas Gerais
• Heitor S. Ramos Universidade Federal de Minas Gerais

DOI: https://doi.org/10.5753/sbrc.2019.7391

Abstract

Regarding its interdisciplinary and broad scope of real-world applications, it is evident the need of extracting knowledge from time series data. Mining this type of data, however, faces several complexities due to its unique properties. In this work, we propose a new feature, retained from the Ordinal Pattern Transition Graph, called probability of self-transition. Our proposal was tested in a real Urban Computing problem, referred to the classification of transportation mode. We had better accuracy results than well-known Information Theory features, besides being less dependent on Ordinal Patterns parameters.

Keywords: Data Mining, Time Series, Urban Computing

References

Aquino, A., Cavalcante, T., Almeida, E., Frery, A., and Rosso, O. (2015). Characterization of vehicle behavior with information theory. The European Physical Journal B, 88(10):257.

Aquino, A., Ramos, H., Frery, A., Viana, L., Cavalcante, T., and Rosso, O. (2017). Characterization of electric load with information theory quantifiers. Physica A: Statistical Mechanics and its Applications, 465:277 – 284.

Bagnall, A., Lines, J., Bostrom, A., Large, J., and Keogh, E. (2017). The great time series classification bake off: a review and experimental evaluation of recent algorithmic advances. Data Mining and Knowledge Discovery, 31(3):606–660.

Bandt, C. and Pompe, B. (2002). Permutation entropy: A natural complexity measure for time series. Phys. Rev. Lett., 88:174102.

Fawaz, H., Forestier, G., Weber, J., Idoumghar, L., and Muller, P.-A. (2019). Deep learning for time series classification: a review. Data Mining and Knowledge Discovery.

Guo, H., Zhang, J.-Y., Zou, Y., and Guan, S.-G. (2018). Cross and joint ordinal partition transition networks for multivariate time series analysis. Frontiers of Physics, 13(5):130508.

Lacasa, L., Luque, B., Ballesteros, F., Luque, J., and Nu˜no, J. C. (2008). From time series to complex networks: The visibility graph. Proceedings of the National Academy of Sciences, 105(13):4972–4975.

Lines, J., Taylor, S., and Bagnall, A. (2018). Time series classification with hivecote: The hierarchical vote collective of transformation-based ensembles. ACM Trans. Knowl. Discov. Data, 12(5):52:1–52:35.

Luque, B., Lacasa, L., Ballesteros, F., and Luque, J. (2009). Horizontal visibility graphs: Exact results for random time series. Phys. Rev. E, 80:046103.

L¨angkvist, M., Karlsson, L., and Loutfi, A. (2014). A review of unsupervised feature learning and deep learning for time-series modeling. Pattern Recognition Letters, 42:11 – 24.

McCullough, M., Small, M., Iu, H., and Stemler, T. (2017). Multiscale ordinal network analysis of human cardiac dynamics. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 375(2096):20160292.

Ravetti, M. G., Carpi, L. C., Gon¸calves, B. A., Frery, A., and Rosso, O. A. (2014). Distinguishing noise from chaos: Objective versus subjective criteria using horizontal visibility graph. PLOS ONE, 9(9):1–15.

Ribeiro, H. V., Jauregui, M., Zunino, L., and Lenzi, E. K. (2017). Characterizing time series via complexity-entropy curves. Phys. Rev. E, 95:062106.

Rosso, O. A., Larrondo, H. A., Martin, M. T., Plastino, A., and Fuentes, M. A. (2007). Distinguishing noise from chaos. Phys. Rev. Lett., 99:154102.

Small, M. (2013). Complex networks from time series: Capturing dynamics. In 2013 IEEE International Symposium on Circuits and Systems, pages 2509–2512. IEEE.

Staniek, M. and Lehnertz, K. (2007). Parameter selection for permutation entropy measurements. International Journal of Bifurcation and Chaos, 17(10):3729–3733.

Wang, X., Ding, H., Trajcevski, G., Scheuermann, P., and Keogh, E. J. (2010). Experimental comparison of representation methods and distance measures for time series data. CoRR, abs/1012.2789.

Wilson, S. J. (2017). Data representation for time series data mining: time domain approaches. Wiley Interdisciplinary Reviews: Computational Statistics, 9(1):e1392.

Yang, Q. and Wu, X. (2006). 10 challenging problems in data mining research. International Journal of Information Technology & Decision Making, 5(04):597– 604.

Zhang, J., Zhou, J., Tang, M., Guo, H., Small, M., and Zou, Y. (2017). Constructing ordinal partition transition networks from multivariate time series. Scientific reports, 7(1):7795.

Zheng, Y., Li, Q., Chen, Y., Xie, X., and Ma, W.-Y. (2008). Understanding mobility based on gps data. In Proceedings of the 10th international conference on Ubiquitous computing, pages 312–321. ACM.

Zunino, L., Soriano, M. C., and Rosso, O. A. (2012). Distinguishing chaotic and stochastic dynamics from time series by using a multiscale symbolic approach. Phys. Rev. E, 86:046210.