一些经典的无监督异常检测算法

原创故黎蚂蚁质量AnTest

基于统计的时序异常检测

3σ检测

该算法假设数据符合正态分布，根据3σ准则，数值分布在（μ-3σ,μ+3σ)中的概率为99.73%。

则认为在该范围之外的均为异常点。

箱形图

简单来说，该算法不假设数据的分布，根据数据的1/4（假设为q1）和3/4分位点（假设为q2），设计正常数据的上下限：

无监督异常检测算法

无监督的异常检测又名为 Outlier Detection，即离群点检测。

基于密度的方法

Local Outlier Factor 局部异常因子

SIGMOD 2000 引用量 7800+

该算法的主要思想在于根据局部密度（local density）来判断样本是否异常：一个正常样本的局部密度应当与相邻样本的局部密度相似，而异常样本的局部密度则会小很多。

该算法最核心的部分是关于数据点密度的刻画。

该算法中有几个关键的概念：

k-距离：某一点和距离该点第k近的点之间距离（不包括该点）；

k-距离邻域：某一点的直线距离不超过该点的k-距离的所有点的集合（该集合中至少应有k个元素）；

可达距离：

即点j和i之间的距离和点j的k-距离的较大值；

如下图所示：

局部可达密度（local reachablity density）：

直观地说，某一点的局部可达密度是该点的的k近邻点的平均可达距离的倒数。显然，距离越短，密度越大，可达距离起到了平滑的作用。

局部异常因子（local outlier factor）：

局部异常因子反映了某点为异常值的程度。它是该点的k近邻点的平均局部可达密度与该点的平均可达密度的比值。LOF算法衡量一个数据点的异常程度，并不是看它的绝对局部密度，而是看它跟周围邻近的数据点的相对密度。这样做的好处是可以允许数据分布不均匀、密度不同的情况。

有关LOF有效性的证明，可以参考原文：📎LOF.pdf

DAGMM ：Deep Autoencoding Gaussian Mixture Model for Unsupervised Anomaly Detection

2018年ICLR 引用量1000+

基于密度的异常检测存在的问题：Especially, when the dimensionality of input data becomes higher, it is more difficult to perform density estimation in the original feature space, as any input sample could be a rare event with low probability to observe。

简单来说，就是在高维空间中，整体的密度分布都会比较低，难以有效地通过密度来区分异常点。为了解决该问题，现有方法通过降维+密度估计的二阶段形式来进行异常检测，这样做的问题在于第一步的降维对于后续行为并不感知，可能会导致异常的信息被舍弃了。

为了解决这一问题，该方法提出了Deep Autoencoding Gaussian Mixture Model（DAGMM，深度自编码高斯混合模型）

首先，DAGMM提出了一个Compression Network，通过一个自编码器同时得到降维结果和重构误差，作者认为这两部分特征可以更为充分地表示异常点；

其次，DAGMM使用一个Gaussian Mixture Model（GMM，高斯混合模型）来进行密度估计。GMM通常利用EM算法进行求解（为什么不用梯度下降呢？可以参考https://spaces.ac.cn/archives/4277），但EM算法无法与前面的降维过程进行联合优化。为了解决该问题，DAGMM提出了一个Estimation Network，该网络以Compression Network的结果作为输入，输出每一个样本的Mixture Membership Prediction，即将EM算法的E步骤中的样本属于各子分布的概率替换为端到端架构中子Estimation network的输出。

E步（根据现有MLN的参数，得到z的分布，也就是样本隶属于不同高斯分布的概率分布）：

正常来说，这一部分应该是根据GMM的参数来算的，但是为了联合优化，改用了一个MLN用来代替。

M步（根据z的分布，估计高斯分布的参数，并对E步中的参数进行更新）：

这三项分别表示第k个高斯分布的混合概率、均值和协方差。

Loss函数：

Loss分为三个部分，分别是：

自编码网络的重构误差；
高斯混合模型的似然函数；

正则化，防止 GMM 中的协方差矩阵的对角线上的值变为0 并最终导致矩阵不可逆。

基于聚类的方法

SVDD：Support Vector Domain Description

