Time series anomaly detection

Question

I am tasked to develop an anomaly detection system for data organised in many 1D (can be more than 1D if I choose, but I think that will complicate the problem even more) daily time series. The series are largely unseasonal, but they may have trends. I started with two simplest implementations, namely exponential time-weighted moving average (i.e. Holt part of Holt-Winters method, since there is no seasonality) and a simple differenced series Δ(t)= Y(t) – Y(t-1) to detect sudden huge movements.

Ultimately, I want to implement an ensemble with a collection of algorithms, because different algorithms deal with different anomalies. (for e.g. immediately after an anomaly, SD is so big that my first algorithm is essentially useless; on the other hand, if there are two consecutive anomalies, second algorithm can’t detect the latter one) Also, I don’t know what kind of anomalies are more important to the end-user, so if I have an ensemble system allowing user to review the result, there can be a supervised learning algorithm to learn the relative weights of different algos.

My concerns are that 1) I am not sure my two simple algorithms are good/robust enough. I reviewed literature, and found more involved statistical/probabilistic methods such as Kalman filter, ARIMA (I actually implemented ARIMA, but iterating to optimal parameters is computationally expensive. Also, it seems fitting ARIMA in python is really painful - takes long time, and gives me loads of warnings like Fail to Converge, and sometimes it just fails outright saying MA/AR coefficients are not invertible. Because I have a lot of time series, it is not possible to visually inspect autocorrelation/partial autocorrelation graphs by eye. However, if you have solution to this problem, I am definitely willing to try) and machine learning algos (like clustering, k-neighbours, etc). I am wondering do are there any recommendations that may be relevant to my problem so I can make my approach more targeted?

2) While finding additive outliers is important, I am also interested implement change detection (e.g. detecting presence of ramp, mean change, variance change, etc.) A Google search did not yield too many promising results. Any suggestions on this area will be highly appreciated.

(using Python by the way)

Answer 1

A few years ago my team implemented a impulse detection algorithm in Holt-Winters (HW) context, this time with strong seasonality and no trend.

The main idea was to look for an unusual difference between prediction at time $t$ and real value: an outlier that goes several times beyond the std. deviation of the noise (the std. deviation being estimated from the past errors).

This article was our starting point: http://www.jmlr.org/papers/volume9/li08a/li08a.pdf. It is worth reading. But soon we realized their precise idea did not and could not work (page 2222 point 3) even if the global outlier idea was OK.

There were many difficult points. One of them is once the impulse has started but not reached the threshold of "it's an impulse", HW is already influenced. We used sort of geometric sequences to balance the fact that is has already been influenced. This worked but was not easy and required a bit of work.

We also needed to work on repeated impulses and implement a rewind because sometimes it's not possible to process things online and you have to recompute things from the past, after eliminating the past impulses.

And this was just for impulses. Ramp is something else.

I don't believe ARIMA would be very helpful for this specific problem. It is more sophisticated but most often not better than HW. One problem: less robust, which is a problem especially with anomalies.

I would recommend to get your hands dirty and try something step by step until it works in most cases, fixing problems one by one. At least, I don't known any mature method to solve this generally.

Answer 2

An approach I can recommend is to use Tukeys methods from his EDA book. Use his smooth algorithms to split the time series into a smooth and a rough. The smooth acts acts as a reference level and the rough is how far the data is away from the reference level. Then apply Tukey outlier detection methods from box plots on the rough data to identify when the data is too far away from the smooth. I use various different versions of smooth and then combine these to give a result. You do not have to use the multiples Tukey recommends for outliers or far out values, you can use multiples that make sense for your data.