数据流频繁项集挖掘研究

论文摘要

20世纪末,随着信息科学技术的不断进步,一种被称为数据流的模型出现在众多现实应用领域中,例如金融市场、网络监测、无线传感器网络等。与传统数据库中的静态数据集不同,数据流是一种源源不断产生,时间维度上严格有序,数值上不断变化的高速数据序列。数据流的这些特点,使得包括频繁项集挖掘在内的传统数据挖掘技术难以直接适用于数据流。本文对数据流中频繁项集挖掘技术进行了深入探索,主要有以下内容:(1)对数据流模型、数据流挖掘特点、现有的研究成果进行了总结,着重讨论了数据流中频繁项集挖掘技术,并在此基础上提出了一种事务链表组模型。(2)在对传统和数据流频繁项集挖掘技术深入研究的基础上,提出了一个基于滑动窗口、事务链表组、近似思想的DSTLG算法,来挖掘数据流中的频繁项集。(3)为了最大程度上减少频繁项集挖掘结果数,本文在数据流频繁项集挖掘DSTLG算法思想的基础上进行扩展,提出了DSMTLG算法,来挖掘数据流中的最大频繁项集。(4)通过一系列实验证明DSTLG及DSMTLG算法有着较好的时间和空间效率,并从时间代价和空间代价两个角度进行了性能分析。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题研究背景及意义
• 1.2 当前研究现状及选题依据
• 1.2.1 国内外研究现状
• 1.2.2 选题依据
• 1.3 本文研究的内容
• 1.4 论文组织结构
• 第二章 数据流挖掘问题描述
• 2.1 数据流模型的研究
• 2.1.1 数据流模型及划分
• 2.1.2 数据流与传统数据的处理模型
• 2.2 数据流挖掘面临的挑战
• 2.2.1 数据流挖掘算法的特点
• 2.2.2 适合数据流算法的处理技术
• 2.3 数据流频繁项集挖掘问题
• 2.4 数据流频繁项集挖掘算法分类
• 2.4.1 基于概率误差区间的算法
• 2.4.2 基于确定误差区间的算法
• 2.5 本章小结
• 第三章 数据流频繁项集挖掘处理机制研究
• 3.1 数据流频繁项集挖掘处理机制
• 3.1.1 近似控制
• 3.1.2 窗口变化
• 3.1.3 数据结构
• 3.1.4 衰减因子
• 3.2 基于数据流模型的近似度保证
• 3.2.1 基于界标模型的近似度保证
• 3.2.2 基于滑动窗口的近似度保证
• 3.2.3 时间倾斜窗口与多时间粒度
• 3.3 数据结构优化机制的研究
• 3.3.1 FP-Tree 与前缀树模型
• 3.3.2 传统多事务链模型
• 3.3.3 数据流中事务链表组模型
• 3.4 本章小结
• 第四章 数据流频繁项集挖掘算法研究
• 4.1 频繁模式分类及相关定义
• 4.2 不同频繁模式比较
• 4.3 数据流频繁项集挖掘DSTLG 算法
• 4.3.1 最大可能频繁度的估计
• 4.3.2 DSTLG 算法求解过程
• 4.3.3 滑动窗口和事务链表组的更新策略
• 4.3.4 事务链表组的修剪与还原
• 4.3.5 频繁项集的请求输出
• 4.4 DSTLG 算法分析与讨论
• 4.5 DSTLG 算法的扩展研究
• 4.5.1 事务链的扩展定义
• 4.5.2 扩展后事务链表组的更新策略
• 4.5.3 最大频繁项集的请求输出
• 4.5.4 扩展算法意义及局限性
• 4.6 本章小结
• 第五章 实验结果及分析
• 5.1 实验环境和测试数据
• 5.2 实验结果
• 5.2.1 稳定性实验
• 5.2.2 对比实验
• 5.2.3 扩展算法实验
• 5.3 实验分析
• 5.3.1 时间性能分析
• 5.3.2 空间性能分析
• 5.4 本章小结
• 第六章 总结与展望
• 6.1 论文总结
• 6.2 未来工作展望
• 参考文献
• 致谢
• 在学期间的研究成果
• 附录
• 附录1 eclipseUML 生成的算法类图
• 附录2 DSTLG 算法核心代码