Abstract
Piecewise linear representation (PLR) of a time series arises in variety of disciplines in data mining. Unlike most PLR methods who separate a discrete time series into a few discontinuous line segments, \( \ell 1 \) trend filtering method is one of the few PLR methods who generates continuous line segment representations. However, the approximation errors of \( \ell 1 \) trend filtering seldom reach its minimum. In this paper, we propose a binary integer programming model to produce a continuous PLR of time series with the least approximation error, and therefore it is well suitable to analyzing time series with an underlying piecewise linear trend. We describe the motives of the proposed method and give some illustrative examples. The improvement in approximation error is demonstrated by some experiments on some real-world time series datasets.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Keogh, E., Pazzani, M.: An enhanced representation of time series which allows fast and accurate classification, clustering and relevance feedback. In: Proceedings of the 4th International Conference of Knowledge Discovery and Data Mining, pp. 239–241. AAAI Press (1998)
Yang, X., Yu, F., Pedrycz, W.: Long-term forecasting of time series based on linear fuzzy information granules and fuzzy inference system. Int. J. Approximate Reasoning 81, 1–27 (2016)
Zhu, Y., Wu, D., Li, S.: A piecewise linear representation method of time series based on feature points. In: International Conference on Knowledge-based and Intelligent Information and Engineering Systems (2007)
Thurlimann, C.M., Durrenmatt, D.J., Villez, K.: Soft-sensing with qualitative trend analysis for waste water treatment plant control. Control Eng. Pract. 70, 121–133 (2018)
Sammaknejad, N., Huang, B., Fatehi, A., Miao, Y., Xu, F., Espejo, A.: Adaptive monitoring of the process operation based on symbolic episode representation and hidden Markov models with application toward an oil sand primary separation. Comput. Chem. Eng. 71, 281–297 (2014)
Janusz, M.E., Venkatasubramanian, V.: Automatic generation of qualitative description of process trends for fault detection and diagnosis. Eng. Appl. Artif. Intell. 4(5), 329–339 (1991)
Charbonnier, S., Gentil, S.: A trend-based alarm system to improve patient monitoring in intensive care units. Control Eng. Pract. 15, 1039–1050 (2007)
Sundarraman, A., Srinivasan, R.: Monitoringtransitions in chemical plants using enhanced trend analysis. Comput. Chem. Eng. 27, 1455–1472 (2003)
Luo, L., Xi, C.: Integrating piecewise linear representation and weighted support vector machine for stock trading signal prediction. Appl. Soft Comput. J. 13(2), 806–816 (2013)
Chang, P.C., Fan, C.Y., Liu, C.H.: Integrating a piecewise linear representation method and a neural network model for stock trading points prediction. IEEE Trans. Syst. Man Cybern. Part C 39(1), 80–92 (2008)
Fitzgerald, W., Lemire, D., Brooks, M.: Quasi-monotonic segmentation of state variable behavior for reactive control. In: Proceedings of the National Conference on Artificial Intelligence, Part 3, vol. 20, pp. 1145–1150 (2005)
Skelton, A., Willms, A.R.: An algorithm for continuous piecewise linear bounding of discrete time series data BIT. Numer. Math. 54(4), 1155–1169 (2014)
Keogh, E., Chu, S., Hart, D., et al.: Segmenting time series: a survey and novel approach. In: Data Mining in Time Series Databases (2003)
Kim, S.J., Koh, K., Boyd, S., Gorinevsky, D.: l1 trend filtering. SIAM Rev. 51(2), 339–360 (2009)
Yang, L., Liu, S., Tsoka, S., Papegeorgiou, L.G.: Mathematical programming for piecewise linear regression analysis. Expert Syst. Appl. 44, 156–167 (2016)
Zhou, B., Ye, H., Zhang, H., Li, M.: A new qualitative trend analysis algorithm based on global polynomial fit. AIChE J. 63(8), 3374–3383 (2017)
Wang, Y.X., Sharpnack, J., Smola, A.J., et al.: Trend filtering on graphs. J. Mach. Learn. Res. 17(1), 3651–3691 (2016)
Duan, L., Yu, F., Pedrycz, W., Wang, X., Yang, X.: Time-series clustering based on linear fuzzy information granules. Appl. Soft Comput. J. 73, 1053–1067 (2018)
History whether data base homepage. http://www.tianqihoubao.com/aqi/beijing.html. Accessed 13 Jan 2019
Wang, J., Yan, Yu., Chen, K.: Determining the number of segments for piece-wise linear representation of discrete-time signals. Comput. Chem. Eng. 120, 46–53 (2019)
Acknowledgements
Funding from Training Programs of Innovation and Entrepreneurship for Undergraduates (201810399037) are gratefully acknowledged.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Xiyang, Y., Jing, Z., Fusheng, Y., Zhiwei, L. (2020). Mathematical Programming for Piecewise Linear Representation of Discrete Time Series. In: Liu, Y., Wang, L., Zhao, L., Yu, Z. (eds) Advances in Natural Computation, Fuzzy Systems and Knowledge Discovery. ICNC-FSKD 2019. Advances in Intelligent Systems and Computing, vol 1075. Springer, Cham. https://doi.org/10.1007/978-3-030-32591-6_17
Download citation
DOI: https://doi.org/10.1007/978-3-030-32591-6_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-32590-9
Online ISBN: 978-3-030-32591-6
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)