↑ 点击蓝字 关注极市平台

作者丨刘腾飞@知乎

来源丨https://www.zhihu.com/column/liutengfei

编辑丨极市平台

极市导读

 

异常检测(Anomaly detection)问题是机器学习算法的一个常见应用。这种算法的一个有趣之处在于：它虽然主要用于非监督学习问题，但从某些角度看，它又类似于一些监督学习问题。本文总结了四种机器学习中异常检测的算法：Isolation Forest、Local Outlier Factor、Principal Component Analysis、DAGMM，每一种算法都从其基本概念开始详细的介绍，后给出了该算法应用在实际中需要注意的要点。 >>感谢CV开发者一路以来对我们的支持，前往文末即可领取【极市】双12福利！

异常检测算法（一）：Isolation Forest

"An outlier is an observation which deviates so much from other observations as to arouse suspicions that it was generated by a different mechanism."

— D. M. Hawkins, Identification of Outliers, Chapman and Hall, 1980.

异常检测 (anomaly detection)，或者又被称为“离群点检测” (outlier detection)，是机器学习研究领域中跟现实紧密联系、有广泛应用需求的一类问题。但是，什么是异常，并没有标准答案，通常因具体应用场景而异。如果要给一个比较通用的定义，很多文献通常会引用 Hawkins 在文章开头那段话。很多后来者的说法，跟这个定义大同小异。这些定义虽然笼统，但其实暗含了认定“异常”的两个标准或者说假设：

1. 异常数据跟样本中大多数数据不太一样。
2. 异常数据在整体数据样本中占比比较小。

为了刻画异常数据的“不一样”，最直接的做法是利用各种统计的、距离的、密度的量化指标去描述数据样本跟其他样本的疏离程度。而 Isolation Forest (Liu et al. 2011) 的想法要巧妙一些，它尝试直接去刻画数据的“疏离”(isolation)程度，而不借助其他量化指标。Isolation Forest 因为简单、高效，在学术界和工业界都有着不错的名声。

算法介绍

我们先用一个简单的例子来说明 Isolation Forest 的基本想法。假设现在有一组一维数据（如下图所示），我们要对这组数据进行随机切分，希望可以把点 A 和点 B 单独切分出来。具体的，我们先在最大值和最小值之间随机选择一个值 x，然后按照 <x 和 >=x 可以把数据分成左右两组。然后，在这两组数据中分别重复这个步骤，直到数据不可再分。显然，点 B 跟其他数据比较疏离，可能用很少的次数就可以把它切分出来；点 A 跟其他数据点聚在一起，可能需要更多的次数才能把它切分出来。

我们把数据从一维扩展到两维。同样的，我们沿着两个坐标轴进行随机切分，尝试把下图中的点A'和点B'分别切分出来。我们先随机选择一个特征维度，在这个特征的最大值和最小值之间随机选择一个值，按照跟特征值的大小关系将数据进行左右切分。然后，在左右两组数据中，我们重复上述步骤，再随机的按某个特征维度的取值把数据进行细分，直到无法细分，即：只剩下一个数据点，或者剩下的数据全部相同。跟先前的例子类似，直观上，点B'跟其他数据点比较疏离，可能只需要很少的几次操作就可以将它细分出来；点A'需要的切分次数可能会更多一些。

按照先前提到的关于“异常”的两个假设，一般情况下，在上面的例子中，点B和点B' 由于跟其他数据隔的比较远，会被认为是异常数据，而点A和点A' 会被认为是正常数据。直观上，异常数据由于跟其他数据点较为疏离，可能需要较少几次切分就可以将它们单独划分出来，而正常数据恰恰相反。这其实正是 Isolation Forest（IF）的核心概念。IF采用二叉树去对数据进行切分，数据点在二叉树中所处的深度反应了该条数据的“疏离”程度。整个算法大致可以分为两步：

1. 训练：抽取多个样本，构建多棵二叉树（Isolation Tree，即 iTree）；
2. 预测：综合多棵二叉树的结果，计算每个数据点的异常分值。

