Abstract
As time series data become more complex and users expect more sophisticated information, numerous algorithms have been proposed to solve these challenges. Among those algorithms to classify time series data, shapelet – a discriminative subsequence of time series data – is considered a practical approach due to its accurate and insightful classification. However, previously proposed shapelet algorithms still suffer from exceedingly high computational complexity, as a result, limiting its scalability to larger datasets. Therefore, in this work, we propose a novel algorithm that speeds up shapelet discovery process. Our algorithm so called “Dual Increment Shapelets (DIS)” is a combination of two-layered incremental neural network and filtering process based on subsequence characteristics. Empirical experiments on forty datasets evidently demonstrate that our proposed work could achieve large speedup while maintaining its accuracy. Unlike the previous algorithm that mainly emphasizes speedup of the search algorithm, DIS essentially reduces the number of shapelet candidates based on subsequence characteristics. As a result, our DIS algorithm could achieve more than three orders of magnitude speedup, comparing with the baseline algorithms, while preserving the accuracy of the state-of-the-art algorithm.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Keogh, E., Wei, L., Xi, X., Vlachos, M., Lee, S.-H., Protopapas, P.: Supporting exact indexing of arbitrarily rotated shapes and periodic time series under Euclidean and warping distance measures. VLDB J. 18, 611–630 (2009)
Keogh, E., Ratanamahatana, C.A.: Exact indexing of dynamic time warping. Knowl. Inf. Syst. 7, 358–386 (2005)
Rakthanmanon, T., Keogh, E.: Fast shapelets: a scalable algorithm for discovering time series shapelets. In: Proceedings of the 2013 SIAM International Conference on Data Mining, pp. 668–676. SIAM (2013)
Ye, L., Keogh, E.: Time series shapelets: a new primitive for data mining. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 947–956. ACM (2009)
Lin, J., Keogh, E., Wei, L., Lonardi, S.: Experiencing SAX: a novel symbolic representation of time series. Data Min. Knowl. Discov. 15, 107–144 (2007)
Bingham, E., Mannila, H.: Random projection in dimensionality reduction: applications to image and text data. In: Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 245–250. ACM (2001)
Lines, J., Bagnall, A.: Alternative quality measures for time series shapelets. In: International Conference on Intelligent Data Engineering and Automated Learning, pp. 475–483. Springer (2012)
Rodriguez, J.J., Kuncheva, L.I., Alonso, C.J.: Rotation forest: a new classifier ensemble method. IEEE Trans. Pattern Anal. Mach. Intell. 28, 1619–1630 (2006)
Rodríguez, J.J., Alonso, C.J.: Support vector machines of interval-based features for time series classification. In: International Conference on Innovative Techniques and Applications of Artificial Intelligence, pp. 244–257. Springer (2004)
Grabocka, J., Schilling, N., Wistuba, M., Schmidt-Thieme, L.: Learning time-series shapelets. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 392–401. ACM (2014)
Ji, C., Liu, S., Yang, C., Pan, L., Wu, L., Meng, X.: A shapelet selection algorithm for time series classification: new directions. Procedia Comput. Sci. 129, 461–467 (2018)
Okada, S., Hasegawa, O.: Motion recognition based on dynamic-time warping method with self-organizing incremental neural network. In: 2008 19th International Conference on Pattern Recognition, ICPR 2008, pp. 1–4. IEEE (2008)
Yang, Y., Deng, Q., Shen, F., Zhao, J., Luo, C.: A shapelet learning method for time series classification. In: 2016 IEEE 28th International Conference on Tools with Artificial Intelligence (ICTAI), pp. 423–430. IEEE (2016)
Bostrom, A., Bagnall, A., Lines, J.: Evaluating Improvements to the Shapelet Transform (2016). www-bcf.usc.edu
Ji, C., Liu, S., Yang, C., Wu, L., Pan, L., Meng, X.: A piecewise linear representation method based on importance data points for time series data. In: 2016 IEEE 20th International Conference on Computer Supported Cooperative Work in Design (CSCWD), pp. 111–116. IEEE (2016)
Bostrom, A., Bagnall, A.: Binary shapelet transform for multiclass time series classification. Trans. Large-Scale Data Knowl.-Cent. Syst. XXXII, 24–46 (2017)
Zhu, J., Rosset, S., Tibshirani, R., Hastie, T.J.: 1-norm support vector machines. In: Advances in Neural Information Processing Systems, pp. 49–56 (2004)
Chen, Y., Keogh, E., Hu, B., Begum, N., Bagnall, A., Mueen, A., Batista, G.: The UCR time series classification archive, July (2015)
Hall, M., Frank, E., Holmes, G., Pfahringer, B., Reutemann, P., Witten, I.H.: The WEKA data mining software: an update. ACM SIGKDD Explor. Newsl. 11, 10–18 (2009)
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. Discov. 31, 606–660 (2017)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Vichit, N., Ratanamahatana, C.A. (2020). Dual Increment Shapelets: A Scalable Shapelet Discovery for Time Series Classification. In: Boonyopakorn, P., Meesad, P., Sodsee, S., Unger, H. (eds) Recent Advances in Information and Communication Technology 2019. IC2IT 2019. Advances in Intelligent Systems and Computing, vol 936. Springer, Cham. https://doi.org/10.1007/978-3-030-19861-9_1
Download citation
DOI: https://doi.org/10.1007/978-3-030-19861-9_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-19860-2
Online ISBN: 978-3-030-19861-9
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)