Anwendung von Wavelets auf zeitreihenbasierte Anomalieerkennungsalgorithmen

25

Ich habe angefangen, mich durch die Statistical Data Mining Tutorials von Andrew Moore zu arbeiten (sehr empfehlenswert für alle anderen, die sich zum ersten Mal in dieses Gebiet wagen). Ich begann mit der Lektüre dieses äußerst interessanten PDFs mit dem Titel "Einführung in zeitreihenbasierte Algorithmen zur Erkennung von Anomalien", in dem Moore viele der Techniken zur Erstellung eines Algorithmus zur Erkennung von Krankheitsausbrüchen nachzeichnet. In der Mitte der Folien, auf Seite 27, listet er eine Reihe weiterer "State-of-the-Art-Methoden" zur Erkennung von Ausbrüchen auf. Die erste Liste enthält Wavelets . Wikipeida beschreibt ein Wavelet als

Eine wellenartige Schwingung mit einer Amplitude, die bei Null beginnt, zunimmt und dann auf Null zurückgeht. Es kann typischerweise als "kurze Schwingung" visualisiert werden

Ihre Anwendung auf Statistiken wird jedoch nicht beschrieben, und meine Google-Suchanfragen liefern hoch akademische Arbeiten, die davon ausgehen, dass sie wissen, wie Wavelets mit Statistiken oder vollständigen Büchern zu diesem Thema zusammenhängen.

Ich möchte ein grundlegendes Verständnis dafür haben, wie Wavelets auf die Erkennung von Zeitreihenanomalien angewendet werden, ähnlich wie Moore die anderen Techniken in seinem Tutorial veranschaulicht. Kann jemand eine Erklärung zur Funktionsweise von Detektionsmethoden mit Wavelets oder einen Link zu einem verständlichen Artikel zu diesem Thema geben?

Oren Hizkiya
quelle

Antworten:

19