训练：构建一棵 iTree 时，先从全量数据中抽取一批样本，然后随机选择一个特征作为起始节点，并在该特征的最大值和最小值之间随机选择一个值，将样本中小于该取值的数据划到左分支，大于等于该取值的划到右分支。然后，在左右两个分支数据中，重复上述步骤，直到满足如下条件：

1. 数据不可再分，即：只包含一条数据，或者全部数据相同。
2. 二叉树达到限定的最大深度。

预测：计算数据 x 的异常分值时，先要估算它在每棵 iTree 中的路径长度（也可以叫深度）。具体的，先沿着一棵 iTree，从根节点开始按不同特征的取值从上往下，直到到达某叶子节点。假设 iTree 的训练样本中同样落在 x 所在叶子节点的样本数为 T.size，则数据 x 在这棵 iTree 上的路径长度 h(x)，可以用下面这个公式计算：

公式中，e 表示数据 x 从 iTree 的根节点到叶节点过程中经过的边的数目，C(T.size) 可以认为是一个修正值，它表示在一棵用 T.size 条样本数据构建的二叉树的平均路径长度。一般的，C(n) 的计算公式如下：

其中，H(n-1) 可用 ln(n-1)+0.5772156649 估算，这里的常数是欧拉常数。数据 x 最终的异常分值 Score(x) 综合了多棵 iTree 的结果：

公式中，e 表示数据 x 从 iTree 的根节点到叶节点过程中经过的边的数目，C(T.size) 可以认为是一个修正值，它表示在一棵用 T.size 条样本数据构建的二叉树的平均路径长度。一般的，C(n) 的计算公式如下：

从异常分值的公式看，如果数据 x 在多棵 iTree 中的平均路径长度越短，得分越接近 1，表明数据 x 越异常；如果数据 x 在多棵 iTree 中的平均路径长度越长，得分越接近 0，表示数据 x 越正常；如果数据 x 在多棵 iTree 中的平均路径长度接近整体均值，则打分会在 0.5 附近。

算法应用

Isolation Forest 算法主要有两个参数：一个是二叉树的个数；另一个是训练单棵 iTree 时候抽取样本的数目。实验表明，当设定为 100 棵树，抽样样本数为 256 条时候，IF 在大多数情况下就已经可以取得不错的效果。这也体现了算法的简单、高效。

Isolation Forest 是无监督的异常检测算法，在实际应用时，并不需要黑白标签。需要注意的是：（1）如果训练样本中异常样本的比例比较高，违背了先前提到的异常检测的基本假设，可能最终的效果会受影响；（2）异常检测跟具体的应用场景紧密相关，算法检测出的“异常”不一定是我们实际想要的。比如，在识别虚假交易时，异常的交易未必就是虚假的交易。所以，在特征选择时，可能需要过滤不太相关的特征，以免识别出一些不太相关的“异常”。

异常检测算法（二）：Local Outlier Factor

Local Outlier Factor（LOF）是基于密度的经典算法（Breuning et. al. 2000）, 文章发表于 SIGMOD 2000, 到目前已经有 3000+ 的引用。在 LOF 之前的异常检测算法大多是基于统计方法的，或者是借用了一些聚类算法用于异常点的识别（比如 ，DBSCAN，OPTICS）。但是，基于统计的异常检测算法通常需要假设数据服从特定的概率分布，这个假设往往是不成立的。而聚类的方法通常只能给出 0/1 的判断（即：是不是异常点），不能量化每个数据点的异常程度。相比较而言，基于密度的LOF算法要更简单、直观。它不需要对数据的分布做太多要求，还能量化每个数据点的异常程度（outlierness）。

算法介绍

LOF 是基于密度的算法，其最核心的部分是关于数据点密度的刻画。如果对 distanced-based 或者 density-based 的聚类算法有些印象，你会发现 LOF 中用来定义密度的一些概念似曾相识。了解了这些核心概念，整个算法也就显而易见了。而整个算法，最主要的是下面四个概念：

K-邻近距离（k-distance）：在距离数据点 p 最近的几个点中，第 k 个最近的点跟点 p 之间的距离称为点 p 的 K-邻近距离，记为 k-distance (p) 。

