早期时间序列分类方法研究综述

doi:10.3969/j.issn.1000-5641.2021.05.011

摘要/Abstract

摘要：

传感器技术的普及使得时间序列数据受到人们越来越多的关注. 早期时间序列分类(Early Time Series Classification, ETSC)希望通过观测尽可能短的时序数据而对其做出尽可能准确的分类, 已在科技金融领域发挥着重要的作用. 首先概述了常见的时间序列分类器, 并综述了基于最小预测长度、基于最大区分子序列和基于模型的3类早期时间序列分类框架的最新研究进展. 然后在每类方法中, 分析了具有代表性的早期时间序列分类模型的关键技术及其优缺点; 整理了科技金融领域的公开数据集和常见的评价指标. 最后对未来的发展趋势做了展望.

关键词: 早期时间序列分类, 时间序列分类器, 最小预测长度, 最大区分子序列, 机器学习

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.

Key words: early time series classification, time series classifier, minimum prediction length, shapelet, machine learning

中图分类号:

TP391

杨梦晨, 陈旭栋, 蔡鹏, 倪葎. 早期时间序列分类方法研究综述[J]. 华东师范大学学报（自然科学版）, 2021, 2021(5): 115-133.

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.

图/表 10

图1

图2

图3

表1

表2

表3

表4

表5

表6

图4

参考文献 82

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. doi: 10.1016/j.dss.2012.11.012
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. doi: 10.1016/S0169-2070(99)00048-5
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. doi: 10.1109/TAI.2020.3027279
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. doi: 10.1016/j.patcog.2010.09.022
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. doi: 10.1007/s10618-014-0361-2
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. doi: 10.1145/1882471.1882478
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. doi: 10.1007/s10618-012-0250-5
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. doi: 10.14778/1454159.1454226
20	胡蓉. 多输出支持向量回归及其在股指预测中的应用. 计算机技术与发展, 2007, (10): 226- 229. doi: 10.3969/j.issn.1673-629X.2007.10.065
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. doi: 10.1016/j.patcog.2011.08.018
29	施沫寒, 王志海. 一种基于时间序列特征的可解释步态识别方法. 中国科学: 信息科学, 2020, 50 (3): 438- 460.
30	徐雷, WEBB G I, PETITJEAN F, 等. 基于动态集成决策树的多类别时间序列分类模型. 计算机应用研究, 2018, 35 (6): 1712- 1715. doi: 10.3969/j.issn.1001-3695.2018.06.024
31	王燕, 郭元凯. 改进的XGBoost模型在股票预测中的应用. 计算机工程与应用, 2019, 55 (20): 202- 207. doi: 10.3778/j.issn.1002-8331.1904-0007
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. doi: 10.1016/j.coldregions.2013.08.009
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. doi: 10.21629/JSEE.2017.01.18
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. doi: 10.1016/j.procs.2017.09.066
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. doi: 10.1109/TITS.2019.2957325
46	XING Z Z, PEI J, PHILIP S Y. Early classification on time series. Knowledge and Information Systems, 2012, 31 (1): 105- 127. doi: 10.1007/s10115-011-0400-x
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. doi: 10.1007/s10618-016-0462-1
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.

样本序号	时间序列	标签
${\boldsymbol{x} }$	(1, 1, 1)	$ {c}_{1} $
${\boldsymbol{y} }$	(2, 1, 2)	$ {c}_{1} $
${\boldsymbol{z} }$	(5, 2, 1)	$ {c}_{2} $
${\boldsymbol{w} }$	(6, 1, 2)	$ {c}_{2} $

方法简称	序列类型	分类器/模型	考虑权衡	早期性策略
1-NN-Early, ECTS	UTS	k-NN		RNNS, 聚簇算法
Relaxed ECTS	UTS	k-NN		RNNS, 聚簇算法
MTSECP	MTS	k-NN		RNNS, 聚簇算法
ECDIRE	UTS	GP		准确度阈值 $ \alpha $
Game Theory	UTS	GP		准确度阈值 $ \alpha $
Gupta-2019^[53]	MTS	GP		准确度阈值 $ \alpha $
Gupta-2020^[54]	MTS	GP	考虑	$ \alpha $ , 概率差值
FECM	MTS	GP	考虑	效应函数
SCR, GSDT	UTS	决策树		特征枚举树

方法简称	序列类型	分类器	考虑权衡	早期性策略
MEShapelet	MTS	决策树		聚簇思想
REACT	MTS	决策树	考虑	信息增益的效应函数
EDSC	UTS			精确度和召回率的效应函数
MEDSC-U	UTS		考虑	精确度和召回率的效应函数
MSD	MTS			信息增益的效应函数
EPIMTS	MTS		考虑	GEFM
IPED	MTS		考虑	聚簇思想
CECMR	MTS			局部极值和转折点
MCFEC	MTS

方法简称	序列类型	分类器/模型	考虑权衡	早期性策略
EarlyOpt^[68,70]	UTS	SVM	考虑	构造停止规则和代价函数
CE^[73]	UTS/MTS	SVM		集成策略
Fore Front Nose^[75]	UTS/MTS	SVM		集成策略
TEASER^[76]	UTS	SVM		集成策略
iHMM^[47]	UTS	HMM		缩减状态变量个数
CBR^[77]	UTS	k-NN
Dachraoui-2015^[71]	UTS	贝叶斯决策	考虑	“未来决策”观点
NoCluster, 2Step^[72]	MTS	贝叶斯决策		“未来决策”观点
Ru?wurm-2019^[80]	UTS/MTS	LSTM+CNN	考虑	注意力机制
MDDNN^[79]	UTS/MTS	LSTM+CNN	考虑	注意力机制
Early Classifier Agent^[78]	UTS	DQN	考虑	奖励函数

方法	主要思想	输入空间	优点	缺点
基于MPL	学习MPL	原生时间序列	思想简单	高时空复杂度
基于Shapelet	选择特征	特征集	高解释性	高计算成本
基于模型	“两步走”策略	均可	高结构化程度	低解释性