Jakiego algorytmu należy użyć do wykrywania nieprawidłowości w szeregach czasowych?

69

tło

Pracuję w Network Operations Center, monitorujemy systemy komputerowe i ich wydajność. Jednym z kluczowych wskaźników do monitorowania jest liczba odwiedzających \ klientów aktualnie podłączonych do naszych serwerów. Aby to pokazać, zbieramy takie dane, jak dane szeregów czasowych i rysujemy wykresy. Grafit pozwala nam to zrobić, ma dość bogaty interfejs API, którego używam do budowania systemu ostrzegania, aby powiadomić nasz zespół, jeśli nastąpi nagły spadek (głównie) i inne zmiany. Na razie ustawiłem próg statyczny na podstawie wartości średniej, ale nie działa on zbyt dobrze (istnieje wiele wyników fałszywie dodatnich) z powodu różnych obciążeń w ciągu dnia i tygodnia (współczynnik sezonowości).

Wygląda to mniej więcej tak: liczba użytkowników na system

Rzeczywiste dane (przykład dla jednej metryki, zakres czasu 15 min; pierwsza liczba to liczba użytkowników, druga sygnatura czasowa):

[{"target": "metric_name", "datapoints": [[175562.0, 1431803460], [176125.0, 1431803520], [176125.0, 1431803580], [175710.0, 1431803640], [175710.0, 1431803700], [175733.0, 1431803760], [175733.0, 1431803820], [175839.0, 1431803880], [175839.0, 1431803940], [175245.0, 1431804000], [175217.0, 1431804060], [175629.0, 1431804120], [175104.0, 1431804180], [175104.0, 1431804240], [175505.0, 1431804300]]}]

Co próbuję osiągnąć

Stworzyłem skrypt Pythona, który odbiera ostatnie punkty danych, porównuje je ze średnią historyczną i ostrzega o nagłej zmianie lub spadku. Z powodu sezonowości próg „statyczny” nie działa dobrze, a skrypt generuje fałszywe alarmy. Chcę ulepszyć algorytm ostrzegania, aby był bardziej precyzyjny i działał bez ciągłego dostrajania progu ostrzegania.

Czego potrzebuję i co odkryłem

Korzystając z googlingu, pomyślałem, że szukam algorytmów uczenia maszynowego do wykrywania anomalii (te nienadzorowane). Dalsze dochodzenie wykazało, że jest ich mnóstwo i bardzo trudno jest zrozumieć, który z nich ma zastosowanie w moim przypadku. Z powodu mojej ograniczonej wiedzy matematycznej nie potrafię czytać wyrafinowanych prac naukowych i szukam czegoś prostego dla początkującego w tej dziedzinie.

Lubię Pythona i trochę znam R, dlatego chętnie zobaczę przykłady dla tych języków. Proszę polecić dobrą książkę lub artykuł, który pomoże mi rozwiązać mój problem. Dziękuję za poświęcony czas i przepraszam za tak długi opis

Przydatne linki

Podobne pytania:

Zasoby zewnętrzne:

— Ilja Chadykin
źródło

1

Czy spojrzałeś na jeden z najprostszych algorytmów, takich jak CUSUM?

— Vladislavs Dovgalecs

@xeon, jeszcze nie. Jestem nowy w temacie i potrzebuję trochę czasu, aby wszystko przetrawić. Dzięki za poruszenie tej kwestii, jest to dobry punkt wyjścia, mogę ją teraz wdrożyć

— Ilya Khadykin

1

To świetne pytanie, @ ma-ge. Mam podobny scenariusz. Moje podejście polegało na ustawianiu alertów poprzez budowanie ciągłych prognoz okresowych za pomocą auto.arimafunkcji z doskonałego forecastpakietu R. (patrz jstatsoft.org/v27/i03/paper ). Możesz dostroić poziomy ufności, dostosowując levelparametr, np

data.model <- auto.arima(data.zoo, ic = c("bic")); data.prediction.warningLimits <- forecast(data.model, h=1, level=0.99)

.

— Alex Woolford

3

Faceci z Twittera napisali bardzo interesujący artykuł na ten temat. Sprawdź to: blog.twitter.com/2015/…

— ognjenz

Hej @IlyaKhadykin Mam nadzieję, że masz się dobrze! czy kiedykolwiek znalazłeś jakieś rozwiązanie tego problemu? Robię coś dokładnie tego samego, w którym z każdą minutą mamy określonych użytkowników, a także dostajemy wiele fałszywych pozytywów. Na razie obliczamy wynik dla każdej 5-minutowej przerwy i dopasowujemy ją do wzorca historycznego. JEŚLI MASZ JAKIEKOLWIEK SZCZEGÓLNE DZIAŁANIE ALGORYTMU, CZY MOŻESZ UDOSTĘPNIĆ, JAK TO ZROBIŁEŚ. Z góry dziękuję!

