Algorithme rapide pour la détection optimale des ruptures

Résumé : Dans les modèles de détection de ruptures, les données sont modélisées par un processus aléatoire dont les paramètres sont soumis à des changements brusques en des instants inconnus, appelés instants de ruptures. La recherche exhaustive des positions des ruptures de norme quadratique minimale se fait par un algorithme de programmation dynamique. L'intérêt de cet algorithme est qu'il permet d'obtenir la solution optimale en réduisant la complexité algorithmique de $O(n^K)$ à $O(K n^2)$, où $K-1$ est le nombre de ruptures fixé et $n$ la taille du signal. Même si le temps de calcul est réduit, cet algorithme ne peut être utilisé sur des signaux de grandes tailles. Nous proposons ici un nouvel algorithme de programmation dynamique permettant d'obtenir la solution optimale en un temps de calcul très nettement réduit. Notamment il permet d'analyser un signal d'un million de points en quelques minutes. Plus précisement, nous d'montrons qu'au pire des cas sa complexité en temps et en espace sont respectivement de $O(K n^2)$ et de $O(K n)$ et nous montrons que son temps de calcul est empiriquement de l'ordre de $O(K n \log(n))$. Par ailleurs, Nous comparons cet algorithme à l'algorithme de programmation dynamique classique. L'algorithme proposé est au pire des cas équivalent et a une complexité empirique bien plus faible.
Type de document :
Communication dans un congrès
42èmes Journées de Statistique, 2010, Marseille, France, France. 2010
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00494813
Contributeur : Conférence Sfds-Hal <>
Soumis le : jeudi 24 juin 2010 - 08:59:09
Dernière modification le : mercredi 29 novembre 2017 - 15:52:39
Document(s) archivé(s) le : lundi 22 octobre 2012 - 14:47:16

Fichier

p177.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00494813, version 1

Collections

Citation

Guillem Rigaill. Algorithme rapide pour la détection optimale des ruptures. 42èmes Journées de Statistique, 2010, Marseille, France, France. 2010. 〈inria-00494813〉

Partager

Métriques

Consultations de la notice

129

Téléchargements de fichiers

119