本文翻译整理自
Anomaly Detection in Streams with Extreme Value Theorydl.acm.org
SPOT/DSPOT 优势与贡献
- 针对高吞吐的单变量流模型设计
- 该方法无需针对每条数据手动设置阈值（实际上还是需要一个定义异常发生概率的参数）
- 对数据分布不作假设（适应能力更强）
- 对固定的数据分布和存在概念漂移的数据分布，分别用SPOT和CSPOT算法进行了讨论
- 原理简单，实现简单
- 对Extreme Value Theory(EVT)提出了通用的快速解法
什么是极值理论 (Extreme Value Theory, EVT)
真实世界的数据很难用一种已知的分布来概括，例如对于某些极端事件（异常），概率模型（例如高斯分布）往往会给出其概率为0。极值理论是在不基于原始数据的任何分布假设下，通过推断我们可能会观察到的极端事件的分布。
极值分布 (Extreme value distributions, EVD)
极值理论的首要目标是发现极端事件的规律，根据已有的某些理论结论，这些极端事件与整体数据分布不同，他们往往遵循自己的数据分布。例如每天的最高温度遵循相同的分布，但是温度的总体分布就不一样了。这个就是极值分布EVD，数学表示如下，其中
![]() 为极值指数，取决于原始数据的规律：
本文给出了三种针对不同
![]() 可能的拟合结果如下：
极值理论的作用
极值理论让我们在原始数据分布非常复杂的情况下，仍然有可能去估计那些极端事件（异常等）。例如下图中，蓝色线段表示的是一个未知分布，但是红色虚线则可以进行拟合推动其分布。我们定义一个异常概率
![]() (这是本算法中的唯一参数)，存在一个可能的值
![]() 使
![]() ，然后接下来就是估计
![]() 使其能拟合红虚线即可。
POT(Peaks-Over_threshold) 拟合方法
对于累计密度函数
![]() （
![]() 表示在
![]() 分布下极值收敛于
![]() )，当且仅当存在
![]() 使得所有
![]() 都有
这个结果说明对于超过阈值t的极值，用X-t表示，遵循帕累托分布（GPD），其参数为
![]() 。也就是说POT方法对于极值分布情况，使用GPD来进行拟合，本文中用估计值
![]() 来计算给定异常概率
![]() 下的分位数：
其中
![]() 是一个初始阈值，其值要尽可能高但是很明显他要小于
![]() ，经验值为98%，
![]() 是所有观测值的总数，
![]() 是峰值的个数也就是那些 大于
![]() 的点个数。
最大似然估计
对于密度为
![]() 独立随机变量
![]() ，其似然函数为：
目标是找到一个参数
![]() 使得观测数据尽可能的发生（MLE的核心目标），在本文所要估计的也就是上文提到的帕累托分布，用log函数进行表示如下，其中
![]() ：
实时流数据异常检测
初始化
给定
![]() 个观测值
![]() 和一个异常发生概率
![]() ，要计算一个阈值
![]() 使得
![]() ，如下图所示，初始化主要是想通过谁当一个较高的阈值
![]() 来找到峰值，然后去拟合一个帕累托分布，然后通过这个分布来推断极值（异常）的可能分布并计算阈值
![]() 从而检测出异常。
对于固定分布的流数据异常检测（SPOT）
对于固定分布的数据异常检测比较简单，基本沿用了上图的模式。首先利用POT估计前
![]() 个值，然后得到初始异常阈值
![]() ，对于接下来的数据，可以进行异常标注或者更新阈值。如果观测数据超过该阈值则视为异常，注意异常值不用来更新阈值，但是那些超过峰值阈值t但却是正常值的数据（peak, not anomaly）可以用来进行阈值更新，因为我们之前那也提到了
![]() 是大于
![]() 的。
对于漂移分布的流数据异常检测（DSPOT）
这一部分讨论的是存在概念漂移（concep drift）也就是数据分布发生变化的数据的异常检测，比如说一些季节性的变化。Drift SPOT(DSPOT)的解决思路是通过对局部数据，用相对值（区别于SPOT的绝对值）进行建模。
在DSPOT中，主要关注每一个观测值的变化量
![]() ，其中
![]() 是对时间i的局部建模，比如滑动平均值
![]() 是最后
![]() 个观测数据，可以视作一个窗口，这样就可以假设其局部分布还是遵从同一个分布的。
本文还给出了一些针对流式数据高速处理需求的数学优化，不在这里详细说明。
本文代码github.com
| 
转播
