传统离群点检测

基于统计学

使用统计模型拟合数据。正常对象出现在该随机模型的高概率区域中，而低概率区域中的对象是离群点。

HBOS：基于直方图的异常检测

过程类似于朴素贝叶斯模型。假设特征相互独立，对每个特征作直方图，对于某个样例，连乘其特征在各个直方图中的频率得到该样例的生成概率。

优点

• 速度快，适合大数据情形

缺点

• 特征相互独立的条件比较强，现实中可能不符合
• 不适合异常数据过多的情形

基于聚类

假定正常数据对象属于大的、稠密的簇、而离群点属于小或稀疏的簇，或者不属于任何簇。

聚类方法主要有三种假设，三种假设下有各自的方法。计算复杂度很大程度上取决于聚类算法的计算复杂度。

• 假设一：不属于任何聚类的点是异常点，主要方法包括
  
  DBSCAN
  
  、SNN clustering、FindOut algorithm、WaveCluster Algorithm。
  
  缺点：不能发现异常簇。

• 假设二：距离最近的聚类结果较远的点是异常点，主要方法包括
  
  K-Means
  
  、Self-Organizing Maps（SOM）、GMM。
  
  首先进行聚类，然后计算样例与其所属聚类中心的距离，计算其所属聚类的类内平均距离，用两者的比值衡量异常程度。
  
  缺点：不能发现异常簇。

• 假设三：稀疏聚类和较小的聚类里的点都是异常点，主要方法包括CBLOF、LDCOF、CMGOS等。
  
  首先进行聚类，然后启发式地将聚类簇分成大簇和小簇。如果某一样例属于大簇，则利用该样例和其所属大簇计算异常得分，如果某一样例属于小簇，则利用该样例和距离其最近的大簇计算异常得分。三种算法的区别在于计算异常得分的方式不同。
  
  优点：考虑到了数据全局分布和局部分布的差异，可以发现异常簇。

基于聚类的异常检测优缺点：

优点

• 测试阶段会很快，以内只需要和有限个簇比较
• 有些聚类算法（k-means）可以在线应用（准实时）

缺点

• 异常检测效果很大程度上依赖于聚类效果，但是聚类算法主要目的是聚类，并不是为了异常检测
• 大数据聚类计算开销比较大，可能是个瓶颈

DBSCAN

把点划分为核心点（稠密区域内部点）、边界点（稠密区域边界点）、噪声点，根据密度可达原理来进行cluster划分。

基于分类

对于具有类标签的数据集，可以训练一个区分正常数据和离群点的分类器，通常的做法是构造但分类模型（one class model），如OC-SVM，SVDD。

One-class SVM

利用核函数将数据映射到高维空间，寻找超平面使得数据和坐标原点间隔最大。

SVDD

利用核函数将数据映射到高维空间，寻找尽可能小的超球体包裹住正常数据。

基于邻近性

离群点与它的最近邻之间的邻近性显著地偏离数据集中其他对象与它们的近邻之间的邻近性。按照邻近性度量，主要有基于距离（

KNN

）和基于密度（

LOF

）的离群点检测方法。

基于距离

这种方法认为异常点距离正常点比较远，因此可以对于每一个数据点，计算它的K-近邻距离（或平均距离），并将距离与阈值进行比较。若大于阈值，则认为是异常点。或者是将全部样本的K-近邻距离排序，取前n个最大的作为异常点。计算距离时一般使用欧式距离，也可以使用角度距离。

优点

• 不需要假设数据的分布

缺点

• 不适合高维数据
• 只能找出异常点，无法找出异常簇
• 你每一次计算近邻距离都需要遍历整个数据集，不适合大数据及在线应用
• 有人用hyper-grid技术提速将KNN应用到在线情况，但是还不是足够快
• 参数K和阈值需要人工调参
• 当正常点较少、异常点较多时，该方法不好使

基于密度

优点

• 可以找出分布不均匀的数据中局部异常的数据
• 可以给出数据的异常得分，得分越高越可能异常，不是二分类

