Matrix Profile XXVIII: Discovering Multi-Dimensional Time Series Anomalies with <i>K</i> of <i>N</i> Anomaly Detection<sup>†</sup>
Sadaf Tafazoli, Eamonn Keogh
Abstract
In recent years there has been significant progress in univariate time series anomaly detection. However, efforts to generalize this success to the multi-dimensional case have met with limited progress. The main difficultly appears to be that in any N-dimensional time series, the anomaly will generally only manifest itself on K of the time series, with K < N. This leads to a chicken-and-egg problem. If we knew which K time series exhibited the anomaly, it would be easy to discover its location. However, we do not know this in advance, and the search space is of size 2N and not obviously amiable to greedy search. In this work we show a novel, simple algorithm that allows us to quickly find the best K of N anomaly subset for any value of K. Moreover, we show a simple metric that can rank the top anomaly subsets for all values of K from 1 to N. While our methods are mostly agnostic to the anomaly scoring model, for concreteness we use the Matrix Profile, and show that we can discover multi-dimensional anomalies that would escape detection by all current rival methods.