Répertoire de publications
de recherche en accès libre
de recherche en accès libre
Lemire, Daniel; Brooks, Martin et Yan, Yuhong (2009). An optimal linear time algorithm for quasi-monotonic segmentation. International Journal of Computer Mathematics, 86 (7). https://doi.org/10.1080/00207160701694153
Fichier(s) associé(s) à ce document :| PDF - 0709.1166v1.pdf |
|
| Catégorie de document : | Articles de revues |
|---|---|
| Évaluation par un comité de lecture : | Oui |
| Étape de publication : | Publié |
| Résumé : | Monotonicity is a simple yet significant qualitative characteristic. We consider the problem of segmenting a sequence 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 using the l_inf norm, and we present an optimal linear time algorithm based on novel formalism. Moreover, given a precomputation in time O(n log n) consisting of a labeling 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 modeling. |
| Adresse de la version officielle : | http://www.tandfonline.com/doi/abs/10.1080/0020716... |
| Déposant: | Lemire, Daniel |
| Responsable : | Daniel Lemire |
| Dépôt : | 22 juill. 2014 21:50 |
| Dernière modification : | 16 juill. 2015 00:47 |
|
RÉVISER |
