时间序列的表示与分类算法综述

doi:10.11896/j.issn.1002-137X.2015.03.001

摘要/Abstract

摘要： 时间序列是按照时间排序的一组随机变量,它通常是在相等间隔的时间段内,依照给定的采样率,对某种潜在过程进行观测的结果。时间序列数据广泛地存在于商业、农业、气象、生物科学以及生态学等诸多领域,从时间序列中发现有用的知识已成为数据挖掘领域的研究热点之一。在时间序列表示方面,主要介绍了非数据适应性表示方法、数据适应性表示方法和基于模型的表示方法；针对时间序列的分类方法,着重介绍了基于时域相似性、形状相似性和变化相似性的分类算法,并对未来的研究方向进行了进一步的展望。

关键词: 时间序列,时间序列分类,时间序列表示

Abstract: Time series is a set of random variables ordered in timestamp.It is often the observation of an underlying process,in which values are collected from uniformly spaced time instants,according to a given sampling rate.Since time series data exist widely in various application domains,such as finance,agriculture,meteorology,biological science,eco-logy and so on,discovering knowledge from time series has become one of the mainly research fields of data mining.In this paper,a comprehensive review on the existing time series representation and classification research was given.In the term of time series representation,three different categories named non-data adaptive,data adaptive and model based were summarized.A summary of several time series classification method,namely similarity in time,similarity in shape and similarity in change was also provided.

Key words: Time series,Time series classification,Time series representation

原继东,王志海. 时间序列的表示与分类算法综述[J]. 计算机科学, 2015, 42(3): 1-7. https://doi.org/10.11896/j.issn.1002-137X.2015.03.001

YUAN Ji-dong and WANG Zhi-hai. Review of Time Series Representation and Classification Techniques[J]. Computer Science, 2015, 42(3): 1-7. https://doi.org/10.11896/j.issn.1002-137X.2015.03.001

参考文献