SVDD属于是One Class SVM问题的一种解决方法。One Class SVM问题是指在仅有一类数据的情况下进行分类，比方说，有一个小和尚，他从小在寺庙长大，从来都只见过男生，没见过女生，那么对于一个男性，他能很快地基于这个男性与他之前接触的男性有类似的特征，给出这个人是男性的答案。但如果是一个女性，他会发现，这个女性与他之前所认知的男性的特征差异很大，进而会得出她不是男性的判断。这类方法主要应用于新值检测（novelty detection），要求数据中不含有异常点。但在实际场景中，由于样本空间并不会找得特别好，也可以尝试用于异常值检测。

SVDD的主要思想在于，找一个采用一个超球体来对空间进行划分。该算法在特征空间中获得数据周围的球形边界，期望最小化这个超球体的体积，从而最小化异常点数据的影响。

其中，R是超球体半径，a是超球体的球心，具体的求解过程不在此阐述。

Deep SVDD：Deep One-Class Classification

ICML 2018 引用量1000+

在SVDD的基础上，通过一个神经网络来进行点的映射：

问题来了：如何去优化这个神经网络呢？参考上面的优化目标设计loss即可。

优化目标如下：

该优化目标分别三项：

第一项跟SVDD一样，希望以一个最小的超球体来对空间进行划分；
第二项是一个惩罚项，要求数据尽可能落在超球体内靠近边缘的位置；其中v是一个用于进行trade-off的超参数，允许部分的点落在超球体外；
第三项是一个权重衰减的正则化项。

基于重构的方法

Variational Autoencoder based Anomaly Detection using Reconstruction Probability

首尔大学 2015 引用量1000+

前面的异常检测方法会首先对高维的数据特征进行降维来更好地区分出异常数据，重新将这些低维特征映射回高维空间的行为叫做重构（reconstruction），重构后的结果与原始数据的差异叫做重构误差（reconstruction error），重构误差越大，则为异常点的概率越高。

本文提出了一个基于变分自编码器（variational autoencoders， VAE）的异常检测算法。

一句话概括VAE：希望构建一个从隐变量z生成目标数据x的模型g，其中z提前假设服从某种分布。

从神经网络的视角来看，VAE的优化loss如下所示：

其中第一项是重构误差（reconstruction loss），即极大化样本的似然；第二项通过一个KL散度来控制z的分布近似于一个标准的正态分布，避免模型对于类似的输入所得到的q差别过大。

该图来自：https://spaces.ac.cn/archives/5253

上图展示了VAE作用的全过程，可以看出来，在推理阶段，使用VAE的步骤如下：

基于VAE的异常检测：

简单来说，由于我们的最终目标是异常检测，并不是真的要去生成数据，因此将原本的数据x从decoder中重新生成的概率的作为数据x是否为异常的评价指标，称之为重构概率（reconstruction probability）。如果重构概率低于所设定的阈值，则认为是异常点。

值得注意的是，训练的时候需要用不含有异常点的数据来训练。

Dount ：Unsupervised Anomaly Detection via Variational Auto-Encoder for Seasonal KPIs in Web Applications

WWW 2018 清华&阿里出品引用量500+

该算法同样是基于变分自编码器（VAE，Variational AutoEncoder）的：通过VAE来重构时间序列，并根据重构误差来判断异常点：

不同的地方在于，该方法针对的是时序的KPIs(key performance indicators)数据，相比较于上文主要有以下两点不同：

在原始VAE上做了一些改进，针对KPI异常检测这个场景增加了一些细节上的优化，如missing data injection、MCMC等等；
打破了VAE必须在不含有异常点的数据上进行训练的限制；

Unsupervised Anomaly Detection with Generative Adversarial Networks to Guide Marker Discovery

IPMI 2017 引用量 1500+

利用强化学习来进行异常检测。

基于时间序列预测的异常检测

时序数据是存在前后关系的，可以根据过往数据对未来的数据进行拟合，然后根据预测出来的数据与实际数据的误差值，通过3sigma来判断误差值是否正常（假设历史数据的误差值服从正态分布），从而判断数据点是否异常。时序预测模型通常是通过寻找历史数据之间的自相关性，来预测未来（假设未来将重复历史的走势），要求序列必须是平稳的，平稳性是时间序列分析的基础。

