# Revisiting Streaming Anomaly Detection: Benchmark and Evaluation

###### Abstract

Anomaly detection in streaming data is a crucial task for many real-world
applications, such as network security, fraud detection, and system
monitoring. However, streaming data often exhibit concept drift, which means
that the data distribution changes over time. This poses a significant
challenge for anomaly detection algorithms, as they need to adapt to the
evolving data to maintain high detection accuracy. Existing streaming anomaly
detection algorithms lack a unified evaluation framework that can assess their
performance and robustness under different types of concept drift and anomaly.
In this paper, we conduct a systematic technical review of the state-of-the-
art methods for anomaly detection in streaming data. We propose a new data
generator, called _SCAR_ (Streaming data generator with Customizable Anomalies
and concept dRifts), that can synthesize streaming data based on synthetic and
real-world datasets from different domains. Furthermore, we adapt four static
anomaly detection models to the streaming setting using a generic
reconstruction strategy as baselines, and then compare them systematically
with 9 existing streaming anomaly detection algorithms on 76 synthesized
datasets that exhibit various types of anomalies and concepts. The challenges
and future research directions for anomaly detection in streaming data are
also presented. All the codes and datasets are publicly available at
https://github.com/yixiaoma666/SCAR.

11footnotetext: These authors contributed equally to this work.

##  1 Introduction

The explosion of streaming data generated by modern information systems has
led to an increased demand for real-time data analytic. Streaming data are
often described to be ‘real-time’, ‘continuous’, ‘ordered’, ‘large data
volume’, ‘potentially unlimited’ and ‘arrival rate uncertain’
[goldenberg2019survey]. Anomalies are rare events or items that are
inconsistent with or deviate from those that are normal or expected
[han2022streaming]. Anomaly detection is the method for identification of data
patterns that deviate significantly from normal behaviour
[chandola2009anomaly]. It has been widely used in many different application
fields including cybersecurity, fraud detection, healthcare, and industrial
monitoring [pang2021deep].

Anomaly detection methods for static data rely on the assumption that the data
distribution remains stationary over time. However, this assumption does not
hold for streaming data, which is unbounded and dynamic in nature. Streaming
data often exhibits _Concept Drift_ , a phenomenon where the underlying data
distribution changes over time, invalidating the previously learned patterns
and models. Concept drift poses a significant challenge to anomaly detection
algorithms for streaming data, as it can degrade their performance and lead to
erroneous predictions and sub-optimal decisions [goldenberg2019survey].

Thus, a streaming anomaly detection task poses two main challenges: memory
efficiency and model adaptation. The former requires an algorithm to use
limited memory resources, as streaming data can be unbounded in data size. The
latter demands the algorithm to update its model dynamically, as streaming
data may undergo concept drift over time.

Our review reveals that anomaly detection and model update are the main focus
of existing research on streaming anomaly detection. Although some surveys
[ntroumpogiannis2023meta, lu2023review, vazquez2023anomaly] have assessed the
current streaming anomaly detection algorithms, their assessments still have
the following limitations:

  * •

The types of concept drifts in real world are diverse, some studies
[webb2016characterizing, goldenberg2019survey, vzliobaite2010learning,
vazquez2023anomaly] introduce a few different types of concept drifts, but
existing assessments often neglect them and cannot ascertain a method’s
ability to adapt to different types of concept drifts.

  * •

The different types of anomalies are not considered or discussed in most
research. The knowledge of an algorithm’s ability to detect different types of
anomalies are not ascertained, users cannot select a suitable method for a
specific task in practice. For example, we found that existing tree-based
[tan2011fast, guha2016robust] and distance-based algorithms
[angiulli2007detecting] usually can only detect global anomalies but not local
anomalies.

  * •

There is a lack of benchmark datasets that contains various types of concept
drifts and anomalies. It is hard to determine the presence, location, and
types of concept drifts in existing real-world anomaly detection datasets,
thus requires artificial datasets to simulate different types of anomalies and
concept drifts in streaming data. However, current data generators, such as
MOA [bifet2010moa], are not capable of generating data with both diverse types
of anomalies and concept drifts.

  * •

The validity of existing assessment methods are questionable. The detection
accuracy is often assessed by ranking individual anomaly scores over the
entire data stream. This is a serious mistake in assessment, especially the
model is updated or retrained due to the concept drifts, which is equivalent
to ranking scores obtained from different models.

Therefore, a systematical assessment is needed to enable users to evaluate the
detection capability of algorithms for different types of concept drifts and
anomalies. To address those limitations, our contributions in this paper are:

  1. 1.

