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

WSDM的英文全称是 The International Conference on Web Search and Data Mining，中文意思是国际互联网检索与数据挖掘会议，由SIGIR、SIGKDD、SIGMOD和SIGWEB四个专委会协调筹办，在互联网搜索、数据挖掘领域享有较高学术声誉，被中国计算机协会推荐为B类会议。在清华大学最新发布的新版计算机学科推荐学术会议和期刊列表中，WSDM已被列为准A类学术会议。

今年 WSDM 2021 于北京时间2021年3月8到12号于线上举行。本次大会共接收了 112 篇论文，接收率仅为18.6%，其中Oral 69篇，接受率为11.4%。

本文简要介绍一篇来自WSDM的论文，其提出了一种快速高效的无监督时序异常检测框架。

论文标题：FluxEV: A Fast and Effective Unsupervised Framework for Time-Series Anomaly Detection

原文地址：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 流式异常检测模型如下图所示：

FluxEV 架构图

主要四个步骤：

1. Data Preprocessing
2. Fluctuation Extraction
3. Two-step Smoothing Processing
4. MOM-based Automatic Thresholding

01

数据预处理

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

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

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

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

• 当缺失值少于 5 个观测点时，使用一阶线性插值方法；
• 否则，使用前一个周期数据加上一个基数，例如 ;

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

数据填充

02

数据波动特征提取

为了简单快速的计算，文章中采用指数加权滑动平均 「EWMA」 的方法作为一个预测器来计算观测值和预测值间的残差。假设 表示 所有观测点的残差，那么 EWMA 的计算方法如下：

其中 表示平滑因子， 表示滑动窗口大小；

03

Two-step平滑处理

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

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

特征处理

「First-step Smoothing」

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

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

「Second-step Smoothing」

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

假设当前观测点为 ，周期长度为 ；对于先于当前时刻的第 个周期，我们使用 值来构造周期处理的滑动窗口而不是单独的 。计算公式如下所示：

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

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

数据处理算法

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

数据平滑效果

04

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

「SPOT」

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

其中 表示初始阈值来查找 peaks， 和 表示 GPD 的形状和规模参数。上式表示数据大于给定阈值 的比例并符合 GPD 分布，因此我们需要估计模型的参数。这就是论文优化的第二项：通过 MOM 优化参数 和 ，最终的阈值可以通过下式计算：

其中 是判定异常的风险系数， 是当前观察点的数量， 是尖峰 的数量；

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

「MOM」

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

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

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

其中 表示峰值与样本间的差值，即, 且 是初始阈值； 是 peaks 的数量。

最后通过下式来估计 GPD 中的参数 和 ，计算方法如下：

POT 算法计算流程如下：

POT算法

综上所述，FluxEV 描述为具体的算法步骤如下图所示：

算法步骤

Experiments

实验中采用的数据集如下：

实验数据

与不同 baselines 对比的结果如下图所示:

实验结果

可以看出 FluxEV F1-score 较大但是 Precision 不高，某种情况下也应该用准确率作为指标。

在正负样本不平衡的情况下，准确率这个评价指标有很大的缺陷。比如在互联网广告里面，点击的数量是很少的，一般只有千分之几，如果用 acc，即使全部预测成负类（不点击）acc 也有 99% 以上，没有意义。

从指标上看提升效果较小，但是性能提升效果可以，如下图所示：

性能对比

在不同类型时间序列数据下 baselines 的效率对比效果如下：

实验结果

FluxEV 在周期性数据和不稳定数据中的效果最好，SPOT 在稳定性数据中的效果最好因为稳定的数据不包含周期体现不出来 FluxEV 对周期数据的优化；

论文中其它的消融实验不再细述，有兴趣的同学可以参考原文；

Thoughts

• 模型超参数太多不好优化，需要根据经验调整；
• 模型简单且效率高，尤其是解释效果和性能超过大部分基于深度学习的模型。