An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation

Lemire, Daniel; Brooks, Martin et Yan, Yuhong (2005). « An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation », dans ICDM-05 (IEEE Conference of Data Mining, Houston, Texas, USA, 27-30 November 2005)

Fichier(s) associé(s) à ce document :

Prévisualisation	PDF Télécharger (120kB)

Résumé

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.

Type:	Communication, article de congrès ou colloque
Mots-clés ou Sujets:	Piecewise Quasi-Monotone Functions, Segmentation, ECG, Spline
Unité d'appartenance:	Télé-université > UER Science et Technologie
Déposé par:	Daniel Lemire
Date de dépôt:	05 juin 2007
Dernière modification:	01 nov. 2014 02:03
Adresse URL :	http://archipel.uqam.ca/id/eprint/315

Modifier les métadonnées (propriétaire du document)

Statistiques