Einfacher Algorithmus zur Online-Ausreißererkennung einer generischen Zeitreihe

Ich arbeite mit einer großen Anzahl von Zeitreihen. Bei diesen Zeitreihen handelt es sich im Grunde genommen um Netzwerkmessungen, die alle 10 Minuten durchgeführt werden. Einige davon sind periodisch (dh die Bandbreite), andere nicht (dh die Menge des Routingverkehrs).

Ich hätte gerne einen einfachen Algorithmus für eine Online- "Ausreißererkennung". Grundsätzlich möchte ich die gesamten Verlaufsdaten für jede Zeitreihe im Speicher (oder auf der Festplatte) behalten und Ausreißer in einem Live-Szenario erkennen (jedes Mal, wenn eine neue Stichprobe erfasst wird). Was ist der beste Weg, um diese Ergebnisse zu erzielen?

Ich verwende derzeit einen gleitenden Durchschnitt, um Rauschen zu entfernen, aber wie geht es dann weiter? Einfache Dinge wie Standardabweichung, verrückt, ... gegen den gesamten Datensatz funktionieren nicht gut (ich kann nicht davon ausgehen, dass die Zeitreihen stationär sind), und ich möchte etwas "genaueres", im Idealfall eine Blackbox wie:

double outlier_detection (double * vector, double value);

Dabei ist vector das Array von double, das die historischen Daten enthält, und der Rückgabewert die Anomaliebewertung für den neuen Stichproben- "Wert".

Hier ist eine einfache R-Funktion, die Ausreißer von Zeitreihen findet (und sie optional in einem Plot anzeigt). Es werden saisonale und nicht saisonale Zeitreihen verarbeitet. Die Grundidee besteht darin, robuste Schätzungen der Trend- und Saisonkomponenten zu finden und diese zu subtrahieren. Dann finden Sie Ausreißer in den Residuen. Der Test für verbleibende Ausreißer ist der gleiche wie für das Standard-Boxplot - Punkte größer als 1,5 IQR über oder unter dem oberen und unteren Quartil werden als Ausreißer angenommen. Die Anzahl der IQRs über / unter diesen Schwellenwerten wird als Ausreißer- "Punktzahl" zurückgegeben. Die Punktzahl kann also eine beliebige positive Zahl sein und für Nicht-Ausreißer Null.

Mir ist klar, dass Sie dies nicht in R implementieren, aber ich finde oft, dass eine R-Funktion ein guter Ausgangspunkt ist. Dann besteht die Aufgabe darin, dies in die jeweils gewünschte Sprache zu übersetzen.

tsoutliers <- function(x,plot=FALSE)
{
    x <- as.ts(x)
    if(frequency(x)>1)
        resid <- stl(x,s.window="periodic",robust=TRUE)$time.series[,3]
    else
    {
        tt <- 1:length(x)
        resid <- residuals(loess(x ~ tt))
    }
    resid.q <- quantile(resid,prob=c(0.25,0.75))
    iqr <- diff(resid.q)
    limits <- resid.q + 1.5*iqr*c(-1,1)
    score <- abs(pmin((resid-limits[1])/iqr,0) + pmax((resid - limits[2])/iqr,0))
    if(plot)
    {
        plot(x)
        x2 <- ts(rep(NA,length(x)))
        x2[score>0] <- x[score>0]
        tsp(x2) <- tsp(x)
        points(x2,pch=19,col="red")
        return(invisible(score))
    }
    else
        return(score)
}

Eine gute Lösung besteht aus mehreren Bestandteilen, darunter:

• Verwenden Sie ein widerstandsfähiges, sich bewegendes Fenster, um Unbeweglichkeit zu beseitigen.

• Drücken Sie die ursprünglichen Daten erneut aus, sodass die Residuen in Bezug auf die Glättung ungefähr symmetrisch verteilt sind. Aufgrund der Art Ihrer Daten ist es wahrscheinlich, dass ihre Quadratwurzeln oder Logarithmen symmetrische Residuen ergeben.