缺点

• 不适合高维数据
• 由于需要遍历数据计算距离，因此计算复杂度也很高，不适合在线应用
• 只能找到异常点，无法找出异常簇
• 需要人工调参

LOF

选取参数MinPts:

一般来说，MinPts的取值应该根据具体数据集的特点来确定。以下是一些选择MinPts的方法:

1.根据数据集的密度选择MinPts: 在数据集的密度较大的区域，MinPts可以取较小的值因为在这些区域中，数据点的邻居数量较多。而在密度较小的区域，MinPts应该取较大的值，因为在这些区域中，数据点的邻居数量较少。

2.根据数据集的大小选择MinPts: 如果数据集比较大，则MinPts应该取较大的值，这样可以减少LOF算法的计算量，加快算法的执行速度。如果数据集比较小，则MinPts可以取较小的值，以便更好地探索数据集的结构。

3.根据领域距离选择MinPts: 在实际应用中，可以通过试验不同的MinPts值，比较得到的LOF值来确定最优的MinPts值。也可以利用基于领域距离的方法(如K-D Tree、球树等)来自动确定MinPts的取值。

总之，选择合适的MinPts值需要根据具体的数据集和应用场景来确定，:需要进行实验和调整。

COF

LOF中计算距离是用的欧式距离，也是默认了数据是球状分布，而COF的局部密度是根据最短路径方法求出的，也叫做链式距离。

INFLO

LOF容易将边界处的点判断为异常，INFLO在计算密度时，利用k近邻点和反向近邻集合，改善了LOF的这个缺点。

LoOP

将LOF中计算密度的公式加了平方根，并假设近邻距离的分布符合正态分布。

基于树

此类方法的思想是通过划分子空间寻找异常点，不同的方法区别主要在三个地方：特征的选取、分割点的选取和分类空间打标签的方案。此类方法不受球形邻近的限制，可以划分任意形状的异常点。此类方法主要包括iForest、SCiForest、RRCF

iForest

此方法适用于异常点较少的情况，采用构造多个决策树的方式进行异常检测。对数据集进行有放回抽样，对每一次抽样出来的样本构建二叉树，构建二叉树时，随机选取一个特征，然后在特征上随机选一个分割点，将该特征小于分割点的数据放在二叉树左边，反之放在右边，直至二叉树达到一定深度或者叶子节点只包含一个数据点为止。进行异常检测时，计算该数据点在多个二叉树上的平均深度，深度越浅越可能是异常值。

iForest只适合检测全局异常点，不适合检测局部异常点，因此有人做了改进, 论文为Improving iForest with Relative Mass.

SCiForest

传统iForest方法在选择特征是随机选取的，SCiForest在选择特征时利用了

方差

；传统iForest选择分割点后形成的分割超平面是平行于坐标轴的，SCiForest可以生成

任意角度

的分割超平面。

RRCF

可以动态增删树种的节点，适用于

流数据

异常检测。

基于树的异常检测优缺点：

优点

• 每棵树都是独立构建，适合分布式计算
• 可以分割任意形状的数据集，不受限于球形近邻
• 测试时速度很快，适合在线处理

缺点

• 只适用于异常点较少的情况
• 不适合高维数据，因为高维数据会有很多无关特征

新技术

基于流数据

流数据是实时，动态的数据，自然地以虚列的形式出现。

基于深度学习

无监督

长短期记忆网络（long short term memory network,LSTM）

生成对抗网络（generative adversarial network，GAN）

自动编码器（autoencoder，AE）

对正常数据进行训练Encoder和Decoder，进行异常检测时，如果Decoder出来的向量与原始向量差别很大，就认为是异常数据。

降噪自动编码器（denoising autoeecoder，DAE）

空间变换网络（spatial transformer network，STN）

递归神经网络（recurrent neural network，RNN）

对抗自编码器（adversarial autoeecoder，AAE）

变分自编码器（variational autoencoder，VAE）

部分参考：https://www.jianshu.com/p/c5e4e7dce972