SPOT：基于极值优化理论的流式单变量时间序列异常检测模型

论文标题｜ Anomaly Detection in Streams with Extreme Value Theory
论文来源｜ KDD 2017
论文链接｜ https://dl.acm.org/doi/10.1145/3097983.3098144
源码链接｜ Ref: https://github.com/DawnsonLi/EVT

TL;DR

论文首次提出基于极值优化理论来检测单变量时间序列中的异常点，不依赖于手工设定阈值和假设数据的分布情况，唯一的参数是 risk 来控制负阳例的数量；论文中提出的 SPOT 方法不仅可以用于离群点异常检测，更适用于自动设定阈值，此外针对数据漂移情况提出改良的 DSPOT 模型；实验部分在真实数据集中验证了其有效性。

Algorithm/Model

Background

其背景知识较为复杂，包括：

极值理论（EVT，Extreme value theory）
极值分布函数 (EVD，Extreme value distributions)
POT（Peaks-Over-Threshold）方法
参数最大似然估计及其优化技巧

以下简单介绍下推导流程，详细介绍参考原文。

真实世界的数据很难用一种已知的分布来概括，例如对于某些极端事件（异常），概率模型（例如高斯分布）往往会给出其概率为 0。极值理论是在不基于原始数据的任何分布假设下，通过推断我们可能会观察到的极端事件的分布，这就是极值分布（EVD）。其数学表达式如下：

$G_{\gamma}: x \mapsto \exp \left(-(1+\gamma x)^{-\frac{1}{\gamma}}\right), \quad \gamma \in \mathbb{R}, \quad 1+\gamma x>0$

其中 $\gamma$ 表示极值指数，取决于不同分布的极值数据情况。

不同参数 $\gamma$ 对应的长尾分布形状不太一样，如下图所示，

为了拟合长尾分布的极值事件概率 $\mathbb{P}\left(X>z_{q}\right)<q$ ，需要估计参数 $\gamma$ 的值，有很多参数估计的方法，

论文中用到的就是基于极值理论的 Peaks-Over-Threshold (POT) 方法，推导后可以拟合一个帕累托分布 (GPD, Generalized Pareto Distribution) 最后优化得到阈值计算公式如下：

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

其中 $t$ 是初始阈值，经验值是 98% 分位数； $q$ 是极值事件概率（我理解的应该就是上文提到的参数 risk 系数）; $n$ 是所有观测点的数量； $N_t$ 是峰值数量即 $X_i>t$ 。

因此上式中我们需要估计两个参数 ${\hat{\sigma}}~~{\hat{\gamma}}$ 。参数估计的方法有很多，矩估计 Method of Moments (MOM) 或者概率加权矩估计 Probability Weigted Moments (PWM) 但是都没有最大似然估计有效？所以本文中使用的最大参数估计的方法。