logo

时间序列异常值检测

Anomaly Detection

wangzf / 2022-04-24

目录

时间序列异常检测介绍

异常检测需要解决两个主要问题:

按异常在时间序列中的不同表现形式，时间序列异常一般可以分为 3 种，但也有其他角度的分类方法:

时间序列异常检测方法主要包括:

  1. 基于统计分布的方法
  2. 基于距离的方法
  3. 基于密度的方法
  4. 基于聚类的方法
  5. 基于树的方法
  6. 基于降维的方法
  7. 基于分类的方法
  8. 基于预测的方法
  9. 基于神经网络方法

时间序列异常检测挑战

时间序列异常值分类

传统分类

传统分类方法因为异常值与正常值的上下文定义边界模糊， 导致集体异常值和上下文异常值的定义边界也模糊。 上下文异常值的上下文在不同的文献中通常非常不同，它们可以是一个小窗口， 包含相邻点或在季节性方法具有相似相对位置的点

img

img

点异常值

Point Anomaly

点异常指：一个值的突然上升或下降，相对于全局其他数据的异常实例，某些点与全局大多数都不一样

例如，夏季月份您家中的电力消耗增加

上下文异常值

Contextual Anomaly

上下文异常通常在它们自己的上下文中具有相对较大/较小的值，但不是全局的。 即某个时间点的表现与前后时间段内存在较大差异

例如，一个人在锻炼时心率达到 150 BPM 可能是正常的，但在凌晨 4 点保持相同的 BPM 则令人担忧。 这是一个上下文异常，上下文是人们通常在凌晨 4 点睡着了

集体异常值

Collective Anomaly

集体异常是趋势的其余部分的持续变化。这也可能是一组点异常。 相对于整个数据集异常的相关异常数据实例的集合。 即个体不存在异常，但是个体同时出现表现出异常状态

例如，夏季月份您家中的电力消耗增加

深度方法分类

img

点(Point)异常值

模式(Pattern)异常值

关于三类 Pattern 异常，可以基于 shapelet 函数来定义:

$$X_{i,j} = \rho(2 \pi T_{i,j}, \omega) + \tau(T_{i,j})$$

其中:

如果 $s$ 为相似相度量函数，那么以上三种异常类型可以分别定义为：

时间序列异常检测数据集

SEQ

基于 shapelet 函数，可以获取 35 个合成数据集(可称 NeurlIPS-TS synthestic datasets or SEQ), 其中 20 个单变量，15 个多变量数据集。该数据集覆盖各类异常数据

其他

img

时间序列异常检测方法

img

img

基于统计分布的方法

基于统计的方法最直观，适用于几乎所有类型的时间序列。在这种方法中，异常值的上限和下限是根据特定的统计量创建的， 例如：均值、标准差、Z 统计量、T 统计量、分布的百分位数

3-Sigma

基于正态分布，3-Sigma 准则认为值在 $(\mu - 3\sigma, \mu + 3\sigma)$ 区间的概率为 99.74%， 当数据分布超过这个区间时即认为是异常数据，为提升准确率可采用同环比策略

img

取整个序列的均值和标准差是不可取的，因为在这种情况下，边界将是静态的。 边界应该在滚动窗口的基础上创建，就像考虑一组连续的观察来创建边界， 然后转移到另一个窗口。该方法是一种高效、简单的离群点检测方法

Z-Score

Z-Score 方法假定数据是高斯分布，异常值是分布尾部的数据点，因此远离数据的平均值。 距离的远近取决于使用公式归一化数据集 $z_{i}$ 的设定阈值 $z_{threshold}$

$$z_{i} = \frac{x_{i} - \mu}{\sigma}$$

异常值也进行了标准化处理，如果绝对值大于 $z_{threshold}$ 则认为该观测值为异常值：

$$|z_{i}| > z_{threshold}$$

这里 $z_{threshold}$ 一般设置为 2.5、3.0、3.5。当 $z_{threshold} = 3$ 作为阈值去提出异常点时， 便相当于 3-Sigma

Boxplot

