A Novel Accuracy-Constrained Scheme for Efficient Trend Extraction of Industrial Time-Series Data

Data trend extraction provides a useful means to qualitatively capture the underlying variations of time-series data. A class of algorithms is built upon segmentation and piecewise polynomial fitting, where the model complexity is primarily controlled by the number of data segments. However, it is not trivial to specify when tackling datasets of different sizes, and expensive computations are required in current global optimization algorithms. To address these issues, we propose a novel data trend extraction and segmentation method based on accuracy-constrained polynomial fitting. Two normalized indices are coined to define constraints on the accuracy of piecewise polynomial fitting, which allows for an interpretable and clear tuning guideline to regulate model complexities of segmentation when facing data trajectories of different lengths. By exploiting the structure of the constrained fitting problem, a breadth-first search (BFS) algorithm is established, with two branch pruning (BP) strategies designed to remarkably improve the solution efficiency. In particular, we prove that the proposed solution algorithm has a desirable <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathcal {O}(n^{2})$ </tex-math></inline-formula> complexity that does not grow with the number of segments and is much lower than that of generic global optimization algorithms. Comprehensive case studies show that compared with conventional methods, our approach enjoys better empirical performance, easier tuning of parameters, and lower computational cost.