Data Analysis and Applications

Survey of early time series classification methods

  • Mengchen YANG ,
  • Xudong CHEN ,
  • Peng CAI ,
  • Lyu NI
Expand
  • School of Data Science and Engineering, East China Normal University, Shanghai 200062, China

Received date: 2021-08-03

  Online published: 2021-09-28

Abstract

With the increasing popularity of sensors, time-series data have attracted significant attention. Early time series classification (ETSC) aims to classify time-series data with the highest level of accuracy and smallest possible size. ETSC, in particular, plays a critical role in fintech. First, this paper summarizes the common classifiers for time-series data and reviews the current research progress on minimum prediction length-based, shapelet-based, and model-based ETSC frameworks. There are pivotal technologies, advantages, and disadvantages of the representative ETSC methods in separate frameworks. Next, we review public time-series datasets in fintech and commonly used performance evaluation criteria. Lastly, we explore future research directions pertinent to ETSC.

Cite this article

Mengchen YANG , Xudong CHEN , Peng CAI , Lyu NI . Survey of early time series classification methods[J]. Journal of East China Normal University(Natural Science), 2021 , 2021(5) : 115 -133 . DOI: 10.3969/j.issn.1000-5641.2021.05.011

References

1 KAO L J, CHIU C C, LU C J, et al. A hybrid approach by integrating wavelet-based feature extraction with MARS and SVR for stock index forecasting. Decision Support Systems, 2013, 54 (3): 1228- 1244.
2 LEUNG M T, DAOUK H, CHEN A S, et al. Forecasting stock indices: A comparison of classification and level estimation models. International Journal of Forecasting, 2000, 16 (2): 173- 190.
3 MORI U, MENDIBURU A, MIRANDA I M, et al. Early classification of time series using multi-objective optimization techniques. Information Sciences, 2019, 492 (3): 204- 218.
4 马超红, 翁小清. 时间序列早期分类综述. 微型机与应用, 2016, 35 (16): 13- 15.
5 SANTOS T, KERN R. A literature survey of early time series classification and deep learning [C/OL]// SamI40 Workshop at i-KNOW’16. [2021-07-02]. http://ceur-ws.org/Vol-1793/paper4.pdf.
6 GUPTA A, GUPTA H P, BISWAS B, et al. Approaches and applications of early classification of time series: A review. IEEE Transactions on Artificial Intelligence, 2020, 1 (1): 47- 61.
7 ABANDA A, MORI U, LOZANO J A. A review on distance based time series classification. Data Mining and Knowledge Discovery, 2018, 33, 378- 412.
8 WEI L, KEOGH E. Semi-supervised time series classication [C]// Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2006: 748-753.
9 原继东, 王志海, 孙艳歌, 等. 面向复杂时间序列的k近邻分类器 . 软件学报, 2017, 28 (11): 3002- 3017.
10 JEONG Y S, JEONG M K, OMITAOMU O A. Weighted dynamic time warping for time series classification. Pattern Recognition, 2011, 44 (9): 2231- 2240.
11 BERNDT D J, CLIFFORD J. Using dynamic time warping to find patterns in time series [C]// Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining. AAAI, 1994: 359-370.
12 CHEN Y P, KEOGH E, HU B, et al. The UCR time series classication archive[EB/OL].(2015-07-15)[2021-07-21]. https://www.cs.ucr.edu/~eamonn/time_series_data/.
13 LINES J, BAGNALL A. Time series classification with ensembles of elastic distance measures. Data Mining and Knowledge Discovery, 2015, 29 (3): 565- 592.
14 XI X P, KEOGH E, SHELTON C, et al. Fast time series classification using numerosity reduction [C]// Proceedings of the 23rd International Conference on Machine Learning. 2006: 1033–1040.
15 ESLING P, AGON C. Time-series data mining. ACM Computing Surveys, 2012, 45 (1): 1- 34.
16 XING Z Z, PEI J, KEOGH E. A brief survey on sequence classification. ACM SIGKDD Explorations Newsletter, 2010, 12 (1): 40- 48.
17 WANG X Y, MUEEN A, DING H, et al. Experimental comparison of representation methods and distance measures for time series data. Data Mining and Knowledge Discovery, 2013, 26 (2): 275- 309.
18 CHEN Y P, HU B, KEOGH E, et al. DTW-D: Time series semi-supervised learning from a single example [C]// Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2013: 383–391.
19 DING H, TRAJCEVSKI G, SCHEUERMANN P, et al. Querying and mining of time series data: Experimental comparison of representations and distance measures. VLDB Endowment, 2008, 1 (2): 1542- 1552.
20 胡蓉. 多输出支持向量回归及其在股指预测中的应用. 计算机技术与发展, 2007, (10): 226- 229.
21 张倩倩, 林天华, 祁旭阳, 等. 基于机器学习的股票预测研究综述. 河北省科学院学报, 2020, 37 (4): 15- 21.
22 TAY F E H, CAO L J. Modified support vector machines in financial time series forecasting. Neurocomputing, 2002, 48 (1/2/3/4): 847- 861.
23 李翔宇, 李瑞兴, 曾燕清. 基于改进核函数的支持向量机时间序列数据分类. 信阳农林学院学报, 2021, 31 (1): 121- 126.
24 JALALIAN A, CHALUP S K. GDTW-P-SVMs: Variable-length time series analysis using support vector machines. Neurocomputing, 2013, 99 (1): 270- 282.
25 KATE R J. Using dynamic time warping distances as features for improved time series classification. Data Mining and Knowledge Discovery, 2015, 30 (2): 283- 312.
26 PANIGRAHI S S, MANTRI J K. A text based Decision Tree model for stock market forecasting [C]// Proceedings of the 2015 International Conference on Green Computing and Internet of Things (ICGCIoT). 2015: 405–411.
27 YAMADA Y, SUZUKI E, YOKOI H, et al. Decision-tree induction from time-series data based on a standard-example split test [C]// Proceedings of the 20th International Conference on International Conference on Machine Learning. 2003: 840–847.
28 DOUZAL A, AMBLARD C. Classification trees for time series. Pattern Recognition, 2012, 45 (3): 1076- 1091.
29 施沫寒, 王志海. 一种基于时间序列特征的可解释步态识别方法. 中国科学: 信息科学, 2020, 50 (3): 438- 460.
30 徐雷, WEBB G I, PETITJEAN F, 等. 基于动态集成决策树的多类别时间序列分类模型. 计算机应用研究, 2018, 35 (6): 1712- 1715.
31 王燕, 郭元凯. 改进的XGBoost模型在股票预测中的应用. 计算机工程与应用, 2019, 55 (20): 202- 207.
32 ANDERSSON J O. The new foundations of evolution: on the tree of life. Systematic Biology, 2010, 60 (1): 114- 115.
33 HENDRIK J, MURPHY M, ONSLOW T. Classification trees as a tool for operational avalanche forecasting on the Seward Highway, Alaska. Cold Regions Science and Technology, 2014, 97, 113- 120.
34 LIU G, WANG X J, LI R F. Multi-scale RCNN model for financial time-series classication[EB/OL]. (2019-11-21)[2021-07-02]. https://arxiv.org/pdf/1911.09359.pdf.
35 SUTSKEVER I, VINYALS O, LE Q V. Sequence to sequence learning with neural networks [C]// Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2. 2014: 3104–3112.
36 SZEGEDY C, LIU W, JIA Y Q, et al. Going deeper with convolutions [C]// 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, 2015: 1–9. DOI: 10.1109/CVPR.2015.7298594.
37 CUI Z C, CHEN W L, CHEN Y X. Multi-scale convolutional neural networks for time series classification[EB/OL]. (2016-03-22)[2021-07-02]. https://arxiv.org/pdf/1603.06995v4.pdf.
38 Z?BIK M, KORYTKOWSKI M, ANGRYK R, et al. Convolutional neural networks for time series classification. Journal of Systems Engineering and Electronics, 2017, 28 (1): 162- 169.
39 WANG Z G, YAN W Z, OATES T. Time series classification from scratch with deep neural networks: A strong baseline[C]// 2017 International Joint Conference on Neural Networks (IJCNN) . IEEE, 2017: 1578-1585.
40 ULYANOV D, VEDALDI A, LEMPITSKY V. Instance normalization: The missing ingredient for fast stylization [EB/OL]. (2016-07-27)[2021-07-02]. https://arxiv.org/pdf/1607.08022v3.pdf.
41 MEHDIYEV N, LAHANN J, EMRICH A, et al. Time series classification using deep learning for process planning: A case from the process industry. Procedia Computer Science, 2017, 114, 242- 249.
42 MALHOTRA P, TV V, VIG L, et al. TimeNet: Pre-trained deep recurrent neural network for time series classification [C]// 25th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning. 2018: 607–612.
43 RAJAN D, THIAGARAJAN J. A generative modeling approach to limited channel ECG classification [C]// 2018 40th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC). IEEE, 2018: 2571-2574.
44 包振山, 郭俊南, 谢源, 等. 基于LSTMG-GA的股票价格涨跌预测模型. 计算机科学, 2020, 47 (1): 467- 473.
45 GUPTA A, GUPTA H P, BISWAS B, et al. An early classification approach for multivariate time series of on-vehicle sensors in transportation. IEEE Transactions on Intelligent Transportation Systems, 2020, 21 (12): 5316- 5327.
46 XING Z Z, PEI J, PHILIP S Y. Early classification on time series. Knowledge and Information Systems, 2012, 31 (1): 105- 127.
47 ANTONUCCI A, SCANAGATTA M, MAUA D D, et al. Early classification of time series by hidden Markov models with set-valued parameters [C]// Proceedings of the NIPS Time Series Workshop. 2015: pp 1-5.
48 XING Z Z, PEI J, DONG G Z, et al. Mining sequence classifiers for early prediction [C]// SIAM International Conference on Data Mining. 2008: 644–655.
49 XING Z Z, PEI J, YU P S. Early prediction on time series: A nearest neighbor approach [C]// Proceedings of the 21st International Jont Conference on Artifical Intelligence. 2009: 1297-1302.
50 MA C H, WENG X Q, SHAN Z N. Early classification of multivariate time series based on piecewise aggregate approximation [C]// International Conference on Health Information Science, HIS 2017, Lecture Notes in Computer Science, vol 10594. Cham: Springer, 2017: 81–88.
51 MORI U, MENDIBURU A, KEOGH E, et al. Reliable early classification of time series based on discriminating the classes over time. Data Mining and Knowledge Discovery, 2017, 31 (1): 233- 263.
52 GUPTA A, PAL R, MISHRA R, et al. Game theory based early classification of rivers using time series data [C]// 2019 IEEE 5th World Forum on Internet of Things (WF-IoT). IEEE, 2019: 686–691.
53 GUPTA A, GUPTA H P, DUTTA T. Early classification approach for multivariate time series using sensors of different sampling rate [C]// 2019 16th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON). IEEE, 2019: 1–2. DOI: 10.1109/SAHCN.2019.8824960.
54 GUPTA A, GUPTA H P, BISWAS B, et al. A divide-and conquer–based early classification approach for multivariate time series with different sampling rate components in IoT [J]. ACM Transactions on Internet of Things, 2020, 1(2): 1–21.
55 GUPTA A, GUPTA H P, BISWAS B, et al. A fault-tolerant early classification approach for human activities using multivariate time series. A fault-tolerant early classification approach for human activities using multivariate time series, 2021, 20 (5): 1747- 1760.
56 LI S, LI K, FU Y. Early recognition of 3D human actions. ACM Transactions on Multimedia Computing, Communications, and Applications, 2018, 14 (1): 1- 20.
57 XING Z Z, PEI J, YU P S, et al. Extracting interpretable features for early classification on time series [C]// Proceedings of the 2011 SIAM International Conference on Data Mining (SDM). SIAM, 2011: 247–258.
58 GHALWASH M F, RADOSAVLJEVIC V, OBRADOVIC Z. Utilizing temporal patterns for estimating uncertainty in interpretable early decision making [C]//Proc SIGKDD, 2014: 402–411.
59 LIN Y F, CHEN H H, TSENG V S, et al. Reliable early classification on multivariate time series with numerical and categorical attributes [C]// Advances in Knowledge Discovery and Data Mining, PAKDD 2015, Lecture Notes in Computer Science, vol 9077. Cham: Springer, 2015: 199–211.
60 GHALWASH M F, OBRADOVIC Z. Early classification of multivariate temporal observations by extraction of interpretable shapelets [J]. BMC Bioinformatics, 2012, 13: Article number 195.
61 HE G L, DUAN Y, QIAN T Y, et al. Early prediction on imbalanced multivariate time series [C]// Proceedings of the 22nd ACM International Conference on Information & Knowledge Management. ACM, 2013: 1889–1892.
62 GHALWASH M F, RADOSAVLJEVIC V, OBRADOVIC Z. Extraction of interpretable multivariate patterns for early diagnostics [C]// 2013 IEEE 13th International Conference on Data Mining. IEEE, 2013: 201–210.
63 ZHAO L, LIANG H Y, YU D M, et al. Asynchronous multivariate time series early prediction for ICU transfer [C]// Proceedings of the 2019 International Conference on Intelligent Medicine and Health. ACM, 2019: 17–22.
64 HE G L, ZHAO W, XIA X W. Confidence-based early classification of multivariate time series with multiple interpretable rules [J]. Pattern Analysis and Applications, 2020, 23: 567–580.
65 HE G L, DUAN Y, ZHOU G F, et al. Early classification on multivariate time series with core features [C]// Database and Expert Systems Applications, DEXA 2014, Lecture Notes in Computer Science, vol 8644. Cham: Springer, 2014: 410–422.
66 NG A Y, JORDAN M I. On discriminative vs. generative classifiers: A comparison of logistic regression and naive bayes [C]// NIPS, 2002: 841–848.
67 CHENG W H, ERFANI S M, ZHANG R, et al. Predicting complex activities from ongoing multivariate time series [C]// Proceedings of the 27th International Joint Conference on Artificial Intelligence. ACM, 2018: 3322–3328.
68 LI K, LI S, FU Y. Early classification of ongoing observation [C]// 2014 IEEE International Conference on Data Mining. IEEE, 2014: 310–319.
69 MORI U, MENDIBURU A, DASGUPTA S, et al. Early classification of time series by simultaneously optimizing the accuracy and earliness [J]. IEEE Transactions on Neural Networks and Learning Systems, 2017, 29(10): 4569–4578.
70 MORI U, MENDIBURU A, DASGUPTA S, et al. Early classification of time series from a cost minimization point of view [C]// Proceedings of the NIPS Time Series Workshop. 2015: 1-5.
71 DACHRAOUI A, BONDU A, CORNU′EJOLS A. Early classification of time series as a non myopic sequential decision making problem [C]// Machine Learning and Knowledge Discovery in Databases, ECML PKDD 2015, Lecture Notes in Computer Science, vol 9284. Cham: Springer, 2015: 433–447.
72 TAVENARD R, MALINOWSKI S. Cost-aware early classification of time series [C]// Machine Learning and Knowledge Discovery in Databases, ECML PKDD 2016, Lecture Notes in Computer Science, vol 9851. Cham: Springer, 2016: 632–647.
73 ANDO S, SUZUKI E. Minimizing response time in time series classification [J]. Knowledge and Information Systems, 2016, 46(2): 449–476.
74 GONZALEZ C J A, DIEZ J J R. Boosting interval-based literals: Variable length and early classification [C]// Series in Machine Perception and Artificial Intelligence: Volume 83, Data Mining in Time Series and Streaming Databases. Singapore: World Scientific Publishing Co Pte Ltd, 2004: 149–171.
75 HATAMI N, CHIRA C. Classifiers with a reject option for early time-series classification[C]//2013 IEEE Symposium on Computational Intelligence and Ensemble Learning (CIEL). IEEE, 2013: 9–16.
76 SCH?FER P, LESER U. Teaser: Early and accurate time series classification [J]. Data Mining and Knowledge Discovery, 2020, 34: 1336–1362.
77 BREGON A, SIMON M A, RODRIGUEZ J J, et al. Early fault classification in dynamic systems using case-based reasoning [C]// Current Topics in Artificial Intelligence, CAEPIA 2005, Lecture Notes in Computer Science, vol 4177. Berlin: Springer, 2006: 211–220.
78 MARTINEZ C, PERRIN G, RAMASSO E, et al. A deep reinforcement learning approach for early classification of time series [C]// 2018 26th European Signal Processing Conference (EUSIPCO). IEEE, 2018: 2030–2034.
79 HUANG H S, LIU C L, TSENG V S. Multivariate time series early classification using multi-domain deep neural network [C]// 2018 IEEE 5th International Conference on Data Science and Advanced Analytics (DSAA). IEEE, 2018: 90–98.
80 RU?WURM M, LEFEVRE S,COURTY N, et al. End-to-end learning for early classification of time series [EB/OL]. (2019-01-30)[2021-07-02]. https://arxiv.org/pdf/1901.10681.pdf.
81 Kaggle Datssets [EB/OL]. [2021-07-02]. https://www.kaggle.com/datasets.
82 GHALWASH M F, RAMLJAK D, OBRADOVIC Z. Early classification of multivariate time series using a hybrid hmm/svm model [C]// 2012 IEEE International Conference on Bioinformatics and Biomedicine. IEEE, 2012: 1–6. DOI: 10.1109/BIBM.2012.6392654.
Outlines

/