Propose a new data generator _SCAR_ (Streaming data generator with
Customizable Anomalies and concept dRifts) that can synthesize streaming data
based on synthetic and real-world datasets from different domains.

  2. 2.

Systematically evaluate 9 existing streaming anomaly detection algorithms for
different types of anomaly and concept drift on 76 synthesized datasets. We
also evaluate a generic reconstruction strategy to adapt four static anomaly
detectors to the streaming setting as baselines.

  3. 3.

Identify the challenges, limitations and future research directions of
existing streaming anomaly detection algorithms and evaluation methods.

The rest of this paper is organized as follows: Section 2 provides the basic
definition of streaming anomaly detection, following by the review the state-
of-the-art streaming anomaly detection algorithms in Sections 3. Section 4
provides the definitions of anomaly and concept drift types in terms of
distribution and introduce the proposed data generator. The experimental
settings and empirical evaluation are reported in Section 5. We discuss the
future direction of streaming anomaly detection in Section 6 and the
conclusion is provided in the last section.

##  2 Problem Definition

Let each data point $x$ in a data stream is an independent and identically
distributed (i.i.d.) sample generated from an underlying data distribution or
concept; and the data distribution may change over time.

######  Definition 1.

A data stream is a sequenc of subsequences $X_{i}\subset\mathbb{R}^{d}$:

$X=\\{X_{1},X_{2},\dots,X_{n}\\}$ (1)

where $x\sim\mathcal{P}_{X_{i}}$ denotes that $x$ is an i.i.d. sample
generated from the distribution $\mathcal{P}_{X_{i}}$.

Note that data stream is different from time series data, where the data
points in the latter are not i.i.d., and may have trend or seasonal
components.

######  Definition 2.

A concept drift occurs when the distribution changes from one subsequence to
the next [gama2014survey, webb2016characterizing]:

$\mathcal{P}_{X_{i}}\neq\mathcal{P}_{X_{i+1}}.$ (2)

######  Definition 3.

An anomaly point $a\in X_{i}$ in a data stream is defined as:

$a\nsim\mathcal{P}_{X_{i}}$ (3)

In this paper, we only focus on the problem of detecting anomalies under
unsupervised learning settings, where the anomalies are the rare and deviating
points from the normal (the majority) in the underlying data distribution.

##  3 Streaming Anomaly Detection Methods

According to our review, existing streaming anomaly detection algorithms are
essentially the extension of static anomaly detection algorithms. The
streaming anomaly detection algorithms typically have two components: one for
detecting anomalies from the incoming data stream, and another for updating
the underlying model to adapt to the evolving data characteristics. Table 1
summarises the methods for streaming anomaly detection.

Table 1: Streaming Anomaly Detection Algorithms Comparison. I, C and R represent incremental, conditional and reconstruct update, respectively. The last four algorithms are the static anomaly detectors with reconstruction strategy, introduced in Section 5.2. Algorithms | Type | Detector | Update
---|---|---|---
Memstream [bhatia2022memstream] | DL |  AE+$k$-NN | I/R
ILOF [pokrajac2007incremental] | Density | LOF | I
MILOF [salehi2016fast] | Density | LOF | I
DILOF [na2018dilof] | Density | LOF | I
KELOS [qin2019scalable] | Density | KDE | I
STARE [yoon2020ultrafast] | Density | KDE | I
RS-Hash [sathe2016subspace] | Density | HDE | I
LODA [pevny2016loda] | Density | HDE | I
xStream [manzoor2018xstream] | Density | HSC | I
MStream [bhatia2021mstream] | Statistic | Hash | I
HS-Trees [tan2011fast] | iTree | HST | I
RRCF [guha2016robust] | iTree | RRCT | I
IDForest [xiang2022edge] | iTree | iForest | I
STORM [angiulli2007detecting] | Distance |  $r$-NN | I
MCOD [kontaki2011continuous] | Distance |  $r$-NN | I
CPOD [tran2020real] | Distance |  $r$-NN | I
LEAP [cao2014scalable] | Distance |  $r$-NN | I
NETS [yoon2019nets] | Distance | Cells | I
iForestASD [ding2013anomaly] | Tree | iForest | C
ARCUS [yoon2022adaptive] | DL | AE | C
iForests | iTree | iForest | R
LOFs | Density | LOF | R
iNNEs | Density | isolation | R
IDKs | Density | IDK | R

###  3.1 Basic Anomaly Detectors

We categorize the existing anomaly detectors commonly used in streaming
anomaly detection into four categories: density-based, distance-based,
isolation-tree-based (iTree), deep learning-based and statistic-based.

