论文题目: 最大频繁项集挖掘算法的研究
论文类型: 博士论文
论文专业: 计算机科学与技术
作者: 颜跃进
导师: 陈火旺,李舟军
关键词: 数据挖掘,关联规则,频繁项集,最大频繁项集,前瞻剪枝,超集存在判断,频繁模式树,最大频繁项集树,组合频繁模式树
文献来源: 国防科学技术大学
发表年度: 2005
论文摘要: 随着信息技术尤其是网络技术的快速发展，人们收集、存储和传输数据的能力不断提高，导致数据出现了爆炸性增长。与此形成鲜明对比的是，对人们决策有价值的知识却非常匮乏。知识发现与数据挖掘正是在这一背景下诞生的一门新科学。 关联规则是数据挖掘当前研究的主要模式之一，它用于确定数据集中不同域或属性之间的联系，找出有价值的多个域之间的依赖关系。频繁项集挖掘是生成关联规则的关键步骤，其效率问题是关联规则挖掘中的一大难点和热点。频繁项集挖掘可分为完全频繁项集挖掘、频繁闭项集挖掘和最大频繁项集挖掘三类。论文基于数据集和最大频繁项集的不同表示结构，从剪枝策略、尾项集的项排序策略和超集存在判断方法等角度对最大频繁项集的挖掘问题进行了深入的分析和研究。 位图是—种有效的数据集和项集的表示结构。论文基于位图提出了深度优先挖掘算法DFMfi。算法DFMfi充分利用位图的字节特性，优化了项集的匹配和合并操作，并首次在其中引入了基于局部最大频繁项集的超集存在判断方法。论文证明了算法DFMfi的正确性，并通过实验说明其在运行时间上少于同类算法。 近几年来，数据集的另—种压缩表示结构—FP-Tree结构越来越受到研究者们的青睐，论文第二部分研究基于FP-Tree结构的最大频繁项集挖掘问题，其中使用FP-Tree表示数据集及其投影，并利用MFI-Tree保存已有最大频繁项集。分析和实验说明已有算法中的超集存在判断为耗时操作，针对这种情况，论文在单棵MFI-Tree表示下基于最大频繁项集投影提出一种新的超集存在判断方法，并证明了多棵MFI-Tree表示下存在一种简单的超集存在判断方法，二者均可有效降低超集存在判断的时间开销。相应于两种超集存在判断方法，论文分别提出了算法FPMFI和FIMFI。在算法FIMFI里，论文分析了尾项集的项排序策略对压缩搜索空间的影响，提出了一种高效的、基于FP-Tree和MFI-Tree信息的尾项集项排序策略。通过使用新的前瞻剪枝方法，算法FIMFI拓展了前瞻剪枝的范围，加大了前瞻剪枝成功的可能性，尽可能地压缩了搜索空间。此外，FPMFI算法中的非冗余子树结构是寻求高效数据集压缩结构的一次尝试。实验表明，在稠密数据集上，这两个算法相对于同类算法均具有一定的优越性。其中FIMFI算法比同类算法中性能最优的FPMax~*算法平均快30％-40％。 论文最后提出一种能同时压缩表示数据集和最大频繁项集的新的数据结构—CFP-Tree，基于CFP-Tree结构定义了最大化子集，并提出了CfpMfi算法。通过其与FPMax~*
论文目录:
目录
图表索引
摘要
ABSTRACT
第一章 绪论
1.1 数据挖掘技术背景概述
1.1.1 数据挖掘技术的兴起
1.1.2 数据挖掘的定义和任务
1.1.3 数据挖掘的过程和应用
1.1.4 数据挖掘技术面临的主要挑战
1.2 论文的工作和结构
1.2.1 论文的工作
1.2.2 论文的组织结构
第二章 关联规则挖掘概述
2.1 关联规则挖掘
2.1.1 关联规则挖掘的基本概念
2.1.2 关联规则的分类
2.1.3 关联规则挖掘的研究现状
2.2 频繁项集挖掘相关工作
2.2.1 完全频繁项集挖掘算法
2.2.2 频繁闭项集挖掘算法
2.2.3 最大频繁项集挖掘算法
2.3 小结
第三章 基于单MFI-Tree结构挖掘最大频繁项集
3.1 引言
3.2 相关知识
3.2.1 深度优先搜索策略
3.2.2 FP-Tree(Frequent Pattern Tree)结构
3.2.3 MFI-Tree(Maximal Frequent Itemsets Tree)结构
3.3 基于单MFI-Tree结构的最大频繁项集挖掘算法FPMFI
3.3.1 基于最大频繁项集投影的超集存在判断
3.3.2 非冗余FP子树
3.3.3 算法FPMFI
3.4 性能分析与比较
3.5 小结
第四章 基于位图格式挖掘最大频繁项集
4.1 位图数据格式
4.2 剪枝策略
4.2.1 子集非频繁剪枝(Subset Infrequency Prune)
4.2.2 超集频繁剪枝(Superset Frequency Prune)
4.2.3 父等价剪枝(Parent Equivalence Prune)
4.3 局部最大频繁项集
4.4 基于位图数据格式的最大频繁项集挖掘算法DFMfi
4.5 性能分析与比较
4.6 小结
第五章 基于多MFI-Tree结构挖掘最大频繁项集
5.1 引言
5.2 相关知识
5.2.1 可能扩展项集和频繁扩展项集
5.2.2 多MFI-Tree结构表示最大频繁项集集合相关信息
5.3 基于多MFI-Tree结构的最大频繁项集挖掘算法FIMFI
5.3.1 剪枝策略
5.3.2 尾项集的项排序策略
5.3.3 超集存在判断
5.3.4 算法FIMFI
5.4 性能比较
5.5 小结
第六章 基于组合FP-Tree结构挖掘最大频繁项集
6.1 CFP-Tree(Combined FP-Tree)结构
6.1.1 CFP-Tree结构及其性质
6.1.2 CFP-Tree构造过程
6.2 CfpMfi算法
6.2.1 基于CFP-Tree结构的最大频繁项集挖掘算法CfpMfi
6.2.2 基于最大化子集的超集存在判断
6.2.3 基于最大化子集的尾项集的项排序策略
6.3 性能比较
6.3.1 剪枝性能
6.3.2 时间性能比较
6.3.3 最大内存使用量比较
6.4 小结
第七章 结论与展望
7.1 本文研究工作总结
7.2 基于FP-Tree挖掘频繁闭项集
7.3 今后工作
致谢
攻读博士学位期间发表的论文
攻读博士学位期间参加的科研工作
参考文献
发布时间: 2006-09-22
参考文献
- [1].最大频繁项集挖掘算法及应用研究[D]. 王卉.华中科技大学2004
- [2].数据流频繁模式挖掘关键算法及其仿真应用研究[D]. 敖富江.国防科学技术大学2008
相关论文
- [1].关联规则优化方法的研究[D]. 贺志.北京交通大学2007
- [2].关联规则的挖掘及其算法的研究[D]. 陆楠.吉林大学2007
标签：数据挖掘论文; 关联规则论文; 频繁项集论文; 最大频繁项集论文; 前瞻剪枝论文; 超集存在判断论文; 频繁模式树论文; 最大频繁项集树论文; 组合频繁模式树论文;