数据流top-K频繁模式挖掘算法研究

论文摘要

数据流是近年来产生的一种新型数据模型,广泛出现在多种应用领域,如Web点击流分析、交通流量监控与管理、电力供应管理与预测、传感器网络数据分析、电信数据管理、金融服务、商业交易管理和分析等。数据流模型不同于传统的数据库模型,具有快速、实时、连续、无界等特点,由此决定了数据流的查询或挖掘算法与基于传统的数据库的挖掘技术有显著的区别,其算法应是单遍扫描（one-pass）的。由于存贮容量的有限性,不可能完整地保存全部数据流元素。一种有效的方法是设计一个远小于原数据流规模的结构,保存已流过数据的概要特征,用于数据流的查询处理及分析,因而挖掘结果通常是近似的。鉴于数据流的高速性和连续性,数据流算法应是动态增量的,亦必须是高时空效率的。现有的数据库挖掘技术已不再适合数据流环境。因此,流数据环境下的数据挖掘研究具有更大的机遇和挑战性。论文针对数据流挖掘分析处理中的几个基本问题进行了探讨和研究,主要内容如下:1.动态增量地挖掘数据流界标窗口的top-K频繁模式。挖掘top-K频繁模式在现实生活中有重要应用,为此我们研究有效算法TOPSIL-Miner动态增量地挖掘数据流界标窗口的top-K频繁模式。设计了存储流数据摘要信息的概要结构TOPSIL-Tree以及动态记录挖掘相关信息的树层最大支持度表MaxSL、项目序表OIL、候选结果集TOPSET和最小支持度表MinSL等概要结构,并分析了与这些数据结构相关的挖掘特性,在此基础上研究挖掘算法的若干优化措施。并对算法的误差上界进行了理论分析研究。算法具有较高的时空效率和精确度。2.高效挖掘数据流滑动窗口top-K频繁N模式集。滑动窗口模型因其更关注最近到达的流数据,所以有很高的实用价值。在基于滑动窗口的数掘流挖掘分析中,不但要及时地增量地处理源源不断到来的流数据,而且还要考虑过期数据的处理,因而比基于界标窗口的挖掘技术具有更大的挑战性。提出了有效挖掘数据流滑动窗口top-K频繁N模式集的近似算法TOPSIS。采用批处理的方法,将滑动窗口划分为若干基本窗口作为处理单元。设计概要结构TOPSIS-Tree和RELIS分别存储和记录流数据的摘要信息和当前滑动窗口的挖掘结果,并设计了三种优化策略用以提高算法的时空效率:（1）滑动窗口更新时剪枝最新基本窗口的无功节点;（2）挖掘过程中动态提升支持度阈值;（3）启发式自适应调整剪枝阈值。同时,对算法在挖掘频繁模式产生的支持度误差进行了理论分析。算法具有较好的适应性和可伸缩性,用户可以根据需要,通过调整功用参数在执行效率和结果精度方面取得均衡。3.有效挖掘数据流滑动窗口top-K闭合频繁模式。闭合频繁模式是频繁模式的精确简洁表示,能够唯一地确定所有的频繁模式及其支持度,并且在数目上往往比频繁模式小几个数量级。研究了一种有效挖掘数据流滑动窗口top-K闭合频繁模式的近似算法TCIS。设计了一种新的压缩前缀扩展树结构TCIS-Tree,该结构不仅存储当前滑动窗口的概要数据信息,而且还记录了业已发现的候选闭合模式信息。在TCIS-Tree的更新和挖掘过程中,采用数据过滤、启发式动态调整剪枝阈值、挖掘阈值等若干优化措施,有效地提高算法的时空效率。结合TCIS-Tree采用一种二级哈希结构快速地进行模式的闭合性判别。有效地实现了滑动窗口top-K闭合模式的挖掘。4.数据流分位数查询。分位数是数据集合的一个重要统计量。设计了一个基于规范数直方图的概要结构——Nord Histogram,并在此基础上实现了数据流分位数查询的单遍扫描近似算法NORMAL,其时间和空间复杂度均线性于概要结构中桶的个数,与数据流的长度无关,因而具有很好的可伸缩性。该方法在均匀分布的数据上取得了优良性能。对算法精度与内存需求的关系进行了理论分析。针对上述研究,本文进行了一系列实验研究,对算法的时间消耗、空间需求以及精确性进行了测试,并和已有的有关算法进行了比较。实验表明,上述算法具有较高的时空效率和精确性能,有效地实现了相关的数据流挖掘任务。