Density-based anomaly detection methods assume that a point is more likely to
be an anomaly if its neighborhood region is more sparse, they can handle both
local and global anomalies. Two representative methods are LOF (Local Outlier
Factor) [breunig2000lof] and Density Estimation. LOF measures the degree of
isolation of each data point by comparing its local density with its nearest
neighbours the data points with high LOF scores are regarded as anomalies.
Several streaming anomaly detectors ILOF [pokrajac2007incremental], MILOF
[salehi2016fast] and DILOF [na2018dilof] are based on LOF. Density Estimation
estimates the probability density of each data point and identifies anomalies
as those with low density values. KELOS [qin2019scalable] and STARE
[yoon2020ultrafast] use _Kernel Density Estimation_ (KDE) to estimate the
density of each data point. RS-Hash [sathe2016subspace] and LODA
[pevny2016loda] use _Histogram Density Estimation_ to approximate the density
distribution, and xStream [manzoor2018xstream] uses _Half-Space Chains_ (HSC)
compute the density.

The intuition of isolation-tree-based anomaly detection algorithms is that the
anomalies are few and different, thus they are easier to be isolated from the
normal data [liu2008isolation]. _Isolation Forest_ (iForest)
[liu2008isolation] constructs a binary tree by randomly selecting a feature
and a split value between the minimum and maximum values of that feature. The
anomaly score of a data point is its path length in the random tree, a shorter
path length indicates a higher probability of being an outlier. iForest is the
basic anomaly detector used in tree-based streaming anomaly detection
algorithms IDForest [xiang2022edge] and iForestASD [ding2013anomaly]. However,
iForest is not suitable for high-dimensional data due to the random selection
of a dimension for each partition of the data space. Furthermore, iForest can
only detect global anomalies but fail to handle local anomalies. The anomaly
detector _Half Space Tree_ (HST) and _Robust Random Cut Tree_ (RRCT) in
streaming anomaly detection algorithms HS-Trees [tan2011fast] and RRCF
[guha2016robust] are inspired by iForest, respectively. By contrast, RRCF
overcomes the high-dimensional data anomaly detection problem of iForest by
randomly selecting a subset of dimensions.

Distance-based anomaly detection methods assume that a point is far away from
its nearest neighbours. The nearest neighbours can be defined by $k$ nearest
neighbors ($k$-NN) and reverse nearest neighborhood set ($r$-NN)
[boukerche2020outlier]. $k$-NN identify a point $p$ to be an anomaly if its
distance to its nearest $k$ neighbors is significantly larger than a
threshold, the distance can be calculated based on different rules. LOF is
usually considered a density-based approach, the density in LOF is based on
$k$-NN. $r$-NN identifies a point $p$ to be an anomaly if it has fewer than
$k$ neighbors within distance $r$, otherwise $p$ is considered as normal.
STORM [angiulli2007detecting], MCOD [kontaki2011continuous], CPOD
[tran2020real] and LEAP [cao2014scalable] are inspired by $r$-NN. NETS
[yoon2019nets] groups data points at similar locations and handles the outlier
detection at the group level .

Autoencoder (AE) is a deep learning model that widely used in anomaly
detection. Memstream [bhatia2022memstream] uses encoder to extract the
features of each point and uses $k$-NN to detect the anomalies. ARCUS
[yoon2022adaptive] uses AE to reconstruct input data and computes
reconstruction error, the point with reconstruction error is more likely an
anomaly. The statistic-based MStream [bhatia2021mstream] employs hash
functions to detect group anomalies in multi-aspect streaming data and the
anomaly scores are computed by chi-squared statistic.

###  3.2 Model Update

Figure 1: Model Update

The streaming anomaly detection algorithms can adopt different strategies to
update their models, such as: reconstruct, incremental, and conditional
updates. Figure 1 demonstrates these three strategies.

Reconstruct update indicates that streaming anomaly detection algorithms
periodically retrain the model using the latest data to accommodate potential
changes in data distribution. We apply it to 4 static anomaly detectors and
transform them into streaming detectors, as detailed in Section 5.2.

Incremental update implies that the algorithms update their models by
incorporating new information from the incoming data points, while preserving
the original model structure. The incremental update only modifies the
information (density, r-NN etc.) of the points that are affected by the new
point. This strategy enables the algorithms to adjust to the latest data
distribution, while reducing computational resources and enhancing the
execution efficiency.

Conditional update implies that the algorithms have a mechanism to identify
concept drift, and only update their models when such drift happens. However,
among the algorithms we consider, only iForestASD and ARCUS have this
mechanism. iForestASD identifies concept drift by checking the outlier rate in
the window, and if it is lower than a threshold, it assumes that the data
distribution has shifted and rebuilds the iForest model using the new window
data. ARCUS will update the model if the anomaly scores of current batch is
significantly different from that of the previous batch.

