An optimal linear time algorithm for quasi-monotonic segmentation1

This is an expanded version of a conference paper 15.

Abstract

Monotonicity is a simple yet significant qualitative characteristic. We consider the problem of segmenting a sequence in up to K segments. We want the segments to be as monotonic as possible and to alternate signs. We propose a quality metric for this problem using the l _∞ norm, and we present an optimal linear time algorithm based on a novel formalism. Moreover, given a precomputation in time O(n log n) consisting of a labelling of all extrema, we compute any optimal segmentation in constant time. We compare experimentally its performance to two piecewise linear segmentation heuristics (top-down and bottom-up). We show that our algorithm is faster and more accurate. Applications include pattern recognition and qualitative modelling.

Keywords:

• time series
• segmentation
• monotonicity
• design of algorithms

AMS Subject Classification :

• H.2.8

Notes

This is an expanded version of a conference paper 15.

The data is attributed to Ramsay and Silverman 16.