可达距离（rechability distance）：可达距离的定义跟K-邻近距离是相关的，给定参数k时， 数据点 p 到 数据点 o 的可达距离 reach-dist（p, o）为数据点 o 的K-邻近距离 和 数据点p与点o之间的直接距离的最大值。即：

局部可达密度（local rechability density）：局部可达密度的定义是基于可达距离的，对于数据点 p，那些跟点p的距离小于等于 k-distance（p）的数据点称为它的 k-nearest-neighbor，记为 ，数据点 p 的局部可达密度为它与邻近的数据点的平均可达距离的倒数，即：

局部异常因子（local outlier factor）：根据局部可达密度的定义，如果一个数据点跟其他点比较疏远的话，那么显然它的局部可达密度就小。但LOF算法衡量一个数据点的异常程度，并不是看它的绝对局部密度，而是看它跟周围邻近的数据点的相对密度。这样做的好处是可以允许数据分布不均匀、密度不同的情况。局部异常因子即是用局部相对密度来定义的。数据点 p 的局部相对密度（局部异常因子）为点p的邻居们的平均局部可达密度跟数据点p的局部可达密度的比值，即：

了解了 LOF 的定义，整个算法也就显而易见了：

1. 对于每个数据点，计算它与其它所有点的距离，并按从近到远排序；

2. 对于每个数据点，找到它的 k-nearest-neighbor，计算 LOF 得分。

算法应用

LOF算法中关于局部可达密度的定义其实暗含了一个假设，即：不存在大于等于 k 个重复的点。当这样的重复点存在的时候，这些点的平均可达距离为零，局部可达密度就变为无穷大，会给计算带来一些麻烦。在实际应用时，为了避免这样的情况出现，可以把 k-distance 改为 k-distinct-distance，不考虑重复的情况。或者，还可以考虑给可达距离都加一个很小的值，避免可达距离等于零。

LOF 算法需要计算数据点两两之间的距离，造成整个算法时间复杂度为 。为了提高算法效率，后续有算法尝试改进。FastLOF （Goldstein，2012）先将整个数据随机的分成多个子集，然后在每个子集里计算 LOF 值。对于那些 LOF 异常得分小于等于 1 的，从数据集里剔除，剩下的在下一轮寻找更合适的 nearest-neighbor，并更新 LOF 值。这种先将数据粗略分成多个部分，然后根据局部计算结果将数据过滤来减少计算量的想法，并不罕见。比如，为了改进 K-means 的计算效率， Canopy Clustering 算法也采用过比较相似的做法。

异常检测算法（三）：Principal Component Analysis

Principal Component Analysis（PCA）是最常见的数据降维的方法。根据 Wikipedia 的介绍，它最早是由 Karl Pearson（同时也是卡方检验的发明者） 在1901年提出，到现在已经一百多年了。作为一种降维的方法，PCA可以将原数据进行线性变换，并找出数据中信息含量最大的主要成分，去除信息含量较低的成分，从而减少冗余，降低噪音。通常在异常检测的语境里，噪音（noise）、离群点（outlier）和 异常值（anomaly）是同一件事情的不同表述。所以，PCA既然可以识别噪音，自然也可以检测异常。

PCA的相关概念

我们先简单回顾一下 PCA的相关概念。假设原始数据是一个的矩阵，这里m表示数据样本的数量，n表示每一条数据样本的特征数目。一般的，我们先要对原始数据做一些预处理：

1. 中心化：将原始数据每一列进行零均值化，即将该列上的每一个数值都减去该列的均值。

2. 归一化：将中心化之后的数据的每一列进行方差归一化，即将该列上的每一个数值都除以该列的标准差。

上面的两步预处理是通常做法。中心化的主要目的是让后面的公式描述更简洁，并不影响特征值分解。归一化是为了让不同变量的方差变化尺度控制在相同的范围内，消除不同量纲的影响，使得它们更有可比性。我们将预处理之后的矩阵表示为  ，则 PCA 的主要步骤如下：

1. 计算协方差矩阵 

2. 求解协方差矩阵的特征值  和特征向量 

3. 按照特征值从大到小的顺序，将特征向量从左至右排列，将前k个特征向量组成的矩阵表示为 

4. 将  映射到低维的k维空间（  ），则映射之后的数据 

   
   

