异常数据实时检测方法研究综述

2022-10-24李永飞李铭洋

现代计算机 2022年16期

吴琼，李永飞，李铭洋

（华北科技学院计算机学院，三河 065200）

0 引言

异常数据通常也称为离群值、噪声等。Edgeworth把异常值定义为“显然严重偏离样本集合中其他观测值的观测值”。异常数据检测是指从数据中找出明显与其他数据不同的数据，最早采用基于统计学的方法，现在已成为数据挖掘的四大任务之一。异常数据所占比例较小但却可能蕴含丰富的内容，因此异常数据检测具有重要的研究意义和应用价值，对保障数据可信性也有重要作用。

从Knox等提出“基于距离的异常数据”的概念以来，异常数据检测已经成为数据挖掘中的一个研究热点。异常值可能来源于机械故障、仪器错误、人为错误等，其产生往往不可避免，而且会影响数据分析的结果，甚至可能造成严重后果。目前，异常数据检测已经广泛应用于诸多领域。在医疗卫生行业，异常数据检测可以及时发现病人的身体指标异常，提早治疗，避免病情恶化。在生态环境监测领域，可以对各项监测指标的异常情况尽早采取应对措施。在应急管理的事前数据采集和处理阶段，异常数据实时检测可以对突发事件及时响应，进而及时调整应对措施。

近年来，随着大数据时代的到来，海量数据的产生对数据处理的方法提出了更多的挑战。异常数据检测的实时性和准确性方面有了更高的要求。异常数据检测的核心问题是异常检测算法模型的构建，它将直接影响异常检测的检测率。

本文主要介绍传统异常数据检测方法和异常数据实时检测方法。首先介绍常用的异常检测方法以及它们常用的检测算法，主要分为基于统计学和基于机器学习两大类；接着介绍异常数据实时检测方法以及采用的算法；最后对异常数据实时检测的发展趋势进行总结和展望。

1 异常检测方法

1.1 基于统计学的方法

基于统计学的异常检测方法，一般建立一个数据分布模型，然后计算对象符合该模型的概率，将低概率的对象视为异常。最简单的方法有箱线图、3σ准则、Grubbs检验等，这些方法都需要假设数据服从某种分布，然后利用数据去进行参数估计。复杂一些的还有混合高斯建模、基于马尔科夫模型和时间序列建模，等等。基于统计学的方法优点是鲁棒性较好，适合低维度数据。但是处理高维数据受限制，而且受数据分布和模型参数的影响，因此限制了它的应用范围。

1.2 基于机器学习的方法

机器学习算法按照是否需要人工标记可以分为无监督、有监督和半监督模式。无监督模式不需要任何标签，也不依赖完善的先验知识，因此在异常检测领域应用更加广泛。

基于聚类的异常检测方法将数据分为不同的簇，而异常数据是不属于任何一个簇的。

聚类分析属于无监督模式，不依赖预先对数据的标记和训练，可以根据数据的相似度把数据划分为多个类或类簇。K-means算法逻辑简单、计算复杂度低、聚类效果也不错，是应用最广泛的聚类算法之一。由于异常数据检测的结果依赖于聚类算法的分析结果，因此要求在使用K-means算法实现异常检测时能够解决聚类结果不稳定的问题。文献［9］提出基于近邻传播算法和最大最小距离算法结合使用的APMMD算法，利用近邻传播算法和最大最小距离思想计算初始聚类中心，并将获得的初始聚类中心应用于K-means聚类算法中，使迭代次数降低，其聚类结果保持稳定且具有较高的异常检测的准确率。

基于近邻度的方法包括基于距离和基于密度的方法。这种方法不需要假设数据的分布。

（1）基于距离的方法。基于距离的方法通过计算数据与近邻数据之间的距离来判断出异常数据，一般采用欧式距离和曼哈顿距离，主要应用于全局近邻。常用的算法是K-最近邻（K-nearest neighbor）算法，它是一种简单易用、有监督模式的机器学习算法。KNN算法首先找到k个最近的邻居，然后根据k个最近的邻居计算异常分数。

（2）基于密度的方法。基于密度的方法与基于近邻度的异常点检测密切相关，是在基于距离的基础上，把数据之间的距离和周围邻近的数据个数相结合。它通过比较每个点和其邻域点的密度，当点与包围其的邻居的密度不同时，被认定为异常点。经典的方法是Breunig等提出的局部离群点方法LOF（the local outlier factor）。LOF中计算距离采用欧式距离，LOF为每个点分配一个局部离群因子（LOF），LOF的大小表示该点的局部密度与其最近邻居的局部密度之比，LOF越高，则表明是异常点的可能性越大。基于连通性的异常检测算法COF（connectivity-based outlier factor）的局部密度通过链式距离方式计算求出。LOF和COF算法都是借助数据的相对密度计算异常分值，得分越高越可能是异常数据。由于LOF数据量的增多该算法的时间复杂度较高，文献［13］提出改进的LOF算法即K-LOF算法。先利用计算效率高的K-means聚类算法对数据进行检测预处理获得初选异常数据，然后用基于密度的LOF算法再挖掘出最终的异常数据。结果表明，相比LOF算法K-LOF不但提高了检测的精确度，也降低了异常数据检测的计算复杂度。

