2-1 异常检测（Anomaly detection）方法小结

  异常检测技术被广泛应用到各个应用领域之中，包括疾病检测、金融欺诈检测、网络入侵检测等。在智能运维领域，异常检测处理的数据类型主要是时间序列数据（KPI序列）和文本数据（日志），处理方法主要有基于规则处理、基于统计学处理和基于机器学习处理，在机器学习处理方法中，根据数据的标签情况，又分为有监督、半监督和无监督三种情况。
  异常数据主要包括三类：异常点、背景异常、群体异常。异常点是最常见的一种。背景异常是指，在特定的背景下是异常数据，在其他背景下不是异常数据。群体异常是指，某个群体内的单个数据不像是异常的，但这个群体在整个数据集中是异常的。
  文章首先按照基于规则、基于统计、基于机器学习三个方向对异常检测算法做了总结，然后又分高维数据、时间序列数据和文本数据三部分做了介绍，最后总结了下常用算法的优缺点以及相应的参考文献。重点部分和重点论文已用黑体加粗。

一、基于规则处理

  这种方法第一步需要获取规则，主要有两种方法，一是设计算法自动提取，二是专家手工制定。第二步是判断行为是否和异常规则相似。
  优点：可以精准找出符合规则的异常
  缺点：受限于专家知识，规则库可能不完善；
    规则库需要经常更新，否则无法发现新的异常种类；
    在将行为和规则库对比时，会花费一些时间（取决于规则库的大小）。

二、基于统计学处理

  需要假设数据服从某种分布，然后利用数据去进行参数估计。
  方法主要三种，简单的比如有3σ准则、箱型图、Grubbs检验等。复杂点的比如有时间序列建模（移动平均、指数平滑、ARMA、ARIMA）。还有混合方法，假设正常数据和异常数据来自不同的高斯分布，然后用Grubbs检验；或者仅对正常数据进行混合高斯建模或者泊松建模等等。
  优点：适合低维数据、鲁棒性较好
  缺点：对假设依赖比较严重

三、基于机器学习处理

  无监督：无标注，假设数据中正常数据比异常数据多很多。常用方法分为基于统计分布、基于距离、基于密度、基于距离、基于聚类和基于树的五类方法。
  半监督：被标注的全是正常数据。常用方法包括one-class SVM、AutoEncoder、GMM等。
  有监督：数据标注是个问题，并且处理时需要注意类别不均衡现象，不适用于检测新类别。常用方法包括LR、SVM、RF、NN等。

3.1 无监督方法

  在实际应用场景中，数据大多是没有标签的，因此无监督方法是实际应用中使用最广泛的方法。

3.1.1 基于统计分布

HBOS：基于直方图的异常检测
  过程类似于朴素贝叶斯模型。假设特征相互独立，对每个特征作直方图，对于某个样例，连乘其特征在各个直方图中的频率得到该样例的生成概率。
  优点：
    速度快，适合大数据情形
  缺点：
    特征相互独立的条件比较强，现实中可能不符合
    不适合异常数据过多的情形

3.1.2 基于距离（KNN）

  这种方法认为异常点距离正常点比较远，因此可以对于每一个数据点，计算它的K-近邻距离（或平均距离），并将距离与阈值进行比较。若大于阈值，则认为是异常点。或者是将全部样本的K-近邻距离排序，取前n个最大的作为异常点。计算距离时一般使用欧式距离，也可以使用角度距离。
基于距离的异常检测优缺点
  优点：
    不需要假设数据的分布
  缺点：
    不适合高维数据
    只能找出异常点，无法找出异常簇
    你每一次计算近邻距离都需要遍历整个数据集，不适合大数据及在线应用
    有人用hyper-grid技术提速将KNN应用到在线情况，但是还不是足够快
    参数K和阈值需要人工调参
    当正常点较少、异常点较多时，该方法不好使
    当使用欧式距离时，即默认是假设数据是球状分布，因此在边界处不容易识别异常
    仅可以找出全局异常点，无法找到局部异常点

