TopoMAD：云系统中基于时空数据的无监督异常检测模型

论文标题｜ A Spatiotemporal Deep Learning Approach for Unsupervised Anomaly Detection in Cloud Systems
论文来源｜ TNNLS(B) 2020
论文链接｜ https://ieeexplore.ieee.org/document/9228885
源码链接｜数据集：https://github.com/QAZASDEDC/TopoMAD

TL;DR

针对云系统中的脏数据问题，论文中提出一种无监督的异常检测模型 TopoMAD (topology-aware multivariate time series anomaly detector) ，该模型通过随机的 seq2seq 变分自动编码器模型来表示云系统数据的时空特征。系统拓扑和时序信息是指不同组件间根据滑动窗口聚合的指标数据，然后分别使用 GCN 和 LSTM 来提取系统空间特征和时序特征。实验部分在两个数据集中验证了论文提出的模型优于其它 baselines。

Problem Statement

对于拓扑多变量时间序列的异常检测任务是：给定个历史滑动窗口的数据 $S\left(X_{t} \mid X_{t-W: t-1}, E\right)$ 来判定观测点 $X_t$ 的数据是否异常。论文中使用的符号表示如下图所示：

Model / Algorithm

文中先简单陈述了所涉及的基础模型包括 GCN，GAT，LSTM 和 VAE 等，在此不再赘述。

详细内容可以参考博主其它文章：

论文中 TopoMAD 整体的模型架构如下图所示：

主要包含一下流程：

Data Integration and Preprocessing
Building Block: GraphLSTM
Network Architecture
Ofﬂine Model Training
Computing Anomaly Scores
Threshold Selection

数据处理

给定一个集群节点示例如下图所示：

论文中仅考虑按照时间窗口聚合的指标数据和静态图结构，但是实际生产环境由于变更和负载均衡等原因，拓扑图往往是动态的，这应该如何解决呢？🧐 🤔

GraphLSTM

结合了 GCN/GAT 和 LSTM 的模块 GraphLSTM 作为模型的特征提取模块，架构图如下图所示。

⚠️ 这一项 novelty 并不够，因为就我所知在非常多的 paper 中已经用过了，主要的计算公式如下所示：

$\begin{aligned} f_{t} &=\operatorname{sigmoid}\left(\mathbf{W}_{f} *_{\mathcal{G}}\left(\left[h_{t-1}, x_{t}\right], E\right)+\mathbf{b}_{f}\right) \\ i_{t} &=\operatorname{sigmoid}\left(\mathbf{W}_{i} *_{\mathcal{G}}\left(\left[h_{t-1}, x_{t}\right], E\right)+\mathbf{b}_{i}\right) \\ g_{t} &=\tanh \left(\mathbf{W}_{g} *_{\mathcal{G}}\left(\left[h_{t-1}, x_{t}\right], E\right)+\mathbf{b}_{g}\right) \\ c_{t} &=f_{t} * c_{t-1}+i_{t} * g_{t} \\ o_{t} &=\operatorname{sigmoid}\left(\mathbf{W}_{o} *_{\mathcal{G}}\left(\left[h_{t-1}, x_{t}\right], E\right)+\mathbf{b}_{o}\right) \\ h_{t} &=o_{t} * \tanh \left(c_{t}\right) \end{aligned}$

其中 $*_{\mathcal{G}}$ 表示图卷积操作， $*$ 表示 Hadamard product （即矩阵对应元素相乘）；

模型架构和离线训练

TopoMAD 主要框架是 stochastic seq2seq auto-encoder，接下来就是 GraphLSTM 的堆积过程了。

训练的模型和推断的模型不太一样，这稍微的区别就体现在下面 “teacher forcing”，主要流程如下图所示；

训练时的模型使用一个超参数 $\lambda$ 来控制概率来选择输入是原始序列还是重构的序列，这就是所谓的 teacher forcing?

采用 variational lower bound on the marginal likelihood，训练的损失函数如下：

$\begin{aligned} \mathcal{L}\left(\theta, \phi ; X_{t_{0}: t}\right)=&-D_{\mathrm{KL}}\left(q_{\phi}\left(z_{t} \mid X_{t_{0}: t}\right) \| p_{\theta}\left(z_{t}\right)\right) \\ &+\mathbf{E}_{q_{\phi}\left(z_{t} \mid X_{t_{0}: t}\right)}\left(\log \left(p_{\theta}\left(X_{t_{0}: t} \mid z_{t}\right)\right)\right) \\ =&-D_{\mathrm{KL}}\left(q_{\phi}\left(z_{t} \mid X_{t_{0}: t}\right) \| \mathcal{N}(0, I)\right) \\ &+\frac{1}{L} \sum_{l=1}^{L} \sum_{j=t_{0}}^{t} \log \left(p_{\theta}\left(X_{j} \mid z_{t}^{(l)}, X_{j+1: t}\right)\right) \end{aligned}$

异常分数计算

在观测点 $X_t$ 时通过重构概率计算得到的异常分数，计算方法如下所示：

$\operatorname{temp} S_{t}=-\mathbf{E}_{q_{\phi}\left(z_{t} \mid X_{t_{0}: t}\right)}\left(\log \left(p_{\theta}\left(X_{t} \mid z_{t}\right)\right)\right)$

由于输入的是时间序列，前 $W-1$ 个观测点同样可以计算异常分数来优化当前时刻的异常分数计算，因此整体的计算公式如下：

$S_{t}=-\frac{1}{L * D} \sum_{d=0}^{D-1} \sum_{l=1}^{L} \log \left(p_{\theta}\left(X_{t} \mid z_{t+d}^{(l)}, X_{t+1: t+d}\right)\right)$

其中 $L$ 表示采样数量， $D$ 表示采用前多少个观测点；

对于系统中的每个组件的异常分数，可以计算所有节点相对重构概率较低且异常分数较大的值：

$S_{t}=-\max _{0 \leq i<N} \frac{1}{L * D} \sum_{d=0}^{D-1} \sum_{l=1}^{L} \log \left(p_{\theta}\left(X_{t}^{i} \mid z_{t+d}^{(l)}, X_{t+1: t+d}\right)\right)$

其中 $N$ 表示系统中组件数量， $X_t^i$ 表示组件 $i$ 在 $t$ 时刻的指标值。

阈值选择

论文中通过训练集中的异常分数集合来选择阈值。一般情况下正常数据集合的异常分数和异常数据集合的异常分数间的 gap 比较大，因此来定义一种方法来计算这两个数据集合的距离，使得距离最大的异常分数 $\tau$ 就是异常阈值，计算分数如下所示：

$d\left(S_{<\tau}, S_{>\tau}\right)=\frac{\min \left(S_{>\tau}\right)-\max \left(S_{<\tau}\right)}{\min \left(S_{>\tau}\right)+\max \left(S_{<\tau}\right)-2 * \min \left(S_{<\tau}\right)}$

Experiments

论文中采用了两个数据集且数据是开源的，特征如下表所示：

采用的评价指标主要包括AP，mAP 和 F1，计算公式如下：

$\begin{aligned} P &=\frac{T P}{T P+F P}, \quad R=\frac{T P}{T P+F N} \\ A P &=\sum_{i}\left(R_{i}-R_{i-1}\right) P_{i}, \quad m A P=\frac{\sum A P_{C}}{N(\text { Classes })} \end{aligned}$