Grasp heuristic for time series compression with piecewise aggregate approximation
RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 1, pp. 243-259.

The Piecewise Aggregate Approximation (PAA) is widely used in time series data mining because it allows to discretize, to reduce the length of time series and it is used as a subroutine by algorithms for patterns discovery, indexing, and classification of time series. However, it requires setting one parameter: the number of segments to consider during the discretization. The optimal parameter value is highly data dependent in particular on large time series. This paper presents a heuristic for time series compression with PAA which minimizes the loss of information. The heuristic is built upon the well known metaheuristic GRASP and strengthened with an inclusion of specific global search component. An extensive experimental evaluation on several time series datasets demonstrated its efficiency and effectiveness in terms of compression ratio, compression interpretability and classification.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2018089
Classification : 90C59
Mots-clés : Time series, optimization, compression, classification
Siyou Fotso, Vanel Steve 1 ; Mephu Nguifo, Engelbert 1 ; Vaslin, Philippe 1

1 
@article{RO_2019__53_1_243_0,
     author = {Siyou Fotso, Vanel Steve and Mephu Nguifo, Engelbert and Vaslin, Philippe},
     title = {Grasp heuristic for time series compression with piecewise aggregate approximation},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {243--259},
     publisher = {EDP-Sciences},
     volume = {53},
     number = {1},
     year = {2019},
     doi = {10.1051/ro/2018089},
     zbl = {1414.90365},
     mrnumber = {3911629},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2018089/}
}
TY  - JOUR
AU  - Siyou Fotso, Vanel Steve
AU  - Mephu Nguifo, Engelbert
AU  - Vaslin, Philippe
TI  - Grasp heuristic for time series compression with piecewise aggregate approximation
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2019
SP  - 243
EP  - 259
VL  - 53
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2018089/
DO  - 10.1051/ro/2018089
LA  - en
ID  - RO_2019__53_1_243_0
ER  - 
%0 Journal Article
%A Siyou Fotso, Vanel Steve
%A Mephu Nguifo, Engelbert
%A Vaslin, Philippe
%T Grasp heuristic for time series compression with piecewise aggregate approximation
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2019
%P 243-259
%V 53
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2018089/
%R 10.1051/ro/2018089
%G en
%F RO_2019__53_1_243_0
Siyou Fotso, Vanel Steve; Mephu Nguifo, Engelbert; Vaslin, Philippe. Grasp heuristic for time series compression with piecewise aggregate approximation. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 1, pp. 243-259. doi : 10.1051/ro/2018089. http://www.numdam.org/articles/10.1051/ro/2018089/

[1] A. Bagnall, E. Keogh, J. Lines, A. Bostrom, J. Large, Time Series Classification Website. Available at: http://timeseriesclassification.com (2016).

[2] A. Bagnall, J. Lines, A. Bostrom, J. Large, E. Keogh, The great time series classification bake off: a review and experimental evaluation of recent algorithmic advances. Data Min. Knowl. Discov. 31 (2017) 606–660. | DOI | MR

[3] A. Camerra, T. Palpanas, J. Shieh, E. Keogh, isax 2.0: Indexing and mining one billion time series. In: 2010 IEEE 10th International Conference on Data Mining – ICDM (2010) 58–67. | DOI

[4] K.S. Candan, R. Rossini, X. Wang, M.L. Sapino, sdtw: computing dtw distances using locally relevant constraints based on salient feature alignments. VLDB Endowment 5 (2012) 1519–1530. | DOI

[5] Y. Chen, E. Keogh, B. Hu, N. Begum, A. Bagnall, A. Mueen, G. Batista, The UCR time series classification archive. Available at: http://www.cs.ucr.edu/~eamonn/time_series_data/ (2015).

[6] S. Chu, E.J. Keogh, D.M. Hart, M.J. Pazzani, et al., Iterative deepening dynamic time warping for time series. In: Proc. of the 2002 SIAM International Conference on Data Mining. SIAM (2002) 195–212. | DOI

[7] J. Cuřín, P. Fleury, J. Kleindienst, R. Kessl, Meeting state recognition from visual and aural labels. In: Learning for Multimodal Interaction, Springer, 2007, 24–25.

[8] T.A. Feo, M.G. Resende, Greedy randomized adaptive search procedures. J. Glob. Optim. 6 (1995) 109–133. | DOI | MR | Zbl