3.1.3 基于密度（KNN）

  基于距离的方法中，阈值是一个固定值，属于全局性方法。但是有的数据集数据分布不均匀，有的地方比较稠密，有的地方比较稀疏，这就可能导致阈值难以确定（稠密的地方和稀疏的地方最好不用同一阈值）。我们需要根据样本点的局部密度信息去判断异常情况。基于密度的方法主要有LOF、COF、ODIN、MDEF、INFLO、LoOP、LOCI、aLOCI等。
LOF
  首先对于每一个数据点，找出它的K个近邻，然后计算LOF得分，得分越高越可能是异常点。
  LOF是一个比值，分子是K个近邻的平均局部可达密度，分母是该数据点的局部可达密度。可达密度是一个比值，分子是K-近邻的个数，分母是K-近邻可达距离之和。A到B的可达距离定义：A和B的真实距离与B的k-近邻距离的最大值。
COF
  LOF中计算距离是用的欧式距离，也是默认了数据是球状分布，而COF的局部密度是根据最短路径方法求出的，也叫做链式距离。
INFLO
  LOF容易将边界处的点判断为异常，INFLO在计算密度时，利用k近邻点和反向近邻集合，改善了LOF的这个缺点。
LoOP
  将LOF中计算密度的公式加了平方根，并假设近邻距离的分布符合正态分布。
  其他算法具体细节还没有看。
基于密度的异常检测优缺点
优点：
  可以找出分布不均匀的数据中局部异常的数据
  可以给出数据的异常得分，得分越高越可能异常，不是二分类
缺点：
  不适合高维数据
  由于需要遍历数据计算距离，因此计算复杂度也很高，不适合在线应用
  只能找到异常点，无法找出异常簇
  需要人工调参

3.1.4 基于聚类

  此类方法主要有三种假设，三种假设下有各自的方法。计算复杂度很大程度上取决于聚类算法的计算复杂度。
  假设一：不属于任何聚类的点是异常点，主要方法包括DBSCAN、SNN clustering、FindOut algorithm、WaveCluster Algorithm。
  缺点：不能发现异常簇

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

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

基于聚类的异常检测优缺点：
  优点：
    测试阶段会很快，以内只需要和有限个簇比较
    有些聚类算法（k-means）可以在线应用（准实时）
  缺点：
    异常检测效果很大程度上依赖于聚类效果，但是聚类算法主要目的是聚类，并不是为了异常检测
    大数据聚类计算开销比较大，可能是个瓶颈

3.1.5 基于树

  此类方法的思想是通过划分子空间寻找异常点，不同的方法区别主要在三个地方：特征的选取、分割点的选取和分类空间打标签的方案。此类方法不受球形邻近的限制，可以划分任意形状的异常点。此类方法主要包括iForest、SCiForest、RRCF
iForest
  此方法适用于异常点较少的情况，采用构造多个决策树的方式进行异常检测。对数据集进行有放回抽样，对每一次抽样出来的样本构建二叉树，构建二叉树时，随机选取一个特征，然后在特征上随机选一个分割点，将该特征小于分割点的数据放在二叉树左边，反之放在右边，直至二叉树达到一定深度或者叶子节点只包含一个数据点为止。进行异常检测时，计算该数据点在多个二叉树上的平均深度，深度越浅越可能是异常值。
  iForest只适合检测全局异常点，不适合检测局部异常点，因此有人做了改进, 论文为Improving iForest with Relative Mass.
SCiForest
  传统iForest方法在选择特征是随机选取的，SCiForest在选择特征时利用了方差；传统iForest选择分割点后形成的分割超平面是平行于坐标轴的，SCiForest可以生成任意角度的分割超平面。
RRCF
  可以动态增删树种的节点，适用于流数据异常检测

基于树的异常检测优缺点：
  优点：
    每棵树都是独立构建，适合分布式计算
    可以分割任意形状的数据集，不受限于球形近邻
    测试时速度很快，适合在线处理
  缺点：
    只适用于异常点较少的情况
    不适合高维数据，因为高维数据会有很多无关特征

3.2 半监督方法

  此类方法适用于标注的数据全都是正常数据，常用方法有one-class SVM、SVDD、AutoEncoder、GMM、Naïve Bayes等。此类方法与无监督方法有些重合，因为无监督方法的基本假设就是数据集中正常数据远远多于异常数据。