##  4 Benchmark Dataset Generator

In this section, we first review the existing benchmark datasets and then
present _SCAR_ , a benchmark dataset generator that synthesize streaming data
with various anomalies and concept drifts. The design of _SCAR_ is independent
of the performance of any specific streaming anomaly detection algorithm or
the suitability of any specific anomaly detection environment. Our generated
datasets encompass common scenarios in streaming data analysis, such as
continuous and i.i.d. data. We aim to provide a flexible and representative
benchmark for streaming anomaly detection algorithms, without biasing towards
any specific method or setting.

###  4.1 Existing Datasets Review

HS-Tree [tan2011fast] and LODA [pevny2016loda] simulates concept drift by
stitching two real anomaly detection datasets of the same dimension, where the
stitching of the two datasets is considered as a change point because the data
distribution has changed. In addition, some other methods [pevny2016loda,
sathe2016subspace, bhatia2022memstream] simulate streaming anomaly detection
datasets by using ordered clustering or classification datasets, where each
cluster is treated as a concept, anomalies are generated by randomly selecting
some of the features and replacing them with outlier points.

However, these methods simulate sudden changes without other concept drift
types. ARCUS [yoon2022adaptive] generates different concept drift types
including sudden, incremental and gradual between the classes. But it only
focuses on global anomalies and neglects local anomalies in sub-regions of the
data based on classification datasets.

There are also many benchmark datasets for time series anomaly detection, such
as ADBench [han2022adbench] and UCR [UCRArchive2018]. Those time series
datasets are non-i.i.d. data and need to be considered as time-dependent.
However, since streaming data is considered as independently and homogeneously
distributed, time series anomaly detection, classification and clustering
benchmark datasets cannot be used in streaming anomaly detection. MOA
[bifet2010moa] is an open framework that able to generate either concept drift
detection or outlier detection datasets separately, but cannot efficiently
generate them together.

In summary, existing datasets on streaming anomaly detection focus on either
concept drift or anomaly detection, and there is a lack of benchmark datasets
that include both. Inspired by existing algorithms, we propose a dataset
generator _SCAR_ which can produce streaming data with different concept drift
types and anomaly types.

###  4.2 Synthetic Datasets Generation

We generate realistic synthetic datasets with _SCAR_ by injecting specific
anomaly types into streaming data with predefined distribution and density. We
simulate common types of concept drifts and anomalies to evaluate the
performance of streaming anomaly detection algorithms systematically.

####  4.2.1 Concept Drift Types

While many algorithms state that they can cope with the impact of concept
drift on model performance, they do not consider the change types of concept
drift, which makes it challenging to understand the pros and cons of streaming
data anomaly algorithms with respect to specific concept drift types.

To better understand the impact of change types and analyze the response of
the stream anomaly detection algorithm, we created the datasets based on
different baseline datasets from Section 4.2.2 by injecting concept drifts of
different change types as follows:

  * •

Sudden Change: a concept is changed suddenly between two adjacent
subsequences, i.e.,

$\mathcal{D}(\mathcal{P}_{X_{i}},\mathcal{P}_{X_{i+1}})>\tau,$ (4)

where $\mathcal{D}$ is a function calculating the dissimilarity between two
concepts, and $\tau$ is a threshold value.

  * •

Transition change: a concept keeps changing to another concept over a time
period. Because transition change may have countless change types, we
introduce two change types which are easy to simulate.

    * –

Gradual Change: a concept $\mathcal{P}_{X_{i}}$ is gradually changed to
another concept $\mathcal{P}_{X_{i+1}}$ over some time steps $k\in[1,\dots,t]$
in which points are generated from a joint distribution derived from two
weighted independent distributions $\mathcal{P}_{X_{i}}$ and
$\mathcal{P}_{X_{i+1}}$, i.e.,

$\alpha_{k}\mathcal{P}_{X_{i}}\ \cdot\ (1-\alpha_{k})\mathcal{P}_{X_{i+1}},$
(5)

where $\alpha_{i}$ is a weight factor which is monotonic decreasing over the
time: $0\leq\alpha_{k+1}<\alpha_{k}\leq 1$ for $k\in[1,t]$.

    * –

Incremental Change: a concept keeps approaching another concept
$\mathcal{P}_{X_{i}}$ over a short period $S=\\{s_{1},s_{2},\dots,s_{t}\\}$. ,
i.e.,

$\forall_{k\in[1,t-1]}~{}\mathcal{D}(\mathcal{P}_{s_{k}},\mathcal{P}_{X_{i}})>\mathcal{D}(\mathcal{P}_{s_{k+1}},\mathcal{P}_{X_{i}}),$
(6)

