An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation

Abstract

Monotonicity is a simple yet significant qualitative characteristic. We consider the problem of segmenting an array in up to K segments. We want segments to be as monotonic as possible and to alternate signs. We propose a quality metric for this problem, present an optimal linear time algorithm based on novel formalism, and compare experimentally its performance to a linear time top-down regression algorithm. We show that our algorithm is faster and more accurate. Applications include pattern recognition and qualitative modeling.

Keywords

Piecewise Quasi-Monotone Functions, Segmentation, ECG, Spline

Reference

Daniel Lemire, Martin Brooks, Yuhong Yan, An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation, In Proceedings of IEEE Data Mining 2005 (ICDM-05), November 2005.

Download

Hint : It is sometimes necessary to hold down shift while clicking in order to save a document.

Software

The software used for this paper is available from Daniel Lemire upon request.

BibTeX

@inproceedings{YLBICDMO05,
   author    = {Daniel Lemire and Martin Brooks and Yuhong Yan},
   title     = {An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation},
   booktitle = {ICDM'05},
   pages={709--712},
   year      = {2005}
}

Authors

Related work

Valid XHTML 1.0! Valid CSS!