One-class SVM
  利用核函数将数据映射到高维空间，寻找超平面使得数据和坐标原点间隔最大
SVDD
  利用核函数将数据映射到高维空间，寻找尽可能小的超球体包裹住正常数据。
AutoEncoder
  对正常数据进行训练Encoder和Decoder，进行异常检测时，如果Decoder出来的向量与原始向量差别很大，就认为是异常数据。
GMM
  对正常数据进行高斯混合模型建模，最大似然估计参数。进行异常检测时，将其特征带入模型，可得出它属于正常数据的概率。
Naïve Bayes
  过程同高斯混合模型。

3.3 有监督方法

  常规分类器都可以使用，需要注意样本不均衡问题。通常情况下，异常样本会远远小于正常样本，因此需要处理样本不均衡问题，比如上采样、下采样、调整阈值等等。评估时需要靠precision和recall，而不是accuracy。

四、数据类型

4.1. 高维数据

  在高维数据中，传统的异常数据的定义不能再使用，利用上述方法在高维空间中直接寻找异常点效果也不好。常用的方法是使用降维技术，在降维后的子空间里寻找异常点。常用的降维技术有PCA、kernal PCA、AutoEncoder、深度信念网络等，其中深度信念网络效果是相对比较好的。

4.2. 时间序列数据

  这种情况往往属于有监督类型。处理时间序列数据时，常常是利用一些统计方法构造特征，然后利用分类器进行分类。构造特征的方法包括移动平均、指数平滑等时间序列相关知识。

4.3. 文本数据

  基于日志的异常检测通常包括三类：基于规则、有监督和无监督。
  基于规则的方法需要人工制定规则，优缺点前面已说到。
  有监督方法是常规的二分类任务，同样有样本不均衡问题。
  无监督方法中，传统是首先解析出日志模板，然后划定时间窗，在每个时间窗内将多条日志编码成向量，然后用PCA等无监督方式进行异常检测。缺点是只能判断某时间窗内是否有数据异常，无法判断单个日志是否异常。
  一篇论文（DeepLog）提供了另外一个思路，属于无监督类型。首先对日志进行解析，得到日志模板和日志变量，分别使用LSTM判断流数据中日志模板是否正常、日志变量是否正常。其中，对于判断模板是否正常，做法是将每一个模板当成一个单词，基于正常数据使用LSTM拟合模板数据流。对于判断变量是否正常，做法是将数据流按模板分开，生成每一个模板对应的数据流，然后每一个模板数据流里的变量流进行LSTM拟合。在异常检测时，判断待检测值是否出现在LSTM的输出概率最高前K个值，如果出现就说明正常。

五、参考文献

