异常检测算法综述

王鑫，张涛，金映谷

（大连民族大学机电工程学院，大连116605）

0 引言

异常检测[1-2]就是检测数据中不符合行为的异常数据，根据研究应用的领域不同，异常数据可以称之为离群点、污点、不一致点。近年来，异常检测在很多领域都得到应用，如：网络入侵检测、故障诊断、疾病检测、身份识别、欺诈检测，等等。异常检测问题可以大致总结为两类[3]：一是对结构化数据进行异常检测。对结构化数据进行异常检测的核心思想就是找到与正常数据差异大的点，通常把这个点称为离群点，但对结构化数据进行异常检测通常面临的问题就是如何定义边界来区分正常点和异常点；二是对非结构化数据的异常检测。常见的图像识别，通过对图像的检测，识别出异常点。但是，对于异常的定义没有标准答案，通常根据具体情况而异。根据现有研究阶段得到的成果，采用异常检测通常有两个标准[4]：

（1）异常数据跟样本中大多数数据不一样，存在差异性大。

（2）异常数据在总体数据样本中所占的比例小。

1 异常检测类别以及原理

由于训练的数据集存在不同，根据训练集的不同，异常检测大致分为三类：

（1）全监督异常检测（Supervised Anomaly Detec⁃tion）[5]

全监督异常检测就是训练的数据集都被标签化，分别标记成正常和异常。全监督检测算法根据训练集中的标签进行训练，得到网络模型，在测试阶段，通过对网络模型输入未知类别的样本测试，得到输出结果。在现实的实践中，由于标记样本是个复杂的过程，因此，全监督异常检测的应用范围很窄。

（2）半监督异常检测（Semi-Supervised Anomaly De⁃tection）[6]

半监督异常检测只是对数据集中正常的样本进行标签化，然后通过训练被标签化的正常样本，得到“正常”模型，将数据样本与“正常”模型的偏差定义为异常度，如果当异常度大于设定的阈值，最终的输出结果将是异常，相反，如果异常度小于设定的阈值，输出结果将是正常。半监督异常检测面临着和全监督异常检测一样的问题，都需要标签化的样本，因此在实际中应用并不广泛。

（3）无监督异常检测（Unsupervised Anomaly Detec⁃tion）[7]

无监督异常检测的数据集没有任何的标签，无监督异常检测的数据集包含正常数据和异常数据，通常情况下，正常的数据要比异常数据多。无监督异常检测通过训练正常的数据集，得到网络模型，并得到一个异常分类分数，当将测试数据输入到网络模型中，也会得到一个分数，通过比较，如果测试数据得到的分数大于异常分类分数时，则测试数据的输出结果为异常，反之则为正常。在实际生产中，通常正常的数据要远远大于异常数据，而且无监督异常检测不需要对数据集进行标签化，所以无监督异常检测应用最为广泛。

2 异常检测算法

异常检测算法的基本思想是：用正常的数据去训练模型，得到阈值，然后再去判断新的数据是否异常。常见的几种异常检测算法有：基于概率统计、基于聚类、基于最近邻等[8]。对基于异常检测算法的比较，详细信息如表1 所示，其中包含各种异常检测算法中的的主流算法（模型）、优缺点对比。

表1 基于异常检测算法的比较

2.1 基于概率统计异常检测算法

基于概率统计的异常检测算法[9]通过分为两步，第一步假设数据服从一定的分布，如正态分布、泊松分布；第二步是计算每个点属于这个分布的概率，最后得出该点是否异常。

一般情况下根据估计参数的方法来确定分布模型，利用数据集的数据去估计，得到一个估计的模型。通常在一元正态分布异常检测时，常常利用3 原则，当数据不在3 标准内，则视为异常。多元正态分布中，用到基于协方差矩阵的Mahalanobis 距离。基于概率统计的异常检测算法对于模型的选择十分关键，选择了错误的模型，检测对象就很可能被错误地判为异常点。李际磊[10]对于现有的网络入侵检测系统的检测技术进行分析，指出现有技术的不足并提出基于概率统计的网络异常检测方法。该方法通过统计IP、端口、时间、周期等因子来判断网络行为是否异常，通过对算法的不断优化与实验，该方法对DDoS 攻击、木马盗窃等网络异常行为有较高的检测准确率和速度。陈开河等人[11]为解决地铁出行存在的异常情况对地铁系统带来的不利影响，提出基于概率统计的地铁出行异常的集成检测方法，该方法包含三个方面相关联的检测算法：出行时间、出行时间差、出行时间比值。经过实验，该方法有效可行，而且与其相关联的三个算法形成互补，极大地提高检测率。卫薇等人[12]针对电力IT 监控对象特征数据，提出基于统计模型的电力IT 监控对象特征数的异常检测方法，经过试验表明，该方法解决了传统电力IT 监控软件存在的缺点，其在异常检测的准确率、召回率上有明显的提升。曹晨曦等人[13]提出一种基于统计的时间序列数据的异常点检测方法，该方法能有效的检测出异常点出现的位置，从而避免异常点对时间序列数据带来的负面影响。通过用数据进行实验表明，预测精度会提高3.4%-4.4%。