另外，还有一些专用的异常检测方法，如One Class SVM和孤立森林（Isolation Forest）。这类算法的思路是不需要利用统计、距离和密度的量化指标去表达异常数据的疏离程度，而是直接描述正常数据与异常数据的疏离程度。

（1）One Class SVM算法。One Class SVM属于无监督学习算法，不需要标记训练集和输出标签。该算法的思路比较简单，首先找一个超平面将正常数据找出来，再通过正常数据的特征去学习一个决策边界，然后通过这个边界去判断新来的数据是否与训练数据类似，超出边界则为异常。由于该算法只有一个Class，比较适合解决极度不平衡的数据异常检测。文献［14］得出One Class SVM算法核函数计算时间比较长，因此不适合用于大量数据的处理。

（2）孤立森林算法。孤立森林算法是2008年由南京大学周志华教授团队首次提出，2012年又进行了改进。孤立森林算法属于无监督学习，它通过样本的疏密程度去描述样本之间的差异。异常点被定义为“容易被孤立的离群点”。它由多个iTree（孤立二叉树）构成，每个iTree的构建是从数据特征集合中随机选择一个分割值，通过这个分割值对数据进行划分然后构造左右子树，直到所有数据被划分或已经达到树的高度限制，其中只关心路径较短的点，它们更可能是异常点。这种划分情况下，异常数据点在iTree中更靠近根节点，同时低密度的点远离大多数样本，将很早被孤立。孤立森林算法是线性时间复杂度，与K-means、LOF等算法相比较，它不需要计算有关的距离、密度的指标，处理异常数据快速且高效。因此适合实时在线异常数据检测。表1列出了常用异常检测算法的优缺点比较。

表1 异常检测算法优缺点比较

2 基于流处理框架的异常数据实时检测

由于传统方法不能满足海量的动态化数据的实时异常检测的需求。因此出现了基于流处理框架的新方法。动态化的数据，也称为数据流，它具有动态产生且事先无法预知的特点。动态数据需要刚到达就及时处理，同时满足数据实时性异常检测要求，数据处理效率要求更高。目前异常数据实时检测中主要采用基于Storm、Spark等实时流处理框架结合机器学习算法和基于滑动窗口的方法等。依靠流数据分析处理方法实现异常检测，可以用在实时数据分析场景中。基于流处理框架的异常数据实时检测方法对比如表2所示。

表2 基于流处理框架的异常数据实时检测方法对比

2.1 结合机器学习算法的方法

Hadoop核心是分布式文件系统HDFS和并行化计算模型MapReduce。随着海量数据的产生，为了加快数据的处理速度则采用并行化计算。文献［17］为了解决初始聚类中心敏感问题，利用最大最小距离的思想改进了K-means聚类算法，同时采用MapReduce并行化实现该算法的分布式聚类。结果表明提高了算法的计算效率，并且降低了算法执行过程的通信开销。文献［18］采用基于Hadoop平台中的MapReduce并行计算框架，并使用基于密度的LOF算法的分布式财务异常数据分析模型。采用MapReduce并行化计算框架，算法在运行时可以在多个计算节点运行。将MapReduce框架和加入领域关系的LOF算法结合使用，可以并行计算，进而提高了数据处理速度和算法的准确率。

由于孤立森林算法的每棵树随机采样独立生成，具有很好的处理大数据的能力和速度，可以进行并行化处理。同时还存在孤立二叉树间异常能力的差异性，文献［19］采用加权计算测试样本在孤立森林算法中异常值，同时采用基于内存的Spark框架不同于Hadoop框架中从HDFS中读取数据，比较适合迭代次数多的算法。结果表明在大规模数据下可以加快检测速度和提高检测精度。文献［20］提出基于HDFS框架的数据异常检测方法，利用分布式HDFS框架可以快速准确地存储数据，采用基于支持向量数据描述并结合最小闭包球算法实现实时异常检测。该方法降低了时间复杂度，提高了异常检测率，并减少了运行时间。

由于K-means聚类算法在处理大量数据时效率较低，文献［21］提出了基于Apache Flink流计算框架结合流处理思想的SK-means（stream K-means）方法，提高了算法的执行效率，聚类效果更好并且可以较快地进行异常数据检测。文献［22］提出基于分布式流处理框架Spark Streaming，采用流回归机器学习算法和正态统计技术相结合的方法进行数据异常检测。该方法可以实时且准确分析瓦斯浓度流数据中的异常数据，解决了流数据中大数据机器学习处理和实时性问题。文献［23］提出基于Storm实时处理平台采用动态KNN的累积距离的异常检测方法。该方法适用于实时处理框架，每一组时间序列只用动态地保存个时间点的数值，可以简化操作和节省内存。同时可以动态地观察数据检测结果。

