Détection de ruptures

En analyse statistique, le problème de détection de ruptures est un problème de régression ayant pour but d'estimer les instants où un signal présente des changements dans la distribution. Ces instants sont matérialisés sur les deux figures par des lignes verticales bleues. Classiquement, on réalise de la détection de rupture pour un signal ayant des changements dans la moyenne. De manière plus générale, on réalise de la détection de ruptures pour un signal ayant des changements dans la distribution (par exemple, dans la moyenne et la variance).

Exemple de signal ayant des changements dans la moyenne.
Exemple de signal ayant des changements dans la distribution.

La détection de ruptures peut s'appliquer à un signal sonore d'une émission dont on souhaite estimer les instants où l'on change de situations, à la détection d'attaques informatiques (variations de flux réseaux)[1], ou encore au contrôle qualité.

Cet article traite du problème de détection de ruptures rétrospective (dite offline) où l'on dispose de l'ensemble des données du signal. Ce contexte est différent d'une détection temps réel (dite online) où les données du signal arrivent à la volée, mais moins à même de détecter précisément l'instant de rupture.

Formalisation du problèmeModifier

Soit   un signal réel, provenant d'observations recueillies au cours des instants  , présentant des changements dans la distribution. En notant   la loi de probabilité de  , la distribution de   vérifie :

 

avec   étant les vrais instants de ruptures (on note   (  est le vrai nombre de segments) avec la convention   et  ). On cherche à estimer ces instants de ruptures à l'aide d'un algorithme.

Dans le cas de la détection de rupture dans la moyenne, le modèle est :

 

avec   est la fonction de régression et   est un bruit d'espérance nulle et de variance  . La fonction de régression   est supposée constante par morceaux avec des discontinuités à chaque vrai instant de ruptures  .

Dans le cas de la détection de ruptures dans la distribution, on recode les observations initiales   par de nouvelles observations   définies par    est un noyau symétrique et semi-défini positif (en) (par exemple   :   est le noyau linéaire ; autre exemple   :   est le noyau Gaussien de paramètre   ). Pour un noyau symétrique et semi-défini positif  , le théorème de Moore-Aronszahn assure l'existence d'un espace de Hilbert à noyau reproduisant   de noyau reproduisant  .

Le modèle est :

 

avec   est la fonction de régression et   est un bruit d'espérance nulle et de variance  . De plus,   appartiennent à  . La fonction de régression   est supposée constante par morceaux avec des discontinuités à chaque vrai instant de ruptures  .

Méthodes existantesModifier