为了更清楚的理解步骤4里的“映射”操作，我们可以拿单个数据样本  和特征向量  来举例。根据步骤4中的公式，样本  在特征向量  方向上的坐标为  。回想一下关于点乘的几何定义，我们有：

这里  为点乘的两个向量的夹角，这里  是长度为1的单位向量，所以  ，刚好为样本  在特征向量  方向上的投影（坐标）。如果把所有数据点的映射用矩阵的形式表示出来，那就是步骤4的公式了。

我们将原始数据映射到低维空间之后，也可以根据数据在低维空间里的坐标来重构原始数据。PCA的其中一种推导方式就是基于重构误差得到的。假设数据样本  映射到 k 维空间的坐标为  , 则基于该 k 维坐标重构的数据为：

上面的重构公式比较直观，即：重构的数据坐标为数据在低维空间每个方向上的坐标乘以该方向上的单位向量之后的求和。如果把所有数据样本的重构用矩阵的形式表示出来，则：

后面我们在描述PCA用于异常检测的时候还会用到这里的重构公式。

PCA用于异常检测

PCA在异常检测方面的做法，大体有两种思路：一种是将数据映射到低维特征空间，然后在特征空间不同维度上查看每个数据点跟其它数据的偏差；另外一种是将数据映射到低维特征空间，然后由低维特征空间重新映射回原空间，尝试用低维特征重构原始数据，看重构误差的大小。两种思路看似不太一样，其实本质上是差不多的。

我们先来讲讲第一种思路。PCA在做特征值分解之后得到的特征向量反应了原始数据方差变化程度的不同方向，特征值为数据在对应方向上的方差大小。所以，最大特征值对应的特征向量为数据方差最大的方向，最小特征值对应的特征向量为数据方差最小的方向。原始数据在不同方向上的方差变化反应了其内在特点。如果单个数据样本跟整体数据样本表现出的特点不太一致，比如在某些方向上跟其它数据样本偏离较大，可能就表示该数据样本是一个异常点。

对于某一个特征向量  ，数据样本  在该方向上的偏离程度  可以用如下的公式计算：

这里的  主要起归一化的作用，这样可以使得不同方向上的偏离程度具有可比性。在计算了数据样本在所有方向上的偏离程度之后，为了给出一个综合的异常得分，最自然的做法是将样本在所有方向上的偏离程度加起来，即：

这个公式只是计算异常得分的一种方式。也有一些算法采取了略微不同的做法，比如，有的只考虑数据在前 k 个特征向量方向上的偏差，或者只考虑后 r 个特征向量方向上的偏差，即：

主要起归一化的作用，这样可以使得不同方向上的偏离程度具有可比性。在计算了数据样本在所有方向上的偏离程度之后，为了给出一个综合的异常得分，最自然的做法是将样本在所有方向上的偏离程度加起来，即：

这里的  和  是人为设定的两个阈值，如果得分大于阈值则判断为异常。

一般而言，前几个特征向量往往直接对应原始数据里的某几个特征，在前几个特征向量方向上偏差比较大的数据样本，往往就是在原始数据中那几个特征上的极值点。而后几个特征向量有些不同，它们通常表示某几个原始特征的线性组合，线性组合之后的方差比较小反应了这几个特征之间的某种关系。在后几个特征方向上偏差比较大的数据样本，表示它在原始数据里对应的那几个特征上出现了与预计不太一致的情况。到底是考虑全部特征方向上的偏差，前几个特征向量上的偏差，还是后几个特征向量上的偏差，在具体使用时可以根据具体数据灵活处理。

前面提到，PCA用于异常检测时候，还有一种思路是基于重构误差的。直观上理解，PCA提取了数据的主要特征，如果一个数据样本不容易被重构出来，表示这个数据样本的特征跟整体数据样本的特征不一致，那么它显然就是一个异常的样本。对于数据样本  , 假设其基于 k 维特征向量重构的样本为  , 则该数据样本的异常得分可以用如下的公式计算：

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

算法延伸

PCA 是一种线性的数据降维的方法，为了识别一些更为复杂的异常，最自然的做法是应用 kernel PCA。就异常检测的使用方式而言，kernel PCA 并无太大差异，这里就不做赘述。

