Zastosowanie falek do algorytmów wykrywania anomalii opartych na szeregach czasowych

25

Zacząłem pracować nad samouczkami w zakresie eksploracji danych statystycznych autorstwa Andrew Moore'a (wysoce zalecane dla każdego, kto pierwszy wejdzie w tę dziedzinę). Zacząłem od przeczytania tego niezwykle interesującego pliku PDF zatytułowanego „Wprowadzenie do algorytmów wykrywania anomalii opartych na szeregach czasowych”, w którym Moore śledzi wiele technik stosowanych w tworzeniu algorytmu do wykrywania wybuchów chorób. W połowie slajdów, na stronie 27, wymienia szereg innych „najnowocześniejszych metod” wykorzystywanych do wykrywania epidemii. Pierwszy wymieniony to falki . Wikipeida opisuje falkę jako

oscylacja falowa o amplitudzie, która zaczyna się od zera, zwiększa się, a następnie maleje z powrotem do zera. Zazwyczaj można to zwizualizować jako „krótką oscylację”

ale nie opisuje ich zastosowania w statystykach, a moje wyszukiwania w Google przynoszą wysoce naukowe prace, które zakładają, że wiedza na temat tego, w jaki sposób falki odnoszą się do statystyki lub pełnych książek na ten temat.

Chciałbym podstawową wiedzę na temat zastosowania falek do wykrywania anomalii szeregów czasowych, podobnie jak Moore ilustruje inne techniki w swoim samouczku. Czy ktoś może wyjaśnić, w jaki sposób działają metody wykrywania za pomocą falek lub link do zrozumiałego artykułu na ten temat?

Oren Hizkiya
źródło

Odpowiedzi:

19