箱线图是基于四分位距(IQR)检测异常点的

img

Grubbs 检验

Grubbs 检验常被用来检验服从正态分布的单变量数据集(univariate dataset) 中的单个异常值。 若有异常值，则其必为数据集中的最大值或最小值

Grubbs 检验的原假设与备择假设如下：

Grubbs 检验需要总体是正态分布。算法流程如下：

  1. 序列样本从小到大排序
  2. 求序列样本的均值 mean 和标准差 std
  3. 计算 min 和 max 与 mean 的差距，更大的那个为可疑值
  4. 求可疑值的 Z-score(standard score)，如果大于 Grubbs 临界值，那么就是异常值
  5. 排除序列中的异常值，对剩余序列循环做 1-4 步骤

Grubbs 临界值可以查表得到，它由两个值决定：

Grubbs 检验方法的局限：

基于方差分析的方法

Elliptic Envelope

Elliptic Envelope，椭圆包格

Elliptic Envelope 算法的思路是，假设常规数据隐含这一个已知的概率分布。基于这个假设，我们尝试确定数据的形状（边界）， 也可以将远离边界的样本点定义为异常点。sklearn 提供了一个 sklearn.covariance.EllipticEnvelope 类， 它可以根据数据做一个鲁棒的协方差估计，然后学习到一个包围中心样本点并忽视离群点的椭圆

组内方差法

基于距离的方法

KNN

KNN 依次计算每个样本与它最近的 $K$ 个样本的平均距离， 再利用计算的距离与阈值进行比较，如果大于阈值，则认为是异常值

基于密度的方法

LOF

Local Outlier Factor，LOF

LOF 是基于密度的经典算法，通过给每个数据点都分配一个依赖于邻域密度的离群因子 LOF， 进而判断该数据点是否为离群点。它的好处在于可以量化每个数据点的异常程度(outlierness)

img

数据点 P 的局部相对密度(局部异常因子，LOF)：

$$LOF_{k}(P) = \frac{\sum_{N_{k}(P) \in O}\frac{lrd_{k}(O)}{lrd_{k}(P)}}{|N_{k}(P)|} \\ = \frac{\frac{\sum_{N_{k}(P) \in O}lrd_{k}(O)}{|N_{k}(P)|}}{lrd_{k}(P)}$$

数据点 P 在 $k$ 邻域内点的平均局部可达密度：

$$\frac{\sum_{N_{k}(P) \in O}lrd_{k}(O)}{|N_{k}(P)|}$$

数据点 P 的局部可达密度(数据点 P 最近邻的平均可达距离的倒数。距离越大，密度越小)：

$$lrd_{k}(P) = \frac{1}{\frac{\sum_{N_{k}(P) \in O} reach\_dist_{k}(O, P)}{|N_{k}(P)|}}$$

点 P 到点 O 的第 $k$ 可达距离：

$$reach\_dist_{k}(O, P) = max\{d_{k}(O), d(O, P)\}$$

其中:

整体来说，LOF 算法流程如下：

COF

Connectivity-Based Outlier Factor，COF

COF 是 LOF 的变种，相比于 LOF，COF 可以处理低密度下的异常值， COF 的局部密度是基于平均链式距离计算得到。 在一开始的时候一样会先计算出每个点的 k-nearest neighbor。 而接下来会计算每个点的 Set Based Nearest Path，如下图

img

假使 $k=5$，所以 F 的 neighbor 为 B、C、D、E、G。而对于 F 离他最近的点为 E， 所以 SBN Path 的第一个元素是 F、第二个是 E。离 E 最近的点为 D 所以第三个元素为 D， 接下来离 D 最近的点为 C 和 G，所以第四和五个元素为 C 和 G，最后离 C 最近的点为 B， 第六个元素为 B。所以整个流程下来，F 的 SBN Path 为 $\{F, E, D, C, G, C, B\}$。 而对于 SBN Path 所对应的距离 $e=\{e_1, e_2, e_3,\ldots,e_k\}$，依照上面的例子 $e=\{3,2,1,1,1\}$