论文目录

• 致谢
• 中文摘要
• ABSTRACT
• 第一章 引言
• 1.1 研究背景和意义
• 1.2 数据流管理系统模型
• 1.3 数据流处理模型的基本要求
• 1.4 数据流模型分类
• 1.5 数据流技术研究现状
• 1.5.1 数据流管理系统
• 1.5.2 数据流挖掘技术
• 1.6 论文主要研究内容
• 1.7 论文组织结构
• 第二章 基本概念与理论
• 2.1 数据挖掘的特点及任务
• 2.2 关联规则挖掘
• 2.2.1 基本概念
• 2.2.2 频繁模式增长（FP-growth）算法
• 2.2.3 闭合频繁模式
• 2.3 数据流挖掘相关技术
• 2.3.1 窗口技术
• 2.3.2 算法近似技术
• 2.4 基于确定误差区间的频繁模式挖掘近似算法
• 第三章 数据流界标窗口top-K频繁模式挖掘
• 3.1 问题的提出及相关研究
• 3.2 相关定义及概要结构
• 3.3 算法TOPSIL-Miner的优化
• 3.3.1 剪枝平凡模式
• 3.3.2 自适应提升挖掘阈值
• 3.3.3 动态提升剪枝阈值
• 3.4 挖掘界标窗口top-K频繁模式
• 3.4.1 挖掘算法TOPSIL-Miner
• 3.4.2 TOPSIL-Tree的增量更新过程Tree-increment（）
• 3.4.3 top-K频繁模式的挖掘过程Tree-mining（）
• 3.5 算法误差分析
• 3.6 实验研究
• 3.6.1 实验数据
• 3.6.2 算法时空性能与比较实验
• 3.6.3 算法精确性实验研究
• 3.7 本章小结
• 第四章 数据流滑动窗口top-K频繁N模式集挖掘
• 4.1 相关研究
• 4.2 基本概念及相关定义
• 4.3 算法的优化策略
• 4.3.1 优化一:剪枝无功节点
• 4.3.2 优化二:动态提升支持度阈值
• 4.3.3 优化三:自适应调整剪枝阈值
• 4.4 挖掘滑动窗口top-K频繁N模式集算法描述
• 4.4.1 基本窗口插入TOPSIS-Tree
• 4.4.2 更新滑动窗口
• 4.4.3 top-K频繁N模式集的挖掘过程
• 4.5 算法精确性分析
• 4.6 实验研究
• 4.6.1 实验数据
• 4.6.2 算法性能及精确度研究
• 4.7 本章小结
• 第五章 挖掘数据流滑动窗口top-K闭合频繁模式
• 5.1 相关研究
• 5.2 研究问题及相关定义
• 5.3 算法优化措施
• 5.3.1 构造TCIS-Tree时提升挖掘阈值
• 5.3.2 数据过滤
• 5.3.3 启发式动态调整挖掘阈值和TCIS-Tree剪枝阈值
• 5.3.4 减小搜索空间
• 5.3.5 模式闭合性检查机制
• 5.4 滑动窗口top-K闭合频繁模式挖掘
• 5.4.1 TCIS算法
• 5.4.2 TCIS-Tree的更新
• 5.4.3 基于TCIS-Tree的top-K闭合频繁模式挖掘
• 5.5 实验研究
• 5.5.1 时间与空间效率实验
• 5.5.2 精确性实验测试
• 5.6 本章小结
• 第六章 数据流分位数查询算法研究
• 6.1 相关研究
• 6.2 问题的提出及相关定义
• 6.2.1 问题的提出
• 6.2.2 相关定义
• 6.3 NORMAL算法描述
• 6.3.1 NORMAL算法
• Histogram的更新'>6.3.2 规范数直方图Nord_Histogram的更新
• Histogram的分位数近似计算'>6.3.3 基于Nord_Histogram的分位数近似计算
• 6.3.4 算法的时间与空间复杂度分析
• 6.4 算法的精确度分析
• 6.5 实验研究及分析
• 6.6 本章小结
• 第七章 总结与展望
• 7.1 研究工作总结
• 7.2 未来工作展望
• 参考文献
• 攻读学位期间撰写和发表的论文
• 学位论文数据集