KDD 2019 | 基于谱残差和 CNN 的时间序列异常检测模型

论文标题 ｜ Time-Series Anomaly Detection Service at Microsoft
论文来源 ｜ KDD 2019
论文链接 ｜ https://arxiv.org/abs/1906.03821
源码链接 ｜ https://github.com/microsoft/anomalydetector

TL;DR

论文中基于 Spectral Residual (SR) 和卷积网络提出了一种新颖的单变量时间序列异常检测算法 SR-CNN，是第一篇将 SR 从视觉显著性检测应用到时间序列异常检测问题上的工作，结合 CNN 主要是为了提升 SR 的性能。实验部分在公开数据集和微软生产环境数据中验证了 SR-CNN 的有效性。

Background

生产环境中时间序列异常检测算法主要需要解决三个问题：Unsupervised + Generation + Efficiency。

这些问题能够解决那说明就确实是一个非常棒的工作了 👍🏻

📢 Bonus：Holt-winters 算法对周期性数据效果较好，SPOT 算法对突刺型数据效果好。

Algorithm/Model

论文提出的整体框架如下图所示

主要包括三个模块：

• data ingestion：将数据按照设定粒度采集然后存储到 Kafka 和 InfluxDB 中。
• experimentation platform：测试异常检测模型性能并收集可能的标注信息 (K8s)。
• online compute：流式异常检测并结合多个异常检测结果触发告警 (Flink)。

关注时间序列异常检测算法模块。

SR

Spectral Residual（SR）算法主要包括三步：

1. 通过傅里叶变换计算对数振幅谱；
2. 计算谱残差；
3. 通过傅里叶逆变换将序列还原到空域；

给定$n\times 1$ 维序列$\mathbf{x}$，其数学表达形式如下

$$\begin{array}{l} A(f)=\text { Amplitude }(\mathfrak{F}(\mathbf{x}))\\ P(f)=\text { Phrase }(\mathfrak{F}(\mathbf{x}))\\ L(f)=\log (A(f))\\ A L(f)=h_{q}(f) \cdot L(f)\\ R(f)=L(f)-A L(f)\\ S(\mathbf{x})=\left\|\mathfrak{F}^{-1}(\exp (R(f)+i P(f)))\right\| \end{array}$$

其中$\mathfrak{F}， \mathfrak{F}^{-1}$ 表示傅里叶变换和逆变换；$A(f)$ 表示振幅谱；$P(f)$ 表示相位谱；$L(f)$ 是振幅谱的对数形式；$AL(f)$ 是平均谱，近似为$L(f)$ 经过$h_q(f)$ 卷积得到的形式，$h_q(f)$ 为$q\times q$ 的单位矩阵；$R(f)$ 表示 spectral residual 谱残差，是原始序列的压缩表示，其中 innovation part 突变部分将会较为显著；最后通过傅里叶逆变换将序列转为空域得到$S(\mathbf{x})$ 称之为 saliency map 显著图。

📢 注意：源代码中作者使用滑动平均，与卷积操作原理相同。

以时间序列表示以上处理结果：

从上图中可以看出，通过 SR 处理后的序列异常点非常明显，因此可以通过非常简单的规则来检测异常。

例如使用固定阈值$\tau$，给定显著图$S(\mathbf{x})$，输出序列$O(\mathbf{x})$ 计算方法为

$$O\left(x_{i}\right)=\left\{\begin{array}{ll} 1, & \text { if } \left.\frac{S\left(x_{i}\right)-\overline{S\left(x_{i}\right)}}{\overline{S\left(x_{i}\right)}}\right)>\tau \\ 0, & \text { otherwise } \end{array}\right.$$

其中$\overline{S(x_i)}$ 表示$S(x_i)$ 中$z$ 个点的局部平均。

给定流式序列$x_1, x_2, ...,x_n$ 任务是判断$x_n$ 是否是异常点，但是 SR 是在滑动窗口内进行变换而且发现 SR 方法只有预测点在滑动窗口中心位置时才效果比较好。为了解决这个问题，因此论文中在序列输入 SR 之前在$x_n$ 后增加几个 estimated points，其$x_{n+1}$ 值为

$$\begin{array}{r} \bar{g}=\frac{1}{m} \sum_{i=1}^{m} g\left(x_{n}, x_{n-i}\right) \\ x_{n+1}=x_{n-m+1}+\bar{g} \cdot m \end{array}$$

其中$g(x_i, x_j)$ 表示点$x_i$ 和$x_j$ 间直线的梯度，那么$\overline{g}$ 表示$m$ 个点的平均梯度，实验中$m$ 值通常取 5。

论文中发现第一个估计值非常给你重要，因此在输入序列后直接添加$k$ 个$x_{n+1}$。

总结下，基础的 SR 算法包含以下超参数：

• 时间窗口$w$
• 估计点数量$k$
• 异常阈值$\tau$

SR-CNN

在 saliency map 上通过固定阈值的方法进行异常检测太简单了，因此论文中提出用 CNN 作为判别模型直接对时间序列分类。🤙🏻

但是 CNN 是有监督所以就必须人工生成数据来训练模型，怎么生成呢？在时间序列上插入异常点并计算得到训练集 saliency maps​。插入值计算方法如下

$$x=(\bar{x}+\operatorname{mean})(1+v a r) \cdot r+x$$

其中$\overline{x}$ 表示局部均值；$mean, var$ 表示当前滑动窗口内所有点的均值和标准差；$r\in N(0,1)$ 为随机采样值。实验中收集生产环境的数据并采用了 65 million 个点作为训练集。

SR-CNN 整体模型架构如下图所示，采用交叉熵作为损失函数。

Experiments

实验部分采用的数据集概述如下

实验结果对比如下

不同类型时间序列的异常检测性能如下

整体而言 SR-CNN 方法还行，但用的最多的还是 SR。

记录下 SR 通用实验参数，卷积矩阵$h_q(f)$ 维度为 3，局部处理点数量$\mathbb{z}$ 为 21, 阈值$\tau$ 为 3，估计点数量$k$ 为 5，滑动窗口大小随数据集变化。

Thoughts

• 一种新的思路来解决时间序列异常检测问题而且可以用到工业界 👍🏻
• 后续的 CNN 部分可有可无，用的最多的还是 SR 模型来做数据处理。
• 关注的一点是实验中效率和准确性都比 SPOT 系列好。

---

---