Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/inria-00494813
Contributor : Conférence Sfds-Hal Connect in order to contact the contributor
Submitted on : Thursday, June 24, 2010 - 8:59:09 AM
Last modification on : Tuesday, June 15, 2021 - 2:57:01 PM
Long-term archiving on: : Monday, October 22, 2012 - 2:47:16 PM

File

p177.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00494813, version 1
  • PRODINRA : 244940

Collections

Citation

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

Share

Metrics

Record views

84

Files downloads

100