数据流上的频繁项集挖掘算法研究

论文摘要

数据流是目前的一个新兴的热门领域，国内外学者都纷纷提出各种数据流处理的技术、算法和各种具体应用项目。数据流是一个按时间到来的有序的项集。和传统静态数据库中的数据不同的是，数据流是连续的、无限的、通常以很高的速度到来的并且数据分布随着时间而改变。数据流频繁模式挖掘是数据流挖掘基本问题之一，已经引起国内外研究者的广泛关注，提出了许多有效的数据流频繁模式挖掘算法。针对数据流的特点，论文对数据流处理技术和数据流挖掘中的关键问题进行了研究和总结。论文对一些关键问题的解决技术进行了研究。论文对经典的频繁项集挖掘算法进行了介绍和分析。分析可以看出数据流的无限性、高速性使得经典的频繁项集挖掘算法难以适用到数据流中。此外，论文对于当前现存的一些数据流中频繁项集挖掘算法进行了介绍，比较分析和总结，并且设计实现了数据流中挖掘频繁项集的算法FP-stream和Time-Sensitive Sliding Window。本文在上述工作的基础上提出了FP-FT算法，用户通过它可以快速获取最近一个时期内的频繁项集。该算法采用了嵌入了时间窗口的前缀树的结构来存储频繁项集，方便了对数据块中数据项的操作，节约了一定的空间。分析和实验表明，与传统算法相比该算法具有较好的空间和时间效率，适合数据流中频繁项集的挖掘。

论文目录

• 致谢
• 中文摘要
• ABSTRACT
• 1 引言
• 1.1 研究背景与意义
• 1.2 国内外研究现状
• 1.2.1 国外研究现状
• 1.2.2 国内的研究现状
• 1.3 本文的贡献
• 1.4 本文的组织结构
• 2 数据挖掘与数据流综述
• 2.1 数据挖掘
• 2.2 数据流
• 2.2.1 数据流的概念及特点
• 2.2.2 数据流技术
• 2.2.3 研究热点
• 2.3 数据流挖掘
• 2.3.1 数据流挖掘的特点
• 2.3.2 数据流频繁项集挖掘及关键问题
• 3 频繁项集挖掘算法
• 3.1 基本概念
• 3.2 经典的频繁项集挖掘算法
• 3.2.1 Apriori算法
• 3.2.2 FP-growth算法
• 3.3 数据流中频繁项集挖掘算法
• 3.3.1 采样算法
• 3.3.2 略图算法
• 3.3.3 滑动窗口算法
• 3.3.4 分段算法
• 3.3.5 相关实验
• 3.4 算法的分析与比较
• 4 数据流频繁项集挖掘FP-FT算法
• 4.1 引言
• 4.2 问题定义
• 4.3 FP-FT算法
• 4.3.1 构造FP-FT树
• 4.3.2 项集的插入和更新算法
• 4.3.3 FP-FT树中失效数据块的处理算法
• 4.3.4 树的剪枝算法
• 4.3.5 完整的FP-FT算法
• 4.3.6 范例
• 4.4 实验结果分析和比较
• 4.5 小结
• 5 总结和展望
• 参考文献
• 学位论文数据集