基于滑动窗口的数据流频繁闭合项集挖掘研究

论文摘要

随着信息技术特别是网络技术飞速发展,人们收集、存贮、传输数据能力不断提高。数据出现了爆炸性增长,与此形成鲜明对比的是,对决策有价值的知识却非常匾乏。知识发现与数据挖掘技术正是在这一背景下诞生的一门新学科。频繁模式挖掘是数据挖掘领域的一个基本问题,研究内容一般包括事务、序列、树和图。其方法被广泛应用于许多其它数据挖掘任务中,如相关性分析,周期分析,最大模式,闭合模式,查询,分类,索引等等。由于问题本身的基础性和内在复杂性,频繁模式挖掘方法成为许多研究者关注的课题。如何实时挖掘数据流滑动窗口中的频繁闭合模式集是一个很大的挑战。本文针对数据流的特点,根据Moment算法提出了一种基于频繁闭项集挖掘的增量式维护算法,首先,算法通过滑动窗口来增量更新数据流事务,使用高效的项的位序列表示来降低滑动窗口的时间和空间复杂度。然后,为适应数据流快速、大量的特性,设计了一种新的数据结构New-CFIT,该结构不仅能够增量更新,而且可以快速地挖掘滑动窗口中的所有频繁闭合项集。其次,一种基于散列的技术被用于压缩存储挖掘出来的频繁闭项集。最后,为保证挖掘结果的准确性,利用了一棵压缩的模式树来进行频繁闭项集的检查,其目的是进行两种闭包检查:（1）超集检查,检查新发现的频繁闭项集是否是另一个具有相同支持度的已经发现的闭项集的超集;（2）子集检查,检查新发现的频繁闭项集是否是另一个具有相同支持度的已经发现的闭项集的子集。实验证明,在最近数据流频繁闭项集挖掘上,本文提出的算法与moment算法相比,不仅能得到比较高的准确度,而且执行速度更快,内存占用更小。

论文目录

• 摘要
• ABSTRACT
• 目录
• 1 引言
• 1.1 研究背景
• 1.2 国内外研究现状
• 1.3 本文的主要研究工作与组织结构
• 2 数据流模型与数据流处理技术
• 2.1 数据流处理模型及划分
• 2.2 传统数据处理模型和数据流处理模型的比较
• 2.3 基于数据集的数据流处理技术
• 2.4 基于滑动窗口模型的处理技术
• 2.5 本章小节
• 3 频繁闭项集挖掘算法
• 3.1 基本概念
• 3.2 频繁闭项集挖掘算法
• 3.3 本章小结
• 4 改进的MOMENT算法（A-MOMENT）
• 4.1 算法相关定义与项集的位向量表示方法
• 4.2 基于散列的技术的频繁闭项集计数
• 4.3 New-CFIT的数据结构与构造
• 4.4 更新New-CFIT及相应算法
• 4.5 频繁项集闭包的检查
• 4.6 频繁闭合项集挖掘算法总结
• 4.7 本章小结
• 5 试验结果及分析
• 5.1 实验环境和测试数据集
• 5.2 试验结果与分析
• 5.3 本章小结
• 6 结束语及未来工作
• 参考文献
• 致谢