where $\mathcal{D}$ is a dissimilarity function.

Both gradual change and incremental change can be defined as a special type of
sudden change as the concept keeps changing over a time period. For gradual
change, a point in the changing period is from either $\mathcal{P}_{X_{i}}$ or
$\mathcal{P}_{X_{i+1}}$. However, for incremental change, a point in the
changing period is from a new distribution that is more similar to
$\mathcal{P}_{X_{i+1}}$ over time. For example, we can simulate
$\mathcal{P}_{X_{i}}$ and $\mathcal{P}_{X_{i+1}}$ using the Gaussian
distribution with different $\sigma$ and $\mu$ values, i.e.,
$\mathcal{P}_{X_{i}}=\mathcal{N}\\{\mu_{i},\sigma_{i}^{2}\\}$ and
$\mathcal{P}_{X_{i+1}}=\mathcal{N}\\{\mu_{i+1},\sigma_{i+1}^{2}\\}$. Then we
define
$\forall_{k\in[1,t-1]},\mathcal{P}_{s_{k}}=\mathcal{N}\\{\mu_{k},\sigma_{k}^{2}\\}$,
where $\mu_{k}=\mu_{i}+(k-1)\times\frac{\mu_{i+1}-\mu_{i}}{t-1}$ and
$\sigma_{k}=\sigma_{i}+(k-1)\times\frac{\sigma_{i+1}-\sigma_{i}}{t-1}$.

####  4.2.2 Anomaly Types

We consider global and local anomalies which are defined as:

  * •

Global Anomaly is a data point that far outside the entirety of the dataset.
For example, an anomaly point $a_{g}$ is located at global sparse regions and
can be usually identified using a global density/dissimilarity threshold,
i.e., $pdf(a_{g})>\tau$, where $pdf(.)$ is a probability density function.

  * •

Local Anomaly is a data point with low density relative to nearby normal (non-
anomalous) points in a region of high average density, i.e., a local anomaly
can have higher density than normal points in another region of low average
density. For example, a data point $a_{d}$ deviate from a dense cluster
$X_{d}$ can be a local anomaly, if existing a sparse cluster $X_{s}$,
$\forall_{x\in X_{s}}\ pdf(a_{d})>pdf(x)$.

We aim to evaluate the performance of streaming anomaly detection algorithms
on these datasets and analyze how they handle different types of concept drift
and anomaly. This approach enables a more thorough investigation of anomaly
detection under different density conditions, thus revealing the complexity of
anomaly representation in streaming data.

###  4.3 Real-world Datasets Simulation

To simulate the concept drift scenarios on real-world datasets, we manipulate
existing classification and anomaly detection datasets. We consider each class
in a dataset as a unique concept, and subsequently stream all data points from
the same class before transitioning to another class, i.e., the drift occurs
when the streaming data transitions to a different class. In order to ensure
that the points within each class remain independent and identically
distributed from the same concept, we randomly shuffled them before streaming.

Moreover, we use two strategies to generate anomalies in the real-world data
as follows:

  1. 1.

Replacing scheme:  To introduce anomalies in a numeric dataset, we randomly
sampled a small subset of points and replaced some randomly selected features
of each sampled instance with values outside the original range of these
features. This strategy was applied to all numeric datasets in our
experiments.

  2. 2.

Inserting scheme: Given a stream with the points from one class, we introduce
anomalies by randomly injecting a few points from a different class. We only
applied this strategy to image datasets, since replacing feature values would
only create noisy pixels in an image, rather than changing its semantic
meaning.

In our evaluation, we collected 17 numerical real-word datasets and 2 image
datasets. For every dataset, we chose three classes for simulating concept
drifts and anomalies. For numeric datasets, we randomly selected 2% points and
changed 50% their features with the replacing scheme. For the two image
datasets, each non-drift segment includes 98% of points from one class as
normal points, while 2% of points from other two classes (each class occupies
1%) as anomalies, as shown in Figure 2.

Figure 2: Illustration of different class distributions in a simulated stream.
The points from a class with the pdf value of 1% are labeled as anomalies.

##  5 Experiments and Empirical Evaluation

(a) S1

(b) S2

Figure 3: Visualisation of two synthetic datasets. (a) S1 is a 1-dimensional
streaming dataset that contains 5 concept drifts. Blue points are normal, red
points are anomalies and green shadows are concept drift periods. (b) S2 is a
2-dimensional streaming dataset shown in the top left figure. We also show the
2-dimensional projects of data points during the time periods of 1-2000,
2001-4000 & 4001-6000 due to the sudden drifts at 2001 and 4001.

