A new approach for optimal offline time-series segmentation with error bound guarantee. (July 2021)

• Record Type: Journal Article
• Authors: Carmona-Poyato, Ángel; Fernández-Garcia, Nicolás Luis; Madrid-Cuevas, Francisco José; Durán-Rosal, Antonio Manuel
• Is Part Of: Pattern recognition. Volume 115(2021)
• Publication Date: 2021-07
• Subjects: Data representation -- Optimal time series segmentation -- Error bound guarantee -- L∞-norm; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2021.107917
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: An optimal offline time-series segmentation with error bound guarantee is proposed (OSFS method). The OSFS method is based on finding the shortest path in a directed graph. In order to reduce the computational time, the feasible space method (FS), proposed by Liu, is used. A new performance measure to evaluate the performance of heuristic and metaheuristic methods has also been proposed. These results demonstrate that the L-infinity norm produces better results than the L ∞ -norm. Abstract: Piecewise Linear Approximation is one of the most commonly used strategies to represent time series effectively and approximately. This approximation divides the time series into non-overlapping segments and approximates each segment with a straight line. Many suboptimal methods were proposed for this purpose. This paper proposes a new optimal approach, called OSFS, based on feasible space (FS) Liu et al. (2008)[1], that minimizes the number of segments of the approximation and guarantees the error bound using the L ∞ -norm. On the other hand, a new performance measure combined with the OSFS method has been used to evaluate the performance of some suboptimal methods and that of the optimal method that minimizes the holistic approximation error ( L 2 -norm). The results have shown that the OSFS method is optimal and demonstrates the advantages of L ∞ -norm over L 2 -norm.