• Wenden Sie Kontrollkartenmethoden oder zumindest Kontrollkartendenken auf die Residuen an.

Was das letztere betrifft, so zeigt das Kontrolldiagramm-Denken, dass "herkömmliche" Schwellenwerte wie 2 SD oder das 1,5-fache des IQR jenseits der Quartile schlecht funktionieren, weil sie zu viele falsche außer Kontrolle geratene Signale auslösen. Bei der Arbeit mit Regelkarten werden normalerweise 3 SD verwendet, wobei das 2,5-fache (oder sogar das 3-fache) des IQR jenseits der Quartile ein guter Ausgangspunkt wäre.

Ich habe mehr oder weniger die Natur der Rob Hyndman-Lösung umrissen und dabei zwei Hauptpunkte hinzugefügt: die potenzielle Notwendigkeit, die Daten neu auszudrücken, und die Weisheit, konservativer bei der Signalisierung eines Ausreißers zu sein. Ich bin mir jedoch nicht sicher, ob Löss für einen Online-Detektor geeignet ist, da er an den Endpunkten nicht gut funktioniert. Sie können stattdessen einen so einfachen Filter wie einen Moving Median-Filter verwenden (wie bei Tukeys resistenter Glättung). Wenn Ausreißer nicht in Bursts auftreten, können Sie ein schmales Fenster verwenden (5 Datenpunkte, die möglicherweise nur mit einem Burst von 3 oder mehr Ausreißern innerhalb einer Gruppe von 5 zusammenbrechen).

Sobald Sie die Analyse durchgeführt haben, um eine gute Wiederholung der Daten festzustellen, ist es unwahrscheinlich, dass Sie die Wiederholung ändern müssen. Daher muss Ihr Online-Detektor nur auf die neuesten Werte (das neueste Fenster) verweisen, da er die früheren Daten überhaupt nicht verwendet. Wenn Sie sehr lange Zeitreihen haben, können Sie die Autokorrelation und die Saisonalität (z. B. wiederkehrende tägliche oder wöchentliche Schwankungen) weiter analysieren, um das Verfahren zu verbessern.

(Diese Antwort beantwortete eine doppelte (jetzt geschlossene) Frage unter Erkennen ausstehender Ereignisse , in der einige Daten in grafischer Form dargestellt wurden.)

Die Erkennung von Ausreißern hängt von der Art der Daten ab und davon, was Sie davon erwarten. Allzweckmethoden basieren auf robusten Statistiken. Bei diesem Ansatz geht es darum, den Großteil der Daten so zu charakterisieren, dass sie nicht von Ausreißern beeinflusst werden, und dann auf einzelne Werte zu verweisen, die nicht in diese Charakterisierung passen.

Da es sich um eine Zeitreihe handelt, ist es zusätzlich kompliziert, ständig Ausreißer (neu) erkennen zu müssen. Wenn dies im Verlauf der Serie geschehen soll, dürfen wir nur ältere Daten für die Erkennung verwenden, keine zukünftigen Daten! Zum Schutz vor den vielen wiederholten Tests möchten wir außerdem eine Methode verwenden, die eine sehr niedrige Rate an falsch positiven Ergebnissen aufweist.

Diese Überlegungen lassen darauf schließen, dass ein einfacher, robuster Ausreißertest für sich bewegende Fenster über die Daten ausgeführt wird . Es gibt viele Möglichkeiten, aber eine einfache, leicht zu verstehende und leicht zu implementierende basiert auf einem laufenden MAD: Median der absoluten Abweichung vom Median. Dies ist ein stark robustes Maß für die Variation innerhalb der Daten, ähnlich einer Standardabweichung. Ein äußerer Peak wäre mehrere MADs oder mehr größer als der Median.

Es bleibt noch einiges zu tun : Wie stark sollte eine Abweichung von der Masse der Daten von außen betrachtet werden, und wie weit sollte man in der Zeit zurückschauen? Lassen wir diese als Parameter für das Experimentieren. Hier ist eine RImplementierung, die auf Daten (mit , um die Daten zu emulieren) mit entsprechenden Werten angewendet wird :n = 1150 $x = (1,2,\ldots,n)$$n=1150$$y$

