数据流聚集查询和频繁模式挖掘的研究

论文摘要

数据流模型的出现对传统的数据管理技术提出了巨大的挑战,由于数据的流动性和无限性等特点,已有的数据库技术无法对数据流数据进行有效的管理,因此,必须进行数据流管理新技术的研究。数据流管理技术已经引起了数据库界的广泛关注,成为当前的一个研究热点。研究数据流相关技术不仅有重要的学术价值,而且在传感器网络、气象监测与分析、移动物体位置跟踪、股票分析、邮件过滤、网络监控与安全等领域有着巨大的应用前景。本文对数据流管理系统和数据流挖掘中的若干关键问题进行了深入探索,主要有以下内容:(1)数据流管理系统的体系结构:面向高速数据流,提出了一个基于硬件预处理的数据流管理系统体系结构。目前已有的原型系统都是从查询优化、系统调度等方面来提高数据的处理速度,在高速数据流环境下都存在明显的不足,因此,本文从一个全新的角度构建新一代数据流管理系统,在体系结构上采用软硬件协同的思想和前端硬件预处理技术,实现数据的高速处理。(2)高速数据流聚集查询:目前已有的聚集算法绝大多数是采用近似技术,以牺牲精度来换取速度的提高。随着硬件技术的快速发展和硬件成本的迅速下降,软硬件协同技术逐渐引起了人们的关注。本文提出了一种软硬件协同的高速数据流聚集查询方法,发挥了硬件在处理速度上的优势和软件在灵活性方面的长处,也研究了提高查询资源共享度的方法。(3)分布式数据流增量聚集查询:分布式处理是数据流管理系统发展的必然趋势。而在分布式系统中,传输量往往是系统的主要瓶颈,因此,本文研究并提出了一种分布式数据流增量聚集方法,可以显著地降低系统的通信量。(4)数据流频繁闭合模式:频繁闭合模式能够唯一地决定所有的频繁模式及其准确的支持度,并且往往数量比频繁模式小几个数量级,在实际中更容易理解和应用。本文研究了动态数据流环境下的频繁闭合模式挖掘,目前还很少有这方面的研究报道。滑动窗口和界标窗口是数据流环境下两种最重要的窗口类型,本文分别研究并提出了基于滑动窗口和基于界标窗口的数据流频繁闭合模式挖掘新算法,算法具有较好的适应性和可扩展性,用户可以根据需要,通过调整允许误差在执行效率和结果精度方面取得平衡。(5)数据流变化检测:在数据流环境下,模式的改变往往比正常模式提供更多有价值的信息,因此,数据流变化检测是数据流挖掘的核心问题之一。本文运用信息熵理论,从频繁项集角度出发,提出了一种基于最大频繁项集信息熵的数据流变化检测方法,不仅可以反映关联规则挖掘中频繁模式的变化,而且也可以有效地反映数据集的改变。

论文目录

• 摘要
• Abstract
• 表索引
• Table Index
• 图索引
• Figure Index
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 数据流及其特点
• 1.1.2 数据流管理系统
• 1.1.3 数据流挖掘
• 1.2 研究现状
• 1.2.1 数据流管理系统及其相关实现技术
• 1.2.2 数据流挖掘算法
• 1.3 主要研究工作和内容安排
• 第二章 软硬件协同的高速数据流聚集查询
• 2.1 基于硬件预处理的数据流管理系统的体系结构
• 2.2 数据流聚集的相关工作
• 2.3 软硬件协同的数据流实时聚集查询
• 2.3.1 求和（Sum）的实现
• 2.3.2 平均值（Avg）的实现
• 2.3.3 最大值（Max）的实现
• 2.3.4 聚集的多窗口共享
• 2.4 算法分析和实验验证
• 2.4.1 算法的时间复杂性分析
• 2.4.2 实验仿真
• 2.5 本章 小结
• 第三章 分布式数据流增量聚集
• 3.1 相关研究
• 3.2 分布式数据流近似增量聚集查询
• 3.2.1 基本问题的定义
• 3.2.2 增量聚集的基本思路
• 3.2.3 VSB-Tree 更新和查询算法
• 3.2.4 VSB-Tree 的节点合并
• 3.3 算法分析和性能测试
• 3.3.1 算法分析
• 3.3.2 性能测试
• 3.4 本章 小结
• 第四章 数据流频繁闭合模式的挖掘
• 4.1 相关研究
• 4.2 基本概念
• 4.3 滑动窗口中的频繁闭合项集
• tree 的结构'>4.3.1 DSCFI_tree 的结构
• tree 的构造和增量更新'>4.3.2 DSCFI_tree 的构造和增量更新
• CFI'>4.3.3 频繁闭合项集的挖掘算法DS_CFI
• 4.3.4 实验研究
• 4.4 界标窗口中的频繁闭合项集
• 4.4.1 全局潜在频繁1 项集的生成和更新
• 4.4.2 FP-CDS 树的更新和频繁闭合项集的生成
• 4.4.3 完整的FP-CDS 算法
• 4.4.4 实验研究
• 4.4.4.1 性能分析
• 4.4.4.2 对比分析
• 4.5 本章 小结
• 第五章 基于最大频繁项集信息熵的数据流变化检测
• 5.1 相关研究
• 5.2 信息熵的基本概念和性质
• 5.3 数据流变化检测算法
• 5.3.1 基于信息熵的数据流变化判定准则
• 5.3.2 滑动窗口中的最大频繁项集
• 5.3.3 数据流变化检测算法
• 5.4 实验研究
• 5.5 本章 小结
• 第六章 总结与展望
• 6.1 工作总结
• 6.2 未来工作的展望
• 致谢
• 参考文献
• 附录
• 附录1 参与的科研项目
• 附录2 攻读博士学位期间发表的论文