方法	论文
**HBOS	**M. Goldstein, A. Dengel. Histogram-based Outlier Score (HBOS): A fast Unsupervised Anomaly Detection Algorithm[C]. In: Wölfl S, editor. KI-2012: Poster and Demo Track. Online;2012. p. 59–63
GMM	X. Yang, L. J. Latecki, D. Pokrajac. Outlier Detection with Globally Optimal Exemplar-Based GMM[C]. Siam International Conference on Data Mining, SDM 2009, April 30 - May 2, 2009, Sparks, Nevada, Usa. DBLP, 2009:145-154
KNN	S. Ramaswamy, R. Rastogi, K. Shim. Efficient Algorithms for Mining Outliers from Large Data Sets [C]. ACM SIGMOD International Conference on Management of Data. ACM, 2000:427-438、F. Angiulli, C. Pizzuti. Fast Outlier Detection in High Dimensional Spaces[C]. European Conference on Principles of Data Mining and Knowledge Discovery. Springer-Verlag, 2002:15-26
KNN-weight	F. Angiulli, C. Pizzuti. Fast Outlier Detection in High Dimensional Spaces[C]. European Conference on Principles of Data Mining and Knowledge Discovery. Springer-Verlag, 2002:15-26
**LOF	M. M. Breunig. LOF: identifying density-based local outliers[J]. 2000, 29(2):93-104
COF	J. Tang, Z. Chen, A. Fu, D. Cheung. Enhancing Effectiveness of Outlier Detections for Low Density Patterns[C]. Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, Berlin, Heidelberg, 2002:535-548
INFLO	W. Jin, A. K. H. Tung, J. Han, et al. Ranking Outliers Using Symmetric Neighborhood Relationship[J]. Lecture Notes in Computer Science, 2006, 3918:577-593.
**LoOP	H. P. Kriegel, E. Schubert, A. Zimek. LoOP:local outlier probabilities[C]. ACM, 2009:1649-1652
CBLOF	Z. He, X. Xu, S. Deng. Discovering cluster-based local outliers[J]. Pattern Recognition Letters, 2003, 24(9–10):1641-1650
LFCOF	M Amer, M. Goldstein. Nearest-Neighbor and Clustering based Anomaly Detection Algorithms for RapidMiner[C]. Rapidminer Community Meeting and Conferernce. 2012
CMGOS	M. Goldstein. Anomaly Detection in Large Datasets[M]. 2014
**DBSCAN+GMM	Bigdeli E, Mohammadi M, Raahemi B, et al. A fast and noise resilient cluster-based anomaly detection[J]. Pattern Analysis & Applications, 2017, 20(1):1-17.
**iForest	F. T. Liu, M. T. Kai, Z. H. Zhou. Isolation-Based Anomaly Detection[M]. ACM, 2012, 6 (1) :1-39
**iForest局部异常	Aryal S, Kai M T, Wells J R, et al. Improving iForest with Relative Mass[C]// Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, Cham, 2014:510-521.
**SCiForest	F. T. Liu, M. T. Kai, Z. H. Zhou. Isolation-Based Anomaly Detection[M]. ACM, 2012, 6 (1) :1-39
RRCF	G. Roy, G. Roy, G. Roy, et al. Robust random cut forest based anomaly detection on streams[C]. International Conference on International Conference on Machine Learning. JMLR.org, 2016:2712-2721
AutoEncoder	S. S. Khan, B. Taati. Detecting unseen falls from wearable devices using channel-wise ensemble of autoencoders[J]. Expert Systems with Applications. 2017, 87:280-290
One-class SVM	W. Khreich, B. Khosravifar, A. Hamou-Lhadj, et al. An anomaly detection system based on variable N-gram features and one-class SVM[J]. Information and Software Technology, 2017, 91:186-197
SVDD	D.M.J Tax, R.P.W. Duin. Support vector domain description. Pattern Recognition Letters[J]. 1999, vol.20:1191-1199
SVM	Wang G P, Yang J X, Li R. Imbalanced SVM‐Based Anomaly Detection Algorithm forImbalanced Training Datasets[J]. Etri Journal, 2017, 39(5):621-631.
**随机森林	Liu D, Zhao Y, Xu H, et al. Opprentice:Towards Practical and Automatic Anomaly Detection Through Machine Learning[C]// Internet Measurement Conference. ACM, 2015:211-224.
PCA	Xu W, Huang L, Fox A, et al. Detecting large-scale system problems by mining console logs[C]// ACM Sigops, Symposium on Operating Systems Principles. ACM, 2009:117-132.
**系统日志	He S, Zhu J, He P, et al. Experience Report: System Log Analysis for Anomaly Detection[C]// IEEE, International Symposium on Software Reliability Engineering. IEEE, 2016:207-218.**
**LSTM无监督	Du M, Li F, Zheng G, et al. DeepLog: Anomaly Detection and Diagnosis from System Logs through Deep Learning[C]// ACM Sigsac Conference on Computer and Communications Security. ACM, 2017:1285-1298.
**深度信念网络+one-class SVM	Erfani S M, Rajasegarar S, Karunasekera S, et al. High-dimensional and large-scale anomaly detection using a linear one-class SVM with deep learning[J]. Pattern Recognition, 2016, 58(C):121-134.
**无监督异常检测方法测评	Goldstein M, Uchida S. A Comparative Evaluation of Unsupervised Anomaly Detection Algorithms for Multivariate Data[J]. Plos One, 2016, 11(4):e0152173.