Algorithme simple pour la détection des valeurs aberrantes en ligne d'une série chronologique générique

Je travaille avec une grande quantité de séries chronologiques. Ces séries temporelles sont essentiellement des mesures de réseau toutes les 10 minutes, et certaines sont périodiques (c'est-à-dire la bande passante), d'autres pas (c'est-à-dire la quantité de trafic de routage).

Je voudrais un algorithme simple pour faire une "détection des valeurs aberrantes" en ligne. Fondamentalement, je souhaite conserver en mémoire (ou sur disque) l'intégralité des données historiques de chaque série chronologique et détecter toute valeur aberrante dans un scénario réel (chaque fois qu'un nouvel échantillon est capturé). Quel est le meilleur moyen d’atteindre ces résultats?

J'utilise actuellement une moyenne mobile afin de supprimer un peu de bruit, mais ensuite? Des choses simples comme l'écart type, fou, ... par rapport à l'ensemble des données ne fonctionnent pas bien (je ne peux pas supposer que les séries chronologiques sont stationnaires), et j'aimerais quelque chose de plus "précis", idéalement une boîte noire telle que:

double outlier_detection (double * vecteur, double valeur);

où vecteur est le tableau de double contenant les données historiques et la valeur renvoyée est le score d'anomalie pour le nouvel échantillon "valeur".

Voici une simple fonction R qui trouvera des valeurs éloignées de la série temporelle (et les affichera éventuellement dans un graphique). Il traitera les séries chronologiques saisonnières et non saisonnières. L'idée de base est de trouver des estimations robustes de la tendance et des composantes saisonnières et de les soustraire. Puis trouvez des valeurs aberrantes dans les résidus. Le test pour les valeurs aberrantes résiduelles est le même que pour la boîte à moustaches standard - les points supérieurs à 1,5 IQR au-dessus ou en dessous des quartiles inférieur et supérieur sont considérés comme des valeurs aberrantes. Le nombre d'IQR au-dessus / au-dessous de ces seuils est renvoyé sous forme de "score" aberrant. Donc, le score peut être n'importe quel nombre positif et sera égal à zéro pour les non-aberrants.

Je réalise que vous n'implémentez pas ceci dans R, mais je trouve souvent qu'une fonction R est un bon point de départ. Ensuite, la tâche est de traduire cela dans la langue requise.

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)
}

Une bonne solution aura plusieurs ingrédients, y compris:

• Utilisez une fenêtre mobile résistante et lisse pour éliminer la non-stationnarité.

• Ré-exprimez les données d'origine de sorte que les résidus par rapport au lissé soient répartis de manière approximativement symétrique. Compte tenu de la nature de vos données, il est probable que leurs racines carrées ou logarithmes donnent des résidus symétriques.

• Appliquez les méthodes de la carte de contrôle, ou au moins la pensée de la carte de contrôle, aux résidus.

En ce qui concerne ce dernier point, la carte de contrôle montre que des seuils "conventionnels" tels que 2 SD ou 1,5 fois le IQR au-delà des quartiles fonctionnent mal car ils génèrent trop de faux signaux incontrôlables. Les gens utilisent généralement 3 écarts-types dans les tableaux de contrôle, d'où 2,5 (voire 3) le IQR au-delà des quartiles serait un bon point de départ.