在深度学习大行其道的今天，另外一种备受关注的数据降维的方法是深度学习中的 Autoencoder。它跟PCA的差别主要是非线性和线性的差别。相信很多人看到前面基于PCA的重构误差进行异常检测时，也意识到了 Autoencoder 也可以以类似的方式做异常检测。而 Autoencoder 有很多种不同的类型，比如 Denoising Autoencoder，Variational Autoencoder 等等，后面我们可以用单独的篇幅再来具体讲解如何用它们来做异常检测。

机器学习-异常检测算法（四）：DAGMM

自编码器（Autoencoder）在异常检测上有很多应用，之前看到 ICLR-2018 的一篇文章《Deep Autoencoding Gaussian Mixture Model for Unsupervised Anomaly Detection》，觉得有些想法有点意思，跟我之前思考过的问题有点相关， 一直想简单介绍一下。

算法核心思想

文章介绍的算法简称 DAGMM，主要的想法跟异常检测算法系列的上一篇文章《机器学习-异常检测算法（三）：Principal Component Analysis》有很大关联。在上一篇文章里，我们提到 PCA 应用于异常检测，大体上有两种套路：（1）将原始数据映射到低维特征空间，然后在低维空间里查看每一个点跟其他数据点的偏离程度；（2）将原始数据映射到低维特征空间，然后由低维特征空间重新映射回原空间，尝试用低维特征重构原始数据，看重构误差的大小。这两个套路反应出这样一个信息：自编码器中间隐藏层特征和最后的重构误差对于识别异常都是有用的。

DAGMM 的作者同样注意到了这个信息，为了形象的说明这点，文章还专门给了一个例子，就是下面这张图：

上图中，横轴是应用自编码器将数据压缩到一维空间的坐标，纵轴是数据点的重构误差。图中蓝色点是正常数据点，红色是异常数据点。显然，从图中我们可以看出，右上角这部分异常数据点可以通过重构误差跟其他点区别开来，而左下角这部分异常点则可以在低维特征空间（这里压缩到了一维）很明显的跟其他点区分开。

DAGMM 算法试图通过一个基于 Autoencoder+“GMM” 的神经网络模型综合考虑上述两方面信息进行异常检测，这里 GMM 是打引号的，原因在下面会解释。

算法步骤简述

DAGMM 的网络结构（如上图）分为两个部分：压缩网络 和 估计网络。压缩网络是一个常规的 autoencoder。通过压缩网络我们可以得到前面提到的两部分关键信息：一个是中间隐藏层特征（低维空间特征信息）Z_c，一个是由输入向量 x 和输出向量 x' 计算得到的重构误差 Z_r（重构误差的信息）。关于重构误差，文章中建议了两种方式来计算，欧式距离和余弦相似度。当我们同时使用这两种方式来计算重构误差的时候，Z_r 就是一个长度为 2 的向量。最后，由压缩网络得到的这两个向量（Z_c 和 Z_r）拼接在一起，作为输入接入到后面的估计网络。

估计网络的部分有点好玩，结构上它只是常规的多层神经网络，但它其实是 GMM（高斯混合模型）的“替代品”，用于模拟 GMM 的结果。具体的，假设 GMM 中 gaussian component 的个数为 k，则估计网络的输出 p 经过 softmax 层可以得到样本分别归属 k 个 component 的概率，即：

得到 N 个样本分别归属不同 component 的概率之后，我们可以用来估计 GMM 的几个重要参数：均值、方差、协方差矩阵。这步跟常规的高斯混合模型的参数更新过程无异。

上述几个参数确定之后，sample energy （也就是样本的 negative log-likelihood）也就很容易计算了：

到这里我们可以看到，估计网络的作用就是模拟 GMM 得到样本归属各个 component 的概率，这部分信息进而用来更新 GMM 的参数，计算得到 sample energy。而 sample energy 是目标函数的一部分，通过优化目标函数，估计网络的参数也会得到更新。

最后补充介绍一下 DAGMM 的目标函数（如下图），总共包含三个部分，第一项为 autoencoder 部分的重构误差，第二部分为高斯混合模型部分（估计网络部分）的 sample energy ，第三项是一个正则项。