所以可以说假使想计算 p 点的 SBN Path， 只要直接计算 p 点和其 neighbor 所有点所构成的 graph 的 minimum spanning tree， 之后再以 p 点为起点执行 shortest path 算法，就可以得到 SBN Path。 有了 SBN Path 后，接下来就会计算 p 点的链式距离

$$ac\_distance(p) = \sum_{i=1}^{k}\frac{2(k+1-i)}{k(k+1)}dist(e_{i})$$

有了 $ac\_distance$ 后，就可以计算 COF：

$$COF(p) = \frac{ac\_distance(p)}{\frac{1}{k} \sum_{o \in N_{k}(p)} ac\_distance(o)}$$

SOS

Stochastic Outlier Selection，SOS

SOS 的思想是：当一个点和其它所有点的关联度(affinity)都很小的时候，它就是一个异常点。 将特征矩阵(feature martrix)或者相异度矩阵(dissimilarity matrix)输入给 SOS 算法， 会返回一个异常概率值向量(每个点对应一个)

img

SOS 算法的流程：

  1. 计算相异度矩阵 $D$
    • 相异度矩阵(dissimilarity matrix)是各样本两两之间的度量距离，比如欧式距离或汉明距离等
  2. 计算关联度矩阵 $A$
    • 关联度矩阵(affinity matrix)反映的是度量距离方差，如图：点 $x_{5}$ 的密度最大，方差最小； $x_{6}$ 的密度最小，方差最大

img

  1. 计算关联概率矩阵 $B$
    • 关联概率矩阵(binding probability matrix)就是把关联矩阵(affinity matrix)按行归一化得到的

img

  1. 算出异常概率向量

    • 得到了关联概率矩阵，每个点的异常概率值就用如下的公式计算， 当一个点和其它所有点的关联度(affinity)都很小的时候，它就是一个异常点

    $$p(x_{i} \in C_{0}) = \prod_{j \neq i}(1 - b_{ji})$$

基于聚类的方法

K-Means 聚类

K-Means 聚类是一种无监督机器学习算法，经常用于检测时间序列数据中的异常值。 该算法查看数据集中的数据点，并将相似的数据点分组为 K 个聚类。 通过测量数据点到其最近质心的距离来区分异常。 如果距离大于某个阈值，则将该数据点标记为异常。 K-Means 算法使用欧几里得距离进行比

DBSCAN

DBSCAN 算法(Density-Based Spatial Clustering of Applications with Noise)的输入和输出如下， 对于无法形成聚类簇的孤立点，即为异常点(噪声点)

DBSCAN 输入：

DBSCAN 输出：

DBSCAN 中的三种点的类别:

img

DBSCAN 中的四种点的关系:

img

DBSCAN 的算法实现步骤:

img

DBSCAN 算法具体处理流程如下:

  1. 从数据集中任意选取一个数据对象点 p
  2. 如果对于参数 Eps 和 MinPts，所选取的数据对象点 p 为核心点，则找出所有从 p 密度可达的数据对象点，形成一个簇
  3. 如果选取的数据对象点 p 是边缘点，选取另一个数据对象点
  4. 重复以上 2、3 步，直到所有点被处理

GMM

基于树的方法

孤立森林

Isolation Forest，孤立森林

孤立森林(Isolation Forest，iForest)中的 “孤立” (isolation) 指的是 “把异常点从所有样本中孤立出来”， 论文中的原文是 “separating an instance from the rest of the instances”。

孤立森林是一种基于决策树的异常检测机器学习算法。它通过使用决策树的分区隔离给定特征集上的数据点来工作。 换句话说，它从数据集中取出一个样本，并在该样本上构建树，直到每个点都被隔离。 为了隔离数据点，随机选择 m 个特征，通过在所选特征的最大值和最小值之间随机选择一个值来分割数据点。 观察值的划分递归地重复，直到所有的观察值被孤立。 特征的随机分区将为异常数据点在树中创建更短的路径，从而将它们与其余数据区分开来