# Parameters to tune to the circumstances:
window <- 30
threshold <- 5

# An upper threshold ("ut") calculation based on the MAD:
library(zoo) # rollapply()
ut <- function(x) {m = median(x); median(x) + threshold * median(abs(x - m))}
z <- rollapply(zoo(y), window, ut, align="right")
z <- c(rep(z[1], window-1), z) # Use z[1] throughout the initial period
outliers <- y > z

# Graph the data, show the ut() cutoffs, and mark the outliers:
plot(x, y, type="l", lwd=2, col="#E00000", ylim=c(0, 20000))
lines(x, z, col="Gray")
points(x[outliers], y[outliers], pch=19)

Auf einen Datensatz wie die in der Frage dargestellte rote Kurve angewendet, ergibt sich folgendes Ergebnis:

Die Daten werden in Rot angezeigt, das 30-Tage-Fenster des Medians + 5 * MAD-Schwellenwerte in Grau und die Ausreißer - das sind einfach die Datenwerte über der Graukurve - in Schwarz.

(Der Schwellenwert kann nur ab dem Ende des Anfangsfensters berechnet werden . Für alle Daten in diesem Anfangsfenster wird der erste Schwellenwert verwendet. Deshalb ist die graue Kurve flach zwischen x = 0 und x = 30.)

Die Auswirkungen der Änderung der Parameter sind: (a) Erhöhen des Werts von windowglättet tendenziell die Graukurve und (b) Erhöhen thresholdder Graukurve. Wenn man dies weiß, kann man ein anfängliches Segment der Daten nehmen und schnell Werte der Parameter identifizieren, die die äußeren Peaks am besten vom Rest der Daten trennen. Wenden Sie diese Parameterwerte an, um den Rest der Daten zu überprüfen. Wenn ein Diagramm anzeigt, dass sich die Methode im Laufe der Zeit verschlechtert, bedeutet dies, dass sich die Art der Daten ändert und die Parameter möglicherweise neu eingestellt werden müssen.

Beachten Sie, wie wenig diese Methode von den Daten annimmt: Sie müssen nicht normal verteilt sein. Sie müssen keine Periodizität aufweisen. Sie müssen nicht einmal negativ sein. Es wird lediglich davon ausgegangen, dass sich die Daten im Laufe der Zeit auf einigermaßen ähnliche Weise verhalten und die äußeren Spitzen sichtbar höher sind als die übrigen Daten.

Wenn jemand experimentieren möchte (oder eine andere Lösung mit der hier angebotenen vergleichen möchte), ist hier der Code, mit dem ich Daten wie die in der Frage gezeigten erstellt habe.

n.length <- 1150
cycle.a <- 11
cycle.b <- 365/12
amp.a <- 800
amp.b <- 8000

set.seed(17)
x <- 1:n.length
baseline <- (1/2) * amp.a * (1 + sin(x * 2*pi / cycle.a)) * rgamma(n.length, 40, scale=1/40)
peaks <- rbinom(n.length, 1,  exp(2*(-1 + sin(((1 + x/2)^(1/5) / (1 + n.length/2)^(1/5))*x * 2*pi / cycle.b))*cycle.b))
y <- peaks * rgamma(n.length, 20, scale=amp.b/20) + baseline

Wenn Sie sich Sorgen über Annahmen mit einem bestimmten Ansatz machen, besteht ein Ansatz darin, mehrere Lernende auf verschiedene Signale vorzubereiten, dann Ensemblemethoden zu verwenden und die "Stimmen" Ihrer Lernenden zu aggregieren, um die Ausreißerklassifizierung vorzunehmen.

Übrigens, dies ist möglicherweise lesenswert oder lohnenswert, da es auf einige Lösungsansätze für das Problem verweist.

• Online-Ausreißererkennung über Datenströme