[1] Agrawal R,Faloutsos C,Swami A.Efficient similarity search in sequence databases[C]∥Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms (FODO 1993).1993:69-84
[2] Azzouzi M,Nabney I T.Analysing time series structure withHidden Markov Models[C]∥Proceedings of the IEEE Confe-rence on Neural Networks and Signal Processing.1998:402-408
[3] Bagnall A,Janacek G J,Powell M.A likelihood ratio distancemeasure for the similarity between the fourier transform of time series[C]∥Proceedings of the Advances in Knowledge Disco-very and Data Mining,9th Pacific-Asia Conference(PAKDD 2005).2005:737-743
[4] Bagnall A,Davis L,Hills J,et al.Transformation based ensembles for time series classification[C]∥Proceedings of the 2012 SIAM International Conference on Data Mining (SDM 2012).2012:307-318
[5] Balakrishnan S,Madigan D.Decision trees for functional variables[C]∥Proceedings of the 2006 International Conference on Data Mining (ICDM 2006).2006:798-802
[6] Batista G,Wang X,Keogh E.A complexity-invariant distancemeasure for time series[C]∥Proceedings of the eleventh SIAM conference on data mining (SDM 2011).2011:699-710
[7] Berndt D J,Clifford J.Using dynamic time warping to find patterns in time series[C]∥KDD Workshop.1994:359-370
[8] Breiman L.Random forests[J].Machine Learning,2001,45(1):5-32
[9] Cryer J D,Chan K.时间序列分析及应用 [M].潘红宇,等译.北京:机械工业出版社,2011
[10] Buza K.Fusion methods for time-series classification[D].University of Hildesheim,Germany,2011
[11] Chan K,Fu A W.Efficient time series matching by wavelets[C]∥Proceedings of the 15th International Conference on Data Engineering (ICDE 1999).1999:126-133
[12] Cheng H,Yan X,Han J,et al.Discriminative frequent patternanalysis for effective classification[C]∥Proceedings of the 23rd International Conference on Data Engineering (ICDE 2007).2007:716-725
[13] Cheng H,Yan X,Han J,et al.Direct discriminative pattern mi-ning for effective classification[C]∥Proceedings of the 24th International Conference on Data Engineering (ICDE 2008).2008:169-178
[14] Chiu B,Keogh E,Lonardi S.Probabilistic discovery of time series motifs[C]∥Proceedings of the 9th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD 2003).2003:493-498
[15] Cong G,Tan K,Tung A,et al.Mining top-k covering rulegroups for gene expression data[C]∥Proceedings of the ACM SIGMOD International Conference on Management of Data.2005:670-681
[16] Das G,Lin K,Mannila H,et al.Rule discovery from time series[C]∥Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining (KDD98).1998:16-22
[17] Deng K,Moore A W,Nechyba M C.Learning to recognize time series:combining ARMA models with memory-based learning[C]∥Proceedings of the IEEE International Symposium on Computational Intelligence in Robotics and Automation.1997:246-251
[18] Deng H,Runger G,Tuv E,et al.A time series forest for classification and feature extraction[J].Information Sciences,2013,239:142-153
[19] Deshpande M,Kuramochi M,Karypis G.Frequent sub-struc-ture-based approach for classification chemical compounds[C]∥Proceedings of the IEEE International Conference on Data Mi-ning (ICDM 2003).2003:35-42
[20] Ding H,Trajcevski G,Scheuermann P,et al.Querying and mi-ning of time series data:experimental comparison of representations and distance measures[C]∥Proceedings of the 34th International Conference on Very Large Data Bases (VLDB 2008).2008:1542-1552
[21] Douzal-Chouakria A,Amblard C.Classification trees for time series[J].Pattern Recognition,2012,45:1076-1091
[22] Esling P,Agon C.Time-series data mining[J].ACM Computing Surveys,2012,45(1):12
[23] Faloutsos C,Ranganathan M,Manolopoulos Y.Fast subse-quence matching in time-series databases[C]∥Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data.1994:419-429
[24] Fu A,Keogh E,Lau L,et al.Scaling and time warping in time series querying[J].The VLDB Journal,2008,17(4):899-921
[25] Fu T.A review on time series data mining[J].Engineering Applications of Artificial Intelligence,2011,24:164-181
[26] Hartmann B,Link N.Gesture recognition with inertial sensorsand optimized dtw prototypes[C]∥Proceedings of IEEE International Conference on Systems Man and Cybernetics (SMC).2010:2102-2109
[27] Hills J,Lines J,Baranauskas E,et al.Time series classification with shapelets[J].Data Mining and Knowledge Discovery,2013,27(1)
[28] Hu M,Liu B.Opinion feature extraction using class sequential rules[C]∥AAAI Spring Symposium:Computational Approaches to Analyzing Weblogs.2006:61-66
[29] Jeong Y,Jeong M,Omitaomu O.Weighted dynamic time war-ping for time series classification[J].Pattern Recognition,2011,44 (9):2231-2240
[30] Kalpakis K,Gada D,Andputtagunta V.Distance measures foreffective clustering of ARIMA time series[C]∥Proceedings of the IEEE International Conference on Data Mining (ICDM 2001).2001:273-280
[31] Keogh E,Pazzani M.An enhanced representation of time series which allows fast and accurate classification,clustering and relevance feedback[C]∥Proceedings of the 4th International Conference of Knowledge Discovery and Data Mining.1998:239-241
[32] Keogh E,Chakrabarti K,Pazzani M,et al.Dimensionality reduction for fast similarity search in large time series databases[J].Knowledge for Information System,2001,3(3):263-286
[33] Keogh E,Chu S,Hart D,et al.An online algorithm for segmenting time series[C]∥Proceedings of the 2001 IEEE InternationalConference on Data Mining (ICDM 2001).2001:289-296
[34] Keogh E,Kasetty S.On the need for time series data miningbenchmarks:a survey and empirical demonstration[J].Data Mining and Knowledge Discovery,2003,7(4):349-371
[35] Keogh E,Ratanamahatana C A.Exact indexing of dynamic time warping[J].Knowledge and Information Systems,2004,7(3):358-386
[36] Li W,Han J,Pei J.CMAR:Accurate and efficient classification based on multiple-class association rules[C]∥Proceedings of the 2001 IEEE International Conference on Data Mining.2001:369-376
[37] Liabotis I,Theodoulidis B,Saraee M.Improving similaritysearch in time series using wavelets[J].International Journal of Data Warehousing and Mining,2006,2 (2):1116-1137
[38] Lin J,Keogh E,Lonardi S,et al.Finding motifs in time series[C]∥Proceedings of 2nd Workshop on Temporal Data Mining at KDD.2002:53-68
[39] Lin J,Keogh E J,Wei L,et al.Experiencing SAX:a novel symbolic representation of time series[J].Data Mining Knowledge Discovery,2007,15(2):107-144
[40] Lin T,Kaminski N,Bar-Joseph Z.Alignment and classification of time series gene expression in clinical studies[J].Bioinforma-tics,2008,24(13):147-155
[41] Lines J,Bagnall A,Caiger-Smith P,et al.Classification of household devices by electricity usage profiles[C]∥Proceedings of the 12th International Conference on Intelligent Data Engineering and Automated Learning (IDEAL 2011).2011:403-412
[42] Lines J,Davis L M,Hills J,et al.A shapelet transform for time series classification[C]∥Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2012).2012:289-297
[43] Liu B,Hsu W,Ma Y.Integrating classification and associationrule mining[C]∥Proceedings of the Fourth International Conference on Knowledge Disco-very and Data Mining (KDD 1998).1998:80-86
[44] McGovern A,Rosendahl D,Brown R,et al.Identifying predictive multi-dimensional time series motifs:an application to severe weather prediction[J].Data Mining and Knowledge Disco-very,2011,22:232-258
[45] Mueen A,Keogh E,Zhu Q,et al.Exact discovery of time series motifs[C]∥Proceedings of the SIAM International Conference on data mining (SDM 2009).2009:473-484
[46] Mueen A,Keogh E,Shamlo N.Finding time series motifs indisk-resident data[C]∥Proceedings of the 9th IEEE International Conference on Data Mining (ICDM 2009).2009:367-376
[47] Mueen A,Keogh E J,Young N.Logical-shapelets:an expressive primitive for time series classification[C]∥Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2011).2011:1154-1162
[48] Nanopoulos A,Alcock R,Andmanolopoulos Y.Feature-basedclassification of time-series data[J].International Journal of Computer Research,2001,10:49-61
[49] Popivanov I,Miller R J.Similarity search over time-series data using wavelets[C]∥Proceedings of the 18th International Conference on Data Engineering (ICDE 2002).2002:212-221
[50] Povinelli R J,Johnson M T,Lindgren A C,et al.Time series classification using Gaussian mixture models of reconstructed phase spaces[J].IEEE Transactions on Knowledge and Data Engineering,2004,6(16):779-783
[51] Rakthanmanon T,Campana B,Mueen A,et al.Searching andmining trillions of time series subsequences under dynamic time warping[C]∥Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2012).2012:262-270
[52] Rakthanmanon T,Keogh E.Fast shapelets:a scalable algorithm for discovering time series shapelets[C]∥Proceedings of the 13th SIAM International Conference on Data Mining (SDM13).2013:668-676
[53] Ratanamahatana C A,Keogh E,Bagnall A J,et al.A novel bit level time series representation with implications for similarity search and clustering[C]∥Proceedings of 9th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining (PAKDD 2005).2005:771-777
[54] Ting J,Fu T C,Chung F L.Mining of stock data:intra- and inter-stock pattern associative classification[C]∥Proceedings of the 2006 International Conference on Data Mining (ICDM 2006).2006:30-36
[55] Veloso A,Meira W,Zaki M J.Lazy associative classification[C]∥Proceedings of the 6th International Conference on Data mining (ICDM 2006).2006:645-654
[56] Wang J,Karypis G.HARMONY:Efficiently mining the bestrules for classification[C]∥Proceedings of the Fifth SIAM International Conference on Data Mining.2005:205-216
[57] Wang X,Mueen A,Ding H,et al.Experimental comparison of representation methods and distance measures for time series data[J].Journal of Data Mining and Knowledge Discovery,2013,26:275-309
[58] Xi X,Keogh E,Shelton C,et al.Fast time series classificationusing numerosity reduction[C]∥Proceedings of the 23th International Conference on Machine Learning (ICML2006).2006:1033-1040
[59] Xing Z,Pei J,Keogh E J.A brief survey on sequence classification[J].SIGKDD Explorations,2010,12(1):40-48
[60] Xing Z,Pei J,Yu P,et al.Extracting interpretable features for early classification on time series[C]∥Proceedings of the 11th SIAM International Conference on Data Mining (SDM 2011).2011:247-258
[61] Xing Z,Pei J,Yu P.Early classification on time series[J].Knowledge-based Information Systems,2012,31(1):105-127
[62] Yamada Y,Suzuki E,Yokoi H,et al.Decision-tree inductionfrom time-series data based on a standard-example split test[C]∥Proceedings of the Twentieth International Conference (ICML 2003).2003:840-847
[63] Yan X F,Han J W.gSpan:Graph-based substructure pattern mining[C]∥Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM 2002).2002:721-724
[64] Ye L,Keogh E J.Time series shapelets:a new primitive for data mining[C]∥Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2009).2009:947-956
[65] Ye L,Keogh E J.Time series shapelets:a novel technique that allows accurate,interpretable and fast classification[J].Data Mining and Knowledge Discovery,2011,22(1/2):149-182
[66] Yin X,Han J.CPAR:Classification based on predictive association rules[C]∥Proceedings of the SIAM International Conference on Data Mining.2003:369-376
[67] Zakaria J,Mueen A,Keogh E.Clustering time series using unsupervised-shapelets[C]∥Proceedings of the 12th IEEE International Conference on Data Mining (ICDM 2012).2012:785-794
[68] Zhong S,Andghosh J.HMMs and coupled HMMs for multi-channel EEG classification[C]∥Proceedings of the IEEE International Joint Conference on Neural Networks.2002:1154-1159

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed