Application des ondelettes aux algorithmes de détection d'anomalies basées sur des séries chronologiques

25

J'ai commencé à me frayer un chemin à travers les didacticiels d'exploration de données statistiques d'Andrew Moore (fortement recommandé pour toute autre personne qui s'aventure dans ce domaine). J'ai commencé par lire ce PDF extrêmement intéressant intitulé "Présentation introductive des algorithmes de détection d'anomalies basées sur des séries chronologiques" dans lequel Moore retrace à travers de nombreuses techniques utilisées dans la création d'un algorithme pour détecter les épidémies. Au milieu des diapositives, à la page 27, il énumère un certain nombre d'autres «méthodes de pointe» utilisées pour détecter les épidémies. Le premier répertorié est les ondelettes . Wikipeida décrit une ondelette comme

une oscillation ondulatoire avec une amplitude qui commence à zéro, augmente, puis redescend à zéro. Il peut généralement être visualisé comme une "brève oscillation"

mais ne décrit pas leur application aux statistiques et mes recherches sur Google donnent des articles très académiques qui supposent une connaissance du lien entre les ondelettes et les statistiques ou des livres complets sur le sujet.

Je voudrais une compréhension de base de la façon dont les ondelettes sont appliquées à la détection d'anomalies de séries temporelles, de la manière dont Moore illustre les autres techniques dans son tutoriel. Quelqu'un peut-il expliquer le fonctionnement des méthodes de détection utilisant des ondelettes ou un lien vers un article compréhensible sur le sujet?

Oren Hizkiya
la source

Réponses:

19