2.2 基于最近邻异常检测算法

基于最近邻的异常检测算法[14]通常根据近邻度分为全局近邻和局部近邻，在全局近邻异常检测算法中常见的是基于距离的异常检测算法[15]；局部近邻异常检测算法中常见是基于密度的异常检测算法[16]。

“农三代”是吴躜辉身上一个闪亮的标签，2009年他毕业于浙江农林大学，刚一毕业就进入了浙江爱普农业科技发展有限公司工作，到今年已经整整十个年头了。说起选择农资行业的原因，吴躜辉说走进农资这个行业并不是他偶然的一个行为，而是经过深思熟虑后所做下的决定。

（1）基于距离异常检测算法

基于距离的异常检测算法主要应用于全局近邻，常用的算法是KNN 算法[17]，KNN 算法主要思想是异常点距离正常点的距离比较远。KNN 算法其原理对于每个数据点，通过找到k 个最近的邻居，然后根据k 个最近的邻居计算异常分数，计算异常分数的方法主要有两种：1 是使用第k 个最近的距离（简称K-近邻距）离；2 是计算所有的k 个距离，然后求出平均距离（简称平均距离）。通常在实际中方法2 的应用程度比较高。

曾存等人[18]为了能提高柴油机异常情况的检测速度，提出基于空间几何法和距离法的柴油机异常热工参数检测方法。通过对热工参数进行实验，验证了两种方法的可行性，同时也能快速准确的确定异常样本数据。霍文君等人[19]通过总结已有异常检测算法存在低准确率问题，在现有的时间序列异常检测算法中，结合优点，弥补不足，提出一种新的基于欧氏距离的在线异常检测算法。该算法通过对运维时的时间序列进行实验，最终结果表明该算法能快速准确地检测出异常数据。陈嘉伟等人[20]在手势识别方面，通过解决传统的k 最近邻算法的缺点，提出一种基于改进KNN 算法应用于动态手势识别。该算法通过记录手势信号的特征量作为训练和测试，并及时存储。通过实验结果表面，改进的KNN 算法相较于原始的KNN 算法在成果率方面提升10&左右。

（2）基于密度异常检测算法

对于数据集存在分布不均匀，有稠密的地方，有疏松的地方，这就造成分割的阈值难以确定，为解决这一问题，提出基于密度的异常检测算法。基于密度的异常检测算法是根据样本点的局部密度信息去判断是否异常，常见的基于密度的异常检测算法有：LOF、IN⁃FLO、LoOP 等。

LOF 算法[21]其基本原理是对数据点进行计算，找出其k 个近邻，然后计算LOF 得分，得分越高则异常的可能性越大。LOF 是一个比值，其分子是k 个近邻的平均局部可达密度，分母则是该数据点局部可达密度。可达密度则是k-近邻个数与k-近邻可达距离的比值。高泽雄[22]提出基于LOF 算法的规律异常车辆检测，首先对卡口过车的轨迹数据进行特征提取，然后利用LOF 算法对车辆的规律进行异常检测，从而发现规律异常车辆。该方法的提出，为大范围异常车辆检测，社会稳定提供帮助。应裴昊等人[23]为解决电力数据网对业务流量进行异常检测的需求，提出基于LOF 的电力数据网业务流量异常检测方法。该方法通过对LOF算法进行改进，计算每个流量包与附近流量包的分隔程度，进而推算出是否存在异常。该方法相对于传统的方法具有更高的灵活性，进过实验仿真，验证该方法的可行性，能有效地提高检测效率，减少成本。

LoOP 算法[27]与其他算法存在不同，相对于基于全局的KNN 算法还是LOF 的算法，其输出结果都是异常分数，对于异常分数作为输出结果而言，通常缺少一个衡量的标准，即不知道输出多少分会被判定为异常点，LoOP 算法通过输出异常概率解决问题。LoOP 算法计算局部密度的方法的基本原理通常会假设距离最近的邻居服从高斯分布。距离总是以正数值存在，所以符合“半高斯”分布（均值的右边）。使用“半高斯”分布的标准差（也称为概率集距离）。每个数据点会与其邻居产生一个局部异常检测分数，最后应用一个归一化函数和一个高斯误差函数，将异常检测分数转换成一个概率的形势输。

