数据流突发检测若干关键技术研究

论文摘要

数据流的本质特征为变化性及不可预测性。作为数据流一种重要的数据分析方法,数据流突发检测能够及时检测数据流中特定元素的数量异常变化,因此得到了学术界和工业界的广泛关注。应用领域有:光子爆发检测、股票波动检测、网络流量异常波动检测等。数据流突发检测是一个新兴的研究领域,存在许多值得研究且尚未解决的问题:（1）数据流元素及其频数的高效存储。突发检测关心频数变化较大的元素,因此须保存所有相异元素及其频数,而海量数据流中相异元素数目庞大且总数不断变化,每个元素频数的差异也很大。如何高效地存储这些元素及其频数,降低存储开销的同时支持高效的查询处理,是一个基础、关键、值得研究的问题;（2）在某些应用场合,数据流整体的数据量波动剧烈,导致单个元素频数随之变化剧烈。在建立突发模型时,要考虑如何减小数据流整体数据量的波动对单个元素流量的影响;（3）突发检测作为典型的数据流监测应用,并不是孤立的。现有的多个监测应用如Top-k,频繁项挖掘,变化检测、离群点检测等都是相对独立串行工作。如何在单遍处理的前提下,利用有限的存储和计算资源,实时并行地完成多个监测任务,是一个很有意义的工作。本文紧紧围绕着数据流突发检测这个中心,针对上述若干挑战性问题,从数据流处理角度出发,对突发检测处理流程中几个关键问题进行了研究。本文的主要贡献为:1、针对总数动态变化的海量相异数据流元素存储问题,提出了一种自适应的、灵活的、可动态扩展的布卢姆过滤器ExBF。ExBF由一个或多个称为桶的子布卢姆过滤器组成,并由目录和桶的两级结构组成可扩展哈希数据结构,以管理和维护这些桶。与PBF、SpBF、ScBF等已有数种容量可扩展的布卢姆过滤器相比,ExBF的优势为:（1）元素更新和查询时间复杂度为O（1）,不随桶数目的增多而线性增加;（2）扩展方式灵活,扩展时仅重新分布一个桶的元素,数据迁移量为总数据量的1/2n,其中n为桶的数目;（3）在元素数目较少时能够动态缩减桶的数目和目录的大小;（4）能够保证假阳性率限制在任意事先确定的范围内。2、针对数据流元素及其频数的高效存储问题,提出了一个基于改良的计数型布卢姆过滤器BCBF+HSet保存所有元素频数的基本方法。该方法使用相对静态和固定的结构,能提高约25%的存储效率,且能应对少数元素频数的剧烈变动。针对数据流中所有元素及其频数重尾分布的特点,提出了一个基于分层计数型布卢姆过滤器HCBF的方法,该方法在选取合适分层参数的情况下,能提高约30%的存储效率。3、在突发模型的建立方面,针对数据流整体数据量波动比较剧烈的情况下进行准确突发检测的问题,提出了流量无关的突发检测方法FFBD,该方法使用单个元素数量与总体元素数量的比值作为单个元素滑动窗口内的聚合函数值,并使用前后两个滑动窗口内的聚合函数值的比值来判断突发。与典型的聚合塔突发检测方法相比,FFBD方法使用多约2%的存储空间,高约5%的计算复杂度,但能有效地规避整体数据流的显著变化对单个元素突发检测带来的影响,有着更好的检测效果。4、在数据流多监测任务协同处理方面,基于数据流滑动窗口模型,提出了一个基于网格划分的多监测任务协同处理方法GD-MMTPM,将监测离群点、监测变化和监测突发等三个监测任务统一起来,使用单遍处理的方式进行统一处理。该方法能同时检测出离群点、变化和突发,且只需维护网格的简单信息,与其它方法相比,能够显著地减少时间复杂度和空间复杂度。综上所述,本文的工作针对数据流中进行突发检测的问题,围绕着该问题的几个挑战进行突破研究,提出了数个算法、方法及模型。由于突发检测在数据流挖掘中的重大理论意义及广阔应用前景,本文对于促进突发检测问题的理论研究和实用化具有一定的理论意义和应用价值。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 突发检测需求背景
• 1.1.2 突发检测的提出
• 1.2 相关工作分析
• 1.2.1 数据流模型
• 1.2.2 已有的数据流处理应用
• 1.2.3 突发检测
• 1.2.4 相关工作小结
• 1.3 本文工作
• 1.3.1 主要研究内容
• 1.3.2 主要创新点
• 1.4 论文结构
• 第二章 基于布卢姆过滤器的动态扩展元素存储方法ExBF
• 2.1 相关工作分析
• 2.1.1 布卢姆过滤器
• 2.1.2 可扩展布卢姆过滤器
• 2.1.3 可扩展布卢姆过滤器小结
• 2.2 自适应可动态扩展布卢姆过滤器ExBF
• 2.2.1 数据结构
• 2.2.2 元素的插入
• 2.2.3 桶的分裂
• 2.2.4 目录的扩展
• 2.2.5 元素的成员查询
• 2.2.6 元素删除的支持
• 2.2.7 性能分析
• 2.3 实验验证
• 2.3.1 实验设置
• 2.3.2 实验结果
• 2.3.3 实验结论
• 2.4 本章小结
• 第三章 基于布卢姆过滤器的高效元素计数存储方法
• 3.1 相关工作分析
• 3.1.1 计数型布卢姆过滤器
• 3.1.2 光谱布卢姆过滤器
• 3.1.3 动态计数过滤器
• 3.1.4 计数型布卢姆过滤器小结
• 3.2 改良计数型布卢姆过滤器方法BCBF+HSet
• 3.2.1 数据结构
• 3.2.2 更新算法
• 3.2.3 查询算法
• 3.2.4 性能分析
• 3.2.5 参数选择
• 3.3 分层计数型布卢姆过滤器方法HCBF
• 3.3.1 数据结构
• 3.3.2 更新算法
• 3.3.3 查询算法
• 3.3.4 性能分析
• 3.3.5 参数选择
• 3.4 实验验证
• 3.4.1 实验设置
• 3.4.2 实验结果
• 3.4.3 实验结论
• 3.5 本章小结
• 第四章 流量无关突发检测方法FFBD
• 4.1 相关工作分析
• 4.1.1 偏移小波树方法
• 4.1.2 聚合塔方法
• 4.1.3 基于阈值比率的方法
• 4.2 流量无关突发检测算法FFBD
• 4.2.1 数据结构
• 4.2.2 更新与突发检测算法
• 4.2.3 性能分析
• 4.3 一个短文本突发检测实例
• 4.3.1 动机
• 4.3.2 检测流程
• 4.3.3 实例效果
• 4.4 实验验证
• 4.4.1 实验设置
• 4.4.2 实验结果
• 4.4.3 实验结论
• 4.5 本章小结
• 第五章 数据流多监测任务协同处理方法GD-MMTPM
• 5.1 相关工作分析
• 5.1.1 网格划分算法
• 5.1.2 多监测任务协同处理
• 5.2 多监测任务协同处理方法GD-MMTPM
• 5.2.1 协同处理框架
• 5.2.2 相关算法
• 5.2.3 打分函数的选择
• 5.2.4 性能分析
• 5.3 实验验证
• 5.3.1 实验设置
• 5.3.2 实验结果
• 5.3.3 实验结论
• 5.4 本章小结
• 第六章 结束语
• 6.1 工作总结
• 6.2 研究展望
• 致谢
• 参考文献
• 作者在学期间取得的学术成果