Les ondelettes sont utiles pour détecter les singularités dans un signal (voir par exemple l'article ici (voir la figure 3 pour une illustration) et les références mentionnées dans cet article. Je suppose que les singularités peuvent parfois être une anomalie?

L'idée ici est que la transformée en ondelettes continue (CWT) a des raies maximales qui se propagent le long des fréquences, c'est-à-dire que plus la ligne est longue, plus la singularité est élevée. Voir la figure 3 dans le document pour voir ce que je veux dire! notez qu'il existe un code Matlab gratuit lié à ce papier, il devrait être ici .


De plus, je peux vous donner quelques heuristiques détaillant pourquoi la transformée en ondelettes ( DWT ) DISCRETE (l'exemple précédent concerne la constante ) est intéressante pour un statisticien (excuse la non-exhaustivité):

  • Il existe une large classe de signaux (réalistes (espace Besov)) qui sont transformés en une séquence clairsemée par la transformée en ondelettes. ( propriété de compression )
  • Une large classe de processus (quasi-stationnaires) qui sont transformés en une séquence avec des caractéristiques presque non corrélées ( propriété de décorrélation )
  • Les coefficients d'ondelettes contiennent des informations localisées dans le temps et en fréquence (à différentes échelles). (propriété multi-échelle)
  • Les coefficients d'ondelettes d'un signal se concentrent sur ses singularités .
Robin Girard
la source
19

La liste dans la présentation à laquelle vous faites référence me semble assez arbitraire, et la technique qui serait utilisée dépendra vraiment du problème spécifique. Vous noterez cependant qu'il inclut également des filtres Kalman , donc je soupçonne que l'utilisation prévue est une technique de filtrage. Les transformées en ondelettes relèvent généralement du traitement du signal et seront souvent utilisées comme étape de prétraitement avec des données très bruyantes. Un exemple est le document " Détection d'anomalies multi-échelles " de Chen et Zhan (voir ci-dessous). L'approche consisterait à effectuer une analyse sur le spectre différent plutôt que sur la série bruyante d'origine.

Les ondelettes sont souvent comparées à une transformée de Fourier à temps continu, bien qu'elles aient l'avantage d'être localisées en temps et en fréquence. Les ondelettes peuvent être utilisées à la fois pour la compression du signal et également pour le lissage (rétrécissement des ondelettes). En fin de compte, il pourrait être judicieux d'appliquer une statistique supplémentaire après l'application de la transformée en ondelettes (en examinant la fonction d'autocorrélation par exemple). Un autre aspect des ondelettes qui pourrait être utile pour la détection d'anomalies est l'effet de la localisation: à savoir, une discontinuité n'influencera que l'ondelette qui se trouve à proximité (contrairement à une transformée de Fourier). Une application de ceci est de trouver des séries chronologiques localement stationnaires (en utilisant un LSW).

Guy Nason a un beau livre que je recommanderais si vous voulez approfondir l'application statistique pratique: "Les méthodes d'ondelettes en statistiques avec R ". Cela vise spécifiquement l'application des ondelettes à l'analyse statistique, et il fournit de nombreux exemples du monde réel avec tout le code (en utilisant le package wavethresh ). Le livre de Nason ne traite pas spécifiquement de la «détection d'anomalies», bien qu'il fasse un travail amiral de fournir un aperçu général.

Enfin, l'article de wikipedia fournit de nombreuses bonnes références d'introduction, il vaut donc la peine de les parcourir en détail.

[Remarque: si vous cherchez une bonne technique moderne pour la détection des points de changement, je vous suggère d'essayer un HMM avant de passer trop de temps avec les méthodes d'ondelettes, sauf si vous avez de bonnes raisons d'utiliser des ondelettes dans votre domaine particulier. Ceci est basé sur mon expérience personnelle. Il existe bien sûr de nombreux autres modèles non linéaires qui pourraient être envisagés, donc cela dépend vraiment de votre problème spécifique.]

Shane
la source
1
Ce n'est pas clair pour moi comment les modèles de Markov cachés sont utilisés pour la détection des anomalies, mais j'aimerais beaucoup savoir. La partie qui m'est particulièrement floue est de savoir comment créer une machine à états sous-jacente correcte avec des probabilités de transition significatives (à moins qu'il ne s'agisse que de deux états comme "anomalie" et "pas d'anomalie" avec une probabilité de transition naïve entre eux).
John Robertson
6

Les fonctions de base d'ondelettes discrètes les plus couramment utilisées et implémentées (distinctes du CWT décrit dans la réponse de Robin) ont deux belles propriétés qui les rendent utiles pour la détection d'anomalies:

  1. Ils sont pris en charge de manière compacte.
  2. Ils agissent comme des filtres passe-bande dont la bande passante est déterminée par leur support.

Cela signifie concrètement que votre décomposition en ondelettes discrètes examine les changements locaux du signal à travers une variété d'échelles et de bandes de fréquences. Si vous avez (par exemple) un bruit haute fréquence de grande amplitude superposé à une fonction qui affiche un décalage de faible amplitude sur une période plus longue, la transformée en ondelettes séparera efficacement ces deux échelles et vous permettra de voir le décalage de la ligne de base que beaucoup d'autres les techniques manqueront; un changement dans cette ligne de base peut suggérer une épidémie ou un autre changement d'intérêt. À bien des égards, vous pouvez traiter la décomposition elle-même comme plus fluide (et il y a eu pas mal de travail sur le rétrécissement efficace des coefficients d'ondelettes dans l'estimation non paramétrique, voir par exemple à peu près tout sur les ondelettes de Donoho). Contrairement aux méthodes purement basées sur la fréquence, le support compact signifie qu'ils sont capables de gérer des données non stationnaires. Contrairement aux méthodes purement temporelles, elles permettent un filtrage basé sur la fréquence.

En termes pratiques, pour détecter des anomalies ou des points de changement, vous appliqueriez une transformée en ondelettes discrète (probablement la variante connue sous le nom de "DWT de chevauchement maximal" ou de "DWT invariant par décalage", selon la personne que vous lisez) aux données, et regardez aux ensembles de coefficients de fréquence inférieure pour voir si vous avez des changements importants dans la ligne de base. Cela vous montrera quand un changement à long terme se produit sous n'importe quel bruit quotidien. Percival et Walden (voir les références ci-dessous) dérivent quelques tests de coefficients statistiquement significatifs que vous pouvez utiliser pour voir si un changement comme celui-ci est significatif ou non.

Un excellent travail de référence pour les ondelettes discrètes est Percival et Walden, "Wavelet Methods for Time Series Analysis". Un bon travail d'introduction est "Introduction aux ondelettes et aux transformées en ondelettes, une amorce" par Burrus, Gopinath et Guo. Si vous venez d'un milieu d'ingénierie, alors "Éléments d'ondelettes pour les ingénieurs et les scientifiques" est une bonne introduction du point de vue du traitement du signal.

(Modifié pour inclure les commentaires de Robin)

Riches
la source
Le premier point que vous mentionnez est faux en général je vous suggère de lire la première phrase du chapitre books.google.fr/… dans le livre de Daubechie. De plus, si vous aviez lu ma réponse j'ai déjà mentionné la belle propriété du DWT dans la 2ème partie de ma réponse ...
robin girard
Au premier point, vous avez raison. J'aurais dû dire "Fonctions de base d'ondelettes discrètes les plus couramment utilisées / implémentées"; Je vais modifier pour refléter cela. Au deuxième point, vous avez donné une bonne réponse sur la façon dont certains CWT (le plus souvent une ondelette DOG ou l'ondelette Ricker connexe; quelque chose comme par exemple l'ondelette Gabor ne fournirait pas le comportement que vous décrivez) peuvent détecter des anomalies du type singularité. J'essayais de donner une description analogue de la façon dont le DWT peut être utilisé pour détecter d'autres types d'anomalies.
Rich
Le deuxième point que vous mentionnez est également susceptible d'être faux: le support d'ondelettes (s'il est compact) donne des informations sur la localisation temporelle de l'ondelette et non sur la localisation fréquentielle.
Robin Girard
Les ondelettes discrètes - ou du moins la grande majorité de celles qui sont implémentées et couramment utilisées - sont généralement conçues pour avoir des propriétés basées sur la fréquence utiles sous la contrainte de support compact. La condition de moment de fuite de Daubechies, par exemple, est plus ou moins équivalente à la planéité dans la bande passante. Les propriétés de localisation de fréquence des ondelettes sont généralement ce qui conduit les coefficients à être des représentations clairsemées et permettent d'estimer la variance du bruit sous l'hypothèse "signal + bruit additif à moyenne nulle".
Rich