概述
在数据集中，可能会存在少量数据与其它数据“格格不入”，不符合大量数据的规律，这些数据点被称为异常点或离群点。异常检测（Anomaly Detection），又叫做离群点检测（Outlier Detection），便是从数据中找出异常点的过程。异常检测在实际中被广泛应用，例如信用卡欺诈，工业损毁检测，异常图像检测等。
按照目前比较公认的说法，异常点可以分为如下三种类型：
- 单点异常（全局异常）：即某个点与全局大多数点都不一样。就像在一群鱼中混入了一只乌龟，乌龟就可以算作单点异常。
- 上下文异常：这类异常经常出现于时间序列中，即某个时间点的数据与前后差异较大。例如在气温的时序数据中，在前后都是30度的最高气温中突然出现了一天最高气温为0度。
- 集体异常：这类异常是由多个对象组合构成的，就是单独看某个个体可能不存在异常，但是这些个体同时出现就构成了异常。例如某一天一栋楼里面有20户人家同时搬家，这些事件单独看不属于异常，但是合起来便成为了异常事件。
常用的异常检测方法可以分为无监督异常检测、有监督异常检测和半监督异常检测这三种类型，每一类里面又有一些不同的算法，下面将对无监督方法和有监督方法中一些常见的方法进行介绍。需要说明的是，大多数实际的异常检测需要对没有标签的数据集检测异常点，因此无监督的异常检测使用的更多一些。
无监督异常检测
统计检验
概述
统计检验指的是对数据的正常性做出假设，即假定正常的数据对象是由一个统计模型产生的，而不遵守该模型规则的数据便为异常点。因此，这种方法的有效性高度依赖于为数据所假设的统计模型是否成立。根据如何指定和学习模型，基于统计检验的方法又可以分为参数方法和非参数方法。
参数方法
基于正态分布的检验
正态分布为最常见的一种概率分布之一，因此我们可以假设数据服从正态分布，并基于这一假设来检验异常值。但是这属于一种比较强的假设，因此在实际使用时需要首先对数据集的概率密度进行统计分析，如果确实是大致服从正态分布，或者是可以通过某种数学变换将其变为大致服从正态分布，便可以使用这一办法。否则强行使用将会带来较大的误差。
简单起见，我们先以一维的情况说明其原理。给定一组一维数据集\(D=\{x_1,x_2,\dots,x_m\}\)，假设\(D\)中的样本服从正态分布，我们便可以根据最大似然估计法，求出正态分布模型\(p(x)=\frac{1}{\sqrt{2\pi}\sigma}\exp(-\frac{(x-\mu)^2}{\sigma^2})\)的均值和方差： \[ \mu=\frac{1}{m}\sum_{i=1}^{m}x_i \\ \sigma^2=\frac{1}{m}\sum_{i=1}^{m}(x_i-\mu)^2 \] 如果某个样本计算出来的正态分布概率密度小于某个阈值（根据经验选取），则认为它是异常值。比较常用的判别方法是\(3\sigma\)准则，它指的是，如果样本的值落在\([\mu-3\sigma,\mu+3\sigma]\)这个区间之外，则认为该样本为异常值。
这种方法也可以拓展到多维特征的情形。对于多维的数据，我们可以通过极大似然估计，计算出多维正态分布中的均值向量与协方差矩阵，从而得到一个多维正态分布的概率密度表达式。之后，便可以根据设置的概率密度阈值来判断异常点。对于特征之间两两独立的特殊情况，也可以将概率分布密度简单地表示为多个一维高斯分布的乘积。
同样，这种方法也可以拓展到其它类型的概率分布，例如\(t\)分布，\(F\)分布等，判断异常点的方法与正态分布类似。
Grubbs检验
Grubbs检验可以用于检测一维数据是否为异常点。假设数据集\(D=\{x_1,x_2,\dots,x_m\}\)是从正态分布的样本中产生的，对于其中的每一个数据\(x_i\)，我们可以按照如下的公式计算其z-score： \[ z_i=\frac{|\bar{x}-x_i|}{s} \] 其中\(\bar{x}\)代表样本均值，\(s\)代表样本的标准差。
如果一个样本的\(z_i\)满足如下关系： \[ z_i>\frac{N-1}{\sqrt{N}}\sqrt{\frac{t^2_{\alpha/(2N),N-2}}{N-2+t^2_{\alpha/(2N),N-2}}} \] 那么样本\(x_i\)便被认为是异常点。其中\(t_{\alpha/(2N),N-2}\)指的是自由度为\(N-2\)，置信度取\(\alpha/(2N)\)的\(t\)分布所对应的阈值。
而对于多维数据来说，我们可以借助Mahalanobis距离（它反映了样本之间的相似度，相似度越高则Mahalanobis距离越小）来将其转化为一维数据，从而使用Grubbs检验的方法。对于一组多维数据组成的数据集\(D'=\{\boldsymbol{x}_1,\boldsymbol{x}_2,\dots,\boldsymbol{x}_m\}\)，其均值向量为\(\bar{\boldsymbol{x}}\)，协方差矩阵为\(S\)。那么对于一个任意样本\(\boldsymbol{x}\)，它与均值向量\(\bar{\boldsymbol{x}}\)之间的Mahalanobis距离可以通过如下公式计算： \[ \text{MDist}(\boldsymbol{x},\bar{\boldsymbol{x}})=\sqrt{(\boldsymbol{x}-\bar{\boldsymbol{x}})^T S^{-1}(\boldsymbol{x}-\bar{\boldsymbol{x}})} \] 通过计算Mahalanobis距离，我们将原本多维的数据转化为一维数据，之后便可以使用Grubbs检验来判断异常值。
卡方检验
如果我们假设一个多维数据的每个特征都是从独立同分布的正态分布中产生，那么便可以使用卡方检验来检测异常值。对于一组多维数据组成的数据集\(D=\{\boldsymbol{x}_1,\boldsymbol{x}_2,\dots,\boldsymbol{x}_m\}\)，其中\(\boldsymbol{x}_i=\{x_{i1},x_{i2},\dots,x_{in}\}\)。将\(D\)中每个特征的均值记作\(E_i\)，那么样本\(\boldsymbol{x}_i\)的卡方值可以通过如下公式计算： \[ \chi^2(\boldsymbol{x}_i)=\sum_{j=1}^{n}\frac{(x_{ij}-E_j)^2}{E_j} \] 如果计算出的卡方值大于某个阈值，我们便有理由认为它属于异常值。
非参数方法
分位数
对于一维数据且样本量比较大的情况，四分位数可以方便地用来做异常检测。我们将三个四分位数的位置记为\(q_1,q_2,q_3\)，按照Tukey测试的方法，最小估计值可以用\(q_1-k(q_3-q_1)\)计算，而最大估计值为\(q_3+k(q_3-q_1)\)，它们构成了一个正常区间\([q_1-k(q_3-q_1),q_3+k(q_3-q_1)]\)。如果取\(k=1.5\)，那么在这一区间之外的点被认为是中度异常；如果取\(k=3\)，那么这一区间外的点被认为是极度异常点。
PCA
PCA用来做异常检测的思想是假设数据在低维空间有嵌入，如果某个点在低维空间投影之后表现不好，那么便认为它是异常点。因此，我们可以对原始数据做PCA，找到\(k\)个特征向量，并计算每个样本经过这\(k\)个特征向量投影后的重建误差。如果某个数据点计算出的重建误差较大，那么我们便认为它是异常点。
关于PCA重建误差的计算可参考介绍PCA的相关文章。
One-Class SVM
原理
一类支持向量机（One-Class SVM），又称为支持向量数据描述（Support Vector Data Description，SVDD），它的基本思想是对于一个训练集，构造一个最小的超球面，将尽可能多的数据包起来。如果样本落在超球面内，则认为它属于正常点，否则便属于异常点。下面为算法的详细描述。
假设有一个训练数据集\(D=\{\boldsymbol{x}_1,\boldsymbol{x}_2,\dots,\boldsymbol{x}_m\}\)，\(\boldsymbol{x}_i\in R^n\)为一个\(n\)维向量。我们的目标是在\(n\)维空间内寻找一个体积最小的超球体。这对应于如下的优化问题（体积最小其实也是表面积最小，这也就是优化目标中\(R^2\)的来历）： \[ \min_{R,\xi_i}~R^2+C\sum_{i=1}^{n}\xi_i \\ s.t.~||\boldsymbol{x}_i-\boldsymbol{a}||^2\le R^2+\xi_i,\xi_i\ge 0 \] 其中，\(R\)为超球体的半径，\(\boldsymbol{a}\)为超球体的球心，\(\xi_i\)为松弛因子，\(C\)是一个权衡超球体体积和错误分类的惩罚参数。\(C\)的值越大，最终的超球体所包裹的数据点越多。
使用拉格朗日乘子法，可得原始优化问题的对偶问题为： \[ \min_{\alpha_i} \sum_{i=1}^{n}\sum_{j=1}^{n} \alpha_i \alpha_j \boldsymbol{x}_i \boldsymbol{x}_j^T-\sum_{i=1}^{n}\alpha_i\boldsymbol{x}_i \boldsymbol{x}_i^T \\ s.t.~0\le \alpha_i \le C, ~ \sum_{i=1}^{n}\alpha_i=1 \] 其中\(\alpha_i\)是样本\(\boldsymbol{x}_i\)对应的拉格朗日系数，我们把拉格朗日系数满足\(0< \alpha_i <C\)的那些样本称为支持向量，这些支持向量位于超球体的边界处（即球面上）。在求解完上述的对偶问题之后，超球体的球心和半径可以用如下公式计算： \[ \boldsymbol{a}=\sum_{i=1}^{n}\alpha_i\boldsymbol{x}_i \\ R=\sqrt{\boldsymbol{x}_v\boldsymbol{x}_v^T-2\sum_{i=1}^{n}\alpha_i\boldsymbol{x}_v\boldsymbol{x}_i^T+\sum_{i=1}^{n}\sum_{j=1}^{n} \alpha_i \alpha_j \boldsymbol{x}_i \boldsymbol{x}_j^T} \] 其中\(\boldsymbol{x}_v\)为任意一个支持向量。
对于一个测试样本\(\boldsymbol{x}_t\)，它到超球体球心的距离\(d\)可以用如下公式计算： \[ d=\sqrt{\boldsymbol{x}_t\boldsymbol{x}_t^T-2\sum_{i=1}^{n}\alpha_i\boldsymbol{x}_t\boldsymbol{x}_i^T+\sum_{i=1}^{n}\sum_{j=1}^{n} \alpha_i \alpha_j \boldsymbol{x}_i \boldsymbol{x}_j^T} \] 如果\(d\le R\)则说明测试样本在超球体内部，属于正常样本，反之则属于异常样本。
在上述的推导中，对于两向量的内积计算\(\boldsymbol{x}_i \boldsymbol{x}_j^T\)，同样可以像SVM一样使用核函数进行替换，这样便可以在原始特征空间\(R^n\)中形成非球体的分界面。
代码示例
我们使用Sklearn自带的make_blobs函数来人工生成数据，来演示如何使用sklearn中的one-class SVM。给定簇的数量以及每个簇内的元素个数，make_blobs函数会按照多元高斯分布为每一个簇生成数据。其中每个簇的中心可以自己定义，也可以随机生成；每个簇的标准差也可以自己定义或者是全部使用相同的标准差。
我们使用随机生成的簇中心以及标准差来生成6个簇，然后对这些簇使用one-class SVM。
1 | import numpy as np |
1 | x,y=make_blobs( |
1 | from sklearn.svm import OneClassSVM |
OneClassSVM类在初始化时的关键参数有：kernel、degree、gamma、coef0。这四个参数的含义与SVM相同。
为了展示结果，我们在图中使用不同颜色的点来表示模型给出的正常和异常点，同时绘制出了模型给出的异常区间：
1 | def plot_od(fig,axes,x): |
1 | fig=plt.figure(figsize=(6,4)) |
孤立森林
原理
孤立森林（Isolation Forest）算法是一种适用于连续数据的无监督异常检测方法。这一算法通过递归地随机分割数据集，直到所有的样本点都是孤立的。而在这一策略下，密度很高的簇通常需要被切很多次才能被孤立，而密度很低的点则很容易被孤立。因此在最终得到的孤立树中，异常点所在的叶结点与根节点的距离通常较短。
正如名字所述，孤立森林是由一系列的孤立树所组成的集成模型。对于一个数据集\(D=\{\boldsymbol{x}_1,\boldsymbol{x}_2,\dots,\boldsymbol{x}_m\},x_i\in R^n\)，孤立树的构造算法如下：
- 初始时，孤立树只有一个根节点，其中包含了整个数据集\(D\)；
- 对孤立树的每个叶结点做以下操作，直到树的高度达到最大值或者是叶结点中只含有一个数据：
- 从所有特征中任选一个特征\(q\)；
- 找出当前叶节点所包含的数据中，特征\(q\)的最小值\(q_{\min}\)和\(q_{\max}\)，然后从区间\([q_{\min},q_{\max}]\)中随机选取一个点\(p\)作为分割点；
- 从当前结点生成两个新的子结点，并根据找出的分割点，将特征\(q\)的值小于分割点\(p\)的样本（即\(x_{iq}<p\)的样本）分到左子结点，其余样本分到右子结点。
大部分的异常检测算法通常都期望具有较多的数据，但是对于孤立树来说，小规模的数据集往往可以起到更好的效果。因为根据孤立树的构造原理，如果样本数较多，则需要多次拆分才能将数据分隔开，从而降低了孤立树孤立异常点的能力。因此在构造孤立森林的时候，通常使用下采样的方式来控制数据量，然后使用采样得到的小规模样本去训练孤立树。
在评估阶段，我们需要计算测试样本的异常分数。我们定义函数\(h(\boldsymbol{x})\)代表样本点\(\boldsymbol{x}\)从孤立树的根结点到叶结点所经过边的数量，\(m\)代表用于构造孤立树的样本数量（为了计算简便，我们假定构造孤立森林中的每一棵孤立树时，使用的是相同大小的训练集），其异常分数的计算公式为： \[ s(\boldsymbol{x},m)=2^{-{E[h(\boldsymbol{x})]}/{c(m)}} \] 其中\(E[h(\boldsymbol{x})]\)代表期望路径长度（即样本在孤立森林中的平均路径长度）；\(c(m)\)代表样本数为\(m\)时，路径长度的平均值，\(c(m)=2H(m-1)-2\frac{m-1}{m}\)，\(H(m-1)=\sum_{k=1}^{m-1}\frac{1}{k}\approx \ln(m-1)+0.5772156649\)。异常得分越接近于1，则越可能是异常点，而异常点和非异常点之间的阈值则需要自己设定。
代码示例
我们同样使用Sklearn自带的make_blobs函数来人工生成数据，来演示如何使用sklearn中的孤立森林。
1 | from sklearn.ensemble import IsolationForest |
IsolationForest类在初始化时的关键参数有：
- n_estimators：孤立森林包含多少棵孤立树，默认为100
- max_samples：训练每棵树使用的最大样本数，默认为'auto'；也可以传入一个整数，代表具体数量；或是传入一个浮点数，代表比例
- contamination：判断异常点的阈值，应传入一个[0,0.5]的浮点数。默认为0.5
- max_features：最大特征数，可以传入一个整数或者浮点数。默认为1.0，即使用全部特征
- boostrap：是否使用有放回的采样方式，默认为False
为了展示结果，我们在图中使用不同颜色的点来表示模型给出的正常和异常点，同时绘制出了模型给出的异常区间：
1 | def plot_od(fig,axes,x,contamination_value): |
1 | fig=plt.figure(figsize=(18,4)) |
聚类
通过聚类也可以找出异常点。例如DBSCAN算法在对所有的结点做密度聚类之后可能会剩下个别点，而这些点便被视作是异常点，因为在它周围的数据密度过小。详细参考介绍聚类的相关文章。
局部异常因子
原理
局部异常因子（Local Outlier Factor）算法的思想是通过对比样本点的局部密度与其邻居的局部密度来寻找异常点。对于每个样本来说，都可以为其计算出一个局部异常因子的值，它相当于每个样本的异常分数，可以反映样本相对于周围邻域的隔离程度。数据点\(p\)的局部异常因子的计算公式为： \[ \text{LOF}_k(p)=\frac{\sum_{o\in N_k(p)}\text{lrd}_k(o)}{|N_k(p)|\cdot\text{lrd}_k(p)} \] 下面详细说明这一公式中不同符号的含义。
\(N_k(p)\)指的是\(p\)点的第\(k\)距离邻域，也就是\(p\)的第\(k\)距离（\(p\)与跟它第\(k\)远的点之间的距离，与K近邻中的概念相同）以内的所有点，包括距离第\(k\)近的点在内。可以理解为以\(p\)为圆心，以第\(k\)距离为半径做一个超球体，除\(p\)以外所有落在球内及球上的点都为\(p\)点的第\(k\)距离邻域。由于可能会存在多个距离第\(k\)近的点，因此\(|N_k(p)|\ge k\)。
\(\text{lrd}_k(p)\)指的是点\(p\)在第\(k\)距离下的局部可达密度，它的计算公式为： \[ \text{lrd}_k(p)=1/\left( \frac{\sum_{o\in N_k(p)}\text{reach-distance}_k(p,o)}{|N_k(p)|} \right) \] 其中\(\text{reach-distance}_k(p,o)\)指的是点\(o\)到点\(p\)的第\(k\)可达距离，它的计算公式为\(\text{reach-distance}_k(p,o)=\max \{\text{k-dist}(o),\text{dist}(p,o)\}\)，即点\(o\)的第\(k\)距离与\(o,p\)两点之间真实距离中的最大值。\(\text{lrd}_k(p)\)的值越高，说明\(p\)与其周围的邻域点越可能属于同一簇。
LOF的值反映了邻域点\(N_k(p)\)的局部可达密度与点\(p\)的局部可达密度之比的平均数。这个比值越大，则说明\(p\)与其邻域点的密度相差越大，也就是\(p\)的局部可达密度小于其邻域点的局部可达密度，\(p\)也就越可能是异常点。
代码示例
同样地，我们使用Sklearn自带的make_blobs函数来人工生成数据，来演示如何使用sklearn中的局部异常因子模型。LocalOutlierFactor类在初始化时的关键参数有：
- n_neighbors：算法考虑样本的多少个邻居，默认为20
- metric：计算样本之间距离的方式，默认为闵氏距离
- p：闵氏距离的指数项
- contamination：异常检测的阈值，默认为'auto'，可以手动设为[0,0.5]之间的浮点数
为了展示结果，我们在图中使用不同颜色的点来表示模型给出的正常和异常点，同时绘制出了模型给出的异常区间：
1 | def plot_od(fig,axes,x,neighbors): |
1 | fig=plt.figure(figsize=(18,4)) |
自编码器
自编码器的encoder尝试生成数据的一个压缩表示，而decoder则尝试从压缩表示重建原始输入。在训练过程中，由于使用了大量的正常样本，因此模型可以充分学到正常样本的压缩表示与还原。但是对于异常样本不同于正常样本的分布，因此自编码器在通过压缩向量重建的时候，便很难将异常样本较好地还原出来，也就是说重建误差较大。
根据这一原理，我们可以通过重建误差来检测异常点，这与PCA做异常检测的原理类似。关于自编码器的详细介绍参考相关文章，此处不再赘述。
有监督异常检测
对于有监督的异常检测，可以将其看作是数据不平衡条件下的分类问题。也就是不同类别的样本数量相差过大（比如正常样本有10000条，异常样本只有100条），医疗数据、网络非法访问数据等都比较容易出现这种情况。大多数机器学习模型在碰到样本不均衡的数据集时都会出现性能的下降。为了解决这一问题，从数据集或者模型这两种不同角度出发也有着不同的解决方案。
数据集的处理
重采样
重采样指的是使用不均衡的数据集来建立一个平衡数据集，常用的有以下几种方式：
减少丰富类别的数据量（欠采样），当数据量足够的时候就可以采用这种办法。欠采样将所有的稀有类别样本保存下来，然后从丰富类别样本中随机选择与稀有类别样本数量相近的样本，这样便获得了一个平衡的数据集。
增加稀有类别的数据量（过采样），当数据量不足时便可以考虑这种方法。要增加稀有类别的数据，可以通过简单的重复采样来实现，但是这样并未给稀有类别样本带来额外信息，容易造成过拟合。为了解决这一问题，一种改进思路是给少数类样本加入微小的扰动；另一种方式是使用SMOTE算法进行过采样，这一方法利用了稀有类别样本的相似性来生成新样本，它从一个稀有类别样本的\(k\)个近邻的同类样本中随机选择一个，然后在二者的连线上随机选择一点作为新生成的数据，如下图所示：
![img]()
SMOTE算法可能会生成一些没有提供有益信息的样本，为了解决这一问题，在SMOTE的基础上提出了Borderline-SMOTE和ADASYN这两种改进方法，详情可以参考https://blog.csdn.net/u010654299/article/details/103980964。
如果要训练多个模型来构造集成模型，我们可以为这些模型构造不同的重采样数据集。设数据集\(D\)中的丰富类别样本为\(D_m\)，稀有类别样本为\(D_r\)，我们可以将\(D_m\)分成\(k\)个子集\(D_m=\{D_{m1},D_{m2},\dots,D_{mk}\}\)（子集中的样本可以有交集），然后拿其中的每一个子集\(D_{mi}\)与\(D_r\)组成新的数据集\(D_{i}'=D_{mi}\cup D_r,i=1,2,\dots,k\)。这样我们便得到了\(k\)个均衡的数据集用于训练模型。这一过程可以总结为下图：
![img]()
在构造集成模型时，也可以使用类别比例不同的数据集分别训练模型。例如我们可以分别重采样得到类别比例为1:1，2:1，1:2等的新数据集，用于训练模型。
聚类
除了欠采样之外，另一种减少丰富类别数据量的方法是使用K-means聚类。这种方法对所有的丰富类别样本进行聚类操作，聚类簇数设置为与稀有类别样本接近。在聚类完成之后，只取聚类中心作为丰富类别的样本，然后与稀有类别的所有样本组合成新的数据集。这种办法可以理解为在减少丰富类别样本的同时，尽可能地保留样本的有用信息。
模型的处理
问题转化
在二分类问题中，如果正负样本分布比例极其不均衡，此时我们完全可以从另一个角度去看待这一问题：将其看作一分类或者异常检测问题。此时的目标是对丰富类样本进行建模，从而能够使得模型能够从样本中识别出属于丰富类别的数据，而无法被识别为丰富类别的样本即可看作是稀有类别。
设置权重
在模型训练中，我们可以为稀有类别的样本设置更高的权重，这样可以使得分类器在学习的过程中更加关注于稀有类别样本的预测结果。这种方式其实类似于对稀有类别样本进行简单重复采样。
一些算法会为样本直接设置权重，例如决策树；而还有一些算法是通过在损失函数中为不同类别的样本设置不同的惩罚系数，或者调整分类的阈值来间接地为样本设置权重，例如SVM、逻辑回归、神经网络等模型。
实践
Python的imblearn函数库提供了一些用于处理不均衡样本的函数，以及一些专门用于不均衡样本训练的模型。在处理不均衡样本的时候可以使用。详细的使用方式可以参考：https://imbalanced-learn.org/stable/index.html#
参考
- https://www.zhihu.com/question/280696035
- https://zhuanlan.zhihu.com/p/30169110
- https://zhuanlan.zhihu.com/p/83601244
- https://blog.csdn.net/ljzology/article/details/80407704
- https://blog.csdn.net/anshuai_aw1/article/details/82735201
- https://zhuanlan.zhihu.com/p/97522759
- https://blog.csdn.net/extremebingo/article/details/80108247
- https://blog.csdn.net/bbbeoy/article/details/79159652
- https://blog.csdn.net/wangyibo0201/article/details/51705966
- https://www.jianshu.com/p/71eea3555dbf
- https://blog.csdn.net/jiede1/article/details/70215477
- https://blog.csdn.net/weixin_42462804/article/details/99821091
- https://blog.csdn.net/u010654299/article/details/103980964
- https://imbalanced-learn.org/stable/index.html#