— ak3191

23

Myślę, że kluczem jest „nieoczekiwany” kwalifikator na twoim wykresie. Aby wykryć nieoczekiwane , musisz wiedzieć, czego się spodziewać .

Zaczynam od prostego modelu szeregów czasowych, takiego jak AR (p) lub ARMA (p, q). Dopasuj go do danych, dodaj sezonowość odpowiednio do potrzeb. Na przykład twoim modelem SAR (1) (24) może być: , gdzie oznacza czas w godzinach. Więc przewidujesz wykres na następną godzinę. Ilekroć błąd prognozy jest „za duży”, alert. $y_{t}=c+\phi y_{t-1}+\Phi_{24}y_{t-24}+\Phi_{25}y_{t-25}+\varepsilon_t$ $t$ $e_t=y_t-\hat y_t$

Po oszacowaniu modelu otrzymasz wariancję błędu . W zależności od założeń dystrybucyjnych, takich jak normalne, można ustawić próg w oparciu o prawdopodobieństwo, takie jak dla 99,7% lub jednostronne . $\sigma_\varepsilon$ $\varepsilon_t$ $|e_t|<3\sigma_\varepsilon$ $e_t>3\sigma_\varepsilon$

Liczba odwiedzających jest prawdopodobnie dość trwała, ale bardzo sezonowa. Lepiej byłoby wypróbować manekiny sezonowe zamiast multiplikatywnej sezonowości, wtedy wypróbowałbyś ARMAX, gdzie X oznacza zmienne egzogeniczne, które mogą być niczym manekin wakacyjny, manekin godzinowy, manekin weekendowy itp.

— Aksakal
źródło

5

Podejście to zakłada określony model ARIMA, który będzie miał tendencyjne parametry w oparciu o anomalie, które domyślnie uznano za nieistniejące. Bardziej ogólnym podejściem byłoby TAKŻE najpierw zidentyfikowanie anomalii, a następnie optymalny model ARIMA prowadzący do wbudowanych testów istotności. Dodatkowymi anomaliami mogą być przesunięcia poziomu, pulsacje sezonowe i trendy czasu lokalnego, które wymagają bardziej ogólnego rozwiązania niż zaproponowano tutaj. Zobacz unc.edu/~jbhill/tsay.pdf kompleksowej procedury. Aby uzyskać więcej informacji, możesz także użyć Google „Automatyczne wykrywanie interwencji”.

— IrishStat

@IrishStat Zasugerowałem ARIMAX z manekinami na imprezy. OP może uwzględnić znane zdarzenia, takie jak awarie witryn internetowych z manekinami. Spowoduje to zmniejszenie wariancji błędów i pojawi się więcej alertów. Nie ma powodu, aby budować skomplikowany model, ponieważ po prostu niemożliwe jest rozliczenie wszystkiego, jeśli chodzi o ruch w witrynie. Proste modele będą działać najlepiej.

— Aksakal

2

@ ma-ge, jeszcze jedno: możesz użyć nakładających się interwałów. Załóżmy, że gromadzisz dane co minutę, ale w przypadku modelowania możesz wybrać krok w 10 minut. Powoduje to pewne problemy dotyczące szacowania (z powodu autokorelacji), ale model wynikowy najprawdopodobniej będzie bardziej niezawodny.

— Aksakal

@Aksakal Modele powinny być tak proste, jak to konieczne, ALE niezbyt proste.

— IrishStat

17

Na blogu technicznym Netflix znajduje się artykuł na temat ich narzędzia do wykrywania niezawodnych anomalii (RAD). http://techblog.netflix.com/2015/02/rad-outlier-detection-on-big-data.html

Zajmuje się sezonowością i zestawami danych o bardzo dużej objętości, więc może pasować do twoich wymagań. Kod jest open source Java i Apache Pig https://github.com/Netflix/Surus/blob/master/resources/examples/pig/rad.pig

Podstawowy algorytm oparty jest na solidnym PCA - patrz oryginalny artykuł tutaj: http://statweb.stanford.edu/~candes/papers/RobustPCA.pdf

— Paul McGettigan
źródło

12

Większość algorytmów wykrywania wartości odstających w pakiecie open source dotyczy danych biznesowych szeregów czasowych o niskiej częstotliwości, dane dotyczące częstotliwości dziennej / tygodniowej / miesięcznej. Wydaje się, że te dane dotyczą wyspecjalizowanego obszaru, który jest rejestrowany w kilka minut, więc nie jestem pewien, czy wykrycie wartości odstających typu open source byłoby pomocne. Możesz spróbować dostosować to podejście do swoich danych.

Poniżej przedstawiam niektóre dostępne podejścia do pakietów w open source R:

