Algorithms for Time Series Anomaly Detection

Question

I'm currently using Twitter's AnomalyDetection in R: https://github.com/twitter/AnomalyDetection. This algorithm provides time series anomaly detection for data with seasonality.

Question: are there any other algorithms similar to this (controlling for seasonality doesn't matter)?

I'm trying to score as many time series algorithms as possible on my data so that I can pick the best one / ensemble.

Answer 1

Twitter algorithm is based on

Rosner, B., (May 1983), "Percentage Points for a Generalized ESD Many-Outlier Procedure" , Technometrics, 25(2), pp. 165-172

I'm sure there have been many techniques and advances since 1983!. I have tested on my internal data, and Twitter's anomaly detection does not identify obvious outliers. I would use other approaches as well to test for outliers in time series. The best that I have come across is Tsay's outlier detection procedure which is implemented in SAS/SPSS/Autobox and SCA software. All of which are commercial systems. There is also tsoutliers package which is great but needs specification of arima model in order to work efficiently. I have had issues with its default auto.arima with regards to optimization and model selection.

Tsay's article is a seminal work in outlier detection in time series. Leading journal in forecasting research International Journal of Forecasting mentioned that Tsay's article is one of the most cited work and most influential papers in an article linked above (also see below). Diffusion of this important work and other outlier detection algorithms in forecasting software(especially in open source software) is a rarity.

Answer 2

Here are the options for Anomaly Detection in R as of 2017.

Twitter's AnomalyDetection Package

• Works by using Seasonal Hybrid ESD (S-H-ESD);
• Builds upon the Generalized ESD test for detecting anomalies;
• Can detect both local and global anomalies;
• Employing time series decomposition and robust statistical metrics (e.g. median together with ESD)
• Employs piecewise approximation for long time series;
• Also has method for when time stamps are not available;
• Can specify direction of anomalies, window of interest, toggle the piecewise approximation, and has visuals support.

anomalyDetection Package (different from Twitter's)

• various approaches including Mahalanobis distance, factor analysis, Horn's parallel analysis, block inspection, principle components analysis ;
• Has method for dealing with the results.

tsoutliers package

• Detects outliers in time series following the Chen and Liu procedure (https://www.jstor.org/stable/2290724?seq=1#page_scan_tab_contents);
• Outliers are obtained based on 'less-contaminated' estimates of model parameters, estimated outlier effects using multiple linear regression, and estimates the model parameters and effects jointly.
• Considers innovational outliers, additive outliers, level shifts, temporary changes and seasonal level shifts.

anomalous-acm

• Works by computing a vector of features on each time series (e.g. include lag correlation, strength of seasonality, spectral entropy) then applying robust principal component decomposition on the features, and finally applying various bivariate outlier detection methods to the first two principal components;
• Enables the most unusual series, based on their feature vectors, to be identified;
• Package contains both real and synthetic datasets from Yahoo.

rainbow package

• Uses bagplots and boxplots;
• Identifies outliers with lowest depth or density.

kmodR package

• Uses an implementation of k-means proposed by Chawla and Gionis in 2013 (http://epubs.siam.org/doi/pdf/10.1137/1.9781611972832.21);
• Useful for creating (potentially) tighter clusters than standard k-means and simultaneously finding outliers inexpensively in multidimensional space.

washeR method

• Uses a new non-parametric methodology (https://rivista-statistica.unibo.it/article/viewFile/3617/2968)

The CRAN Task view for Robust Statistical Methods

• A variety of approaches for using robust statistical methods to detect outliers.

EDIT 2018

anomalize: Tidy Anomaly Detection

Answer 3

I've come across a few sources that may help you but they won't be as easy/convenient as running an R script over your data:

• Numenta have a open-sourced their NuPIC platform that is used for many things including anomaly detection.
• Netflix's Atlas Project will soon release an open-source outlier/anomaly detection tool.
• Prelert have an anomaly detection engine that comes as a server-side application. Their trial offers limited usage which may satisfy your needs.

Answer 4

Autobox(my company) provides outlier detection. Twitter's algorithm gets the big outliers, but misses the smaller ones compared to Autobox.

It takes a long time to run, but the results are better for finding the smaller outliers and also changes in the seasonality which are also outliers. Below is the model finding 79 outliers using the first 8,560 observations of 14,398 original observations. The standard version max's out at 10,000 observations, but it could be modified for more, but there is no real reason to have that much data anyway when you want to identify and respond to outliers.

We were influenced by the work done by Tsay on outliers, level shifts, and variance change and Chow's work on parameter changes along with our own work on detecting changes in seasonality,

If you download the 30 day trial and load in the Twitter example data and specify the frequency to be 60 and save 3 trigger files in the installation folder (noparcon.afs, novarcon.afs, notrend.afs) and create a file called stepupde.afs with 100.

Answer 5

In Python, the Anomaly Detection Toolkit (ADTK) provides really a nice interface and suit of functions. This talk from 2019 provides a walkthrough of the features, but essentially the same material can be found in the examples in the docs. The package provides 13 built-in methods for detection ranging from the very simple, e.g. thresholds, to the complex e.g. PCA residuals or changes in variability:

There are also nice plotting abilities and functions to deal with typical things like seasonality.