# Anomaly detection for time series

Anomaly detection (or outlier detection) is a common problem in many industries such as finance (card fraud detection), cyber security (intrusion detection), manufacturing (fault detection) or medicine (anomalous ECG signal). In many of these applications, the training data collected take the form of time series. In this post, we will review the different anomaly detection approaches in time series data.

## 1. Classifying the outlier detection techniques

### 1.1. Input data

• Univariate time series: only one set of observation varying with time.
• Multivariate time series: composed of 2 or more sets of observation recorded during the same period of time.

### 1.2. Outlier type

• Point outlier: when one specific point behaves unusually at a specific time compared to the other values.

(a) O1 and O2 are univariate point outliers.
(b) O1 and O2 are multivariate point outliers. O3 is a univariate point outlier in a multivariate time series.

• Subsequence outlier: when many consecutive points behave unusually

(a) O1 and O2 are univariate subsequence outliers.
(b) O1 and O2 are multivariate subsequence outliers. O3 is a univariate subsequence outlier in a multivariate time series.

• Outlier time series: when an entire time series is behaving unusually (only for multivariate time series)

Variable 4 is an outlier time series in a multivariate time series.

### 1.3. Nature of the method

• Univariate detection method: can only consider a single time-dependent variable (can be applied to univariate or multivariate time series)
• Multivariate detection method: can work with more than one time-dependent variable (can only be applied to multivariate time series)

## 2. Point outlier detection in univariate time series

• Temporal method: if the temporal order of the time series is important for the performance of the method (non-temporal methods will give the same results if the time series is shuffled)
• Streaming methods: if it is able to detect a new incoming data point as an outlier .

### 2.1. Model-based techniques

An anomaly is detected at a time t if the distance to its expected value is higher than a predefined threshold. These techniques fit a model to calculate the expected value, hence the name.

• Estimation model-based methods: if the expected value is calculated using past, current and future data.
• Prediction model-based methods: if the expected value is calculated using only the past data (suitable for detecting anomalies in streaming incoming data).

### 2.2. Density-based methods

In these methods, an anomaly is detected at a data point Xt if less than k neighbors are contained within a threshold of + or – a value R (this is calculated inside a rolling window, since we are dealing with time series).

For example, for a sliding window of length = 11, a number of neighbors k = 3 and a threshold R = 0.5, the points S4 and I10 are not outliers but O13 is an outlier. However when considering the window at time t = 17, the data point I13 is not an outlier anymore.

### 2.3. Histogramming

These methods consists in building a histogram representation of the time series, then detecting the points whose removal from the time series produces a histogram with lower error than the original.

Muthukrishnan et al. 2004

## 3. Point outlier detection in multivariate time series

### 3.1. Univariate techniques

Since a multivariate time series is composed of more than one time-dependent
variable, a univariate analysis can be performed for each variable to detect univariate point outliers, without considering dependencies that may exist between the variables. The same methods discussed in section 2 can be applied.

However, ignoring the correlation dependencies in multivariate time series lead to a loss of information. One solution consists in applying dimensionality reduction techniques to simply the multivariate time series into a lower dimensional representation. The new multivariate time series is composed of uncorrelated variables and univariate detection techniques can then be applied.

### 3.2. Multivariate techniques

These methods take into account the dependencies between the variables of a multivariate time series.

#### 3.2.1. Model-based

The model-based multivariate methods estimate an expected value and compare it with the actual value. There are 2 main types:

• estimation model: use past, current and future values (typically, autoencoder)
• prediction model: only use past values (more adapted for detecting outliers in a streaming fashion)

#### 3.2.2. Dissimilarity-based

These methods consists in measuring the dissimilarity between 2 multivariate points to identify outliers.

Cheng et al. [2008, 2009]
Li et al. 

#### 3.2.3. Histogramming

It’s a generalisation of the univariate case where the aim is to detect the vectors that should be removed so that the compressed representation (histogram) of the remaining data is improved.

Muthukrishnan et al. 

## 4. Subsequence outliers

The aim is to identify a set of consecutive points that jointly behave unusually. This is more challenging than point outlier detection.

### 4.1. Univariate time series

#### 4.1.2. Discord detection

This can be done using the HOT-SAX algorithm.

#### 4.1.2. Dissimilarity-based detection

These techniques are based on the direct comparison of subsequences using a reference of normality.

The reference of normality can be either the same time series, an external time series or the previous subsequence.

#### 4.1.3. Prediction Model-based

These methods intend to build a prediction model that captures the dynamics of the series using past data and thus make predictions of the future. Subsequences that are far from those predictions are flagged as outliers.

Munir et al. : use a CNN

#### 4.1.4. Frequency-based

A subsequence is an outlier if it does not appear as frequently as expected.

#### 4.1.5. Information Theory

The methods assume that a subsequence that occurs frequently is less surprising and thus carries less information than a rare subsequence. Therefore, the aim is to find infrequent but still repetitive subsequences with rare symbols, using the same time series as the reference of normality.