tsoutliers : Implementuje algorytm detekcji wartości odstających Chen i Liu w ramach arima. zobacz moje wcześniejsze pytanie na tej stronie. Fantastyczne podejście, ale bardzo powolne, nie jestem pewien, czy będzie w stanie obsłużyć dane o wysokiej częstotliwości, takie jak twoje. Ma zaletę wykrywania wszystkich typów wartości odstających, jak wspomniano w moim wcześniejszym pytaniu / poście.
Wykrywanie anomalii na Twitterze : wykorzystuje algorytm Rosnera do wykrywania anomalii na podstawie szeregów czasowych. Algorytm rozkłada szeregi czasowe, a następnie wykrywa anomalie. Moim osobistym zdaniem nie jest to skuteczne i dokładne wykrywanie wartości odstających w szeregach czasowych.
tsoutlier w pakiecie prognozy: podobny do algorytmu twittera pod względem rozkładu szeregów czasowych, a następnie wykrywania wartości odstających. Wykryje tylko wartości odstające lub impulsy addytywne.

Istnieją pakiety komercyjne, które mają dedykowane podejścia do prób wykrycia nieprawidłowości. Innym klasycznym podejściem jest TSAY za algorytm wykrywania seria poboczna czas, podobnie jak podejście Chen i Liu wykrywa różne typy skrajnych. Niedawno natknąłem się również na to komercyjne rozwiązanie programowe o nazwie metafor, które może być bardziej odpowiednie dla twoich danych.

Mam nadzieję, że to jest pomocne

— Synoptyk
źródło

Dzięki, daje mi spojrzenie na podobne problemy i podejścia; specjalne podziękowania za linki!

— Ilya Khadykin

Jeśli ktoś szuka Metafor, zostaliśmy przejęci przez Splunk. Nasze algorytmy TSAD są zawarte w najnowszych wersjach Splunk IT Service Intelligence („ITSI”).

— Alex Cruise,

4

