What algorithm should I use to detect anomalies on time-series?

Question

Background

I'm working in Network Operations Center, we monitor computer systems and their performance. One of the key metrics to monitor is a number of visitors\customers currently connected to our servers. To make it visible we (Ops team) collect such metrics as time-series data and draw graphs. Graphite allows us to do it, it has a pretty rich API which I use to build alerting system to notify our team if sudden drops (mostly) and other changes occur. For now I've set a static threshold based on avg value but it doesn't work very well (there are a lot of false-positives) due to different load during the day and week (seasonality factor).

It looks something like this:

The actual data (an example for one metric, 15 min time range; the first number is a number of users, the second - time stamp ):

[{"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]]}]

What I'm trying to accomplish

I've created a Python script which receives recent datapoints, compares them with historical average and alerts if there is a sudden change or drop. Due to seasonality "static" threshold doesn't work well and script generates false-positives alerts. I want to improve an alerting algorithm to be more precise and make it work without constant tuning the alerting threshold.

What advise I need and things I discovered

By googling I figured that I'm looking for machine learning algorithms for anomaly detection (unsupervised ones). Further investigation showed that there are tons of them and it's very difficult to understand which one is applicable in my case. Due to my limited math knowledge I can't read sophisticated scholar papers and I'm looking for something simple to a beginner in the field.

I like Python and familiar with R a bit, thus I'll be happy to see examples for these languages. Please recommend a good book or article which will help me to solve my problem. Thank you for your time and excuse me for such long description

Useful links

Similar questions:

• Time series and anomaly detection
• Time Series Anomaly Detection with Python
• Time series anomalies
• Algorithms for Time Series Anomaly Detection
• Application of wavelets to time-series-based anomaly detection algorithms
• Which algorithm should I use?

External resources:

• Machine Learning - Anomaly Detection Playlist on YouTube
• Detection Algorithms for Biosurveillance: A tutorial

Answer 1

I think the key is "unexpected" qualifier in your graph. In order to detect the unexpected you need to have an idea of what's expected.

I would start with a simple time series model such as AR(p) or ARMA(p,q). Fit it to data, add seasonality as appropriate. For instance, your SAR(1)(24) model could be: $y_{t}=c+\phi y_{t-1}+\Phi_{24}y_{t-24}+\Phi_{25}y_{t-25}+\varepsilon_t$, where $t$ is time in hours. So, you'd be predicting the graph for the next hour. Whenever the prediction error $e_t=y_t-\hat y_t$ is "too big" you throw an alert.

When you estimate the model you'll get the variance $\sigma_\varepsilon$ of the error $\varepsilon_t$. Depending on your distributional assumptions, such as normal, you can set the threshold based on the probability, such as $|e_t|<3\sigma_\varepsilon$ for 99.7% or one-sided $e_t>3\sigma_\varepsilon$.

The number of visitors is probably quite persistent, but super seasonal. It might work better to try seasonal dummies instead of the multiplicative seasonality, then you'd try ARMAX where X stands for exogenous variables, which could be anything like holiday dummy, hour dummies, weekend dummies etc.

Answer 2

On the Netflix tech blog there is an article on their Robust Anomaly Detection tool (RAD). http://techblog.netflix.com/2015/02/rad-outlier-detection-on-big-data.html

It deals with seasonality and very high volume datasets so it may fit your requirements. The code is open source Java and Apache Pig https://github.com/Netflix/Surus/blob/master/resources/examples/pig/rad.pig

The underlying algorithm is based on robust PCA - see original paper here: http://statweb.stanford.edu/~candes/papers/RobustPCA.pdf

Answer 3

Most outlier detection algorithms in open source package are for business time series data with low frequency, daily/weekly/monthly frequency data. This data appears to be for a specialized area that is captured in minutes, so I'm not sure if open source outlier detction would be helpful. You could try to adapt this approaches to your data.

Below I outline some available packages approaches in open source R:

1. tsoutliers: Implements Chen and Liu's outlier detection algorithm within arima framework. see my earlier question on this site. Fantastic approach, but very slow not sure if it will be able to handle high frequency data like yours. It has the advamtage of detecting all types of outliers as mentioned in my earlier question/post.
2. Twitter's Anomaly detection: Uses Rosner's algorithm to detect anomalies based in time series. The algorithm decomposes timeseries and then detects anomalies. In my personal opinion, this is not efficient and accurate in detecting outlires in time series.
3. tsoutlier in forecast package: Similar to twitter's algorithm in terms of decomposing time series and then detecting outliers. Only will detect additive outliers or pulses.

There are commercial packages that have dedicated approaches to try and detect anomolies. Another classic approach is Tsay's time series outlier detection algorithm, similar to Chen and Liu's approach it detects different types of outliers. I recently also stumbled on this commercial software solution called metafor which might be more suited for your data.

Hope this is helpful

Answer 4

What other answers didn't seems to mention is that your problem sounds like a changepoint detection. The idea of changapoint detection is that you are seeking for segments in your data that significantly differ in terms properties (e.g. mean, variance). This can be achieved my using maximum likelihood estimation, where for $m$ changepoints the likelihood function is

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

where $y_1,\dots,y_n$ is your data, $1 < \tau_1 <\dots<\tau_m<n$ are the boundary points marking the changes, and probability distributions $p$ are parametrized by $\theta_i$ for each $i$-th segment. This can be easily generalized to vide variety of situations. A number of algorithms exist to find the parameters, including finding the unknown $m$. There is also software that is available to estimating such models, e.g. changepoint package for R. If you want to learn more, you can check the following publications and the references they provide:

Rebecca Killick and Idris A. Eckley. (2013) changepoint: An R Package for Changepoint Analysis. (online paper)

Eckley, I.A., Fearnhead, P. and Killick, R. (2011) Analysis of changepoint models. [in:] Bayesian Time Series Models, eds. D. Barber, A.T. Cemgil and S. Chiappa, Cambridge University Press.

Answer 5

Have you tried using Statistical Process Control rules (e.g. Western Electric http://en.wikipedia.org/wiki/Western_Electric_rules)?

I use them for time series data - often with a touch of intuition about the data - to assess whether the data is going somewhere I don't want it to go. Like your example, these rules say if the delta / change is consistent over several data points, it flags that there may be an issue.

Also Statistical Process Control (SPC) can be good for working out if you are getting better or worse than before.

One issue with SPC is that much of it relies on a normal distribution which probably doesn't suit your data which can't go below zero. Others better than I with SPC can suggest options here. I like using it to flag an issue but, like all models, is best used with a grain of knowledge about the data itself (and source).

Answer 6

Given that the periodicity of the time series should be well understood a simple, but effective, algorithm based on differencing can be devised.

A simple one-step differencing will detect a sudden drop from a previous value

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

but if the series has a strong periodic component you'd expect that drop to be considerable at a regular basis. In this case it would be better to compare any value to its counterpart at the same point in the previous cycle, that is, one period ago.

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

In the case of the posted question it would be natural to expect two significant periodic components, one the length of a day, the other the length of a week. But this isn't much of a complication, as the length of the longer period can be neatly divided by the length of the shorter.

If the sampling is done every hour, $n$ in the above equation should be set to $24*7 = 168$

If the drops are more of a proportional character a simple difference will easily fail to detect a sudden drop when activity is low. In such circumstances the algorithm can be modified to calculate ratios instead.

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

I did some tests in R using a simulated dataset. In it data is sampled 6 times a day and there are strong daily and weekly periods, along with other noise and fluctuations. Drops were added in at random places and of durations between 1 and 3.
To isolate the drops first ratios was calculated at distance 42, then a threshold set at 0.6, as only negative change of a certain size is of interest. Then a one-step difference was calculated, and a threshold set at -0.5. In the end one false positive appears to have slipped through (the one at the end of week 16). The graphs at the left and right show the same data, just in different ways.

Answer 7

Would it be more useful to think of the changes in the time series as a beginning of a new trend rather than an anomaly? Taking the difference between adjacent points would help tell when the slope (derivative) is changing and might signal the beginning of a new trend in the date. Also taking the differences of the difference values (the second derivative ) might be of use. Doing a Google search on "times series beginning of trend) may give good suggestions for methods. In financial data a late of attention is paid to new trends (do you buy or sell?) so there's papers on this topic.

A good intro to wavelet is "The world according to wavelets" by Hubbard I believe is the author.

Answer 8

I was able to get some nice results for multiple-seasonality time series (daily, weekly) using two different algorithms:

• Seasonal-trend decomposition using loess (or STL) to establish the midpoint series.
• Nonlinear regression to establish thresholds around that midpoint, based on the relationship between the variance and the level.

STL does a time domain decomposition of your time series into a trend component, a single seasonal component, and a remainder. The seasonal component is your high frequency seasonality (e.g., daily), whereas the trend includes both the low frequency seasonality (e.g., weekly) and the trend proper. You can separate the two by simply running STL again on the trend. Anyway once you isolate the remainder series from the other components, you can perform your anomaly detection against that series.

I did a more detailed writeup here:

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

Answer 9

Inspired by David, have you tried to use FFT? It might be able to spot sudden drops because those are indicating your anomalies. The anomalies might appear in a narrow spectrum. So you can easily capture them.