Wavelets sind nützlich, um Singularitäten in einem Signal zu erkennen (siehe zum Beispiel das Papier hier (siehe Abbildung 3 für eine Illustration) und die in diesem Papier erwähnten Referenzen. Ich denke, Singularitäten können manchmal eine Anomalie sein?

Die Idee hierbei ist, dass die kontinuierliche Wavelet-Transformation (CWT) Maxima-Linien aufweist, die sich entlang von Frequenzen ausbreiten, dh je länger die Linie ist, desto höher ist die Singularität. Siehe Abbildung 3 im Artikel, um zu sehen, was ich meine! Beachten Sie, dass es zu diesem Papier kostenlosen Matlab-Code gibt. Er sollte hier sein .


Darüber hinaus kann ich Ihnen einige Heuristiken geben, in denen erläutert wird , warum die Wavelet-Transformation ( DWT ) DISCRETE (vorhergehendes Beispiel ) für einen Statistiker interessant ist (entschuldigen Sie die Unvollständigkeit ):

  • Es gibt eine große Klasse von (realistischen (Besov-Raum-)) Signalen, die durch die Wavelet-Transformation in eine spärliche Sequenz transformiert werden. ( Kompressionseigenschaft )
  • Eine breite Klasse von (quasi-stationären) Prozessen, die in eine Sequenz mit fast unkorrelierten Merkmalen umgewandelt werden ( Dekorrelationseigenschaft )
  • Wavelet-Koeffizienten enthalten Informationen, die zeitlich und frequenzmäßig (in verschiedenen Maßstäben) lokalisiert sind . (Multi-Scale-Eigenschaft)
  • Die Wavelet-Koeffizienten eines Signals konzentrieren sich auf seine Singularitäten .
Robin Girard
quelle
19

Die Liste in der Präsentation, auf die Sie verweisen, scheint mir ziemlich willkürlich zu sein, und die Technik, die verwendet wird, hängt wirklich von dem spezifischen Problem ab. Sie werden jedoch bemerken, dass es auch Kalman-Filter enthält , so dass ich vermute, dass die beabsichtigte Verwendung eine Filtertechnik ist. Wavelet-Transformationen fallen im Allgemeinen unter das Thema Signalverarbeitung und werden häufig als Vorverarbeitungsschritt mit sehr verrauschten Daten verwendet. Ein Beispiel ist das Papier " Multi-Scale Anomaly Detection " von Chen und Zhan (siehe unten). Der Ansatz wäre, eine Analyse des unterschiedlichen Spektrums und nicht der ursprünglichen verrauschten Serie durchzuführen.

Wavelets werden oft mit einer zeitkontinuierlichen Fouriertransformation verglichen, obwohl sie den Vorteil haben, sowohl in der Zeit als auch in der Frequenz lokalisiert zu sein. Wavelets können sowohl zur Signalkomprimierung als auch zur Glättung (Wavelet-Schrumpfung) eingesetzt werden. Letztendlich könnte es sinnvoll sein, eine weitere Statistik anzuwenden, nachdem die Wavelet-Transformation angewendet wurde (indem beispielsweise die Autokorrelationsfunktion betrachtet wird). Ein weiterer Aspekt von Wavelets, der für die Erkennung von Anomalien nützlich sein könnte, ist der Effekt der Lokalisierung: Eine Diskontinuität beeinflusst nämlich nur das Wavelet in der Nähe (im Gegensatz zu einer Fouriertransformation). Eine Anwendung besteht darin, lokal stationäre Zeitreihen (unter Verwendung eines LSW) zu finden.

Guy Nason hat ein schönes Buch, das ich empfehlen würde, wenn Sie sich näher mit der praktischen statistischen Anwendung befassen möchten: " Wavelet Methods in Statistics with R ". Dies zielt speziell auf die Anwendung von Wavelets zur statistischen Analyse ab und er liefert viele Beispiele aus der Praxis zusammen mit dem gesamten Code (unter Verwendung des Wavethresh-Pakets ). Nasons Buch befasst sich nicht speziell mit "Anomalieerkennung", obwohl es eine admirale Aufgabe ist, einen allgemeinen Überblick zu verschaffen.

Schließlich enthält der Wikipedia-Artikel viele gute einführende Verweise, weshalb es sich lohnt, ausführlich darauf einzugehen.

[Als Randnotiz: Wenn Sie eine gute moderne Technik zur Erkennung von Änderungspunkten suchen, würde ich empfehlen, ein HMM zu testen, bevor Sie zu viel Zeit mit Wavelet-Methoden verbringen, es sei denn, Sie haben guten Grund, Wavelets in Ihrem speziellen Bereich zu verwenden. Dies basiert auf meinen persönlichen Erfahrungen. Es gibt natürlich auch viele andere nichtlineare Modelle, die in Betracht gezogen werden könnten, es hängt also wirklich von Ihrem spezifischen Problem ab.]

Shane
quelle
1
Mir ist nicht klar, wie Hidden Markov-Modelle zur Erkennung von Anomalien verwendet werden, aber ich würde es sehr gerne wissen. Der Teil, der mir besonders unklar ist, ist, wie man eine korrekte zugrunde liegende Zustandsmaschine mit sinnvollen Übergangswahrscheinlichkeiten erzeugt (es sei denn, es handelt sich nur um zwei Zustände wie "Anomalie" und "Nicht-Anomalie" mit einer naiven Übergangswahrscheinlichkeit zwischen ihnen).
John Robertson
6

Die am häufigsten verwendeten und implementierten diskreten Wavelet-Basisfunktionen (im Unterschied zu der in Robins Antwort beschriebenen CWT) weisen zwei nützliche Eigenschaften auf, die sie für die Erkennung von Anomalien nützlich machen:

  1. Sie werden kompakt unterstützt.
  2. Sie wirken als Bandpassfilter, wobei das Durchlassband von ihrer Unterstützung bestimmt wird.

In der Praxis bedeutet dies, dass Ihre diskrete Wavelet-Zerlegung lokale Änderungen im Signal über eine Vielzahl von Skalen und Frequenzbändern betrachtet. Wenn Sie zum Beispiel über eine Funktion, die über einen längeren Zeitraum eine Verschiebung geringer Größe anzeigt, hochfrequentes Rauschen mit großer Größe überlagert haben, werden diese beiden Skalen durch die Wavelet-Transformation effizient voneinander getrennt, und Sie können die Grundlinienverschiebung sehen, die bei vielen anderen auftritt Techniken werden fehlen; Eine Verschiebung dieser Grundlinie kann auf einen Krankheitsausbruch oder eine andere Änderung des Interesses hindeuten. In vielerlei Hinsicht können Sie die Zerlegung selbst als glatter behandeln (und es wurde eine Menge Arbeit an der effizienten Schrumpfung von Wavelet-Koeffizienten in nichtparametrischen Schätzungen geleistet, siehe z. B. so ziemlich alles über Wavelets von Donoho). Im Gegensatz zu reinen frequenzbasierten Methoden Durch die kompakte Unterstützung sind sie in der Lage, nicht stationäre Daten zu verarbeiten. Im Gegensatz zu rein zeitbasierten Methoden ermöglichen sie eine frequenzbasierte Filterung.

In der Praxis würden Sie zum Erkennen von Anomalien oder zum Ändern von Punkten eine diskrete Wavelet-Transformation (wahrscheinlich die als "Maximum Overlap DWT" oder "Shift Invariant DWT" bekannte Variante, je nachdem, wen Sie lesen) auf die Daten anwenden und nachsehen bei den niederfrequenten Koeffizientensätzen, um festzustellen, ob Sie signifikante Verschiebungen in der Grundlinie haben. Dies zeigt Ihnen, wann eine langfristige Veränderung unter alltäglichen Geräuschen auftritt. Percival und Walden (siehe Referenzen unten) leiten einige Tests für statistisch signifikante Koeffizienten ab, mit denen Sie feststellen können, ob eine Verschiebung wie diese signifikant ist oder nicht.

Ein ausgezeichnetes Nachschlagewerk für diskrete Wavelets ist Percival und Walden, "Wavelet Methods for Time Series Analysis". Eine gute Einführungsarbeit ist "Introduction to Wavelets und Wavelet-Transformationen, ein Primer" von Burrus, Gopinath und Guo. Wenn Sie einen technischen Hintergrund haben, ist "Elemente von Wavelets für Ingenieure und Wissenschaftler" aus Sicht der Signalverarbeitung eine gute Einführung.

(Bearbeitet, um Robins Kommentare aufzunehmen)

Reich
quelle
Der erste Punkt, den Sie erwähnen, ist im Allgemeinen falsch. Ich schlage vor, dass Sie den ersten Satz des Kapitels books.google.fr/… im Buch Daubechie lesen . Außerdem, wenn Sie meine Antwort gelesen hatten, erwähnte ich bereits die nette Eigenschaft des DWT im 2. Teil meiner Antwort ...
Robin Girard
Bis zum ersten Punkt haben Sie recht. Ich hätte sagen sollen: "Am häufigsten verwendete / implementierte diskrete Wavelet-Basisfunktionen"; Ich bearbeite, um das zu reflektieren. Bis zum zweiten Punkt gaben Sie eine gute Antwort darauf, wie einige CWTs (meistens ein DOG-Wavelet oder das verwandte Ricker-Wavelet; so etwas wie das Gabor-Wavelet würde das von Ihnen beschriebene Verhalten nicht liefern) Anomalien der Singularität erkennen können. Ich habe versucht, eine analoge Beschreibung zu geben, wie DWT zum Erkennen anderer Arten von Anomalien verwendet werden kann.
Rich
Der zweite Punkt, den Sie erwähnen, ist wahrscheinlich auch falsch: Die Wavelet-Unterstützung (wenn sie kompakt ist) gibt Informationen über die zeitliche Lokalisierung des Wavelets und nicht über die Frequenzlokalisierung.
Robin Girard
Diskrete Wavelets - oder zumindest die überwiegende Mehrheit der Wavelets, die implementiert und häufig verwendet werden - sind in der Regel so konzipiert, dass sie unter der Einschränkung der kompakten Unterstützung nützliche frequenzbasierte Eigenschaften aufweisen. Zum Beispiel ist der Zustand des Verschwindens von Daubechies mehr oder weniger gleichbedeutend mit der Ebenheit im Durchlassbereich. Die Frequenzlokalisierungseigenschaften von Wavelets führen normalerweise zu spärlichen Darstellungen der Koeffizienten und ermöglichen die Schätzung der Rauschvarianz unter der Annahme "Signal + Additives Null-Mittelwert-Rauschen".
Rich