Czy próbowałeś używać reguł statystycznej kontroli procesu (np. Western Electric http://en.wikipedia.org/wiki/Western_Electric_rules )?

Używam ich do danych szeregów czasowych - często z odrobiną intuicji na temat danych - aby ocenić, czy dane idą gdzieś, gdzie nie chcę. Podobnie jak w przykładzie, reguły te mówią, że jeśli delta / zmiana jest spójna w kilku punktach danych, oznacza to, że może występować problem.

Również statystyczna kontrola procesu (SPC) może być przydatna do ćwiczenia, jeśli czujesz się lepiej lub gorzej niż wcześniej.

Jednym z problemów związanych z SPC jest to, że wiele z nich zależy od normalnej dystrybucji, która prawdopodobnie nie pasuje do twoich danych, która nie może spaść poniżej zera. Inni lepiej niż ja z SPC mogą tutaj sugerować opcje. Lubię używać go do oznaczania problemu, ale podobnie jak wszystkie modele, najlepiej jest go używać z dużą ilością wiedzy na temat samych danych (i źródła).

— MarkR
źródło

4

Innych odpowiedzi, o których nie wspominano, jest to, że twój problem brzmi jak wykrycie punktu zmiany . Ideą wykrywania zmiennego punktu jest to, że szukasz segmentów w swoich danych, które znacznie różnią się pod względem właściwości (np. Średnia, wariancja). Można to osiągnąć stosując moje oszacowanie maksymalnego prawdopodobieństwa, gdzie dla punktów wymiany jest funkcja prawdopodobieństwa $m$

L (m, τ_{1 : m}, θ_{1 : (m + 1)}) = \prod_{i = 1}^{m + 1} p (y_{(τ_{i - 1} + 1) : τ_{i}} ∣ θ_{i})

$L(m, \tau_{1:m}, \theta_{1:(m+1)}) = \prod_{i=1}^{m+1} p(y_{(\tau_{i-1} + 1):\tau_i}\mid \theta_i)$

gdzie to twoje dane, są punktami granicznymi zaznaczającymi zmiany, a rozkłady prawdopodobieństwa są parametryzowane przez dla każdego segmentu. Można to łatwo uogólnić, aby zobaczyć różne sytuacje. Istnieje szereg algorytmów do wyszukiwania parametrów, w tym do znalezienia nieznanego . Dostępne jest również oprogramowanie do szacowania takich modeli, np. Pakiet dla R. Jeśli chcesz dowiedzieć się więcej, możesz sprawdzić następujące publikacje i odnośniki: $y_1,\dots,y_n$ $1 < \tau_1 <\dots<\tau_m<n$ $p$ $\theta_i$ $i$ $m$ changepoint

Rebecca Killick i Idris A. Eckley. (2013) changepoint: Pakiet R do analizy Changepoint. (papier online)

Eckley, IA, Fearnhead, P. i Killick, R. (2011) Analiza modeli punktów wymiany. [w:] Bayesian Time Series Models , wyd. D. Barber, AT Cemgil i S. Chiappa, Cambridge University Press.

— Tim
źródło

4

Biorąc pod uwagę, że okresowość szeregów czasowych powinna być dobrze zrozumiana, można opracować prosty, ale skuteczny algorytm oparty na różnicowaniu.

Proste różnicowanie w jednym kroku wykryje nagły spadek od poprzedniej wartości

y_{t}^{'} = y_{t} - y_{t - 1}

$y_t'= y_t - y_{t-1}$

ale jeśli seria ma silny składnik okresowy, można oczekiwać, że spadek ten będzie znaczny regularnie. W takim przypadku lepiej byłoby porównać dowolną wartość z jej odpowiednikiem w tym samym punkcie poprzedniego cyklu, tj. Jeden okres temu.

y_{t}^{'} = y_{t} - y_{t - n} where n = length of period

$y_t'= y_t - y_{t-n} \quad \text{where } n=\text{length of period}$

W przypadku zamieszczonego pytania byłoby naturalne oczekiwać dwóch istotnych składników okresowych, jednego o długości jednego dnia, drugiego o długości tygodnia. Nie jest to jednak zbyt skomplikowane, ponieważ długość dłuższego okresu można starannie podzielić przez długość krótszego.

$n$ $24*7 = 168$

Jeśli spadki mają charakter bardziej proporcjonalny, prosta różnica z łatwością nie wykryje nagłego spadku, gdy aktywność jest niska. W takich okolicznościach algorytm można zmodyfikować w celu obliczenia współczynników.

y_{t}^{*} = \frac{y_{t}}{y_{t - n}}

$y_t^*= \frac{y_t}{y_{t-n}}$

Zrobiłem kilka testów w R przy użyciu symulowanego zestawu danych. Próbkowane są w nim dane 6 razy dziennie i występują silne okresy dzienne i tygodniowe, a także inne zakłócenia i fluktuacje. Krople dodawano w losowych miejscach o czasie trwania od 1 do 3.
Aby wyodrębnić krople, najpierw obliczono stosunki w odległości 42, a następnie wartość progową ustaloną na 0,6, ponieważ interesująca jest tylko ujemna zmiana określonego rozmiaru. Następnie obliczono różnicę o jeden krok i próg ustalono na -0,5. W końcu jeden fałszywie pozytywny przeszedł przez (ten pod koniec 16 tygodnia). Wykresy po lewej i prawej stronie pokazują te same dane, tylko na różne sposoby.

— AkselA
źródło

3

Czy bardziej użyteczne byłoby myślenie o zmianach w szeregu czasowym raczej jako początek nowego trendu niż anomalii? Zrozumienie różnicy między sąsiednimi punktami pomogłoby stwierdzić, kiedy nachylenie (pochodna) zmienia się i może sygnalizować początek nowego trendu w dacie. Przydatne może być również uwzględnienie różnic wartości różnic (druga pochodna). Wyszukiwanie w Google „początkowego trendu w szeregu czasowym” może dać dobre sugestie dotyczące metod. W danych finansowych późno zwraca się uwagę na nowe trendy (kupujesz lub sprzedajesz?), Więc są artykuły na ten temat.

Dobrym wstępem do wavelet jest „Świat według fal” Hubbarda, który, jak sądzę, jest autorem.

— DavidF
źródło

2

Udało mi się uzyskać dobre wyniki dla szeregów czasowych z wieloma sezonami (codziennie, co tydzień) przy użyciu dwóch różnych algorytmów:

Rozkład trendów sezonowych za pomocą lessu (lub STL) w celu ustalenia serii punktów środkowych.
Regresja nieliniowa w celu ustalenia progów wokół tego punktu środkowego, na podstawie zależności między wariancją a poziomem.

STL dokonuje rozkładu domeny szeregów czasowych na składnik trendu, pojedynczy składnik sezonowy i pozostałą część. Element sezonowy to twoja sezonowość wysokich częstotliwości (np. Codziennie), podczas gdy trend obejmuje zarówno sezonowość niskiej częstotliwości (np. Tygodniowo), jak i właściwy trend. Możesz je rozdzielić, po prostu ponownie uruchamiając STL dla trendu. W każdym razie, gdy odizolujesz pozostałe serie od innych komponentów, możesz przeprowadzić wykrywanie anomalii względem tej serii.

Tutaj napisałem bardziej szczegółowy:

https://techblog.expedia.com/2016/07/28/applying-data-science-to-monitoring/

— Willie Wheeler
źródło

1

Zainspirowany Davidem, czy próbowałeś użyć FFT? Może być w stanie wykryć nagłe spadki, ponieważ wskazują one na twoje anomalie. Anomalie mogą pojawić się w wąskim spektrum. Możesz więc łatwo je uchwycić.

— Romeo Kienzler
źródło