class: center, middle, inverse, title-slide # Outlier Detection in Non-Stationary Data Streams ##
Priyanga Dilini Talagala
with
Rob J. Hyndman
Kate Smith-Miles ### Monash University, Australia
31.07.2018 --- background-image: url(https://raw.githubusercontent.com/pridiltal/pritalks/master/JSM2018/JSM2018/fig/2_application.png?token=ATXvCiBx5Sch5e4NjMoHVHdy7Zr3B9Xzks5baHbnwA%3D%3D) background-position: 50% 50% background-size: 100% class: right, top ## Motivation --- - Approaches to solving the problem of anomaly detection for temporal data : -- .pull-left[ ### Batch scenario - whole set of data is available - complete events <br/><br/><br/> <img src="fig/2_batch.png" width="100%" /> ] -- .pull-right[ ### Data stream scenario - continuous, unbounded, flow at high speed, high volume - incomplete events <img src="fig/1_stream.gif" width="100%" /> ] --- ### Feature Based Representation of Time series .pull-left[ - Mean - Variance - Changing variance in remainder - Level shift using rolling window - Variance change - Strength of linearity - Strength of curvature ] .pull-right[ - 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 ] --- class: top ### Feature Based Representation of Time series .pull-left[ <img src="fig/3_batch.png" width="100%" style="display: block; margin: auto;" /> ] .pull-right[ <img src="fig/tsfeatures.png" width="100%" style="display: block; margin: auto;" /> ] --- class: top ### Feature Based Representation of Time series .pull-left[ <img src="fig/3_batch.png" width="100%" style="display: block; margin: auto;" /> ] .pull-right[ <img src="fig/5_high_typical.gif" width="100%" style="display: block; margin: auto;" /> ] --- .pull-left[ <img src="fig/P2_plot21a.png" width="95%" style="display: block; margin: auto;" /> ] -- .pull-right[ <img src="fig/P2_plot21b.png" width="95%" style="display: block; margin: auto;" /> ] -- - We define an anomaly as an observation that is very unlikely given the recent distribution of a given system --- ### Main Contributions - Propose a framework that provides early detection of anomalies within a large collection of streaming time series data -- - Propose an algorithm that adapts to nonstationarity (concept drift) -- ### Main Assumptions - A representative data set of the system's typical behavior is available to define the model for the typical behavior of the system. -- ### Proposed Algorithm - Off-line Phase: Building a model of a system's typical behaviour; (similar to Clifton, Hugueny & Tarassenko, 2011) -- - On-line Phase: Testing newly arrived data using the boundary --- class: middle, center <img src="fig/12_logo1.png" width="100%" style="display: block; margin: auto;" /> --- class: middle, center <img src="fig/13_logo2.png" width="100%" style="display: block; margin: auto;" /> --- ### How oddstream works <img src="fig/3_batch.png" width="100%" style="display: block; margin: auto;" /> --- ### How oddstream works <img src="fig/14_oddstream_typical.png" width="100%" style="display: block; margin: auto;" /> --- class: top ### Dimension Reduction for Time Series .pull-left[ `load(train_data)` <img src="fig/4_typical.png" width="90%" style="display: block; margin: auto;" /> ] -- .pull-right[ `tsfeatures <- oddstream::extract_tsfeatures(train_data)` <img src="fig/5_high_typical.gif" width="60%" style="display: block; margin: auto;" /> ] -- `pc<- oddstream::get_pc_space(tsfeatures)` <br/> `oddstream::plotpc(pc$pcnorm)` <img src="fig/6_typicalfeature.png" width="25%" style="display: block; margin: auto;" /> First two PCs explain 85% of variation --- ### Anomalous threshold calculation - Estimate the probability density function of the 2D PC space `\(\longrightarrow\)` Kernel density estimation -- - Draw a large number N of extremes `\((arg min_{x\in X}[f_{2}(x)])\)` from the estimated probability density function -- - Define a `\(\Psi\)`-transform space, using the `\(\Psi\)`-transformation defined by (Clifton et al., 2011) <img src="fig/10_psitrans.png" width="50%" style="display: block; margin: auto;" /> - `\(\Psi\)`-transform maps the density values back into space into which a Gumbel distribution can be fitted. -- - Anomalous threshold calculation `\(\longrightarrow\)` extreme value theory --- class: center, top `oddstream::find_odd_streams(train_data, test_stream)` <img src="fig/18_oddstream_mvtsplot.gif" width="50%" style="display: block; margin: auto;" /> .pull-left[ <img src="fig/16_oddstream_out_loc.gif" width="100%" style="display: block; margin: auto;" /> ] .pull-right[ <img src="fig/17_oddstream_pcplot.gif" width="100%" style="display: block; margin: auto;" /> ] --- class: center, middle, inverse # Anomaly Detection with <br/> <span style="color:#ff08ac"> Non-stationarity </span> --- #### Anomaly detection with non-stationarity <img src="fig/19_nonstationaritytypes.png" width="70%" style="display: block; margin: auto;" /> --- ### Anomaly detection with non-stationarity <img src="fig/20_suddenplot2.png" width="100%" style="display: block; margin: auto;" /> <img src="fig/21_noCD1.png" width="35%" style="display: block; margin: auto;" /> --- ### Anomaly detection with non-stationarity <img src="fig/20_suddenplot3.png" width="100%" style="display: block; margin: auto;" /> <img src="fig/21_noCD2.png" width="35%" style="display: block; margin: auto;" /> --- ### Anomaly detection with non-stationarity <img src="fig/20_suddenplot4.png" width="100%" style="display: block; margin: auto;" /> <img src="fig/21_noCD3.png" width="35%" style="display: block; margin: auto;" /> --- ### Anomaly detection with non-stationarity <img src="fig/20_suddenplot2.png" width="100%" style="display: block; margin: auto;" /> <img src="fig/22_conceptdrift_pval.png" width="100%" style="display: block; margin: auto;" /> - `\(H_{0} : f_{t_{0}} = f_{t_{t}}\)` - squared discrepancy measure `\(T = \int[f_{t_{0}}(x) - f_{t_{t}}(x)]^{2}dx\)` (Anderson et al., 1994) --- ### What Next? - Explore more on feature extraction and feature selection methods to create a better feature space suitable for streaming data context. -- <br/> - Use other dimension reduction techniques such as multidimensional scaling analysis, random projection to see the effect on the performance of the proposed framework. -- <br/> - Do more experiments on density estimation methods to get a better tail estimation. -- <br/> - Extend the algorithm to work with Multidimensional Multivariate Data Streams. --- class: center, middle # Thank You <img src="fig/oddstream1.png" width="15%" style="display: block; margin: auto;" /> `devtools::install_github("pridiltal/oddstream")` Full paper available at: [https://robjhyndman.com/papers/oddstream.pdf](https://robjhyndman.com/papers/oddstream.pdf) <br/><br/>
dilini.talagala@monash.edu
pridiltal
@pridiltal <br/> <sub><sup>Slides created via the R package xaringan</sup></sub>