[9] O.H. Ibarra, C.E. Kim, Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM (JACM) 22 (1975) 463–468. | DOI | MR | Zbl

[10] Itakura, F., Minimum prediction residual principle applied to speech recognition. IEEE Trans. Acoust. Speech Signal Process. 23 (1975) 67–72. | DOI

[11] Y.S. Jeong, M.K. Jeong, O.A. Omitaomu, Weighted dynamic time warping for time series classification. Pattern Recogn. 44 (2011) 2231–2240. | DOI

[12] R.J. Kate, Using dynamic time warping distances as features for improved time series classification. Data Min. Knowl. Discov. 30 (2016) 283–312. | DOI | MR | Zbl

[13] E. Keogh, K. Chakrabarti, M. Pazzani, S. Mehrotra, Dimensionality reduction for fast similarity search in large time series databases. Knowl. Inform. Syst. 3 (2001) 263–286. | DOI | Zbl

[14] E.J. Keogh, M.J. Pazzani, Scaling up dynamic time warping for datamining applications. In: Sixth ACM SIGKDD. ACM (2000) 285–289. | DOI

[15] E.J. Keogh, M.J. Pazzani, Derivative dynamic time warping. In: 1st SIAM International Conference on Data Mining. SIAM (2001) 1–11.

[16] J. Lin, E. Keogh, S. Lonardi, B. Chiu, A symbolic representation of time series, with implications for streaming algorithms. In: 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery. ACM (2003) 2–11.

[17] B. Lkhagva, Y. Suzuki, K. Kawagoe, Extended SAX: Extension of Symbolic aggregate approximation for financial time series data representation. DEWS2006 4A–i8, 7 (2006).

[18] J. Longin, M. Vasilis, W. Qiang, L. Rolf, A. Chotirat, E. Keogh, Elastic partial matching of time series. In: 9th European Conference on Principles and Practice of Knowledge Discovery in Databases, Porto, Portugal (2005).

[19] C. Myers, L. Rabiner, A. Rosenberg, Performance tradeoffs in dynamic time warping algorithms for isolated word recognition. IEEE Trans. Acoust. Speech Signal Process. 28 (1980) 623–635. | DOI | Zbl

[20] T. Rakthanmanon, B. Campana, A. Mueen, G. Batista, B. Westover, Q. Zhu, J. Zakaria, E. Keogh, Searching and mining trillions of time series subsequences under dynamic time warping. In: 18th ACM SIGKDD (2012) 262–270.

[21] C.A. Ratanamahatana, E. Keogh, Making time-series classification more accurate using learned constraints. In: Proc. of the 2004 SIAM International Conference on Data Mining. SIAM (2004) 11–22. | DOI | MR

[22] H. Sakoe, S. Chiba, Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans. Acoust. Speech Signal Process. 26 (1978) 43–49. | DOI | Zbl

[23] S. Salvador, P. Chan, Toward accurate dynamic time warping in linear time and space. Intell. Data Anal. 11 (2007) 561–580. | DOI

[24] V.S. Siyou Fotso, E. Mephu Nguifo, P. Vaslin, Comparaison des Algorithmes de classification. FDTW. Available at: http://fc.isima.fr/~siyou/fdtw (2016).

[25] Y. Sun, J. Li, J. Liu, B. Sun, C. Chow, An improvement of Symbolic aggregate approximation distance measure for time series. Neurocomputing 138 (2014) 189–198. | DOI

[26] L. Ulanova, N. Begum, E. Keogh, Scalable clustering of time series with u-shapelets, In: 2015 SIAM International Conference on Data Mining. SIAM (2015) 900–908. | DOI

[27] X. Wang, A. Mueen, H. Ding, G. Trajcevski, P. Scheuermann, E. Keogh, Experimental comparison of representation methods and distance measures for time series data. Data Min. Knowl. Discov. 26 (2013) 275–309. | DOI | MR

[28] D. Yu, X. Yu, Q. Hu, J. Liu, A. Wu, Dynamic time warping constraint learning for large margin nearest neighbor classification. Inform. Sci. 181 (2011) 2787–2796. | DOI

[29] Z. Zhang, P. Tang, R. Duan, Dynamic time warping under pointwise shape context. Inform. Sci. 315 (2015) 88–101. | DOI | MR

[30] J. Zhao, L. Itti, Shapedtw: shape dynamic time warping. Preprint arXiv: 1606.01601 (2016).

Cité par Sources :