Open access research
publication repository

An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation [r-libre/212]

Lemire, Daniel; Brooks, Martin, & Yan, Yuhong (2005). An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation. In Han, Jiawei; Wah, Benjamin W.; Vijay, Raghavan; Wu, Xindong, & Rastogi, Rajeev (Ed.), Proceedings of the Fifth IEEE International Conference on Data Mining (ICDM-05) (p. 709-712). Piscataway, NJ : IEEE. https://doi.org/10.1109/ICDM.2005.25

File(s) available for this item:
[img]  PDF - lemire-monotonic-web.pdf  
Item Type: Papers in Conference Proceedings
Refereed: Yes
Status: Published
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.
Depositor: Lemire, Daniel
Owner / Manager: Daniel Lemire
Deposited: 05 Jun 2007
Last Modified: 16 Jul 2015 00:47

Actions (login required)