基于极值理论的流数据异常检测(SPOT/DSPOT, KDD'17)

本文翻译整理自 Anomaly Detection in Streams with Extreme Value Theory

SPOT/DSPOT 优势与贡献

  • 针对高吞吐的单变量流模型设计
  • 该方法无需针对每条数据手动设置阈值(实际上还是需要一个定义异常发生概率的参数)
  • 对数据分布不作假设(适应能力更强)
  • 对固定的数据分布和存在概念漂移的数据分布,分别用SPOT和CSPOT算法进行了讨论
  • 原理简单,实现简单
  • 对Extreme Value Theory(EVT)提出了通用的快速解法

什么是极值理论 (Extreme Value Theory, EVT)

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

极值分布 (Extreme value distributions, EVD)

极值理论的首要目标是发现极端事件的规律,根据已有的某些理论结论,这些极端事件与整体数据分布不同,他们往往遵循自己的数据分布。例如每天的最高温度遵循相同的分布,但是温度的总体分布就不一样了。这个就是极值分布EVD,数学表示如下,其中\(\gamma\)为极值指数,取决于原始数据的规律:

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

本文给出了三种针对不同\(\gamma\)可能的拟合结果如下:

极值理论的作用

极值理论让我们在原始数据分布非常复杂的情况下,仍然有可能去估计那些极端事件(异常等)。例如下图中,蓝色线段表示的是一个未知分布,但是红色虚线则可以进行拟合推动其分布。我们定义一个异常概率\(q\)(这是本算法中的唯一参数),存在一个可能的值\(z_q\)使\(\mathbb{P}\left(X>z_{q}\right)<q\),然后接下来就是估计\(\gamma\)使其能拟合红虚线即可。

POT(Peaks-Over_threshold) 拟合方法

对于累计密度函数\(F \in \mathcal{D}_{\gamma}^{1}\)(\(\mathcal{D}_{\gamma}^1\) 表示在\(F\)分布下极值收敛于\(G_{\gamma}\)),当且仅当存在\(\sigma\) 使得所有\(x\in \mathbb{R}, 1+\gamma x\) 都有

\[ \bar{F}_{t}(x)=\mathbb{P}(X-t>x \mid X>t) \underset{t \rightarrow \tau}{\sim}\left(1+\frac{\gamma x}{\sigma(t)}\right)^{-\frac{1}{\gamma}} \]

这个结果说明对于超过阈值\(t\)的极值,用\(X-t\)表示,遵循帕累托分布(GPD),其参数为\(\gamma,\sigma\)。也就是说POT方法对于极值分布情况,使用GPD来进行拟合,本文中用估计值\(\hat{\gamma},\hat{\sigma}\)来计算给定异常概率\(q\)下的分位数:

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

其中\(t\)是一个初始阈值,其值要尽可能高但是很明显他要小于\(z_{q}\),经验值为98%,\(n\)是所有观测值的总数,\(N_t\)是峰值的个数也就是那些大于\(t\)的点个数。

最大似然估计

对于密度为\(f_\theta\)独立随机变量\(X\),其似然函数为: \[ \mathcal{L}\left(X_{1}, \ldots X_{n} ; \theta\right)=\prod_{i=1}^{n} f_{\theta}\left(X_{i}\right) \]

目标是找到一个参数\(\theta\) 使得观测数据尽可能的发生(MLE的核心目标),在本文所要估计的也就是上文提到的帕累托分布,用log函数进行表示如下,其中\(Y_i=X_i-t\)

\[ \log \mathcal{L}(\gamma, \sigma)=-N_{t} \log \sigma-\left(1+\frac{1}{\gamma}\right) \sum_{i=1}^{N_{t}} \log \left(1+\frac{\gamma}{\sigma} Y_{i}\right) \]

实时流数据异常检测

初始化

给定\(n\)个观测值\(X_n\)和一个异常发生概率\(q\),要计算一个阈值\(z_q\)使得\(\mathbb{P}\left(X>z_{q}\right)<q\),如下图所示,初始化主要是想通过谁当一个较高的阈值\(t\)来找到峰值,然后去拟合一个帕累托分布,然后通过这个分布来推断极值(异常)的可能分布并计算阈值\(z_q\)从而检测出异常。

对于固定分布的流数据异常检测(SPOT)

对于固定分布的数据异常检测比较简单,基本沿用了上图的模式。首先利用POT估计前\(n\)个值,然后得到初始异常阈值\(z_q\),对于接下来的数据,可以进行异常标注或者更新阈值。如果观测数据超过该阈值则视为异常,注意异常值不用来更新阈值,但是那些超过峰值阈值\(t\)但却是正常值的数据(peak, not anomaly)可以用来进行阈值更新,因为我们之前那也提到了\(z_q\)是大于\(t\)的。

对于漂移分布的流数据异常检测(DSPOT)

这一部分讨论的是存在概念漂移(concep drift)也就是数据分布发生变化的数据的异常检测,比如说一些季节性的变化。Drift SPOT(DSPOT)的解决思路是通过对局部数据,用相对值(区别于SPOT的绝对值)进行建模。

在DSPOT中,主要关注每一个观测值的变化量\(X-i'=X_i-M_i\),其中\(M_i\)是对时间\(i\)的局部建模,比如滑动平均值\(M_{i}=(1 / d) \cdot \sum_{k=1}^{d} X_{i-k}^{*}\), \(X_{i-1}^{*}, \ldots X_{i-d}^{*}\)是最后\(d\)个观测数据,可以视作一个窗口,这样就可以假设其局部分布还是遵从同一个分布的。

本文还给出了一些针对流式数据高速处理需求的数学优化,不在这里详细说明

本文代码