一般来说，会首先想办法让数据变得平稳（例如STL算法、一阶差分），再采用时序预测方法（例如ARMA 、Holt-Winter模型）来进行拟合。

什么是平稳性？

通常情况下时间序列分析讨论的是弱平稳序列。弱平稳性的定义：

均值 u 是与时间 t 无关的常数；
对于任意时刻 t 和任意时间间隔 k，时间序列 z_t 与 z_{t−k} 的自协方差 r_k 只与 k 有关，与 t 无关。

对于一个时间序列，通常采用 ADF 检验（单位根检验）的方式来判断其是否平稳。

如何让数据变平稳？

STL算法

STL（Seasonal and Trend decomposition using Loess）是一个非常通用和稳健强硬的分解时间序列的方法，其中Loess是一种估算非线性关系的方法。这里不展开进行介绍。

STL的分解结果如下图所示：

一阶差分、二阶差分

一阶差分就是连续相邻两项之差。当自变量从x变到x+1时，函数y=y(x)的改变量∆yx=y(x+1)-y(x)，(x=0，1，2，......)称为函数 y(x)在点x的一阶差分，记为∆y_x=y_(x+1)-y_x，(x=0，1，2，......)。
重复上述动作，做两次相同的动作，即再在一阶差分的基础上用后一个数值再减上一个数值一次，就叫“二阶差分"。

时序预测算法

https://zhuanlan.zhihu.com/p/421710621

ARIMA模型

ARIMA(p, d, q)由三个部分组成：

AR(p)：AR是autoregressive的缩写，表示自回归模型，含义是当前时间点的值等于过去若干个时间点的值的回归——因为不依赖于别的解释变量，只依赖于自己过去的历史值，故称为自回归；如果依赖过去最近的p个历史值，称阶数为p，记为AR(p)模型。
I(d)：I是integrated的缩写，含义是模型对时间序列进行了差分；因为时间序列分析要求平稳性，不平稳的序列需要通过一定手段转化为平稳序列，一般采用的手段是差分；另外，还有一种特殊的差分是季节性差分S，即一些时间序列反应出一定的周期T，让t时刻的值减去t-T时刻的值得到季节性差分序列。
MA(q)：MA是moving average的缩写，表示移动平均模型，含义是当前时间点的值等于过去若干个时间点的预测误差的回归；预测误差=模型预测值-真实值；如果序列依赖过去最近的q个历史预测误差值，称阶数为q，记为MA(q)模型。

值得注意的是，ARMA模型是针对平稳时间序列建立的模型，而ARIMA模型是针对非平稳时间序列建模，不需要提前额外做差分。

首先在训练集上确定参数(p, d, q)，然后即可在测试集上进行预测。

Holt-Winters 模型

Holt-Winters的主要思想在于认为离预测点越近的点，并且随着时间变化权重以指数方式下降，最终年代久远的数据权重将接近于0。

Holt-Winters通常特指三次指数平滑法。

一次指数平滑：权值呈指数级递减的移动平均法

其中

就表示经过平滑的值，为什么叫指数平滑呢？

可以看到，所有先前的观测值都对当前的平滑值产生了影响，但它们所起的作用随着参数 α 的幂的增大而逐渐减小。

二次指数平滑：额外考虑“趋势”信息

所谓趋势，其实就是当前值相比较于上一个值增加或者减少的量。引入了一个变量t，其形式同于一阶指数平滑，考虑到了s的变化情况。

三次指数平滑： 额外考虑季节性特征

在二次指数平滑的基础上，又引入了一个变量p，形式也同于一阶指数平滑，考虑到了周期性信息。

Isolation Forest 孤立森林

周志华出品引用量3000+

该方法的思想在于使用随机森林（random forest），“孤立”的思想体现在，首先随机选择一个特征，然后随机地从最大值和最小值之间选择一个数来“孤立”出一些样本。

这样不断的分割可以看作是树结构的，因此对于一个样本来说，孤立出该样本的次数等同于包含该样本的叶子结点到跟结点的距离。

