Symbolic representation based on trend features for knowledge discovery in long time series

Abstract

The symbolic representation of time series has attracted much research interest recently. The high dimensionality typical of the data is challenging, especially as the time series becomes longer. The wide distribution of sensors collecting more and more data exacerbates the problem. Representing a time series effectively is an essential task for decision-making activities such as classification, prediction, and knowledge discovery. In this paper, we propose a new symbolic representation method for long time series based on trend features, called trend feature symbolic approximation (TFSA). The method uses a two-step mechanism to segment long time series rapidly. Unlike some previous symbolic methods, it focuses on retaining most of the trend features and patterns of the original series. A time series is represented by trend symbols, which are also suitable for use in knowledge discovery, such as association rules mining. TFSA provides the lower bounding guarantee. Experimental results show that, compared with some previous methods, it not only has better segmentation efficiency and classification accuracy, but also is applicable for use in knowledge discovery from time series.

Keywords

Long time series / Segmentation / Trend features / Symbolic / Knowledge discovery

References

[1] Agrawal, R., Srikant, R., 1995. Mining sequential patterns. Proc. 11th Int. Conf. on Data Engineering, p.3―14. [

[2] André-Jönsson, H., Badal, D.Z., 1997. Using signature files for querying time-series data. Proc. 1st European Symp. On Principles of Data Mining and Knowledge Discovery, p.211―220. [

[3] Bao, D., Yang, Z., 2008. Intelligent stock trading system by turning point confirming and probabilistic reasoning. Expert Syst. Appl., 34(1): 620―627. [

[4] Borgelt, C., Kruse, R., 2002. Induction of association rules: apriori implementation. Proc. Computational Statistics, p.395―400. [

[5] Bu, Y., Chen, L., Fu, A.W.C., , 2009. Efficient anomaly monitoring over moving object trajectory streams. Proc. 15th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, p.159―168. [

[6] Chan, K.P., Fu, A.W.C., 1999. Efficient time series matching by wavelets. Proc. 15th Int. Conf. on Data Engineering, p.126―133. [

[7] Dasgupta, D., Forrest, S., 1996. Novelty detection in time series data using ideas from immunology. Proc. 5th Int. Conf. on Intelligent Systems, p.82―87.

[8] Esling, P., Agon, C., 2012. Time-series data mining. ACM Comput. Surv., 45(1), Article 12. [

[9] Faloutsos, C., Ranganathan, M., Manolopoulos, Y., 1994. Fast subsequence matching in time-series databases. Proc. ACM SIGMOD Int. Conf. on Management of Data, p.419―429. [

[10] Guimarães, G., Ultsch, A., 1999. A method for temporal knowledge conversion. Proc. 3rd Int. Symp. on Advances in Intelligent Data Analysis, p.369―380. [

[11] Guimarães, G., Peter, J.H., Penzel, T., , 2001. A method for automated temporal knowledge acquisition applied to sleep-related breathing disorders. Artif. Intell. Med., 23(3): 211―237. [

[12] Kadous, M.W., 1999. Learning comprehensible descriptions of multivariate time series. Proc. 16th Int. Conf. of Machine Learning, p.454―463.

[13] Keogh, E., Chakrabarti, K., Pazzani, M., , 2001. Locally adaptive dimensionality reduction for indexing large time series databases. Proc. ACM SIGMOD Int. Conf. on Management of Data, p.151―162. [

[14] Kontaki, M., Papadopoulos, A.N., Manolopoulos, Y., 2005. Continuous trend-based classification of streaming time series. Proc. 9th East European Conf. on Advances in Databases and Information Systems, p.294―308. [

[15] Kontaki, M., Papadopoulos, A.N., Manolopoulos, Y., 2008. Continuous trend-based clustering in data streams. Proc. 10th Int. Conf. on Data Warehousing and Knowledge Discovery, p.251―262. [

[16] Korn, F., Jagadish, H.V., Faloutsos, C., 1997. Efficiently supporting ad hoc queries in large datasets of time sequences. Proc. ACM SIGMOD Int. Conf. on Management of Data, p.289―300. [

[17] Lavielle, M., Teyssière, G., 2006. Detection of multiple change-points in multivariate time series. Lithuan. Math. J., 46(3): 287―306. [

[18] Lin, J., Keogh, E., Lonardi, S., , 2003. A symbolic representation of time series, with implications for streaming algorithms. Proc. 8th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, p.2―11. [

[19] Manganaris, S., 1997. Supervised Classification with Temporal Data. PhD Thesis, Vanderbilt University, USA.

[20] Mannila, H., Toivonen, H., 1996. Discovering generalized episodes using minimal occurrences. Proc. Int. Conf. on Knowledge Discovery and Data Mining, p.146―151.

[21] Mellit, A., Pavan, A.M., Benghanem, M., 2013. Least squares support vector machine for short-term prediction of meteorological time series. Theor. Appl. Climatol., 111(1-2): 297―307. [

[22] Moody, G.B., Mark, R.G., 1983. A new method for detecting atrial fibrillation using RR intervals. Comput. Cardiol., 10: 227―230.

[23] Phetking, C., Noor Md Sap, M., Selamat, A., 2008. A multiresolution important point retrieval method for financial time series representation. Proc. Int. Conf. on Computer and Communication Engineering, p.510―515. [

[24] Poll, S., de Kleer, J., Feldman, A., , 2010. Second international diagnostics competition—DXC’10. Proc. 21st Int. Workshop on Principles of Diagnosis, p.1―15.

[25] Sarkar, S., Mukherjee, K., Sarkar, S., , 2013. Symbolic dynamic analysis of transient time series for fault detection in gas turbine engines. J. Dynam. Syst., Meas. Contr., 135(1): 014506.1―014506.6. [

[26] Villafane, R., Hua, K.A., Tran, D., , 2000. Knowledge discovery from series of interval events. J. Intell. Inform. Syst., 15(1): 71―89. [

[27] Vullings, H.J.L.M., Verhaegen, M.H.G., Verbruggen, H.B., 1997. ECG segmentation using time-warping. Proc. 2nd Int. Symp. on Advances in Intelligent Data Analysis Reasoning about Data, p.275―285. [

[28] Yeh, A.B., Lin, D.K.J., Venkataramani, C., 2004. Unified CUSUM charts for monitoring process mean and variability. Qual. Technol. Quant. Manag., 1(1): 65―86.