Ich vermute, dass ein ausgeklügeltes Zeitreihenmodell aufgrund der Zeit, die zum Erkennen von Ausreißern mit dieser Methode benötigt wird, für Sie nicht funktioniert. Daher ist hier eine Problemumgehung:

1. Stellen Sie zunächst anhand einer manuellen Analyse der historischen Daten, die die Uhrzeit, den Wochentag oder das Wochenende, den Monat des Jahres usw. berücksichtigen, ein "normales" Grundverkehrsmuster für ein Jahr auf.

2. Verwenden Sie diese Basislinie zusammen mit einem einfachen Mechanismus (z. B. einem von Carlos vorgeschlagenen gleitenden Durchschnitt), um Ausreißer zu erkennen.

Möglicherweise möchten Sie auch die statistische Prozesskontrollliteratur für einige Ideen durchsehen.

Passen Sie die Daten saisonal so an, dass ein normaler Tag eher flach erscheint. Sie können die heutige Probe von 17:00 Uhr nehmen und den Durchschnitt der letzten 30 Tage um 17:00 Uhr subtrahieren oder aufteilen. Suchen Sie dann nach N Standardabweichungen (gemessen mit voreingestellten Daten) nach Ausreißern. Dies könnte getrennt für wöchentliche und tägliche "Jahreszeiten" erfolgen.

Eine Alternative zu dem von Rob Hyndman skizzierten Ansatz wäre die Verwendung von Holt-Winters Forecasting . Die von Holt-Winters abgeleiteten Konfidenzbänder können zur Erkennung von Ausreißern verwendet werden. In diesem Artikel wird die Verwendung von Holt-Winters für die "Erkennung von Fehlern in Zeitreihen zur Netzwerküberwachung" beschrieben. Eine Implementierung für RRDTool finden Sie hier .

Die Spektralanalyse erkennt die Periodizität in stationären Zeitreihen. Der Frequenzbereichsansatz, der auf der Schätzung der spektralen Dichte basiert, ist ein Ansatz, den ich als ersten Schritt empfehlen würde.

Wenn für bestimmte Zeiträume eine Unregelmäßigkeit einen viel höheren Peak bedeutet als für diesen Zeitraum typisch, dann wären die Reihen mit solchen Unregelmäßigkeiten nicht stationär und eine Spektralanalyse wäre nicht angebracht. Unter der Annahme, dass Sie den Zeitraum mit den Unregelmäßigkeiten identifiziert haben, sollten Sie in der Lage sein, ungefähr die Höhe des normalen Peaks zu bestimmen, und können dann einen Schwellenwert festlegen, der über dem Durchschnitt liegt, um die unregelmäßigen Fälle zu kennzeichnen.