2.2 基于结合滑动窗口的方法

滑动窗口机制可以处理最新到达的数据，文献［24］提出基于Storm流数据框架的滑动窗口计算方法。采用Storm平台上实现滑动窗口计算方法进行实时分析，并通过增大滑动窗口的吞吐量，提高了数据异常检测的实时处理效率。但是该方法只对数值型数据实现了实时处理，还需要进一步研究。文献［25］提出基于Storm流处理的数据实时处理方法，采用基于滑动时间窗口实现异常数据检测。可以实现在Storm上实时监测数据预处理、数据异常检测。

为了从海量数据中实时且高效地检测出异常值，文献［26］提出了Flink的异常检测方法，针对实时流数据，首先用Kafka对数据进行实时预处理，然后在Flink平台上利用ARIMA模型进行预测。

3 基于新型算法的异常数据实时检测

随着机器学习、神经网络等领域的发展，又出现了一些新颖且有效的异常数据实时检测方法。基于新型算法的异常数据实时检测方法如表3所示。

表3 基于新型算法的异常数据实时检测方法比较

3.1 基于层级实时记忆的方法

文献［27］提出基于层级实时记忆（hierarchical temporal memory,HTM）的时间序列异常检测算法，HTM算法是一种仿生物结构的机器学习算法，它不需要采用滑动窗口法批处理数据，就可以实现对数据的实时检测。它是“记忆-预测”的运行模式，将复杂的问题转化为模式识别，可以提前预警数据异常。随着云计算技术的发展，云资源的运行会产生海量的时序数据。文献［28］将基于分层时间记忆算法用在企业多云时序数据实时监测中，可以实现实时异常检测。由于云资源监测要实现自动化实时异常检测，而HTM算法存储大量时序数据符合实时流式分析、无监督以及动态数据在线学习的要求。因为该算法运用到监测系统中可以高效地检测异常，并提高企业的运维效率。HTM算法已经应用到许多数据智能处理领域如异常检测、数据预测。针对数据量的不断增长，快速处理的需要，以及无法并行化计算的问题，文献［29］提出了面向多核的并发HTM空间池算法，将HTM空间池区域分区，各区独立完成训练任务并且利用CPU中的计算核心，实现多个核心并行完成。使用基于多核心和共享内存的大数据平台Phoenix，避免带来额外的通信开销，并且提高了算法的执行效率和预测准确率。

3.2 基于长短期记忆神经网络的方法

对于时间序列数据，直接采用LSTM算法自适应性不高，而且单一模型检测结果准确率不高。文献［30］提出通过LSTM网络和自动编码器进行不同组合预测模型，进而影响检测器的性能。由于流数据数量大、到达快速，单个平稳模型可能无法满足数据实时异常检测的要求。文献［31］提出了基于LSTMs-Autoencoder的流数据异常检测算法。该算法采用多个LSTM单元，形成了一个深层递归的神经网络（LSTMs），然后将递归神经网络与自动编码器相结合，实现了对流数据的实时检测并保证检测结果准确，同时还能应对考虑概念漂移现象。

4 总结和展望

基于统计的方法由于数据分布快速且高效，鲁棒性较好适合低维数据，但对高维数据处理受限制。基于机器学习的方法克服了传统统计方法不能处理高维数据的问题。随着数据量的增多、动态数据的产生，对处理数据的速度、实时性有了更高的要求。大数据中的批处理方式处理速度较慢，可以采用基于Storm、Spark、Flink等流式处理框架来实现实时计算和分析，并且高效准确地检测出异常值。随着机器学习、神经网络等领域的发展，又出现了基于层级实时记忆的异常检测算法，它不需要采用滑动窗口法批处理数据，就可以实现对数据的实时检测。

随着海量数据以及动态数据的产生，除了采用流处理框的并行化和实时的计算方法，还需要继续改进算法的性能，进而实时检测更多的异常数据。比如，虽然HTM算法具有较强的自适应性，可以实现异常数据实时检测。但它也存在时间复杂度的问题，要使之应用广泛还需要进一步研究改进。与此同时，对于数据类型的增多和应用领域的扩大，可以研究通过丰富数据编码的方式来实现不同类型的数据异常检测，同时实时数据异常检测效果更好。面对数据不平衡等问题，可以通过从大量数据中学习获得准确有效的特征，建立基于深度学习的神经网络模型，进而提高异常检测的效率。对于不平衡数据的处理也可以采用基于深度学习的异常检测方法。在异常数据实时检测的未来发展中，基于层级实时记忆的和神经网络模型的方法改进，以及基于深度学习的方法是一种趋势。