Le problème de détection de ruptures peut être vu comme un problème de sélection de modèle[2]: chaque segmentation candidate (i.e. liste d'instants de ruptures candidats) est reliée à un modèle qu'il faut choisir. Nous présentons deux approches : l'une utilisant le principe de la programmation dynamique et l'autre l'heuristique de segmentation binaire dans le cadre classique de la détection de ruptures dans la moyenne puis dans le cas général de la détection de ruptures dans la distribution. Pour chacune de ces deux méthodes, nous présentons les algorithmes permettant de calculer une segmentation en   segments   optimisant un critère (ici, le risque empirique).

NotationsModifier

Nous présentons les notations communes aux deux méthodes puis celles qui leur sont spécifiques :

Notation commune

  l'ensemble des segmentions   en   segments  .

Notations pour le cas de la détection de ruptures dans la moyenne

  •   et  .
  •   :   est l'ensemble des vecteurs   constants par morceaux sur les segments de  .
  • Estimateur du risque empirique :  .

Notations pour le cas de la détection de ruptures dans la distribution

  •   et  .
  •   pour   avec  .
  •   :   est l'ensemble des vecteurs   constants par morceaux sur les segments de  .
  • Norme dans   :  .
  • Estimateur du risque empirique :  .

Les méthodes proposées ci-dessous utilisent le risque empirique comme critère à minimiser (  pour la détection de ruptures dans la moyenne ;   pour la détection de ruptures dans la distribution). Pour le noyau linéaire  ,  , les méthodes utilisées dans le cadre classique se déduisent de celles du cas des noyaux par le biais de   : donc on ne présentera les algorithmes que dans le cas des noyaux.

Programmation dynamiqueModifier

La méthode de la programmation dynamique utilise le principe d'optimalité de Bellman : toute solution optimale s'appuie elle-même sur des sous-problèmes résolus localement de façon optimale. On utilise cette méthode exacte pour récupérer pour   la meilleure segmentation en   segments minimisant le risque empirique i.e. :

 


Nous présentons dans cette section l'algorithme de programmation dynamique appliquée au problème de détection de ruptures[3],[4]. Dans un premier temps, nous exprimons le risque empirique   en fonction du noyau   et de   à l'aide des deux résultats suivants ci-dessous.

On montre tout d'abord que, pour  , pour  ,  .

On montre que, pour  ,

 

avec, pour  ,  

KPGD est l'implémentation du principe de la programmation dynamique à noyau appliquée au problème de détection de ruptures. Elle prend en paramètre la matrice de coût   et elle renvoie  .

 algorithme KPGD ( ) 
   for   do
     for   do
        
        
     end for        
   end for
 Fin algorithme


avec  .

La sélection de modèle[4] permet de récupérer   un estimateur du nombre de segments  .   est défini par

 

avec  . La méthode utilisée pour calibrer la constante   est l'heuristique de pente[5]. On obtient ainsi un estimateur  .

Segmentation binaireModifier

L'heuristique de segmentation binaire[6] est une méthode, fonctionnant par dichotomie, permettant de récupérer un minimiseur local   du risque empirique  . Plus précisément, la segmentation binaire cherche à la première itération l'indice   de l'instant de ruptures candidat qui minimise le risque empirique   : cet indice est l'indice de notre premier instant de ruptures estimé. Puis, elle détermine récursivement, à la deuxième itération, deux instants de ruptures candidats   sur chacun des segments délimités par les instants de ruptures estimés. Elle retient comme second instant de ruptures estimé celui (parmi ces deux instants de ruptures candidats) qui minimisent le risque empirique. Puis, on procède de la même manière pour les itérations suivantes. Nous illustrons sur un exemple le fonctionnement de l'algorithme utilisant le principe de la segmentation binaire :

  • Étape 1 : A l'itération  , on cherche   qui minimise le risque empirique   avec   pour   avec :
 

  est notre premier instant de ruptures estimé noté  .

  • Étape 2  : A l'itération on  , on cherche   minimisant le risque empirique sur   et   respectivement. Par exemple,
 

avec  . Puis on choisit parmi les instants de ruptures candidats   celui qui minimise le risque empirique  
et on le note   . Puis, on continue récursivement.

Ainsi, au bout de   itérations, on récupère une segmentation en   segments vérifiant :

 

avec   l'espace des segmentations en   segments où les instants de ruptures estimés   ont été calculés aux itérations précédentes.

Une méthode alternative de segmentation binaire avec temps d'arrêt[7] permet d'estimer le nombre de segments et donc de récupérer un estimateur   de   .

Notes et référencesModifier

Articles
  1. [PDF] Alexandre Lung-Yut-Fong, « Détection de ruptures pour les signaux multidimensionnels. Application à la détection d’anomalies dans les réseaux. », HAL,‎ (lire en ligne)
  2. [PDF] Lucien Birgé et Pascal Massart, « Gaussian model selection. », Journal of the European Mathematical Society,‎ , p. 203-268
  3. [PDF] Zaid Harchaoui et Olivier Cappé, « Retrospective Mutiple Change-Point Estimation with Kernels. », IEEE,‎ , p. 768-772 (lire en ligne)
  4. a et b [PDF] Sylvain Arlot, Alain Celisse et Zaid Harchaoui, « A kernel multiple change-point algorithm via model selection. », Arxiv,‎ (lire en ligne)
  5. Lucien Birgé et Pascal Massart, « Minimal Penalties for Gaussian Model Selection », Probability Theory and Related Fields, vol. 138,‎ , p. 33--73 (lire en ligne).
  6. [PDF] Rebecca Killick, « Optimal detection of changepoints with a linear computational cost. », Journal of the American Statistical Association,‎ , p. 1590--1598
  7. [PDF] Piotr Fryzlewicz, « Wild binary segmentation for multiple change-point detection. », The Annals of Statistics, vol. 42, no 6,‎ , p. 2243--2281 (lire en ligne)