| DOI | Trouver le DOI : https://doi.org/10.1080/00207160701694153 |
|---|
| Auteur | Rechercher : Lemire, Daniel1; Rechercher : Brooks, Martin1; Rechercher : Yan, Yuhong1 |
|---|
| Affiliation | - Conseil national de recherches du Canada. Institut de technologie de l'information du CNRC
|
|---|
| Format | Texte, Article |
|---|
| Sujet | time series; segmentation; monotonicit; design of algorithms |
|---|
| 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 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. |
|---|
| Date de publication | 2009-06-17 |
|---|
| Maison d’édition | Wiley |
|---|
| Dans | |
|---|
| Langue | anglais |
|---|
| Publications évaluées par des pairs | Oui |
|---|
| Numéro NPARC | 23004493 |
|---|
| Exporter la notice | Exporter en format RIS |
|---|
| Signaler une correction | Signaler une correction (s'ouvre dans un nouvel onglet) |
|---|
| Identificateur de l’enregistrement | e62c9fa0-5c3f-447b-8a99-7013b20cdf8c |
|---|
| Enregistrement créé | 2018-11-08 |
|---|
| Enregistrement modifié | 2020-04-16 |
|---|
