Anomaly Detection in Spatio-Temporal Tensor Streams Priyanga Dilini TalagalaJSM 2021
08/08/2021


 pridiltal
 prital.netlify.app
1

MotivationAll these applications generate millions or even billions of individual time series simultaneously
4

MotivationAll these applications generate millions or even billions of individual time series simultaneously
Research question: Finding locations of unusual behaviours
4

Spatio-Temporal Data

Spatio-Temporal Data6

Spatio-Temporal Data

Spatio-Temporal Tensor Data

Anomaly Detection in
Multivariate Spatio-temporal data
with K-measurements

devtools::install_github("pridiltal/mask")

India hourly air pollution data from 244 stations from October 2019 to September 2020

7 of the world's 10 most polluted cities are in India

(Source: IQAir AirVisual 2018 World Air Quality Report & Greenpeace)

PM2.5, PM10, NO2, NH3, SO2, CO, OZONE

MASK FrameworkMain ContributionsPropose a framework to detect spatial anomalies in spatio-temporal tensor data 
Unsupervised anomaly detection algorithm
14

MASK FrameworkMain ContributionsPropose a framework to detect spatial anomalies in spatio-temporal tensor data 
Unsupervised anomaly detection algorithm
What is an anomaly ?An anomaly is a spatial point or region that deviates significantly from the global and/or local distribution of a given network
14

Time-domain representation

Feature-domain representation

Figure reproduced from Talagala, T. S., Hyndman, R. J., & Athanasopoulos, G. (2018). Meta-learning how to forecast time series. Monash Econometrics and Business Statistics Working Papers, 6, 18.

Feature based representation of time seriesMean   
Variance  
Changing variance in remainder 
Level shift using rolling window   
Variance change 
Strength of linearity 
Strength of curvature 
Strength of spikiness 

Burstiness of time series (Fano Factor)  
Minimum  
Maximum  
The ratio between 50% trimmed mean and the arithmetic mean
Moment 
Ratio of means of data that is below and above the global mean  

16

Feature based representation of time series

Naive approach (Unfold PCA)Batch-wise unfolding of the three-way matrix into a two-dimensional matrix.19

Anomalous score calculation using Robust three-way analysis20

Anomalous score calculation using Robust three-way analysis21

Anomalous score calculation using Robust three-way analysis

Matrix SVD (Singular-Value Decomposition)

Anomalous score calculation using Robust three-way analysis

Matrix SVD (Singular-Value Decomposition)

The Tucker3 Model

The Robust Tucker3 Model

$X_{A} = A G (C \otimes B)^{t} + E$

Fitted model ${\hat{X}}_{A} = \hat{A} \hat{G} (\hat{C} \otimes \hat{B})^{t}$
Objective function: $\sum_{i = 1}^{I} \sum_{j = 1}^{J} \sum_{k = 1}^{K} (x_{i j k} - {\hat{x}}_{i j k})^{2}$ $= \sum_{i = 1}^{I} (x_{i} - \hat{x_{i}}) (x_{i} - \hat{x_{i}})^{t}$

Residual distance:

$R D_{i} = \sqrt{\sum_{j = 1}^{J} \sum_{k = 1}^{K} (x_{i j k} - {\hat{x}}_{i j k})^{2}}$

Palma, Todorov and Gallo (2014)

Anomalous score calculation using Robust three-way analysis24

Anomalous threshold calculation using Spacing theorem (Weissman, 1978)

Let $X_{1}, X_{2}, . . ., X_{n}$ be a sample from a distribution function $F$ .

Let $X_{1 : n} \geq X_{2 : n} \geq . . . \geq X_{n : n}$ be the order statistics.

The available data are $X_{1 : n}, X_{2 : n}, . . ., X_{k : n}$ for some fixed $k$ .

Let $D_{i, n} = X_{i : n} - X_{i + 1 : n},$ $(i = 1, 2, . . ., k)$ be the spacing between successive order statistics.

If $F$ is in the maximum domain of attraction of the Gumbel distribution, then the spacings $D_{i, n}$ are asymptotically independent and exponentially distributed with mean proportional to $i^{- 1}$ .

India hourly air pollution data from  244 stations from October 2019 to September 202026

India hourly air pollution data from  244 stations from October 2019 to September 202027

Advantages of the  mask frameworkDetect spatial anomalies in  spatio-temporal tensor data 
28

Advantages of the  mask frameworkDetect spatial anomalies in  spatio-temporal tensor data 
Can take the correlation structure of the  variables into account when detecting anomalies
28

Advantages of the  mask frameworkDetect spatial anomalies in  spatio-temporal tensor data 
Can take the correlation structure of the  variables into account when detecting anomalies
Deal with large amounts of data efficiently 
28

Advantages of the  mask frameworkDetect spatial anomalies in  spatio-temporal tensor data 
Can take the correlation structure of the  variables into account when detecting anomalies
Deal with large amounts of data efficiently 
Deal with time series of different lengths and/or starting points
28

