×

A non-parametric symbolic approximate representation for long time series. (English) Zbl 1428.62393

Summary: For long time series, it is crucial to design low-dimensional representations that preserve the fundamental characteristics of a series. However, most of the approximate representations require the setting of many input parameters. The main defect of working with parameter-laden algorithms is that incorrect settings may cause an algorithm to fail in achieving the best performance, which is the ability of reducing the dimensionality and retaining the shape information. This is especially likely when the selection of the suitable parameter is not trivial or easy for the user. In this paper, we introduce a new approximate representation of time series, the non-parametric symbolic approximate representation (NSAR), which is based on multi-scale, the approximate coefficients of discrete wavelet transform (DWT) and key points. The novelty of the proposed representation is firstly that it uses a hierarchical mechanism to retain shape information of the original time series. Next, the proposed representation is symbolic in employing key points and encoding in approximate coefficients, so it can greatly reduce the dimension of the original time series and potentially allows the application of text-based retrieval techniques. The proposed representation is fast, automatic, and with no parameter tuning by user. To show the efficacy of the new representation, we performed experiments with real and synthetic data. Experimental results show that NSAR can preserve more fundamental characteristics of a series than symbolic approximate representation (SAX) in the same compression ratio, automatically determine the optimal decomposition level for DWT, and has better performance than SAX in the best matching queries.

MSC:

62M10 Time series, auto-correlation, regression, etc. in statistics (GARCH)

Software:

TDSL; TSDL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aboy M, Hornero R, Abasolo D, Alvarez D (2006) Interpretation of the Lempel-Ziv complexity measure in the context of biomedical signal analysis. IEEE Trans Biomed Eng 53(11):2282-2288 · doi:10.1109/TBME.2006.883696
[2] Agrawal, R.; Faloutsos, C.; Swami, A.; Lomet, D. (ed.), Efficient similarity search in sequence databases foundations of data organization and algorithms, 69-84 (1993), Berlin/Heidelberg
[3] Bagnall A, Janacek G (2005) Clustering time series with clipped data. Mach Learn 58(2):151-178 · Zbl 1073.68710 · doi:10.1007/s10994-005-5825-6
[4] Bandt C, Pompe B (2002) Permutation entropy: a natural complexity measure for time series. Phys Rev Lett 88(17):174102-174105 · doi:10.1103/PhysRevLett.88.174102
[5] Bao D, Yang Z (2008) Intelligent stock trading system by turning point confirming and probabilistic reasoning. Expert Syst Appl 34(1):620-627 · doi:10.1016/j.eswa.2006.09.043
[6] Batista GEAPA, Wang X, Keogh EJ (2011) A complexity-invariant distance measure for time series. SDM, (SIAM/Omnipress2011), pp 699-710
[7] Berndt DJ, Clifford J (1996) Finding patterns in time series: a dynamic programming approach. In: Usama MF, Gregory P-S, Padhraic S, Ramasamy U (eds) Advances in knowledge discovery and data mining. American Association for Artificial Intelligence, pp 229-248
[8] Carbone A, Castelli G, Stanley HE (2004) Time-dependent Hurst exponent in financial time series. Phys Stat Mech Appl 344(1-2):267-271 · doi:10.1016/j.physa.2004.06.130
[9] Kin-Pong C, Ada Wai-Chee F (1999) Efficient time series matching by wavelets. Data Engineering, 15th international conference on, pp 126-133
[10] Chaovalit P, Gangopadhyay A, Karabatis G, Chen Z (2011) Discrete wavelet transform-based time series analysis and mining. ACM Comput Surv 43(2):1-37 · Zbl 1293.68218 · doi:10.1145/1883612.1883613
[11] Chen L, Tamer M, Oria V (2005) Robust and fast similarity search for moving object trajectories. In: Proceedings of the 2005 ACM SIGMOD international conference on Management of data, (ACM, Baltimore, Maryland), pp 491-502
[12] Chen L, Tamer M, Oria V (2005) Using multi-scale histograms to answer pattern existence and shape match queries. In: Proceedings of the 17th international conference on Scientific and statistical database management, Lawrence Berkeley Laboratory, Santa Barbara, CA, pp 217-226
[13] Chen Q, Chen L, Lian X, Liu Y, Yu JX (2007) Indexable PLA for efficient similarity search. In: Proceedings of the 33rd international conference on very large data bases, VLDB Endowment, Vienna, Austria, pp 435-446
[14] Fu-lai C, Tak-chung F, Luk R, Ng V (2002) Evolutionary time series segmentation for stock data mining, IEEE international conference on data mining, 2002, pp 83-90
[15] Daw CS, Finney CEA, Kennel MB (2000) Symbolic approach for measuring temporal “irreversibility”. Phys Rev E 62(2):1912-1921 · doi:10.1103/PhysRevE.62.1912
[16] Ding H, Trajcevski G, Scheuermann P, Wang X, Keogh E (2008) Querying and mining of time series data: experimental comparison of representations and distance measures. Proc VLDB Endow 1(2):1542-1552 · doi:10.14778/1454159.1454226
[17] Keogh XXE, Wei L, Ratanamahatana C (2011) The UCR time series classification/clustering homepage. http://www.cs.ucr.edu/ eamonn/time_series_data
[18] Fink E, Gandhi HS (2011) Compression of time series by extracting major extrema. J Exp Theor Artif Intell 23(2):255-270 · doi:10.1080/0952813X.2010.505800
[19] Fink E, Pratt KB, Gandhi HS (2003) Indexing of time series by major minima and maxima, systems, man and cybernetics, 2003 IEEE International Conference on, vol. 2333, pp 2332-2335
[20] Tak-chung F (2011) A review on time series data mining. Eng Appl Artif Intell 24(1):164-181 · doi:10.1016/j.engappai.2010.09.007
[21] Graps A (1995) An introduction to wavelets. IEEE Comput Sci Eng 2(2):50-61 · doi:10.1109/99.388960
[22] Keogh E, Ratanamahatana CA (2005) Exact indexing of dynamic time warping. Knowl Inf Syst 7(3):358-386 · doi:10.1007/s10115-004-0154-9
[23] Keogh E, Chakrabarti K, Pazzani M, Mehrotra S (2001) Dimensionality reduction for fast similarity search in large time series databases. Knowl Inf Syst 3(3):263-286 · Zbl 0989.68039 · doi:10.1007/PL00011669
[24] Keogh E, Chu S, Hart D, Pazzani M (2001) An online algorithm for segmenting time series. IEEE international conference on, data mining, 2001. pp 289-296
[25] Keogh E, Lin J, Fu A (2005) HOT SAX: efficiently finding the most unusual time series subsequence, Fifth IEEE international conference on, data mining. pp. 226-233
[26] Keogh E, Wei L, Xi X, Lee S-H, Vlachos M (2006) LB_Keogh supports exact indexing of shapes under rotation invariance with arbitrary representations and distance measures. In: Proceedings of the 32nd international conference on very large data bases, VLDB Endowment, Seoul, Korea, pp 882-893
[27] Korn F, Jagadish HV, Faloutsos C (1997) Efficiently supporting ad hoc queries in large datasets of time sequences. SIGMOD Rec 26(2):289-300 · doi:10.1145/253262.253332
[28] Lin J, Keogh E, Lonardi S, Chiu B (2003) A symbolic representation of time series, with implications for streaming algorithms. In: Proceedings of the 8th ACM SIGMOD workshop on research issues in data mining and knowledge discovery, pp 2-11
[29] Lin J, Keogh E, Wei L, Lonardi S (2007) Experiencing SAX: a novel symbolic representation of time series. Data Min Knowl Disc 15(2):107-144 · doi:10.1007/s10618-007-0064-z
[30] Megalooikonomou V, Wang Q, Li G, Faloutsos C (2005) A multiresolution symbolic representation of time series. 21st International conference on data engineering, pp 668-679
[31] Perng CS, Wang H, Zhang SR, Parker DS (2000) Landmarks: a new model for similarity-based pattern querying in time series databases. 16th international conference on data engineering, pp 33-42
[32] Pincus SM, Goldberger AL (1994) Physiological time-series analysis: what does regularity quantify? Am J Physiol Heart Circ Physiol 266(4):H1643-H1656
[33] Pratt KB, Fink E (2002) Search for patterns in compressed time series. Int J Image Graph 2(1):89 · doi:10.1142/S0219467802000482
[34] Ratanamahatana, C.; Keogh, E.; Bagnall, A.; Lonardi, S.; Ho, T. (ed.); Cheung, D. (ed.); Liu, H. (ed.), A novel bit level time series representation with implication of similarity search and clustering, No. 3518, 771-777 (2005), Berlin Heidelberg · doi:10.1007/11430919_90
[35] Richman JS, Moorman JR (2000) Physiological time-series analysis using approximate entropy and sample entropy. Am J Physiol Heart Circ Physiol 278(6):H2039-H2049
[36] Hyndman RJ (2011) Time series data library. http://robjhyndman.com/TSDL
[37] Shahabi C, Tian X, Zhao W (2000) TSA-tree: a wavelet-based approach to improve the efficiency of multi-level surprise and trend queries on time-series data. Scientific and statistical database management, 12th International conference, pp 55-68
[38] Shieh J, Keogh E (2009) iSAX: disk-aware mining and indexing of massive time series datasets. Data Min Knowl Disc 19(1):24-57 · doi:10.1007/s10618-009-0125-6
[39] Zarnowitz V, Ozyildirim A (2006) Time series decomposition and measurement of business cycles, trends and growth cycles. J Monet Econ 53(7):1717-1739 · doi:10.1016/j.jmoneco.2005.03.015
[40] Ziv J, Lempel A (1978) Compression of individual sequences via variable-rate coding. IEEE Trans Inf Theory 24(5):530-536 · Zbl 0392.94004 · doi:10.1109/TIT.1978.1055934
[41] Warren Liao T (2005) Clustering of time series data—a survey. Pattern Recogn 38(11):1857-1874 · Zbl 1077.68803 · doi:10.1016/j.patcog.2005.01.025
[42] Widiputra H, Pears R, Kasabov N (2012) Dynamic learning of multiple time series in a nonstationary environment. In: Sayed-Mouchaweh M, Lughofer E (eds) Learning in non-stationary environments. Springer, Berlin, pp 303-347
[43] Box GE, Jenkins GM, Reinsel GC (2013) Time series analysis: forecasting and control. Wiley, New York
[44] Bloomfield P (2004) Fourier analysis of time series: an introduction. Wiley, New York
[45] Catillo-Ortega RM, Marín N, Sánchez D (2011) A fuzzy approach to the linguistic summarization of time series. J Multiple Valued Logic Soft Comput 17:157-182
[46] Lendasse A, François D, Wertz V, Verleysen M (2005) Vector quantization: a weighted version for time-series forecasting. Future Gener Comput Syst 21(7):1056-1067 · doi:10.1016/j.future.2004.03.006
[47] Lughofer E (2008) Extensions of vector quantization for incremental clustering. Pattern Recogn 41(3):995-1011 · Zbl 1132.68646 · doi:10.1016/j.patcog.2007.07.019
[48] Yoon PJ (2014) The wake-sleep cycle eeg of albino rat. http://www.cacs.louisiana.edu/ jyoon
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.