用一个随机超平面对一个数据空间进行切割，切一次可以生成两个子空间。 接下来，再继续随机选取超平面，来切割第一步得到的两个子空间，以此循环下去， 直到每子空间里面只包含一个数据点为止。可以发现，那些密度很高的簇要被切很多次才会停止切割， 即每个点都单独存在于一个子空间内，但那些分布稀疏的点，大都很早就停到一个子空间内了。 所以，整个孤立森林的算法思想：异常样本更容易快速落入叶子结点或者说，异常样本在决策树上，距离根节点更近

img

获得 $t$ 个孤立树后，单棵树的训练就结束了。接下来就可以用生成的孤立树来评估测试数据了， 即计算异常分数 $s$。对于每个样本 $x$，需要对其综合计算每棵树的结果， 通过下面的公式计算异常得分：

$$s(x, n) = 2^{-\frac{E(h(x))}{c(n)}}$$

其中:

异常分数 $s$ 指数部分值域为 $(-\infty, 0)$，因此 $s$ 值域为 $(0, 1)$。 当 PathLength 越小，$s$ 越接近 1，此时样本为异常值的概率越大

RRCF

基于降维的方法

PCA

PCA 在异常检测方面的做法，大体有两种思路：

PCA 在做特征值分解，会得到：

所以，最大特征值对应的特征向量为数据方差最大的方向，最小特征值对应的特征向量为数据方差最小的方向。 原始数据在不同方向上的方差变化反应了其内在特点。如果单个数据样本跟整体数据样本表现出的特点不太一致， 比如在某些方向上跟其它数据样本偏离较大，可能就表示该数据样本是一个异常点

在前面提到第一种做法中，样本 $x_i$ 的异常分数为该样本在所有方向上的偏离程度：

$$Score(x_{i}) = \sum_{j=1}^{n}d_{ij} = \sum_{j=1}^{n}\frac{(x_{i}^{T}) \cdot e_{j}}{}$$

其中，为样本在重构空间里离特征向量的距离。若存在样本点偏离各主成分越远，会越大，意味偏移程度大，异常分数高。 是特征值，用于归一化，使不同方向上的偏离程度具有可比性

在计算异常分数时，关于特征向量（即度量异常用的标杆）选择又有两种方式：

第二种做法，PCA 提取了数据的主要特征，如果一个数据样本不容易被重构出来， 表示这个数据样本的特征跟整体数据样本的特征不一致，那么它显然就是一个异常的样本：

其中，是基于 k 维特征向量重构的样本

基于低维特征进行数据样本的重构时，舍弃了较小的特征值对应的特征向量方向上的信息。 换一句话说，重构误差其实主要来自较小的特征值对应的特征向量方向上的信息。 基于这个直观的理解，PCA 在异常检测上的两种不同思路都会特别关注较小的特征值对应的特征向量。 所以，我们说 PCA 在做异常检测时候的两种思路本质上是相似的， 当然第一种方法还可以关注较大特征值对应的特征向量

AutoEncoder

PCA 是线性降维，AutoEncoder 是非线性降维。根据正常数据训练出来的 AutoEncoder， 能够将正常样本重建还原，但是却无法将异于正常分布的数据点较好地还原，导致还原误差较大。 因此如果一个新样本被编码，解码之后，它的误差超出正常数据编码和解码后的误差范围， 则视作为异常数据。需要注意的是，AutoEncoder 训练使用的数据是正常数据（即无异常值）， 这样才能得到重构后误差分布范围是多少以内是合理正常的。所以 AutoEncoder 在这里做异常检测时， 算是一种有监督学习的方法

基于分类的方法

One-Class SVM

One-Class SVM 算法的思路非常简单，就是寻找一个超平面将样本中的正例圈出来， 预测就是用这个超平面做决策，在圈内的样本就认为是正样本，在圈外的样本是负样本， 用在异常检测中，负样本可看做异常样本。它属于无监督学习，所以不需要标签

One-Class SVM 又一种推导方式是 SVDD(Support Vector Domain Description，支持向量域描述)， 对于 SVDD 来说，我们期望所有不是异常的样本都是正类别，同时它采用一个超球体， 而不是一个超平面来做划分，该算法在特征空间中获得数据周围的球形边界， 期望最小化这个超球体的体积，从而最小化异常点数据的影响

