WSDM 2021 | 快速有效的无监督时间序列异常检测框架 FluxEV

论文标题｜ FluxEV: A Fast and Effective Unsupervised Framework for Time-Series Anomaly Detection
论文来源｜ WSDM 2021
论文链接｜ https://dl.acm.org/doi/10.1145/3437963.3441823
源码链接｜未公布

TL;DR

论文中提出的时间序列异常检测模型 FluxEV 主要是对之前的 SPOT 算法进行优化，主要包括两项：1) SPOT 仅对极值较为敏感因此不能检测出局部波动的异常。2) 使用矩估计 MOM(Method of Moments) 优化 SPOT 中最大似然估计的计算效率。实验部分在两个大型数据中验证 FluxEV 性能优于其它 baselines。

Algorithm/Model

FluxEV 流式异常检测模型如下图所示：

主要四个步骤：

Data Preprocessing
Fluctuation Extraction
Two-step Smoothing Processing
MOM-based Automatic Thresholding

数据预处理

主要处理时间序列数据中的缺失值问题。

之前的关于填充缺失值的方法包括：

Linear interpolation：简单效果不太好；
VAE-based：生成的插值不符合正常模式；

为了减少噪声并且保留其正常模式，论文中使用过的插值策略包括两种情形：

当连续缺失值少于 5 个观测点时，使用一阶线性插值方法；
否则，使用前一个周期数据加上后一个同周期数取平均，例如 $\frac{\mu1+\mu2}{2}$ ;

下图表示不同插值算法的效果对比，发现简单的方法更能保留正常的数据模式。

数据波动特征提取

为了简单快速的计算，文章中采用指数加权滑动平均 EWMA 的方法作为一个预测器来计算观测值和预测值间的残差。假设 $\text{E} = [E_1, \cdots, E_n]$ 表示 $\text{X} = [X_1, \cdots, X_n]$ 所有观测点的残差，那么 EWMA 的计算方法如下：

$\operatorname{EWMA}\left(X_{i-s, i-1}\right)=\frac{X_{i-1}+(1-\alpha) X_{i-2}+\cdots+(1-\alpha)^{s-1} X_{i-s}}{1+(1-\alpha)+\cdots+(1-\alpha)^{s-1}}$

$E_{i}=X_{i}-\operatorname{EWMA}\left(X_{i-s, i-1}\right)$

其中 $\alpha$ 表示平滑因子， $s$ 表示滑动窗口大小；

Tow-step 平滑处理

这两步平滑处理的主要目的是：使正常的波动残差趋近于零而异常的波动保持不变。

考虑时间序列的局部波动和周期模式，文中采用序列化处理 (sequential processing) 和周期性处理 (periodic processing)。如下图所示：

First-step Smoothing

大部分残差数据 $E_i$ 是处于正常范围的且值仅有很小的差别，把这种称为 local noises。我们需要通过 sequential processing 来减小这种局部波动的值，处理方法如下所示：

$\begin{array}{c} \Delta \sigma=\sigma\left(E_{i-s, i}\right)-\sigma\left(E_{i-s, i-1}\right) \\ F_{i}=\max (\Delta \sigma, 0) \end{array}$

其中 $F_i$ 表示 $i$ 时刻经过第一次处理的波动值， $\sigma$ 表示时间窗口 $s$ 内的标准差；

Second-step Smoothing

第二步是为了减小周期噪声数据的影响，但由于数据中会存在数据漂移的影响造成数据周期并不是一一对应的，因此需要采用一种简单的方法来处理数据漂移问题。

假设当前观测点为 $X_t$ ，周期长度为 $l$ ；对于先于当前时刻的第 $p$ 个周期，我们使用 $\max \left(X_{t-p l-d}, . ., X_{t-p l-1}, X_{t-p l}, X_{t-p l+1}, . ., X_{t-p l+d}\right)$ 值来构造周期处理的滑动窗口而不是单独的 $X_{t-p l}$ 。计算公式如下所示：

$\begin{array}{c} M_{i-d}=\max \left(F_{i-2 d, i}\right) \\ \Delta F_{i}=F_{i}-\max \left(M_{i-l(p-1)}, \ldots, M_{i-2 l}, M_{i-l}\right) \\ S_{i}=\max \left(\Delta F_{i}, 0\right) \end{array}$

其中 $d$ 表示半数滑动窗口的值；

整体的处理流程如下图所示，貌似超参数有点多！

对于数据平滑的效果如下图所示：

基于 MOM 和 SPOT 的自动阈值选择方法

SPOT

详细介绍参考另一篇文章：SPOT：基于极值优化理论的流式单变量时间序列异常检测模型

SPOT 算法是一个基于 EVT(Extreme Value Theory) 的 Streaming Peaks-Over-Threshold 方法，POT 方法仅依赖于极值的分布而不依赖于数据分布，主要思想是通过 GPD (Generalized Pareto Distribution) 来近似拟合长尾分布：

$\bar{F}_{t}(x)=P(X-t>x \mid X>t) \sim\left(1+\frac{\gamma x}{\sigma}\right)^{-\frac{1}{\gamma}}$

其中 $t$ 表示初始阈值来查找 peaks， $\gamma$ 和 $\sigma$ 表示 GPD 的形状和规模参数。上式表示数据大于给定阈值 $t$ 的比例并符合 GPD 分布，因此我们需要估计模型的参数。

这就是论文优化的第二项：通过 MOM 优化参数 $\hat{\gamma}$ 和 $\hat{\sigma}$ ，最终的阈值可以通过下式计算

$t h_{F}=t+\frac{\hat{\sigma}}{\hat{\gamma}}\left(\left(\frac{q n}{N_{t}}\right)^{-\hat{\gamma}}-1\right)$

其中 $q$ 是判定异常的风险系数， $n$ 是当前观察点的数量， $N_t$ 是尖峰 $X_i >t$ 的数量；

原始的 SPOT 算法直接在 raw data 上估计参数，本文中在经过 Two-step processing 后的 $S_i$ 数据中来估计参数，这应该也算优化项吧🤓

MOM

矩估计方法的主要思想是利用样本矩来估计总体矩，然后解出总体矩分布中的未知参数。详细理论介绍参考维基百科矩估计。

对于 GPD，均值和标准差分别为：

$E(Y)=\frac{\sigma}{1-\gamma}, \operatorname{var}(Y)=\frac{\sigma^{2}}{(1-\gamma)^{2}(1-2 \gamma)}$

通过样本值替代 GPD 的均值和标准差

$E(Y) ～ \mu=\sum_{i=1}^{N_{t}} \frac{Y_{i}}{N_{t}} \\ \operatorname{var}(Y) ～ S^{2}=\sum_{i=1}^{N_{t}} \frac{\left(Y_{i}-\mu\right)^{2}}{N_{t-1}}$

其中 $Y_i$ 表示峰值与样本间的差值，即 $Y_i=X_i-t$ , $X_i>t$ 且 $t$ 是初始阈值； $N_t$ 是 peaks 的数量。

最后通过下式来估计 GPD 中的参数 $\hat{\gamma}$ 和 $\hat{\sigma}$ ，计算方法如下：

$\begin{array}{l} \hat{\sigma}=\frac{\mu}{2}\left(1+\frac{\mu^{2}}{S^{2}}\right) \\ \hat{\gamma}=\frac{1}{2}\left(1-\frac{\mu^{2}}{S^{2}}\right) \end{array}$