J'ai plus ou moins décrit la nature de la solution de Rob Hyndman en y ajoutant deux points principaux: le besoin éventuel de ré-exprimer les données et la sagesse de faire preuve de plus de prudence en signalant une valeur aberrante. Je ne suis pas sûr que Loess soit bon pour un détecteur en ligne, car cela ne fonctionne pas bien sur les terminaux. Vous pourriez plutôt utiliser quelque chose d'aussi simple qu'un filtre médian en mouvement (comme dans le lissage résistant de Tukey). Si les valeurs aberrantes n'entrent pas en rafales, vous pouvez utiliser une fenêtre étroite (5 points de données, peut-être, qui ne fonctionneront qu'avec une rafale de 3 valeurs aberrantes ou plus dans un groupe de 5).

Une fois que vous avez effectué l'analyse pour déterminer une bonne ré-expression des données, il est peu probable que vous deviez changer la ré-expression. Par conséquent, votre détecteur en ligne n'a vraiment besoin que de référencer les valeurs les plus récentes (la dernière fenêtre) car il n'utilisera pas du tout les données précédentes. Si vous avez de très longues séries chronologiques, vous pouvez aller plus loin dans l'analyse de l'autocorrélation et de la saisonnalité (telles que les fluctuations journalières ou hebdomadaires récurrentes) afin d'améliorer la procédure.

(Cette réponse répond à une question en double (maintenant fermée) de Détecter les événements en attente , qui présente certaines données sous forme graphique.)

La détection des valeurs aberrantes dépend de la nature des données et de ce que vous êtes prêt à assumer à leur sujet. Les méthodes générales reposent sur des statistiques robustes. L'esprit de cette approche est de caractériser la majeure partie des données de manière à ne pas être influencé par des valeurs aberrantes, puis de pointer sur des valeurs individuelles ne correspondant pas à cette caractérisation.

Comme il s’agit d’une série chronologique, le fait de devoir (re) détecter les valeurs aberrantes sur une base continue s’ajoute à la complication. Si cela doit être fait au fur et à mesure du déroulement de la série, nous ne pouvons utiliser que des données plus anciennes pour la détection, pas des données futures! De plus, comme protection contre les nombreux tests répétés, nous voudrions utiliser une méthode qui a un très faible taux de faux positifs.

Ces considérations suggèrent d'exécuter un test des valeurs aberrantes de fenêtre mobile simple et robuste sur les données . Il existe de nombreuses possibilités, mais une solution simple, facile à comprendre et à appliquer est basée sur un MAD en cours: déviation absolue médiane par rapport à la médiane. Il s'agit d'une mesure fortement robuste de la variation dans les données, semblable à un écart-type. Un pic éloigné serait supérieur de plusieurs DAM ou plus à la médiane.

Il reste encore quelques ajustements à faire : quelle déviation par rapport au volume de données devrait être considérée comme dépassée et combien de temps dans le passé faut-il regarder? Laissons cela comme paramètres d'expérimentation. Voici une Rimplémentation appliquée aux données (avec pour émuler les données) avec les valeurs correspondantes :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)

Appliqué à un ensemble de données tel que la courbe rouge illustrée dans la question, il produit ce résultat:

Les données sont affichées en rouge, la fenêtre de 30 jours des seuils médians + 5 * MAD en gris et les valeurs aberrantes - qui sont simplement les valeurs de données situées au-dessus de la courbe grise - en noir.

(Le seuil ne peut être calculé qu'à partir de la fin de la fenêtre initiale. Le premier seuil est utilisé pour toutes les données de cette fenêtre initiale: c'est pourquoi la courbe grise est plate entre x = 0 et x = 30.)

Les effets de la modification des paramètres sont (a) l’augmentation de la valeur de windowaura tendance à lisser la courbe grise et (b) l’augmentation de thresholdla valeur de la courbe grise. Sachant cela, on peut prendre un segment initial des données et identifier rapidement les valeurs des paramètres qui séparent le mieux les pics périphériques du reste des données. Appliquez ces valeurs de paramètre à la vérification du reste des données. Si un graphique montre que la méthode se détériore avec le temps, cela signifie que la nature des données change et que les paramètres peuvent nécessiter un réajustement.

Notez que cette méthode suppose peu de choses sur les données: elles ne doivent pas nécessairement être distribuées normalement; ils ne doivent présenter aucune périodicité; ils n'ont même pas besoin d'être non négatif. Tout ce qu’elle suppose, c’est que les données se comportent de manière raisonnablement similaire dans le temps et que les pics périphériques sont visiblement plus élevés que le reste des données.

Si quelqu'un souhaite expérimenter (ou comparer une autre solution à celle proposée ici), voici le code que j'ai utilisé pour produire des données telles que celles présentées dans la question.

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

Si des hypothèses concernant une approche particulière vous inquiètent, une approche consiste à former un certain nombre d'apprenants sur des signaux différents, puis à utiliser des méthodes d'ensemble et à agréger les «votes» de vos apprenants pour établir la classification des valeurs aberrantes.

BTW, cela peut valoir la peine d'être lu ou écrémé, car il fait référence à quelques approches du problème.

• Détection de valeurs aberrantes en ligne sur des flux de données

Je suppose qu'un modèle de série chronologique sophistiqué ne fonctionnera pas pour vous en raison du temps nécessaire pour détecter les valeurs éloignées à l'aide de cette méthodologie. Par conséquent, voici une solution de contournement:

1. Commencez par établir un modèle de trafic «normal» de base pour une année sur la base d'une analyse manuelle des données historiques, qui prend en compte l'heure du jour, le jour de la semaine par rapport au week-end, le mois de l'année, etc.

2. Utilisez cette ligne de base avec un mécanisme simple (par exemple, la moyenne mobile suggérée par Carlos) pour détecter les valeurs éloignées.

Vous pouvez également consulter la documentation sur le contrôle statistique des processus pour trouver des idées.

Ajustez les données de manière saisonnière, de sorte qu'un jour normal semble plus plat. Vous pouvez prélever l'échantillon de 17h00 et soustraire ou diviser la moyenne des 30 derniers jours à 17h00. Recherchez ensuite les N écarts-types (mesurés à l'aide de données pré-ajustées) pour les valeurs aberrantes. Cela pourrait être fait séparément pour les "saisons" hebdomadaires et quotidiennes.

Une alternative à l'approche décrite par Rob Hyndman serait d'utiliser Holt-Winters Forecasting . Les bandes de confiance dérivées de Holt-Winters peuvent être utilisées pour détecter les valeurs éloignées. Voici un article décrivant comment utiliser Holt-Winters pour "Détection de comportement aberrant dans les séries chronologiques pour la surveillance du réseau". Une implémentation pour RRDTool peut être trouvée ici .

L'analyse spectrale détecte la périodicité dans des séries chronologiques stationnaires. L’approche du domaine fréquentiel basée sur l’estimation de la densité spectrale est une approche que je vous recommanderais tout d’abord.

Si, pour certaines périodes, irrégularité signifie un pic beaucoup plus élevé que ce qui est typique pour cette période, la série présentant de telles irrégularités ne serait pas stationnaire et une analyse spectrale ne serait pas appropriée. Mais en supposant que vous ayez identifié la période comportant les irrégularités, vous devriez pouvoir déterminer approximativement la hauteur maximale normale et pouvoir ensuite fixer un seuil à un niveau supérieur à cette moyenne pour désigner les cas irréguliers.

S'agissant d'une série chronologique, un simple filtre exponentiel http://en.wikipedia.org/wiki/Exponential_smoothing lissera les données. C'est un très bon filtre car vous n'avez pas besoin d'accumuler d'anciens points de données. Comparez chaque valeur de données lissée récemment avec sa valeur non lissée . Une fois que l'écart dépasse un certain seuil prédéfini (selon ce que vous pensez être une valeur aberrante dans vos données), votre valeur aberrante peut alors être facilement détectée.

Dans CI, procédez comme suit pour un exemple 16 bits en temps réel (je pense que cela se trouve quelque part ici <Explication - https://dsp.stackexchange.com/questions/378/what-is-the-best-first-order -approximation-a-un-filtre-moyenne-mobile >)

#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;   
}

Vous pouvez utiliser l'écart type des N dernières mesures (vous devez choisir un N approprié). Un bon score d'anomalie serait le nombre d'écarts-types d'une mesure par rapport à la moyenne mobile.

ce que je fais est de regrouper les mesures par heure et par jour de la semaine et de comparer les écarts types de ces mesures. Ne corrige toujours pas pour des choses comme les vacances et la saisonnalité été / hiver, mais c'est correct la plupart du temps.

L'inconvénient est que vous devez vraiment collecter une année environ de données pour en avoir suffisamment pour que stddev commence à avoir un sens.

Je suggère le schéma ci-dessous, qui devrait être implémenté dans un jour ou deux:

Entraînement

• Recueillez autant d'échantillons que vous pouvez garder en mémoire
• Supprimer les valeurs aberrantes évidentes en utilisant l'écart type pour chaque attribut
• Calculer et stocker la matrice de corrélation ainsi que la moyenne de chaque attribut
• Calculer et stocker les distances de Mahalanobis de tous vos échantillons

Calcul de la "valeur aberrante":

Pour l'échantillon unique dont vous souhaitez connaître la "valeur aberrante":

• Récupérer les moyennes, la matrice de covariance et les distances de Mahalanobis à partir de la formation
• Calculez la distance "d" de Mahalanobis pour votre échantillon
• Renvoie le centile dans lequel "d" tombe (en utilisant les distances de Mahalanobis de l'entraînement)

Ce sera votre score aberrant: 100% est une aberration extrême.

Pour le cas où il faut rapidement calculer les valeurs aberrantes, on pourrait utiliser l’idée de Rob Hyndman et Mahito Sugiyama ( https://github.com/BorgwardtLab/sampling-outlier-detection , bibliothèque (spoutlier), fonction qsp) pour calculer les valeurs aberrantes comme suit:

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)
}

la détection d'anomalies nécessite la construction d'une équation qui décrit l'attente. La détection d'intervention est disponible dans un contexte non causal et causal. Si l'on a une série de prédicteurs comme le prix, les choses peuvent devenir un peu compliquées. Les autres réponses ne semblent pas prendre en compte la cause attribuable aux séries de prédicteurs spécifiés par l'utilisateur, telles que le prix, et pourraient donc être erronées. La quantité vendue peut dépendre du prix, peut-être des prix antérieurs et peut-être de la quantité vendue dans le passé. La base de la détection des anomalies (impulsions, impulsions saisonnières, changements de niveau et tendances de l'heure locale) se trouve dans https://pdfs.semanticscholar.org/09c4/ba8dd3cc88289caf18d71e8985bdd11ad21c.pdf