Shapelet Classification Algorithm Based on Efficient Subsequence Matching

Huiqing Wang; Chun Li; Hongwei Sun; Zhirong Guo; Yingying Bai

doi:10.5334/dsj-2018-006

Abstract

Shapelet classification algorithms are an accurate classification method for time series data. Existing shapelet classifying processes are relatively inefficient and slow due to the large amount of necessary complex distance computations. This paper therefore introduces piecewise aggregate approximation(PAA) representation and an efficient subsequence matching algorithm for shapelet classification algorithms; the paper also proposes shapelet transformation classification algorithm based on efficient series matching. First, the proposed algorithm took the PAA representation for appropriate dimension reduction, and then used a subsequence matching algorithm to simplify the data classification process. The research experimented on 14 public time series datasets taken from UCI and UCR, used the original and new algorithm for classification, and compared the efficiency and accuracy of the two methods. Experimental results showed that the efficient subsequence matching algorithm could be combined with the shapelet classification algorithm; the new algorithm could ensure relatively high classification accuracy, effectively simplified the algorithm calculation process, and improved classification efficiency.

References

Aghabozorgi, S and Wah, T Y 2014 Clustering of large time series datasets. Intelligent Data Analysis, 18(5): 793–817.
Search in Google Scholar Back to article
Aljumeily, D and Hussain, A J 2015 The performance of immune-based neural network with financial time series prediction. Cogent Engineering, 2(1): 985005.
Search in Google Scholar Back to article
Bagnall, A, Davis, L, Hills, J and Lines, J 2012 Transformation Based Ensembles for Time Series Classification. DOI: 10.1137/1.9781611972825.27
Open DOI Search in Google Scholar Back to article
Batista, G E A P A, Wang, X and Keogh, E J 2011 A Complexity-Invariant Distance Measure for Time Series. In: Eleventh Siam International Conference on Data Mining, 699–710. SDM 2011, April 28–30, Mesa, Arizona, Usa. DOI: 10.1137/1.9781611972818.60
Open DOI Search in Google Scholar Back to article
Begum, N and Keogh, E 2014 Rare time series motif discovery from unbounded streams, VLDB Endowment. DOI: 10.14778/2735471.2735476
Open DOI Search in Google Scholar Back to article
Bettaiah, V and Ranganath, H S 2014 An effective subsequence-to-subsequence time series matching approach. In: Science and Information Conference, 112–122. DOI: 10.1109/SAI.2014.6918179
Open DOI Search in Google Scholar Back to article
Buza, K A 2011 Fusion methods for time-series classification, Ph.D. thesis. University of Hildesheim, Germany.
Search in Google Scholar Back to article
Deng, H, Runger, G, Tuv, E and Vladimir, M 2013 A time series forest for classification and feature extraction. Information Sciences, 239(4): 142–153. DOI: 10.1016/j.ins.2013.02.030
Open DOI Search in Google Scholar Back to article
Ding, H, Trajcevski, G, Scheuermann, P, Wang, X and Keogh, E 2008 Querying and mining of time series data. Proceedings of the Vldb Endowment, 1(2): 1542–1552. DOI: 10.14778/1454159
Open DOI Search in Google Scholar Back to article
Esling, P and Agon, C 2012 Time-series data mining. Acm Computing Surveys, 45(1): 1–34. DOI: 10.1145/2379776.2379788
Open DOI Search in Google Scholar Back to article
Hartmann, B and Link, N 2010 Gesture recognition with inertial sensors and optimized DTW prototypes. In: IEEE International Conference on Systems Man and Cybernetics, 2102–2109.
Search in Google Scholar Back to article
He, Q, Dong, Z, Zhuang, F, Shang, T and Shi, Z 2012 Fast Time Series Classification Based on Infrequent Shapelets. In: International Conference on Machine Learning and Applications, 215–219. DOI: 10.1109/ICMLA.2012.44
Open DOI Search in Google Scholar Back to article
Hills, J, Lines, J, Baranauskas, E, Mapp, J and Bagnall, A 2014 Classification of time series by shapelet transformation. Data Mining & Knowledge Discovery, 28(4): 851–881.
Search in Google Scholar Back to article
Jeong, Y S, Jeong, M K and Omitaomu, O A 2011 Weighted dynamic time warping for time series classification. Pattern Recognition, 44(9): 2231–2240. DOI: 10.1016/j.patcog.2010.09.022
Open DOI Search in Google Scholar Back to article
Lines, J and Bagnall, A 2012 Alternative quality measures for time series shapelets, Intelligent data engineering and automated learning (IDEAL), Lect Notes Comput Sci 7435, 475–483.
Search in Google Scholar Back to article
Lines, J, Davis, L M, Hills, J and Bagnall, A 2012 A shapelet transform for time series classification. In: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 289–297. DOI: 10.1145/2339530.2339579
Open DOI Search in Google Scholar Back to article
Mueen, A, Keogh, E and Young, N 2011 Logical-shapelets:an expressive primitive for time series classification. In: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1154–1162. DOI: 10.1145/2020408.2020587
Open DOI Search in Google Scholar Back to article
Petitjean, F, Forestier, G, Webb, G I, Nicholson, A E, Chen, Y and Keogh, E 2015 Dynamic Time Warping Averaging of Time Series Allows Faster and More Accurate Classification. In: IEEE International Conference on Data Mining, 470–479. DOI: 10.1109/ICDM.2014.27
Open DOI Search in Google Scholar Back to article
Rakthanmanon, T, Campana, B, Mueen, A, Batista, G, Westover, B, Zhu, Q, Zakaria, J and Keogh, E 2012 Searching and mining trillions of time series subsequences under dynamic time warping. In: Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, 262–270. DOI: 10.1145/2339530.2339576
Open DOI Search in Google Scholar Back to article
Rakthanmanon, T and Keogh, E 2013 Fast shapelets: A scalable algorithm for discovering time series shapelets. Proceedings of the 2013 SIAM International Conference on Data Mining. DOI: 10.1137/1.9781611972832.74
Open DOI Search in Google Scholar Back to article
Shajina, T and Sivakumar, P B 2012 Human Gait Recognition and Classification Using Time Series Shapelets. In: International Conference on Advances in Computing and Communications, 31–34. DOI: 10.1109/ICACC.2012.8
Open DOI Search in Google Scholar Back to article
Ye, L and Keogh, E 2009 Time series shapelets: a new primitive for data mining. In: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 947–956. Paris, France, June 28–July. DOI: 10.1145/1557019.1557122
Open DOI Search in Google Scholar Back to article
Ye, L and Keogh, E 2011 Time series shapelets: a novel technique that allows accurate, interpretable and fast classification. Data Mining & Knowledge Discovery, 22(1–2): 149–182.
Search in Google Scholar Back to article

Shapelet Classification Algorithm Based on Efficient Subsequence Matching

Abstract

Paradigm

My account