Anomaly detection in time series using breakpoint detection and multiple testing
Détection d'anomalies dans les séries temporelles grâce à la détection de ruptures et aux tests multiples
Résumé
The purpose of this thesis is to develop new methods in the field of anomaly detection. An anomaly detector should identify data points that have been generated by a process different from the reference process.
In general, anomaly detectors are trained on past data and only consider the reference distribution given in the training set. Alternatively, the detector is updated in real time from a fixed length sliding window. Neither approach takes into account the true dynamics of the time series, leading to false positives when the reference distribution changes.
The proposed approach consists in detecting these distribution changes upstream, using breakpoint detectors. Anomalies are then retrieved within the identified homogeneous segments.
The advantage of this approach for a company like Worldline is that it can quickly detect incidents in its system, while reducing the number of false alarms.
In addition, care is taken to theoretically control the number of false positives through the False Detection Rate (FDR).
The first step is an attempt to develop a new estimator of the $p$-value. After comparison with existing estimators, this new estimator turns out to be too complex, with no real gain. The empirical $p$-value estimator is then used.
Then, the problem of anomaly detection on iid series is studied theoretically. A procedure is developed to control the FDR of a series of infinite length by controlling a variant of the FDR on subseries of fixed length. Empirical experiments show under which conditions this control is achieved in practice.
Finally, our new anomaly detector based on breakpoints is introduced for piecewise iid series. It is shown that the FDR control procedure is effective in this new context. However, the use of a breakpoint detector leads to two difficulties: small segment length and breakpoint detection delays. To overcome these difficulties, a confidence score is introduced. The detector is empirically evaluated to show the relevance and limitations of our approach.
L'objectif de ce travail est de développer de nouvelles méthodes dans le domaine de la détection d'anomalies. Un détecteur d'anomalies a pour but d'identifier les points de données qui ont été générés par un processus différent de celui de référence.
Généralement, les détecteurs d'anomalies sont entraînés sur un historique et ne prennent en compte que la loi de référence de l'ensemble d'entraînement. Ou alors, le détecteur est mis à jour en temps réel à partir d'une fenêtre glissante de longueur fixe. Aucune de ces approches ne tient compte de la dynamique réelle de la série temporelle, ce qui conduit à générer des faux positifs lorsque la loi de référence change.
L'approche que l'on propose consiste à détecter en amont ces changements de lois à l'aide de détecteurs de ruptures. Les anomalies sont ensuite retrouvées dans les segments homogènes qui viennent d'être identifiés.
L'intérêt de cette approche pour une entreprise comme Worldline est de pouvoir détecter les incidents survenant sur son système informatique rapidement et en réduisant le nombre de fausses alertes.
On prend aussi soin de contrôler théoriquement le nombre de faux positifs à travers le False Detection Rate (FDR).
Dans un premier temps, on tente de développer un nouvel estimateur de la $p$-valeur. Après comparaison avec l'existant, ce nouvel estimateur s'avère trop complexe sans gain réel. Par la suite, on travaille avec l'estimateur de la $p$-valeur empirique.
Puis, étudie théoriquement le problème de la détection d'anomalies sur des séries iid. On développe ainsi une procédure permettant le contrôle du FDR d'une série de longueur infinie en contrôlant une variante du FDR sur des sous-séries de longueur fixe. Les expériences empiriques permettent de montrer dans quelles conditions ce contrôle est atteint en pratique.
Enfin, on introduit notre nouveau détecteur d'anomalies basé sur les ruptures pour des séries iid par morceaux. On montre que la procédure de contrôle du FDR reste effective dans ce nouveau contexte. L'utilisation d'un détecteur de ruptures entraîne toutefois deux difficultés : les segments de petite longueur et les délais de détection de ruptures. Afin de traiter ces difficultés, on introduit un score de confiance. Le détecteur est évalué empiriquement dans le but de montrer la pertinence et les limites de notre approche.
Origine | Fichiers produits par l'(les) auteur(s) |
---|