###  5.1 Datasets

In this paper, We use _SCAR_ to simulate 74 real-world datasets and 2
synthetic datasets to evaluate the performance of 9 existing streaming anomaly
detection algorithms. Figure 3 shows the 2 synthetic datasets dataset which
contain different concept drift types and anomaly types.

Table 2: ROC-AUC of different algorithm on three datasets. In the Drift
column, S, G and I are for sudden, gradual and incremental concept drift,
respectively. In the Anomaly column, G and L represent for global and local
anomalies, respectively. Note that the sudden drift only happened at the first
time stamp of the corresponding segment, where gradual or incremental drift
exists persistently in the whole corresponding segment. “Average” means the
average ROC-AUC score over all segments’ ROC-AUC scores. Entire means the ROC-
AUC score are calculated based global thresholds for all anomaly scores for a
dataset.

Datasets | Segment | Drift | Anomaly | STORM | HS-Tree | iForestASD | LODA | RS-Hash | xStre | RRCF | MStream | Memstream | IDKs | INNEs | LOFs | iForests
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
S1 | 1-2000 | - | G | 0.97 | 0.98 | 0.99 | 0.99 | 0.99 | 0.97 | 0.99 | 0.63 | 1.00 | 0.97 | 0.97 | 0.97 | 0.99
2001-4000 | S | G | 0.93 | 0.99 | 0.98 | 0.83 | 0.98 | 0.97 | 0.99 | 0.45 | 0.90 | 1.00 | 1.00 | 1.00 | 1.00
4001-5000 | G | G | 0.99 | 1.00 | 1.00 | 0.96 | 0.99 | 0.98 | 1.00 | 0.48 | 0.93 | 1.00 | 1.00 | 0.99 | 1.00
5001-7000 | - | G | 0.99 | 1.00 | 0.99 | 0.97 | 1.00 | 0.98 | 0.99 | 0.68 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00
7001-8000 | I | G | 0.99 | 0.99 | 1.00 | 0.95 | 0.98 | 0.99 | 0.99 | 0.54 | 0.95 | 1.00 | 1.00 | 1.00 | 1.00
8001-10000 | - | G | 0.98 | 0.99 | 0.99 | 0.89 | 0.99 | 0.97 | 1.00 | 0.47 | 0.86 | 1.00 | 1.00 | 1.00 | 1.00
10001-12000 | S | G+L | 0.64 | 0.92 | 0.95 | 0.41 | 0.96 | 0.74 | 0.98 | 0.52 | 0.57 | 1.00 | 1.00 | 1.00 | 0.97
12001-13000 | I | G+L | 0.56 | 0.91 | 0.96 | 0.51 | 0.99 | 0.69 | 0.98 | 0.37 | 0.46 | 0.99 | 1.00 | 1.00 | 0.98
13001-15000 | - | G+L | 0.79 | 0.92 | 0.97 | 0.52 | 0.99 | 0.77 | 0.99 | 0.68 | 0.61 | 1.00 | 1.00 | 1.00 | 0.99
2-17 | Average |  |  | 0.87 | 0.97 | 0.98 | 0.78 | 0.99 | 0.90 | 0.99 | 0.54 | 0.81 | 1.00 | 1.00 | 1.00 | 0.99
| Entire |  |  | 0.81 | 0.90 | 0.98 | 0.73 | 0.96 | 0.94 | 0.99 | 0.52 | 0.75 | 0.99 | 0.99 | 0.99 | 0.99
S2 | 1-2000 | - | G+L | 0.72 | 0.49 | 0.51 | 0.50 | 0.42 | 0.34 | 0.69 | 0.67 | 0.92 | 0.97 | 0.95 | 0.87 | 0.38
2001-4000 | S | G | 0.86 | 0.87 | 0.99 | 0.50 | 0.90 | 0.98 | 0.98 | 0.43 | 1.00 | 1.00 | 0.99 | 0.93 | 0.99
4001-6000 | S | L | 0.65 | 0.47 | 0.57 | 0.50 | 0.45 | 0.53 | 0.75 | 0.52 | 0.79 | 0.92 | 0.88 | 0.86 | 0.51
2-17 | Average |  |  | 0.74 | 0.61 | 0.69 | 0.50 | 0.59 | 0.62 | 0.81 | 0.54 | 0.90 | 0.96 | 0.94 | 0.89 | 0.63
| Entire |  |  | 0.74 | 0.53 | 0.62 | 0.50 | 0.57 | 0.54 | 0.74 | 0.57 | 0.86 | 0.89 | 0.91 | 0.88 | 0.55
COIL20 | 1-10000 | - | G | 0.87 | 0.92 | 1.00 | 0.50 | 0.86 | 0.97 | 0.99 | 0.86 | 0.51 | 1.00 | 1.00 | 1.00 | 1.00
10001-15000 | G | G | 0.78 | 0.97 | 0.98 | 0.50 | 1.00 | 0.93 | 0.98 | 0.95 | 0.56 | 0.99 | 0.99 | 0.98 | 0.99
15001-25000 | - | G | 0.87 | 0.81 | 0.98 | 0.50 | 0.80 | 0.98 | 0.99 | 0.68 | 0.52 | 1.00 | 1.00 | 0.99 | 1.00
25001-35000 | S | G | 0.86 | 1.00 | 0.97 | 0.50 | 1.00 | 0.98 | 0.96 | 0.72 | 0.45 | 1.00 | 1.00 | 1.00 | 0.99
2-17 | Average |  |  | 0.84 | 0.93 | 0.98 | 0.50 | 0.92 | 0.97 | 0.98 | 0.80 | 0.51 | 1.00 | 1.00 | 0.99 | 1.00
| Entire |  |  | 0.85 | 0.94 | 0.98 | 0.50 | 0.92 | 0.96 | 0.98 | 0.66 | 0.50 | 1.00 | 1.00 | 1.00 | 0.99

