数据流上的异常检测

论文摘要

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

论文目录

• 中文摘要
• 英文摘要
• 图目录
• 表目录
• 第一章 绪论
• 1.1 数据流模型
• 1.2 异常检测的应用领域
• 1.2.1 网络流量管理
• 1.2.2 金融数据分析
• 1.2.3 网站访问量监测
• 1.2.4 环境监测
• 1.2.5 工业控制
• 1.3 本文的研究目标与内容
• 1.4 本文的组织结构
• 第二章 相关工作
• 2.1 数据流研究共同关心的问题
• 2.1.1 数据流类型
• 2.1.2 窗口模型
• 2.1.3 概要数据结构
• 2.2 异常检测
• 2.2.1 检测简单聚集函数值的异常
• 2.2.2 检测复杂聚集函数值的异常
• 2.2.3 现有的检测系统
• 2.3 本章小结
• 第三章 问题说明
• 3.1 数据流上异常检测的问题
• 3.1.1 在所有长度的窗口上检测异常
• 3.1.2 在多个不同长度的窗口上检测异常
• 3.1.3 在长度最合适的窗口上检测异常
• 3.1.4 异常检测系统框架
• 3.2 本章小结
• 第四章 基于IH的突变检测
• 4.1 引言
• 4.2 问题定义
• 4.3 突变检测算法
• 4.3.1 False Positive突变检测算法
• 4.3.2 False Negative突变检测算法
• 4.4 倒置桶序列的直方图—IH
• 4.4.1 一种简易的直方图技术
• 4.4.2 一种改进后的直方图技术—倒置桶序列的直方图
• 4.5 误差界限（Error Bound）
• 4.5.1 误差定义
• 4.5.2 理论分析
• 4.6 实验分析
• 4.6.1 实验设置
• 4.6.2 真实数据中突变的分析
• 4.6.3 算法性能分析
• 4.7 综合突变检测
• 4.7.1 问题定义
• 4.7.2 算法
• 4.7.3 实验结果
• 4.8 本章小结
• 第五章 基于单调搜索空间的突变检测
• 5.1 引言
• 5.2 问题定义
• 5.3 数学基础
• 5.3.1 分形的性质
• 5.3.2 实际应用中数据的分形特性
• 5.4 建立单调的搜索空间
• 5.4.1 基于准确分形的单调搜索空间
• 5.4.2 基于近似分形的单调搜索空间
• 5.4.3 单调搜索空间的构建算法
• 5.4.4 改进的单调搜索空间的构建算法
• 5.5 突变检测
• 5.5.1 突变检测算法
• 5.5.2 突变检测的误差界限
• 5.6 NetFlow上的突变检测模型
• 5.6.1 NetFlow介绍
• 5.6.2 突变检测模型
• 5.7 实验分析
• 5.7.1 实验设置
• 5.7.2 性能分析
• 5.8 本章小结
• 第六章 基于分段分形模型的无参数异常检测
• 6.1 引言
• 6.2 数学基础
• 6.2.1 收缩映射
• 6.2.2 迭代函数系统——IFS
• 6.2.3 循环迭代函数系统——RIFS
• 6.3 问题定义
• 6.4 数据流上的分段分形模型
• 6.4.1 逆问题
• 6.4.2 面向局部的分段分形模型
• 6.4.3 误差界限
• 6.4.4 面向全局的分段分形模型
• 6.4.5 基于分段分形模型的突变检测算法
• 6.5 无参数的异常检测算法
• 6.5.1 基于历史数据的异常检测算法
• 6.5.2 基于分段分形模型的异常检测算法
• 6.6 实验分析
• 6.6.1 实验设置
• 6.6.2 性能分析
• 6.7 本章小结
• 第七章 总结与展望
• 7.1 本文工作的总结
• 7.2 未来工作的展望
• 参考文献
• 攻读博士期间发表的论文及专利
• 致谢