假设产生的超球体参数为中心 $o$ 和对应的超球体半径 $r>0$，超球体体积 $V(r)$ 被最小化， 中心 $o$ 是支持行了的线性组合；跟传统 SVM 方法相似，可以要求所有训练数据点 $x_{i}$ 到中心的距离严格小于 $r$。 但是同时构造一个惩罚系数为 C 的松弛变量 $\zeta_{i}$，优化问题入下所示：

$$\underbrace{min}_{r,\rho} V(r) + C\sum_{i=1}^{m}\zeta_{i}$$

$$||x_{i} - o||_{2} \leq r + \xi_{i}, i = 1,2,\ldots,m$$ $$\xi_{i} \geq 0, i = 1,2,\ldots,m$$

C 是调节松弛变量的影响大小，说的通俗一点就是，给那些需要松弛的数据点多少松弛空间， 如果 C 比较小，会给离群点较大的弹性，使得它们可以不被包含进超球体

基于预测的方法

对于单条时序数据，根据其预测出来的时序曲线和真实的数据相比，求出每个点的残差， 并对残差序列建模，利用 KSigma 或者分位数等方法便可以进行异常检测。具体的流程如下

img

ARIMA

可用于通过使用预测值与实际值之间的差异来查找异常

基于时序分解的方法

STL

Seasonal-Trend decomposition using Loess

去除(隔离)时间序列数据中的模式，所以留下的任何东西都是“不规则的”，因此是异常的

img

SH-ESD

Twitter Seasonal Hybrid ESD

SH-ESD 是建立在 ESD(Extreme Studentized Deviate)上的。该方法是基于使用时间序列分解和统计检验

基于神经网络方法

img

深度相关的代表性模型：

img

  1. 特征提取
    • deep learning 和 anomaly detection 是分开的，deep learning 只负责特征提取
  2. 常态特征表征学习：deep learning 和 anomaly detection 是相互依赖的，一起学习正常样本的有效表征
    • 通用常态特征表征学习：这类方法最优化一个特征学习目标函数，该函数不是为异常检测而设计的， 但学习到的高级特征能够用于异常检测，因为这些高级特征包含了数据的隐藏规律
    • 依赖异常度量的特征表征学习：该类方法直接将现有的异常评价指标嵌入表征学习的优化目标中
  3. 端对端异常分数学习
    • deep learning 和 anomaly detection 是完全一体的，通过端到端的学习，直接输出异常分数

特征提取

旨在利用深度学习从高维和/或非线性可分离数据中提取低维特征表征，用于下游异常检测。 特征提取和异常评分完全不相交且彼此独立。因此，深度学习组件仅作为降维工作

优点：

缺点：

学习常态特征表征

通用常态特征表征学习

这类方法最优化一个特征学习目标函数，该函数不是为异常检测而设计的， 但学习到的高级特征能够用于异常检测，因为这些高级特征包含了数据的隐藏规律。 例如：AutoEncoder、GAN、预测模型(LSTM)。

优点：

缺点：

另外，以上方法都有两个共性问题：

依赖异常度量的特征表征学习

该类方法直接将现有的异常评价指标嵌入表征学习的优化目标中， 解决了通用常态特征表征学习中第二个共性问题。 例如 Deep one-class SVM，Deep one-class Support Vector Data Description(Deep one-class SVDD)等

优化：

缺点：

以上缺点在于：没办法直接输出异常分数

端对端异常分数学习

通过端到端的学习，直接输出异常分数。个人对这部分的了解是一片空白， 只能初略转述下综述中的内容，有兴趣的朋友可以阅读原文跟进相关工作

优点：

缺点：

结论和方向

把异常度量目标加入到表征学习中：表征学习时，一个关键问题是它们的目标函数是通用的， 但没有专门针对异常检测进行优化。在前面有提到依赖于异常度量的特征学习， 它便是通过施加来自传统异常度量的约束，来帮助解决这个问题

参考