2.3 基于聚类异常检测算法

基于聚类的异常检测算法[28]通常有三种假设，每个假设下面都有其常见的方法。

假设一：不属于任何簇类的点就是异常点，代表方法DBSCAN 算法[29]；DBSCAN 算法是一种典型的基于密度的聚类算法，该算法通过将紧密相连的样本划为各个不同的类别，最终得出聚类类别结果。阮嘉琨等人[30]分析了高速公路交通流数据具有的复杂性、多变性、波动性等特点，采用传统的异常数据检测方法很能准确的检测出异常数据，于是提出基于DBSCAN 密度聚类的高速公路交通流异常数据检测算法。经过实验表明，该检测方法有很好的检测效果，能够满足实际的路况检测需求。

假设二：距离最近的聚类结果较远的点为异常点，常见方法K-means 算法[31]。该算法首先对数据进行聚类，然后通过计算样本与所属聚类的两个距离，一个是样本与所属聚类中心的距离，一个是样本与所属聚类的类内平均距离，通过两个距离的比值衡量异常程度。李峰等人[32]为解决K-means 算法存在由于选择中心值不当而造成聚类效果不好的问题，提出一种局部迭代的快速K-means 聚类算法。该算法降低聚类更新的时间复杂度，提高聚类效果，最终通过仿真实验与真实数据实验，验证了该算法在提高检测准确率的同时，其检测时间也大幅度缩短。刘慕娴等人[33]提出一种基于K-means 算法的网络流量异常检测模型，该方法先将网络流量数据进行量化，将量化后的熵值进行分类，然后将K-means 聚类算法运用到异常检测中，实现安全检测预警。经过试验，该方法提高了检测准确率，为异常流量检测提供一种高效的手段。

假设三：疏松聚类与较小的聚类里的点都是异常点，主要方法CBLOF 算法[34]、LDCOF 算法[35]。该类方法通过聚类后将聚类簇分成大簇和小簇，如果样本数据属于大簇，则利用该样本和所属大簇进行计算异常得分；如果样本数据属于小簇，则利用该样本距离最近的大簇计算异常得分。钱景辉等人[36]在CBLOF 算法基础上进行改进，提出一种基于多示例学习的时序离群点检测算法MIL-FindCBlof，该算法将数据进行聚类，然后采用全局策略计算因子数值，最后通过计算平均因子来确定离群点。经过实验表明，该算法与经典离群点检测算法相比，在检测的全面性和准确性都有提高。

综上所述，对异常检测算法的研究应用进行总结，详情如表2 所示。

3 结语

异常检测算法在其相应的领域内得到广泛的应用，但是随着研究的深度，可以发现几种典型异常检测算法的优点与不足之处。基于概率统计异常检测算法更适用于对低维数据进行异常检测，其具有很好的鲁棒性，但是其对模型的依赖程度比较高，模型的选取十分关键；基于距离的异常检测算法具有不需要假设数据分布的优点，但是同时也存在不适用于高维数据，需要人工调参数，同时参数k 的选择也是比较不易，仅仅适用于全局异常点，无法适用局部异常；基于密度的异常检测算法适用于分布不均匀的数据，从中找出局部异常的数据，但同时由于需要遍历数据计算距离，计算程度大，不适用于在线使用。基于聚类的异常检测算法通常检测速度快，有的可以应用到实时在线检测，但是也存在一定的问题，如检测效果很大程度比较依赖聚类效果，对于大数据而言，开销成本大。

目前，对异常检测的研究不断深入，衡量异常检测系统的好坏主要指标是检测效率及检测准确率，对于异常检测系统而言，异常检测算法起着决定性的作用。稳定好、速度快、适用性强的异常检测算法将是今后研究的主要方向。

表2 基于异常检测算法的研究应用

本文首先主要对异常检测进行简短的概述，描述了异常检测解决的两类问题及应用异常检测的标准，然后从数据集的角度考虑，分析归纳了异常检测的类别，阐述了其工作原理，随之对异常检测算法进行分类整理，介绍几种典型的异常检测算法的原理并列举其研究现状，最后对典型异常检测算法进行总结，分析其优缺点，并对异常检测算法的发展趋势进行展望。