###  5.2 Experiment methods

We evaluate 9 existing streaming anomaly detection methods based on their code
availability and usability, including STORM, HS-Tree, iForestASD, LODA, RRCF,
RS-Hash, xStream, MStream and Memstream. All source codes are from streaming
anomaly detection Python library _PySAD_ ***PySAD:
https://pysad.readthedocs.io/en/latest/[pysad], except MStream and Memstream
which are from https://github.com/Stream-AD/.

Additional, we use a reconstruct strategy to convert 4 static anomaly
detection algorithms as baselines, i.e., _isolation using Nearest Neighbour
Ensemble_ (iNNE)†††iNNE [bandaragoda2014efficient] randomly partitions the
data space into regions based on nearest-neighbour distances and assigns
isolation scores to each region according to how well they separate the
samples. The point will be considered as an anomaly if its isolation score
exceeds a threshold., _Isolation distributional Kernel_ (IDK)‡‡‡IDK has been
used in various fields of anomaly detection, i.e. time series [ting2022new]
and graph [zhuang2023subgraph]. It calculates the anomaly score by measuring
the similarity between two distributions using a data-dependent point kernel,
and detects anomalies as those that have low similarity to the normal
distribution. In this paper, IDK is used to measure the dissimilarity between
each point and its corresponding subsequence as the anomaly score., _LOF_ and
_iForest_ to streaming anomaly detection algorithms iNNEs and IDKs, LOFs and
iForests, respectively. We keep updating the models using a sliding window.
For each point $x_{i}$, we build the models based on the previous and
afterwards $w$ points, i.e., $\\{x_{i-w},\dots,x_{i}\\}$ and
$\\{x_{i},\dots,x_{i+w}\\}$, and then get the anomaly scores
$S_{\overleftarrow{w}}(x_{i})$ and $S_{\overrightarrow{w}}(x_{i})$,
respectively. The final anomaly score is the smaller one between
$S_{\overleftarrow{w}}(x_{i})$ and $S_{\overrightarrow{w}}(x_{i})$, to reduce
the false positive cases within a drift period.

###  5.3 Evaluation Criteria

We use the area under the receiver operating characteristic curve (AUC-ROC) to
measure the performance of streaming anomaly detection algorithms.

Previous studies commonly adopt an entire evaluation method, i.e., applying a
single threshold to the entire anomaly scores to identify anomalies.§§§AUC-ROC
enumerates all possible global thresholds to calculate the final performance
score. However, we find it may be inappropriate for evaluating streaming data
containing concept drifts, since the anomaly scores are varied due to the
model updates and may not be comparable with a global threshold.

Instead using a global threshold, we introduce a segment evaluation strategy
to evaluate the anomaly scores in each segment independently, i.e., each
segment uses an independently local threshold to find the anomaly. To
implement this strategy, we report AUC-ROC scores for each segment of a
dataset in Table 2.

###  5.4 Empirical Evaluation

Timely model update is sufficient to adapt different concept drift types

