Computer Science ›› 2023, Vol. 50 ›› Issue (2): 146-157.doi: 10.11896/jsjkx.211200065

• Database & Big Data & Data Science • Previous Articles     Next Articles

Study on Time Series Shapelets Extraction Based on Optimization and Two-phase Filtering

LI Chen, WAN Yuan   

  1. School of Science,Wuhan University of Technology,Wuhan 430070,China
  • Received:2021-12-06 Revised:2022-04-22 Online:2023-02-15 Published:2023-02-22
  • Supported by:
    Fundamental Research Funds for the Central Universities of Ministry of Education of China(2021III030JC)

Abstract: Compared with the time series classification methods based on global features,the shapelet-based methods have more advantages in interpretability,efficiency and accuracy.In order to solve the problems of insufficient discrimination of shapelets obtained from existing sparse models and the large scale of shapelets candidates,this paper proposes a shapelets extraction method based on optimization and two-phase filtering.First,the time series are sampled,and the sampled time series are grouped by combining the extreme points and the trend,then the weight of each item in the sparse group lasso regularizer are assigned according to the grouping results.The fused penalty regularization is used in each group of the weighted sparse group lasso to ensure that the adjacent positions of the solution change smoothly.Those sparse regularization terms are combined as constraints to construct the objective function together with the local fisher discriminant analysis.Then,a two-phase filtering framework is established to measure the sparsity of groups,so as to quickly locate the key group that plays a decisive role in classification.Finally,this key group is retained to extract shapelets for time series classification,which reduces the candidates of shapelets.Extensive experiments are carried out on 28 datasets,and the experimental results show that,compared with the existing shapelets-based extraction methods,the proposed method significantly improves the classification accuracy with a good efficiency,and reduces the scale of shapelets to a certain extent.

Key words: Shapelets, Two-phase filtering framework, Weighted sparse group Lasso, Fused penalty, Key group

CLC Number: 

  • TP391
