数据流上的异常检测

摘要

近年来，由于来自实际应用中的需求的推动，数据流上的异常检测技术的研究已经受到了学术界和工业界的越来越多的重视。数据流上的异常检测在金融风险分析、通信网监测、网络流量管理、趋势分析、Web日志分析、网络入侵检测、传感器网络管理等领域具有广泛的应用。例如，为了调节电信网络的性能，需要对电信网中的数据流进行监测，其检测异常的准确性对电信网络的正常运行是至关重要的。同样的应用场景也存在于高速公路上的交通管理，相关趋势的分析和预测，网页点击流的分析，信息系统的入侵检测以及传感器网络的管理等。在这些场景中，有相当一部分应用需要及时地对任务进行处理，以获得尽可能短的响应时间。 然而，传统的数据库技术是用来管理静态数据集的，其很难直接被用于对动态数据的实时监测和挖掘。因此，为了实时地监测数据流，需要采用伸缩性强的异常检测算法在有限的时间内处理大量的数据流。在对数据流的处理中，最大的挑战就是要在有限的内存空间，需要顺序的单遍扫描算法，并且要实时返回精确的结果。本文综述了国际上关于数据流异常检测的研究成果，在分析了现有研究工作的基础上，提出了异常的定义和数据流上异常检测要研究的问题，以及异常检测系统的框架。在对数据流上异常检测的研究过程中，本文的主要贡献有如下三个方面： 1．提出了自适应的突变的定义，自适应的突变更加全面地概括了数据流上的突变信息，并且排除了颠簸数据的干扰。根据该定义，本文又提出了三种突变检测方法，其中包括FalsePositive，FalseNegative和综合突变检测算法，这些算法能够保证以高于用户指定的准确率检测数据流上的突变，而且这些算法既能检测单调聚集函数值的突变，又能检测非单调聚集函数值的突变。突变检测算法所依赖的是本文提出的倒置桶序列的直方图(简称IH)。这种新颖的直方图技术具有较小的时间复杂度0(n(10gn+IogR))和空间复杂度O(logn+log_R)，并能为突变检测提供准确的聚集查询支持，因此与现有直方图技术相比更加适用于数据流上的突变检测。 2．提出了基于单调搜索空间的突变检测算法。首先，提出了数据流上的单调搜索空间的构建算法及改进后的构建算法，从而对实际应用中的近似分形数据进行了分形变换，使得滑动窗口的错排序误差errMs为0。其次，基于单调的搜索空间设计了突变检测算法。该算法能将突变检测处理时间复杂度从0(m)降为D(10gm)，m为需要被检测的滑动窗口数目。最后，分析并给出了基于单调搜索空间的突变检测方法的误差界限，使得本文提出的突变检测算法具有理论上的误差上限的保证。 3．提出了基于分段分形模型的无参数异常检测算法。首先，本文提出了最优的分段分形模型以及数据流上的近似最优分段分形模型。利用近似最优的分段分形模型为长为礼的数据流建模的时间复杂度为0(nlogn)，空间复杂度为O(10gn)。第二，提出了基于分段分形模型的突变检测算法，该算法在分段分形模型具有理论误差界限保证的前提下，能够准确地检测数据流上的突变。第三，本文提出了无参数的异常检测算法。该算法能够在最合适尺寸的滑动窗口上检测异常的情况，不需要用户设定任何参数，也不需要使用训练数据。使用该算法在数据流上检测异常的时间复杂度仅为O(n)，空间复杂度仅为0(1)。 综上所述，本文针对现有异常检测中存在的三类问题，分别提出了从问题定义、概要数据结构到异常检测算法的完整方案，并提出了以本文技术为核心的异常检测系统框架。理论分析和实验结果表明，与已有的研究成果相比，本文给出的异常检测方法具有较高的精度和较低的时间、空间复杂度，更加适用于数据流一的应用场景：金融风险分析、通信网监测、网络流量管理、趋势分析、W曲日志分析、刚络入侵检测、传感器网络管理等。

目录

文摘

英文文摘

论文说明：图目录及表目录

第一章绪论

第二章相关工作

第三章问题说明

第四章基于IH的突变检测

第五章基于单调搜索空间的突变检测

第六章基于分段分形模型的无参数异常检测

第七章总结与展望

参考文献

攻读博士期间发表的论文及专利

致谢

论文独创性声明及使用授权声明