第三项的具体计算方式为：

这项的作用是防止 GMM 中的协方差矩阵的对角线上的值变为 0 并最终导致矩阵不可逆。

上面是算法的训练过程，当做预测的时候，可以根据 GMM 输出的概率值来判断样本是否异常，只需要确定一个阈值就可以了。

需要注意的问题

高斯混合模型在实际求解过程中，运行的代码很容易出现奇异矩阵的问题。尽管算法为了防止协方差矩阵不可逆，在目标函数中增加了正则项，但是在代码实际实现过程中还是需要对可能出现奇异矩阵的情况做特别处理，保障算法平稳运行，比如，可以在对角线添加一个极小值之类（光靠这个可能还不够）。这篇文章对这个问题描述的还比较清楚，有兴趣的可以看看：《Regularized Gaussian Covariance Estimation》（https://freemind.pluskid.org/machine-learning/regularized-gaussian-covariance-estimation/）。

基于深度学习的异常检测算法最近几年层出不穷，后面有机会会继续介绍。还有一些经典的算法，也有好玩的地方。比如，之前一直有一个让我很困惑的问题，为什么 One-Class SVM （不是 SVDD）要找一个可以把坐标原点跟其他数据点分隔开的超平面？并且通过这种方式就可以识别异常。这里的“原点”非常奇怪，原文章也没有给任何直观的解释，只说是受 1963 年的一篇老文章的启发，网上也几乎找不到其他人的解释，大部分人只是把这个当作是作者的一个假设（假设坐标原点是唯一的异常点）。这个问题困扰了我好几年，最近突然看到一篇 2014 年的 Paper，完美答疑, 感觉这个也值得写篇文章。

参考文献

1.F. T. Liu, K. M. Ting and Z. H. Zhou，Isolation-based Anomaly Detection，TKDD，2011

2.M. M. Breunig, H. P. Kriegel, R. T. Ng, J. Sander. LOF: Identifying Density-based Local Outliers. SIGMOD, 2000.

3.M. Goldstein. FastLOF: An Expectation-Maximization based Local Outlier detection algorithm. ICPR, 2012

4.Veeramachaneni, K., Arnaldo, I., Korrapati, V., Bassias, C., Li, K.: AI^2 : training a big data machine to defend. In: 2016 IEEE 2nd International Conference on Big Data Security on Cloud (BigDataSecurity), IEEE International Conference on High Performance and Smart Computing (HPSC), and IEEE International Conference on Intelligent Data and Security (IDS), pp. 49–54 (2016)

5.Shyu M L, Chen S C, Sarinnapakorn K, et al. A novel anomaly detection scheme based on principal component classifier. ICDM, 2003.

推荐阅读

• 工业图像异常检测最新研究总结（2019-2020）
  

• 异常检测（Anomaly Detection）综述
  

• 异常检测问题的实际挑战？从自动化颜艺挑选说起

双12极市回馈送你现金红包，领取即可提现，快来！

福利一：邀好友翻倍概率，瓜分现金666元

关注“极市平台”，回复关键词“1212”，参与抽奖即可瓜分666元现金红包。邀请好友参与抽奖助力，抽中概率翻倍！12月12日当天23点自动开奖~

福利二：邀3位好友，即领现金红包

邀请3位好友参与抽奖助力，即可瓜分100元！数量有限，先到先得！

添加极市小助手微信（ID : cvmart2），备注：姓名-学校/公司-研究方向-城市（如：小极-北大-目标检测-深圳），即可申请加入极市目标检测/图像分割/工业检测/人脸/医学影像/3D/SLAM/自动驾驶/超分辨率/姿态估计/ReID/GAN/图像增强/OCR/视频理解等技术交流群：每月大咖直播分享、真实项目需求对接、求职内推、算法竞赛、干货资讯汇总、与 10000+来自港科大、北大、清华、中科院、CMU、腾讯、百度等名校名企视觉开发者互动交流~

△长按添加极市小助手

△长按关注极市平台，获取最新CV干货

觉得有用麻烦给个在看啦~