一种流数据频繁模式挖掘算法的研究与实现

论文摘要

数据挖掘，是数据库研究中的一个很有应用价值的领域，目的是从大型数据库中提取隐含的、人们事先不知道的、潜在有用的信息或模式。经过近十几年的努力，已经相当成熟。然而，随着电子商务、传感器网络、股票数据分析等的应用，提出一种新的数据模型——流数据。这些数据源源不断地到来，只能按顺序进行处理，因此在流数据环境中进行挖掘是一项具有挑战性的工作，在数据库应用领域有很高的研究价值。本文主要是对流数据中的频繁项集的挖掘进行研究。分析了流数据模型与传统的数据模型的区别、主要的流数据处理技术、当前的挖掘任务等。针对如何在流数据上挖掘频繁模式这一课题，分析了经典的流数据挖掘算法FP-stream算法，结合流数据分段理论和滑动窗口技术，采用批处理式挖掘方式，进行基于滑动窗口的流数据频繁模式挖掘算法DSFP-SW（Data Stream Frequent Pattern based-on Sliding Window）的研究。DSFP-SW算法是一种批处理式的挖掘算法，先将流数据分段，每段作为一个滑动窗口，再将滑动窗口划分为几个基本的窗口，利用改进的频繁模式挖掘算法，计算每个基本窗口的临界频繁项集。为了适应流数据快速、大量的特性，在频繁模式树的基础上，改进了一种新的前缀树结构DSFP-SW-tree来存储每个基本窗口的临界频繁项集，树中的每个结点代表了一个频繁项集。随着滑动窗口的更新，更新DSFP-SW-tree。并每隔一段时间调用剪枝算法，快速地挖掘滑动窗口中所有的频繁模式。通过试验把该算法于经典的FP-Stream算法进行对比，结果表明，本文给出的算法在时间和空间上优于FP-Stream算法，适合流数据挖掘。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景
• 1.2 数据挖掘
• 1.3 国外研究现状
• 1.4 国内研究现状
• 1.5 主要研究工作
• 2 流数据及相关技术
• 2.1 流数据及流数据模型
• 2.1.1 流数据概念及特点
• 2.1.2 流数据模型
• 2.1.3 流数据模型与传统数据模型的区别
• 2.2 流数据管理系统
• 2.2.1 流数据管理系统模型
• 2.2.2 流数据管理系统与关系数据库管理系统的区别
• 2.2.3 已有的流数据管理系统
• 2.2.4 与流数据管理系统相关的研究
• 2.3 流数据处理技术
• 2.3.1 基于数据的技术
• 2.3.2 基于任务的技术
• 2.4 流数据分析及其挖掘
• 2.4.1 流数据挖掘及特点
• 2.4.2 流数据挖掘的关键问题
• 3 基于滑动窗口的流数据频繁模式算法分析
• 3.1 频繁模式
• 3.1.1 频繁模式分类
• 3.1.2 不同频繁模式对比
• 3.2 挖掘方法
• 3.2.1 批处理方法
• 3.2.2 启发式方法
• 3.3 流数据频繁模式挖掘算法
• 3.3.1 算法分析
• 3.3.2 FP-stream算法
• 3.3.3 频繁模式树
• 3.3.4 倾斜时间窗口
• 3.3.5 时间标签窗表格的裁减
• 3.3.6 算法的不足之处
• 3.4 滑动窗口的流数据频繁模式挖掘算法分析
• 3.4.1 前缀树模型
• 3.4.2 DSFP-SW-tree
• 4 基于滑动窗口的流数据频繁模式算法
• 4.1 历史信息的存储
• 4.1.1 线性回归
• 4.1.2 指数衰减
• 4.1.3 滑动窗口策略
• 4.2 DSFP-SW算法
• 4.2.1 DSFP-SW-tree的生成和更新
• 4.2.2 DSFP-SW-tree的增量更新
• 4.2.3 DSFP-SW-tree的剪枝
• 4.2.4 完整的DSFP-SW算法描述
• 5 实验结果及分析
• 5.1 实验环境和测试数据集
• 5.2 评估算法的实验结果
• 5.2.1 算法的可延展性
• 5.2.2 本文算法与FP-stream算法的比较
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