Table 2 presents a comprehensive evaluation of anomaly detection performance
across different segments of 2 synthetic datasets and 1 simulated real-world
image (COIL20) dataset. When looking at the AUC scores in each segment, it
shows that the performance of almost all algorithms do not change
significantly following a drift occurrence, if the anomaly type keeps the
same. Moreover, the majority of models maintain a high performance for global
anomaly detection, even when confronted with the presence of anomalies during
the concept drift. However, MStream and Memstream show poor results on
synthetic dataset and image dataset, respectively. LODA performs poorly on
both S2 dataset and image dataset. It is worth mentioning that all baselines
shown in the last 4 columns of Table 2 present stably high performance on all
segments, except $iForests$ which suffers from detecting local anomalies.
Therefore, for models with timely updates, different concept drifts do not
exert a substantial influence on their anomaly detection capabilities.

Local anomaly is more challenging

In the S2 dataset, we observe that the performance of most algorithms
decreases substantially (more than 0.2) from segment 1-5000 (with global
anomalies only) to segment 10001-15000 (with local anomalies only). Only the
detector IDKs, INNEs and LOFs have the ability to handle local anomalies, due
to they calculate the anomaly score based on local density distribution.
However, tree-based and distance-based algorithms have difficulties in
detecting local anomalies in datasets with varied densities.

Figure 4 shows the average AUC-ROC score of each algorithm over 74 manipulated
real-world datasets. We find that the four baselines relying on reconstructive
updating outperform all other existing streaming anomaly detection algorithms
without considering the updating efficiency.

Figure 4: Average entire AUC-ROC score of 13 algorithms on 74 manipulated
real-world datasets.

##  6 Discussion and Future Direction

###  6.1 Identify anomalies based on anomaly scores

It can be seen from the Table 2 that some algorithms have significantly
different AUC-ROC scores if using different evaluation criteria, i.e., based
on the global threshold or the local segment threshold. In the streaming
anomaly detection task, changes in the data cause continuous updating of the
model, which results in changes in the pattern and range of fluctuations in
the anomaly scores. For instance, some periods of high data fluctuation may
result in many high anomaly scores, and a global threshold may lead to many
false positives. Thus, it is important to use different thresholds for
different periods, or to normalize or standardize the anomaly scores across
periods. However, this topic has received little attention in the literature,
there is a need for more research on how to adapt the thresholds or the
anomaly scores to the dynamic nature of streaming data.

###  6.2 Handle different types of data

Many real-world scenarios include categorical and unstructured data, such as
videos and images, generated in a streaming fashion. For example, video
surveillance cameras, social media platforms, and online shopping websites
produce a large amount of streaming video and image data. Those kinds of data
pose different challenges for anomaly detection, such as high dimensionality,
complex structure, and semantic gap. Therefore, feature extraction such as
deep learning methods can be leveraged to transformed those non-numeric data
into numerical representations, before applying existing streaming anomaly
detection methods reviewed in this paper. How to design efficient feature
extraction methods for streaming datasets is an emerging research topic.

###  6.3 Drift-aware algorithms

Many methods update the model at a fixed frequency, leading to missed
anomalies or redundant updates. This is because a higher update frequency
requires more computational resources, while a lower frequency risks missing
anomalies during concept drift. A demonstration with iForestASD is shown in
Figure 5, such that updating the model only after a concept drift is
sufficient to perform well on S1 dataset. To optimize computational resource
consumption, it is advantageous for streaming anomaly detection algorithms to
promptly detect concept drift and update the model accordingly.

(a) AUC-ROC

(b) Runtime

Figure 5: The performance and runtime of iForestASD with respect to different
update strategies on S1 dataset. Drift-aware update means that the model is
updated only after a concept drift.

###  6.4 Differentiate concept drift and group anomaly

This paper focuses on point anomalies only, which are individual data
instances that differ from the majority of data distribution. Group anomalies
are another type of anomalies, which arise when a group of data instances show
an anomalous pattern together, but not separately. A key challenge in group
anomaly detection is to differentiate between group anomalies and concept
drift, which both involve changes in the data distribution over time. Thus,
the differentiation between group anomalies and concept drift should depend on
the specific application and domain knowledge. For instance, in traffic flow
monitoring, a rise in peak hour traffic can be considered as concept drift,
while a rise in off-peak hour traffic can be identified as a group anomaly.

##  7 Conclusion

In this paper, We introduced _SCAR_ to produce evaluation datasets featuring
diverse concept drifts and anomalies, thereby facilitating the evaluation of
streaming anomaly detection algorithms. Our findings revealed that while the
existing concept drift types exhibited weak impact on model performance due to
the adequacy of model update. In contrast, the underlying anomaly types is a
key factor influencing model effectiveness. We also show that with a generic
reconstruction update strategy, traditional anomaly detectors that are
sensitive to local density distribution can perform well on streaming data
with various kinds of anomaly and concept drift. Furthermore, we provide some
key challenges and future research directions in this topic.