[1]AU YEUNG J F K,WEI Z K,CHAN K Y,et al.Jump Detection in Financial Time Series Using Machine Learning Algorithms[J].Soft Computing,2020,24(3):1789-1801.
[2]AL-HADEETHI H,ABDULLA S,DIYKH M,et al.Adaptive Boost LS-SVM Classification Approach for Time-Series Signal Classification in Epileptic Seizure Diagnosis Applications[J].Expert Systems with Applications,2020,161:113676.
[3]ARUL M,KAREEM A.Applications of Shapelet Transform to Time Series Classification of Earthquake,Wind and Wave Data[J].Engineering Structures,2021,228:111564.
[4]AHMED T,SINGH D.Probability Density Functions BasedClassification of MODIS NDVI Time Series Data and Monitoring of Vegetation Growth Cycle[J].Advances in Space Research,2020,66(4):873-886.
[5]LI H L,LIANG Y,WANG S C.Reviewon Dynamic Time Warping in Time Series Data Mining[J].Control and Decision,2018,33(8):1345-1353.
[6]RATANAMAHATANA C A,KEOGH E J.Three Myths about Dynamic Time Warping Data Mining[C]//Proceedings of the 2005 SIAM International Conference on Data Mining.2005:506-510.
[7]DING H,TRAJCEVSKI G,SCHEUERMANN P,et al.Querying and Mining of Time Series Data:Experimental Comparison of Representations and Distance Measures[J].Proceedings of the VLDB Endowment,2008,1(2):1542-1552.
[8]YE L,KEOGH E.Time SeriesShapelets:A New Primitive for Data Mining[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2009:947-956.
[9]KRUSKAL W H.A Nonparametric Test for the Several Sample Problem[J].Annals of Mathematical Statistics,1952,23(4):525-540.
[10]THEOBALD R B C M.Introduction tothe Theory of Statistics[J].Journal of the Royal Statistical Society Series A(General),1974,137(1):95-96.
[11]HILLS J,LINES J,BARANAUSKAS E,et al.Classification of Time Series by Shapelet Transformation[J].Data Mining and Knowledge Discovery,2014,28(4):851-881.
[12]MUEEN A,KEOGH E,YOUNG N.Logical-Shapelets:An Expressive Primitive for Time Series Classification[C]//Procee-dings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2011:1154-1162.
[13]LIN J,KEOGH E,WEI L,et al.Experiencing SAX:A Novel Symbolic Representation of Time Series[J].Data Mining and Knowledge Discovery,2007,15(2):107-144.
[14]YAHYAOUI H,AL-DAIHANI R.A Novel Trend Based SAX Reduction Technique for Time Series[J].Expert Systems with Applications,2019,130:113-123.
[15]PARK H,JUNG J Y.SAX-ARM:Deviant Event Pattern Discovery from Multivariate Time Series Using Symbolic Aggregate Approxima-tion and Association Rule Mining[J].Expert Systems with Applications,2020,141:112950.
[16]BUHLER J,TOMPA M.Finding Motifs Using Random Projections[J].Journal of Computational Biology,2002,9(2):225-242.
[17]RAKTHANMANON T,KEOGH E.Fast shapelets:A Scalable Algorithm for Discovering Time Series Shapelets[C]//Procee-dings of the 2013 SIAM International Conference on Data Mi-ning.2013:668-676.
[18]WISTUBA M,GRABOCKA J,SCHMIDT-THIEME L.Ultra-Fast Shapelets for Time Series Classifi-cation[J].arXiv:1503.05018,2015.
[19]GORDON D,HENDLER D,ROKACH L.Fast and Space-Efficient Shapelets-Based Time-Series Classification[J].Intelligent Data Analysis,2015,19(5):953-981.
[20]LI Z S,HE Z F.Time Series Shapelet Extraction Based on Principal Component Analysis[J].Computer Systems Applications,2014,23(11):145-149.
[21]GRABOCKA J,SCHILLING N,WISTUBA M,et al.Learning Time-Series Shapelets[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2014:392-401.
[22]HOU L,KWOK J,ZURADA J.Efficient Learning of Timeseries Shapelets[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2016:1209-1215.
[23]KARAMPATZIAKIS N,MINEIRO P.Discriminative Features Via Generalized Eigenvectors[C]//International Conference on Machine Learning.2014:494-502.
[24]TIBSHIRANI R,SAUNDERS M,ROSSET S,et al.Sparsityand Smoothness Via the Fused Lasso[J].Journal of the Royal Statistical Society:Series B(Statistical Methodology),2005,67(1):91-108.
[25]ZHANG Z,ZHANG H,WEN Y,et al.Discrimina-tive Extraction of Features from Time Series[J].Neurocomputing,2018,275:2317-2328.
[26]SUGIYAMA M.Local Fisher Discriminant Analysis for Supervised Dimensionality Reduction[C]//Proceedings of the 23rd International Conference on Machine Learning.2006:905-912.
[27]WANG Y,EMONET R,FROMONT E,et al.Learning Inter-pretable Shapelets for Time Series Classification through Adversarial Regularization[J].arXiv:1906.00917,2019.
[28]WANG Z,YAN W,OATES T.Time Series Classification from Scratch with Deep Neural Networks:A Strong Baseline[C]//2017 International Joint Conference on Neural Networks.2017:1578-1585.
[29]ZHAO H Y,PAN Z S.Multivariate Time Series Classification Based on Shapelets Learning[J].Computer Science,2018,45(5):180-184,219.
[30]SIMON N,FRIEDMAN J,HASTIE T,et al.A Sparse-GroupLasso[J].Journal of Computational and Graphical Statistics,2013,22(2):231-245.
[31]TIBSHIRANI R.Regression Shrinkage and Selection Via theLasso[J].Journal of the Royal Statistical Society:Series B(Methodological),1996,58(1):267-288.
[32]YUAN M,LIN Y.Model Selection and Estimation in Regression with Grouped Variables[J].Journal of the Royal Statistical Society:Series B(Statistical Methodology),2006,68(1):49-67.
[33]JI C,ZHAO C,LIU S,et al.A Fast Shapelet Selection Algorithm for Time Series Classification[J].Computer Networks,2019,148:231-240.
[34]ZHAO C,WANG T J,LIU S J,et al.A Fast Time Series Shapelet Discovery Algorithm Combining Selective Extraction and Subclass Clustering[J].Journal of Software,2020,31(3):763-777.
[35]FRIEDMAN J H.Regularized Discriminant Analysis[J].Journal of the American Statistical Association,1989,84(405):165-175.
[1] ZHAO Hui-yun and PAN Zhi-song. Multivariate Time Series Classification Based on Shapelets Learning [J]. Computer Science, 2018, 45(5): 180-184.
[2] DING Jian and WANG Shu-ying. Incremental Time Series Classification Algorithm Based on Shapelets [J]. Computer Science, 2016, 43(5): 257-260.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!