KDD 2021 | 多维时间序列无监督异常检测方法
#TSer#
异常检测是监控实体（如制造系统和互联网服务）各种状态（即指标）的一项关键任务，这些实体的监控数据一般都是多维时间序列。在真实工业场景中，异常检测常常缺少足够的标签，如何对多维时间序列进行无监督的异常检测是一个非常重要的课题。
来自清华的这篇KDD 2021的应用论文提出了一种无监督的方法（InterFusion），可同时对多维时间序列不同指标间的依赖和时间顺序上的依赖性进行建模。其核心思想是通过两个随机潜变量，通过变分自编码机（VAE）对多维时间序列数据中的正态模式进行建模。此外，该论文还提出了一种基于马尔科夫链蒙特卡洛（MCMC）的方法，对多维时间序列的异常结果进行解释。该论文在来自不同工业领域的四个真实数据集上进行了实验，验证算法的效果。
论文地址：https://dl.acm.org/doi/10.1145/3447548.3467075
论文源码：https://github.com/zhhlee/InterFusion
会议介绍
ACM SIGKDD（Conference on Knowledge Discovery and Data Mining, KDD）是世界数据挖掘领域的最高级别的国际会议，由 ACM（Association of Computing Machinery，计算机学会）的数据挖掘及知识发现专委会（SIGKDD）负责协调筹办，被中国计算机协会荐为A类会议。
自 1995 年以来，KDD 已经以大会的形式连续举办了二十余届全球峰会，作为数据挖掘领域最顶级的学术会议，KDD 大会以论文接收严格闻名，每年的接收率不超过 20%，因此颇受行业关注。
今年KDD发布论文接收结果：本届会议共吸引了 1541 篇论文投递，其中有 238 篇论文被接收，接收率为15.44%，相比 KDD2020 的接收率16.9%继续下降。
概述
下图展现了多维时间序列异常检测的案例：红色标注的是异常段，包括时间顺序上的异常与指标间的异常两种类型的多维时间序列异常。
该论文所宣布的核心贡献如下：
- InterFusion是第一个多维时间序列无监督异常检测算法，该算法使用层次变分自编码机、显式低维互度量和时间嵌入层来联合学习稳健的多维时间序列表示。该方法使用三种设计：层次结构：两视图嵌入和预过滤策略，来解决学习正常多维时间序列模式进行异常检测的挑战；
- 该论文提出了一种新的基于MCMC的多维时间序列异常解释方法，并定义了一个与系统操作员偏好一致的时序分段设定，以定量评估真实数据的异常解释结果；
算法模型
InterFusion的模型整体结构如下图所示：
图a: 圆形代表的随机变量，菱形代表的确定性变量，圆角矩形是神经网络层
图b: 流程框架。实线是离线训练，虚线是在线检测。
该论文采用层级变分自编码机（HVAE），通过层次结构联合训练指标间和时间上的模型参数，同时为多维时间序列数据提出双视图嵌入方法，以表达指标间和时间上依赖的特征。此外，该论文还提出了一种预过滤策略来获得特征的嵌入表示，对训练数据中的潜在异常具有很好的鲁棒性。
01
层次结构
对于多维时间序列中的单个时间序列个体，对应的有不同的低纬隐变量来（z1, z2）来学习指标间和时间上的特征表达。通过HVAE的定义，生成的目标为：
02
双视图嵌入
为了表征多维时间序列中的指标间和时间上的依赖特征，该论文提出了一种双视图嵌入，它通过利用辅助的“重构输入”d，沿着数据空间的时间和指标维度压缩多维时间序列以获得指标间和时间上的嵌入特征表达。
时间上的嵌入表达：
，
f是一维卷积神经网络（Conv1D），W’ 是压缩窗口长度。对于该特征表达的重建则为：
g是一维反卷积神经网络（Dconv1D）。
03
预过滤策略
通常模型需要灵活的指标间嵌入（能够捕获复杂的度量间依赖关系）来对多维时间序列进行建模。
然而，用于训练的真实世界原始多维时间序列数据通常包含异常。因此，直接在原始数据上学习灵活的嵌入可能会面临过度拟合异常模式的风险。因此，受到时序预测的预定采样的启发，该论文提出了一种预过滤策略来导出鲁棒性更强的指标间嵌入z1。
z1建模是从“重构输入d”的输入开始，而不是原始的时间序列x，其旨在过滤掉原始时间序列中的异常，采用正常的序列进行输入，捕捉正常的序列正态性分布。通过这种方式，可以降低了模型过度拟合潜在异常的风险，同时保留了指标间嵌入的灵活性并考虑了学习到的时间信息。
04
模型训练
VAE的训练目标是减少真实数据与重构数据之间的差异性。具体的训练目标如下：
05
模型推断
由于没有标签，我们不知道是否新的数据xt 是不是异常。该论文事先假设新数据是“异常”，并使用 MCMC 插补算法来获得更合理的重新计算：
通过比较重构值与真实值的差异，来衡量异常。
异常的解释
对于多维时间序列数据，我们通过为每个检测到的异常找到一组最异常的指标来解释检测到的异常。然而，异常可能会给学习到的特征表达带来偏差，并进而影响所有维度的重建估计。因此，该论文提出了一种基于 MCMC 的方法来近似正常模式，然后根据修改后的重建概率解释异常。
其核心思想是对于每个检测到的异常实体，根据其原始重建概率重新估计一组“最异常点”xm，然后应用MCMC插补以获得更合理的潜在嵌入和重建，根据前后的对比，判断当前异常维度是真正异常维度的概率。
重建概率为：
最后，InferFusion完整的算法伪代码如下：
实验
该论文的实验基于4个真实场景数据集进行。对于异常检测的准确性，该实验主要使用F1-score（以下简称F1）来评估。而对于段级别的异常解释准确性，该论文提出了一个新的度量标准，即“解释分数”（IPS）。
IPS的公式如下：
代表时序片段，
代表该段中真实的异常指标维度，
是该片段中检测出来的异常个数，
是模型判断出来的具有最高异常可能性的异常维度
最终，实验结果如下：