Falki są przydatne do wykrywania osobliwości w sygnale (patrz na przykład artykuł tutaj (patrz rysunek 3 dla ilustracji) i odnośniki wspomniane w tym artykule. Myślę, że osobliwości mogą czasami być anomalią?

Chodzi o to, że ciągła transformata falkowa (CWT) ma linie maksymalne, które propagują się wzdłuż częstotliwości, tj. Im dłuższa linia, tym wyższa jest osobliwość. Zobacz rysunek 3 w artykule, aby zobaczyć, co mam na myśli! zwróć uwagę, że jest darmowy kod Matlab związany z tym papierem, powinien być tutaj .


Dodatkowo mogę podać kilka heurystyk szczegółowo wyjaśniających, dlaczego DYSKRETNY (poprzedni przykład dotyczy ciągłego) transformata falkowa ( DWT ) jest interesująca dla statystyki (usprawiedliwienie niewyczerpania):

  • Istnieje szeroka klasa (realistycznych (przestrzeń Besowa)) sygnałów, które są przekształcane w rzadką sekwencję za pomocą transformaty falkowej. ( właściwość kompresji )
  • Szeroka klasa (quasi-stacjonarnych) procesów, które są przekształcane w sekwencję o prawie nieskorelowanych cechach ( właściwość dekorelacji )
  • Współczynniki falkowe zawierają informacje zlokalizowane w czasie i częstotliwości (w różnych skalach). (właściwość wieloskalowa)
  • Współczynniki falkowe sygnału koncentrują się na jego osobliwościach .
Robin Girard
źródło
19

Lista w prezentacji, do której się odwołujesz, wydaje mi się dość arbitralna, a technika, która zostanie zastosowana, będzie naprawdę zależeć od konkretnego problemu. Zauważysz jednak, że zawiera on również filtry Kalmana , więc podejrzewam, że zamierzonym zastosowaniem jest technika filtrowania. Transformacje falkowe zwykle podlegają przetwarzaniu sygnału i często są wykorzystywane jako etap przetwarzania wstępnego z bardzo głośnymi danymi. Przykładem jest artykuł „ Wykrywanie anomalii na dużą skalę ” autorstwa Chena i Zhana (patrz poniżej). Podejście polegałoby na przeprowadzeniu analizy innego spektrum niż oryginalnej serii głośnej.

Falki są często porównywane do ciągłej transformacji Fouriera, chociaż mają tę zaletę, że są zlokalizowane zarówno pod względem czasu, jak i częstotliwości. Falki można stosować zarówno do kompresji sygnału, jak i wygładzania (skurczu falki). Ostatecznie sensowne może być zastosowanie dalszych danych statystycznych po zastosowaniu transformaty falkowej (na przykład poprzez sprawdzenie funkcji autokorelacji). Kolejnym aspektem falek, które mogą być przydatne do wykrywania anomalii, jest efekt lokalizacji: mianowicie nieciągłość wpłynie tylko na falkę znajdującą się w pobliżu (w przeciwieństwie do transformaty Fouriera). Jednym z zastosowań tego jest znalezienie lokalnie stacjonarnych szeregów czasowych (przy użyciu LSW).

Guy Nason ma fajną książkę, którą poleciłbym, jeśli chcesz zagłębić się w praktyczne zastosowanie statystyczne: „ Metody Wavelet w statystyce z R ”. Jest to szczególnie ukierunkowane na zastosowanie falek do analizy statystycznej, a on dostarcza wiele przykładów z całego świata wraz z całym kodem (używając pakietu wavethresh ). Książka Nasona nie zajmuje się konkretnie „wykrywaniem anomalii”, chociaż robi admirał, zapewniając ogólny przegląd.

Na koniec artykuł w Wikipedii zawiera wiele dobrych referencji wprowadzających, dlatego warto go szczegółowo przejrzeć.

[Na marginesie: jeśli szukasz dobrej nowoczesnej techniki wykrywania punktu zmiany, sugerowałbym wypróbowanie HMM przed spędzeniem zbyt dużo czasu na metodach falkowych, chyba że masz dobry powód, aby używać falek na danym polu. Opiera się to na moim osobistym doświadczeniu. Istnieje oczywiście wiele innych modeli nieliniowych, które można rozważyć, więc tak naprawdę zależy to od konkretnego problemu.]

Shane
źródło
1
Nie jest dla mnie jasne, w jaki sposób Ukryte Modele Markowa są wykorzystywane do wykrywania anomalii, ale bardzo chciałbym wiedzieć. Część, która jest dla mnie szczególnie niejasna, to jak stworzyć prawidłową maszynę stanów leżącą u podstaw ze znaczącymi prawdopodobieństwami przejścia (chyba że są to tylko dwa stany, takie jak „anomalia” i „nie anomalia” z naiwnym prawdopodobieństwem przejścia między nimi).
John Robertson
6

Najczęściej używane i implementowane dyskretne funkcje bazowe falek (w odróżnieniu od CWT opisanego w odpowiedzi Robina) mają dwie ładne właściwości, które czynią je przydatnymi do wykrywania anomalii:

  1. Są kompaktowo obsługiwane.
  2. Działają jak filtry pasmowoprzepustowe z pasmem pasmowym określonym przez ich wsparcie.

W praktyce oznacza to, że dyskretny rozkład falkowy analizuje lokalne zmiany sygnału w różnych skalach i pasmach częstotliwości. Jeśli masz (na przykład) szum o dużej wielkości i wysokiej częstotliwości nałożony na funkcję, która wyświetla przesunięcie o niskiej wielkości w dłuższym okresie, transformacja falkowa skutecznie oddzieli te dwie skale i pozwoli ci zobaczyć przesunięcie linii bazowej tak wiele innych techniki tęsknią; zmiana tego poziomu odniesienia może sugerować wybuch choroby lub inną zmianę zainteresowania. Na wiele sposobów możesz traktować sam rozkład jako płynniejszy (i wykonano sporo pracy nad wydajnym skurczem współczynników falkowych w szacunkach nieparametrycznych, patrz np. Prawie wszystko na falkach Donoho). W przeciwieństwie do metod opartych wyłącznie na częstotliwościach kompaktowa obsługa oznacza, że ​​są w stanie obsługiwać dane niestacjonarne. W przeciwieństwie do metod opartych wyłącznie na czasie, umożliwiają one filtrowanie oparte na częstotliwości.

W praktyce, w celu wykrycia anomalii lub zmiany punktów, zastosowałbyś do danych dyskretną transformatę falkową (prawdopodobnie wariant znany jako „DWT maksymalnego nakładania się” lub „niezmienny DWT przesunięcia”, w zależności od tego, kto czytasz) i przeglądaj w zestawach współczynników o niższej częstotliwości, aby sprawdzić, czy masz znaczące przesunięcia w linii podstawowej. To pokaże, kiedy pod wpływem codziennego hałasu dochodzi do długoterminowej zmiany. Percival i Walden (patrz odnośniki poniżej) opracowali kilka testów dla statystycznie znaczących współczynników, których można użyć, aby sprawdzić, czy takie przesunięcie jest znaczące, czy nie.

Doskonałą pracą referencyjną dla dyskretnych falek jest Percival i Walden, „Metody falkowe do analizy szeregów czasowych”. Dobrym wstępem jest „Wprowadzenie do falek i transformat falkowych, podkład” Burrusa, Gopinatha i Guo. Jeśli pochodzisz z inżynierii, to „Elementy falek dla inżynierów i naukowców” to dobre wprowadzenie z punktu widzenia przetwarzania sygnałów.

(Edytowane w celu uwzględnienia komentarzy Robin)

Bogaty
źródło
Pierwszy punkt, o którym wspominasz, jest ogólnie fałszywy. Sugeruję przeczytanie pierwszego zdania rozdziału books.google.fr/... w książce Daubechie. Ponadto, jeśli przeczytałeś moją odpowiedź, wspomniałem już o ładnej własności DWT w drugiej części mojej odpowiedzi ...
Robin Girard
Do pierwszego punktu masz rację. Powinienem był powiedzieć „najczęściej używane / wdrażane dyskretne funkcje bazowe falek”; Będę edytować, aby to odzwierciedlić. W drugim punkcie dałeś dobrą odpowiedź na to, w jaki sposób niektóre CWT (najczęściej falka DOG lub związana z nią falka Rickera; coś takiego jak np. Falka Gabor nie zapewniłaby opisanego przez ciebie zachowania) może wykryć anomalie osobliwości. Próbowałem podać analogiczny opis tego, w jaki sposób można użyć DWT do wykrywania innych rodzajów anomalii.
Bogaty
Drugi punkt, o którym wspominasz, jest również prawdopodobnie fałszywy: wsparcie falki (jeśli jest zwarte) podaje informacje o czasowej lokalizacji falki, a nie lokalizacji częstotliwości.
Robin Girard
Dyskretne falki - lub przynajmniej zdecydowana większość tych, które są implementowane i powszechnie stosowane - są zazwyczaj zaprojektowane tak, aby miały użyteczne właściwości oparte na częstotliwości w ramach zwartego ograniczenia podparcia. Na przykład warunek zanikania Daubechies jest mniej więcej równy płaskości w paśmie przenoszenia. Właściwości lokalizacji falek są zwykle tym, co prowadzi do tego, że współczynniki są rzadkimi reprezentacjami i pozwalają na oszacowanie wariancji szumu przy założeniu „sygnał + addytywny szum zerowy”.
Bogaty