收藏！14 种异常检测方法总结

,本文收集整理了公开网络上一些常见的异常检测方法（附资料来源和代码）。,,基于正态分布，3sigma准则认为超过3sigma的数据为异常点。,,图1: 3sigma,Z-score为标准分数，测量数据点和平均值的距离，若A与平均值相差2个标准差，Z-score为2。当把Z-score=3作为阈值去剔除异常点时，便相当于3sigma。,箱线图时基于四分位距（IQR）找异常点的。,图2: boxplot,资料来源：,Grubbs’Test为一种假设检验的方法，常被用来检验服从正态分布的单变量数据集（univariate data set）Y中的单个异常值。若有异常值，则其必为数据集中的最大值或最小值。原假设与备择假设如下：,使用Grubbs测试需要总体是正态分布的。,算法流程：,1. 样本从小到大排序,2. 求样本的mean和dev,3. 计算min/max与mean的差距，更大的那个为可疑值,4. 求可疑值的z-score (standard score)，如果大于Grubbs临界值，那么就是outlierGrubbs临界值可以查表得到，它由两个值决定：检出水平α（越严格越小），样本数量n，排除outlier，对剩余序列循环做 1-4 步骤 [1]。详细计算样例可以参考。,局限：,1、只能检测单维度数据,2、无法精确的输出正常区间,3、它的判断机制是“逐一剔除”，所以每个异常值都要单独计算整个步骤，数据量大吃不消。,4、需假定数据服从正态分布或近正态分布,资料来源：,依次计算每个样本点与它最近的K个样本的平均距离，再利用计算的距离与阈值进行比较，如果大于阈值，则认为是异常点。优点是不需要假设数据的分布，缺点是仅可以找出全局异常点，无法找到局部异常点。,资料来源：,LOF是基于密度的经典算法（Breuning et. al. 2000），通过给每个数据点都分配一个依赖于邻域密度的离群因子 LOF，进而判断该数据点是否为离群点。它的好处在于可以量化每个数据点的异常程度（outlierness）。,,图3：LOF异常检测,数据点 的局部相对密度（局部异常因子）为点 邻域内点的平均局部可达密度跟数据 点 的局部可达密度的比值, 即：,,数据点P的局部可达密度=P最近邻的平均可达距离的倒数。距离越大，密度越小。,,点P到点O的第k可达距离=max(点O的k近邻距离，点P到点O的距离)。,,,图4：可达距离,点O的k近邻距离=第k个最近的点跟点O之间的距离。整体来说，LOF算法流程如下：,资料来源：,COF是LOF的变种，相比于LOF，COF可以处理低密度下的异常值，COF的局部密度是基于平均链式距离计算得到。在一开始的时候我们一样会先计算出每个点的k-nearest neighbor。而接下来我们会计算每个点的Set based nearest Path，如下图：,,图5：Set based nearest Path,假使我们今天我们的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={e1, e2, e3,…,ek}，依照上面的例子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后，我们就可以计算COF：,,资料来源：,将特征矩阵（feature martrix）或者相异度矩阵（dissimilarity matrix）输入给SOS算法，会返回一个异常概率值向量（每个点对应一个）。SOS的思想是：当一个点和其它所有点的关联度（affinity）都很小的时候，它就是一个异常点。,,图6：SOS计算流程,SOS的流程：,相异度矩阵D是各样本两两之间的度量距离, 比如欧式距离或汉明距离等。关联度矩阵反映的是 度量距离方差, 如图7, 点 的密度最大, 方差最小; 的密度最小, 方差最大。而关联概率 矩阵 (binding probability matrix)就是把关联矩阵(affinity matrix)按行归一化得到的, 如图 8 所 示。,,图7：关联度矩阵中密度可视化,,图8：关联概率矩阵,得到了binding probability matrix，每个点的异常概率值就用如下的公式计算，当一个点和其它所有点的关联度（affinity）都很小的时候，它就是一个异常点。,,DBSCAN算法（Density-Based Spatial Clustering of Applications with Noise）的输入和输出如下，对于无法形成聚类簇的孤立点，即为异常点（噪声点）。,,图9：DBSCAN,处理流程如下：,资料来源：,孤立森林中的 “孤立” (isolation) 指的是 “把异常点从所有样本中孤立出来”，论文中的原文是 “separating an instance from the rest of the instances”。我们用一个随机超平面对一个数据空间进行切割，切一次可以生成两个子空间。接下来，我们再继续随机选取超平面，来切割第一步得到的两个子空间，以此循环下去，直到每子空间里面只包含一个数据点为止。我们可以发现，那些密度很高的簇要被切很多次才会停止切割，即每个点都单独存在于一个子空间内，但那些分布稀疏的点，大都很早就停到一个子空间内了。所以，整个孤立森林的算法思想：异常样本更容易快速落入叶子结点或者说，异常样本在决策树上，距离根节点更近。随机选择m个特征，通过在所选特征的最大值和最小值之间随机选择一个值来分割数据点。观察值的划分递归地重复，直到所有的观察值被孤立。,图10：孤立森林,获得 t 个孤立树后，单棵树的训练就结束了。接下来就可以用生成的孤立树来评估测试数据了，即计算异常分数 s。对于每个样本 x，需要对其综合计算每棵树的结果，通过下面的公式计算异常得分：,指数部分值域为(−∞,0)，因此s值域为(0,1)。当PathLength越小，s越接近1，此时样本为异常值的概率越大。,资料来源：,PCA在异常检测方面的做法，大体有两种思路：(1) 将数据映射到低维特征空间，然后在特征空间不同维度上查看每个数据点跟其它数据的偏差；(2) 将数据映射到低维特征空间，然后由低维特征空间重新映射回原空间，尝试用低维特征重构原始数据，看重构误差的大小。PCA在做特征值分解，会得到：,所以，最大特征值对应的特征向量为数据方差最大的方向，最小特征值对应的特征向量为数据方差最小的方向。原始数据在不同方向上的方差变化反应了其内在特点。如果单个数据样本跟整体数据样本表现出的特点不太一致，比如在某些方向上跟其它数据样本偏离较大，可能就表示该数据样本是一个异常点。,,在计算异常分数时，关于特征向量（即度量异常用的标杆）选择又有两种方式：,,得分大于阈值C则判断为异常。,第二种做法，PCA提取了数据的主要特征，如果一个数据样本不容易被重构出来，表示这个数据样本的特征跟整体数据样本的特征不一致，那么它显然就是一个异常的样本：,,基于低维特征进行数据样本的重构时，舍弃了较小的特征值对应的特征向量方向上的信息。换一句话说，重构误差其实主要来自较小的特征值对应的特征向量方向上的信息。基于这个直观的理解，PCA在异常检测上的两种不同思路都会特别关注较小的特征值对应的特征向量。所以，我们说PCA在做异常检测时候的两种思路本质上是相似的，当然第一种方法还可以关注较大特征值对应的特征向量。,资料来源：,PCA是线性降维，AutoEncoder是非线性降维。根据正常数据训练出来的AutoEncoder，能够将正常样本重建还原，但是却无法将异于正常分布的数据点较好地还原，导致还原误差较大。因此如果一个新样本被编码，解码之后，它的误差超出正常数据编码和解码后的误差范围，则视作为异常数据。需要注意的是，AutoEncoder训练使用的数据是正常数据（即无异常值），这样才能得到重构后误差分布范围是多少以内是合理正常的。所以AutoEncoder在这里做异常检测时，算是一种有监督学习的方法。,图11：自编码器,资料来源：,One-Class SVM，这个算法的思路非常简单，就是寻找一个超平面将样本中的正例圈出来，预测就是用这个超平面做决策，在圈内的样本就认为是正样本，在圈外的样本是负样本，用在异常检测中，负样本可看作异常样本。它属于无监督学习，所以不需要标签。,,图12：One-Class SVMOne-Class,SVM又一种推导方式是SVDD（Support Vector Domain Description，支持向量域描述），对于SVDD来说，我们期望所有不是异常的样本都是正类别，同时它采用一个超球体，而不是一个超平面来做划分，该算法在特征空间中获得数据周围的球形边界，期望最小化这个超球体的体积，从而最小化异常点数据的影响。,假设产生的超球体参数为中心 o 和对应的超球体半径r>0，超球体体积V(r)被最小化，中心o是支持行了的线性组合；跟传统SVM方法相似，可以要求所有训练数据点xi到中心的距离严格小于r。但是同时构造一个惩罚系数为C的松弛变量 ζi，优化问题入下所示：,,C是调节松弛变量的影响大小，说的通俗一点就是，给那些需要松弛的数据点多少松弛空间，如果C比较小，会给离群点较大的弹性，使得它们可以不被包含进超球体。详细推导过程参考资料[15] [16]。,资料来源：,对于单条时序数据，根据其预测出来的时序曲线和真实的数据相比，求出每个点的残差，并对残差序列建模，利用KSigma或者分位数等方法便可以进行异常检测。具体的流程如下：,图13：基于预测的方法,异常检测方法总结如下：,,参考资料,​[1] 时序预测竞赛之异常检测算法综述 ,- 鱼遇雨欲语与余，知乎：,https://zhuanlan.zhihu.com/p/336944097,[2] 剔除异常值栅格计算器_数据分析师所需的统计学：,异常检测 - weixin_39974030，CSDN：,https://blog.csdn.net/weixin_39974030/article/details/112569610,[3] 异常检测算法之(KNN)-K Nearest Neighbors ,- 小伍哥聊风控，知乎：,https://zhuanlan.zhihu.com/p/501691799,[4] 一文读懂异常检测 LOF 算法（Python代码）,- 东哥起飞，知乎：,https://zhuanlan.zhihu.com/p/448276009,[5] Nowak-Brzezińska, A., & Horyń, C. (2020). Outliers in rules-the comparision of LOF, COF and KMEANS algorithms. ,*Procedia Computer Science*, *176*, 1420-1429.,[6] 機器學習_學習筆記系列(98)：,基於連接異常因子分析(Connectivity-Based Outlier Factor)  ,- 劉智皓 (Chih-Hao Liu),[7] 异常检测之SOS算法 - 呼广跃，知乎：,https://zhuanlan.zhihu.com/p/34438518,[8] 异常检测算法 -- 孤立森林（Isolation Forest）剖析 ,- 风控大鱼，知乎：,https://zhuanlan.zhihu.com/p/74508141,[9] 孤立森林(isolation Forest)-一个通过瞎几把乱分进行异常检测的算法 ,- 小伍哥聊风控，知乎：,https://zhuanlan.zhihu.com/p/484495545,[10] 孤立森林阅读 - Mark_Aussie，博文：,https://blog.csdn.net/MarkAustralia/article/details/12018189,[11] 机器学习-异常检测算法（三）：,Principal Component Analysis - 刘腾飞，知乎：,https://zhuanlan.zhihu.com/p/29091645,[12] Anomaly Detection异常检测--PCA算法的实现 ,- CC思SS，知乎：,https://zhuanlan.zhihu.com/p/48110105,[13] 利用Autoencoder进行无监督异常检测(Python) ,- SofaSofa.io，知乎：,https://zhuanlan.zhihu.com/p/46188296,[14] 自编码器AutoEncoder解决异常检测问题,（手把手写代码） - 数据如琥珀，知乎：,https://zhuanlan.zhihu.com/p/260882741,[15] Python机器学习笔记：,One Class SVM - zoukankan，博文：,http://t.zoukankan.com/wj-1314-p-10701708.html,[16] 单类SVM: SVDD - 张义策，知乎：,https://zhuanlan.zhihu.com/p/65617987[17] 
,[17]【TS技术课堂】时间序列异常检测 - 时序人，文章：,https://mp.weixin.qq.com/s/9TimTB_ccPsme2MNPuy6uA