随机构造很多树形成一个森林，这样一来，每个样本的平均距离可以用来度量该样本的离群程度。这个距离越短，则说明该样本越容易被孤立出来，也就更像一个异常点。

SR(Spectral Residual)算法:Time-Series Anomaly Detection Service at Microsof

该算法的思想来自于计算机视觉中的显著性检验，简单来说，大量图片做均值之后的log频谱趋近于一条直线：

那么一张图片的log频谱减去平均图片的log频谱就是其显著部分，做差之后进行反傅立叶变换复原图片得到显著区域。

对应到时间序列数据，以一定长度的滑动窗口序列作为输入，分别计算其振幅频谱和相位频谱，然后对振幅频谱取log，再对log后的结果做卷积来近似出平均log频谱，并将log振幅频谱减去平均log频谱（这个值就是sepctral residual，谱残差），最后通过exp和反傅立叶变化得到saliency map（显著性图）。在显著性图中比较特别的点可能对应着异常点。

得到显著性图之后，就可以通过一些简单的策略来找到其中比较特别的点，例如：

另外，由于SR算法在异常点处于序列中间时效果较好，因此可以在执行SR算法之前简单地对曲线进行延长：

Anomaly Transformer：Time Series Anomaly Detection with Association Discrepancy

ICLR 2022 Spotlight 清华大学引用量 30+

首先，Transformers通过自注意力（self-attention）机制建模了时间序列上不同时间点之间的关联关系，这种关联关系给我们提供了时序上下文的信息，例如趋势、周期等。但是由于在实际场景中，异常点的数量往往远小于正常点的数量，所以很难将异常点与整个序列关联起来；由于时间序列的连续性，往往异常点会与其相邻的点又比较强的关联性。与此相反，正常点则会与整个序列都会有较强的关联性。这种整个序列和邻近先验之间的关联差异为时序异常检测提供了天然的、强区分度的判据。
针对这一直觉，本文提出了Anomaly Transformer模型用于建模时序关联，同时利用极小极大（Minimax）关联学习策略进一步突出正常、异常点之间差别，实现了基于关联差异（Association Discrepancy）的时序异常检测。

可以看到，Series-Association就是正常的attention，而Prior-Association是一个带参数的、可学习的高斯核函数，其中心在对应时间点的索引上。这种设计可以利用高斯分布的单峰特点，使数据更加关注邻近的点。

为了量化正常点和异常点的区别，定义了如下的关联差异：

最终优化的目标如下，利用重建误差来进行模型优化的同时，使用了一个额外关联差异损失来增大关联差异，这样可以使得异常点的重建更加的艰难，进而更加可辨别：

然而直接最小化关联差异将使得高斯核的尺度参数σ急剧变小，结果就会导致先验分布无意义。因此，为了更好的控制关联学习的过程，本文采用了一种Minimax策略。在最小化阶段，我们让先验关联P近似从原始时序中学得的序列关联S，该过程将使得先验关联适应不同的时序模式。在最大化阶段，我们优化序列关联S来最大化关联之间的差异，该过程将使得序列关联更加注意非临接的点，使得异常点的重建更加困难。

最终，异常检测的依据如下：

一句话总结：重构误差越大，关联差异越小，则该点为异常点的可能性就越大。

时序异常检测开源算法库

TODS：https://tods-doc.github.io/

pyod：https://pyod.readthedocs.io/en/latest/

配套的有一个benchmark：https://github.com/Minqi824/ADBench，可以一起使用。

异常检测的资源整合：https://github.com/yzhao062/anomaly-detection-resources

Reference

综述、benchmark：

只针对时间序列的OD

Revisiting Time Series Outlier Detection: Definitions and Benchmarks ：

Tsb-uad: an end-to-end benchmark suite for univariate time-series anomaly detection

针对广义的OD

ADBench: Anomaly Detection Benchmark

sklearn异常检测算法库：https://scikit-learn.org/stable/modules/outlier_detection.html?highlight=outli

https://zhuanlan.zhihu.com/p/142320349

如对本文有任何建议或问题，请关注我们的微信公众号，我们将私信回复 ❤️

‍

继续滑动看下一个