Josif Grabocka
Lars Schmidt-Thieme
ABSTRACT
Shapelets are discriminative sub-sequences of time series that best predict the target variable. For this reason, shapelet discovery has recently attracted considerable interest within the time-series research community. Currently shapelets are found by evaluating the prediction qualities of numerous candidates extracted from the series segments. In contrast to the state-of-the-art, this paper proposes a novel perspective in terms of learning shapelets. A new mathematical formalization of the task via a classification objective function is proposed and a tailored stochastic gradient learning algorithm is applied. The proposed method enables learning near-to-optimal shapelets directly without the need to try out lots of candidates. Furthermore, our method can learn true top-K shapelets by capturing their interaction. Extensive experimentation demonstrates statistically significant improvement in terms of wins and ranks against 13 baselines over 28 time-series datasets.
Supplemental Material
- K.-W. Chang, B. Deka, W. mei W. Hwu, and D. Roth. Efficient pattern-based time series classification on gpu. In M. J. Zaki, A. Siebes, J. X. Yu, B. Goethals, G. I. Webb, and X. Wu, editors, ICDM, pages 131--140. IEEE Computer Society, 2012. Google Scholar
Digital Library
- A. Das and D. Kempe. Algorithms for subset selection in linear regression. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC '08, pages 45--54, New York, NY, USA, 2008. ACM. Google ScholarDigital Library
- J. Demsar. Statistical comparisons of classifiers over multiple data sets. J. Mach. Learn. Res., 7:1--30, Dec. 2006. Google ScholarDigital Library
- H. Ding, G. Trajcevski, P. Scheuermann, X. Wang, and E. J. Keogh. Querying and mining of time series data: experimental comparison of representations and distance measures. PVLDB, 1(2):1542--1552, 2008. Google ScholarDigital Library
- B. Hartmann and N. Link. Gesture recognition with inertial sensors and optimized dtw prototypes. In IEEE International Conference on Systems Man and Cybernetics, 2010.Google ScholarCross Ref
- B. Hartmann, I. Schwab, and N. Link. Prototype optimization for temporarily and spatially distorted time series. In the AAAI Spring Symposia, 2010.Google Scholar
- Q. He, F. Zhuang, T. Shang, Z. Shi, et al. Fast time series classification based on infrequent shapelets. In 11th IEEE International Conference on Machine Learning and Applications, 2012. Google ScholarDigital Library
- J. Hills, J. Lines, E. Baranauskas, J. Mapp, and A. Bagnall. Classification of time series by shapelet transformation. Data Mining and Knowledge Discovery, 2013. Google ScholarDigital Library
- J. Lines and A. Bagnall. Alternative quality measures for time series shapelets. In Intelligent Data Engineering and Automated Learning, volume 7435 of Lecture Notes in Computer Science, pages 475--483. 2012. Google ScholarDigital Library
- J. Lines, L. Davis, J. Hills, and A. Bagnall. A shapelet transform for time series classification. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2012. Google ScholarDigital Library
- A. Mueen, E. Keogh, and N. Young. Logical-shapelets: an expressive primitive for time series classification. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2011. Google ScholarDigital Library
- T. Rakthanmanon and E. Keogh. Fast shapelets: A scalable algorithm for discovering time series shapelets. Proceedings of the 13th SIAM International Conference on Data Mining, 2013.Google ScholarCross Ref
- P. Sivakumar and T. Shajina. Human gait recognition and classification using time series shapelets. In IEEE International Conference on Advances in Computing and Communications, 2012. Google ScholarDigital Library
- E. W. Wild. Optimization-based Machine Learning and Data Mining. ProQuest, 2008.Google Scholar
- Z. Xing, J. Pei, and P. Yu. Early classification on time series. Knowledge and information systems, 31(1):105--127, 2012. Google ScholarDigital Library
- Z. Xing, J. Pei, P. Yu, and K. Wang. Extracting interpretable features for early classification on time series. Proceedings of the 11th SIAM International Conference on Data Mining, 2011.Google ScholarCross Ref
- L. Ye and E. Keogh. Time series shapelets: a new primitive for data mining. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2009. Google ScholarDigital Library
- L. Ye and E. Keogh. Time series shapelets: a novel technique that allows accurate, interpretable and fast classification. Data Mining and Knowledge Discovery, 22(1):149--182, 2011. Google ScholarDigital Library
- J. Zakaria, A. Mueen, and E. Keogh. Clustering time series using unsupervised-shapelets. In Proceedings of the 12th IEEE International Conference on Data Mining, 2012. Google ScholarDigital Library
Index Terms
- Learning time-series shapelets
Recommendations
Learning multivariate shapelets with multi-layer neural networks for interpretable time-series classification
AbstractShapelets are discriminative subsequences extracted from time-series data. Classifiers using shapelets have proven to achieve performances competitive to state-of-the-art methods, while enhancing the model’s interpretability. While a lot of ...
Time-series Shapelets with Learnable Lengths
CIKM '23: Proceedings of the 32nd ACM International Conference on Information and Knowledge ManagementShapelets are subsequences that are effective for classifying time-series instances. Learning shapelets by a continuous optimization has recently been studied to improve computational efficiency and classification performance. However, existing methods ...
Random Dilated Shapelet Transform: A New Approach for Time Series Shapelets
Pattern Recognition and Artificial IntelligenceAbstractShapelet-based algorithms are widely used for time series classification because of their ease of interpretation, but they are currently outperformed by recent state-of-the-art approaches. We present a new formulation of time series shapelets ...
Comments