Da es sich um Zeitreihendaten handelt, glättet ein einfacher Exponentialfilter ( http://en.wikipedia.org/wiki/Exponential_smoothing) die Daten. Es ist ein sehr guter Filter, da Sie keine alten Datenpunkte akkumulieren müssen. Vergleichen Sie jeden neu geglätteten Datenwert mit seinem ungeglätteten Wert. Sobald die Abweichung einen bestimmten vordefinierten Schwellenwert überschreitet (abhängig davon, was Sie für einen Ausreißer in Ihren Daten halten), kann Ihr Ausreißer leicht erkannt werden.

In CI wird Sie wie folgt für eine Echtzeit - 16 - Bit - Probe (Ich glaube , das hier irgendwo gefunden <Erläuterung - https://dsp.stackexchange.com/questions/378/what-is-the-best-first-order -iir-approximation-zu-einem-gleitenden-durchschnitt-filter >)

#define BITS2 2     //< This is roughly = log2( 1 / alpha ), depending on how smooth you want your data to be

short Simple_Exp_Filter(int new_sample) 
{static int filtered_sample = 0;
long local_sample = sample << 16; /*We assume it is a 16 bit sample */
filtered_sample += (local_sample - filtered_sample) >> BITS2;   
return (short) ((filtered_sample+0x8000) >> 16); //< Round by adding .5 and truncating.   
}


int main()
{
newly_arrived = function_receive_new_sample();
filtered_sample = Simple_Exp_Filter(newly_arrived);
if (abs(newly_arrived - filtered_sample)/newly_arrived > THRESHOLD)
    {
    //AN OUTLIER HAS BEEN FOUND
    }
 return 0;   
}

Sie können die Standardabweichung der letzten N Messungen verwenden (Sie müssen ein geeignetes N auswählen). Ein guter Anomalie-Score wäre, wie viele Standardabweichungen eine Messung vom gleitenden Durchschnitt aufweist.

ich gruppiere die messungen nach stunde und tag der woche und vergleiche die standardabweichungen davon. Korrigiert immer noch nicht für Dinge wie Urlaub und Sommer- / Wintersaison, ist aber die meiste Zeit korrekt.

Der Nachteil ist, dass Sie wirklich ungefähr ein Jahr an Daten sammeln müssen, um genügend Daten zu haben, damit stddev Sinn ergibt.

Ich schlage das folgende Schema vor, das an einem Tag oder so implementiert werden sollte:

Ausbildung

• Sammeln Sie so viele Proben, wie Sie im Speicher halten können
• Entfernen Sie offensichtliche Ausreißer mit der Standardabweichung für jedes Attribut
• Berechnen und speichern Sie die Korrelationsmatrix sowie den Mittelwert der einzelnen Attribute
• Berechnen und speichern Sie die Mahalanobis-Entfernungen aller Ihrer Proben

Berechnung der "Outlierness":

Für das einzelne Beispiel, von dem Sie seine "Äußerlichkeit" wissen möchten:

• Rufen Sie die Mittelwerte, die Kovarianzmatrix und die Mahalanobis-Distanz s vom Training ab
• Berechnen Sie den Mahalanobis-Abstand "d" für Ihre Probe
• Geben Sie das Perzentil zurück, in das "d" fällt (unter Verwendung der Mahalanobis-Abstände vom Training).

Das ist Ihre Ausreißer-Punktzahl: 100% ist ein extremer Ausreißer.

Für den Fall, dass man die Ausreißer schnell berechnen muss, könnte man die Idee von Rob Hyndman und Mahito Sugiyama ( https://github.com/BorgwardtLab/sampling-outlier-detection , library (spoutlier), function qsp) verwenden, um zu berechnen die Ausreißer wie folgt:

library(spoutlier)
rapidtsoutliers <- function(x,plot=FALSE,seed=123)
{
    set.seed(seed)
    x <- as.numeric(x)
    tt <- 1:length(x)
    qspscore <- qsp(x)
    limit <- quantile(qspscore,prob=c(0.95))
    score <- pmax((qspscore - limit),0)
    if(plot)
    {
        plot(x,type="l")
        x2 <- ts(rep(NA,length(x)))
        x2[score>0] <- x[score>0]
        tsp(x2) <- tsp(x)
        points(x2,pch=19,col="red")
        return(invisible(score))
    }
    else
        return(score)
}

Die Erkennung von Anomalien erfordert die Erstellung einer Gleichung, die die Erwartung beschreibt. Die Interventionserkennung ist sowohl in nicht-kausaler als auch in kausaler Umgebung verfügbar. Wenn man eine Vorhersage-Serie wie den Preis hat, kann es etwas komplizierter werden. Andere Antworten hier scheinen nicht die zuweisbare Ursache zu berücksichtigen, die auf benutzerdefinierte Vorhersage-Reihen wie den Preis zurückzuführen ist, und könnten daher fehlerhaft sein. Die verkaufte Menge kann durchaus vom Preis, möglicherweise früheren Preisen und möglicherweise der in der Vergangenheit verkauften Menge abhängen. Die Grundlage für die Erkennung von Anomalien (Impulse, saisonale Impulse, Pegelverschiebungen und lokale Zeittrends) finden Sie unter https://pdfs.semanticscholar.org/09c4/ba8dd3cc88289caf18d71e8985bdd11ad21c.pdf