Advantages of the  mask frameworkDetect spatial anomalies in  spatio-temporal tensor data 
Can take the correlation structure of the  variables into account when detecting anomalies
Deal with large amounts of data efficiently 
Deal with time series of different lengths and/or starting points
Anomalous scoring techniques- unsupervised
28

Advantages of the  mask frameworkDetect spatial anomalies in  spatio-temporal tensor data 
Can take the correlation structure of the  variables into account when detecting anomalies
Deal with large amounts of data efficiently 
Deal with time series of different lengths and/or starting points
Anomalous scoring techniques- unsupervised
Anomalous threshold has a probabilistic interpretation
28

Advantages of the  mask frameworkDetect spatial anomalies in  spatio-temporal tensor data 
Can take the correlation structure of the  variables into account when detecting anomalies
Deal with large amounts of data efficiently 
Deal with time series of different lengths and/or starting points
Anomalous scoring techniques- unsupervised
Anomalous threshold has a probabilistic interpretation
The framework can easily be extended to streaming data such that it can provide near-real-time support
28

stray/oddstream Vs mask

Definition: Recent past distribution of a given system
Semi-supervised

Definition: Current global and/or local distribution of a given system
Unsupervised

What next?Explore more on feature extraction and feature selection methods to create a better feature space suitable for streaming data context.
30

What next?Explore more on feature extraction and feature selection methods to create a better feature space suitable for streaming data context.
Use other dimension reduction techniques for tensor data such as  multilinear PLS (N-PLS) to see the effect on the performance of the proposed framework.
30

What next?Explore more on feature extraction and feature selection methods to create a better feature space suitable for streaming data context.
Use other dimension reduction techniques for tensor data such as  multilinear PLS (N-PLS) to see the effect on the performance of the proposed framework.
Develop effective, interactive data visualisation tools for further investigation of the detected spatial anomalies.
30

Thank you

priyangad@uom.lk

pridiltal

https://prital.netlify.app/
(Slides available)

devtools::install_github("pridiltal/mask")

Slides created via xaringan.

Key ReferencesDi Palma, M. A., V. Todorov, and M. Gallo. "Robust multiway analysis of compositional data in R."
Talagala, Priyanga Dilini, Rob J. Hyndman, and Kate Smith-Miles. "Anomaly detection in high-dimensional data." Journal of Computational and Graphical Statistics (2020): 1-15.
Talagala, P. D., Hyndman, R. J., Smith-Miles, K., Kandanaarachchi, S., & Munoz, M. A. (2020). Anomaly detection in streaming nonstationary temporal data. Journal of Computational and Graphical Statistics, 29(1), 13-27.
32

↑, ←, Pg Up, k	Go to previous slide
↓, →, Pg Dn, Space, j	Go to next slide
Home	Go to first slide
End	Go to last slide
Number + Return	Go to specific slide
b / m / f	Toggle blackout / mirrored / fullscreen mode
c	Clone slideshow
p	Toggle presenter mode
t	Restart the presentation timer
?, h	Toggle this help

Anomaly Detection in Spatio-Temporal Tensor Streams

Priyanga Dilini Talagala

JSM 2021

08/08/2021 pridiltal prital.netlify.app

Motivation

Motivation

Spatio-Temporal Data

Spatio-Temporal Data

Spatio-Temporal Data

Spatio-Temporal Tensor Data

Spatio-Temporal Tensor Data

Spatio-Temporal Tensor Data

Spatio-Temporal Tensor Data

Anomaly Detection in Multivariate Spatio-temporal data with K-measurements

India hourly air pollution data from 244 stations from October 2019 to September 2020

7 of the world's 10 most polluted cities are in India

MASK Framework

Main Contributions

MASK Framework

Main Contributions

What is an anomaly ?

Time-domain representation

Feature-domain representation

Feature based representation of time series

Feature based representation of time series

Feature based representation of time series

Naive approach (Unfold PCA)

Batch-wise unfolding of the three-way matrix into a two-dimensional matrix.

Anomalous score calculation using Robust three-way analysis

Anomalous score calculation using Robust three-way analysis

Anomalous score calculation using Robust three-way analysis

Anomalous score calculation using Robust three-way analysis

The Robust Tucker3 Model

Anomalous score calculation using Robust three-way analysis

Anomalous threshold calculation using Spacing theorem (Weissman, 1978)

India hourly air pollution data from 244 stations from October 2019 to September 2020

India hourly air pollution data from 244 stations from October 2019 to September 2020

Advantages of the mask framework

Advantages of the mask framework

Advantages of the mask framework

Advantages of the mask framework

Advantages of the mask framework

Advantages of the mask framework

Advantages of the mask framework

stray/oddstream Vs mask

What next?

What next?

What next?

Thank you

Key References

Help

08/08/2021

pridiltal
prital.netlify.app

Anomaly Detection in
Multivariate Spatio-temporal data
with K-measurements