频繁模式挖掘和动态维护的理论与方法研究

论文摘要

频繁模式挖掘是许多数据挖掘任务中的核心问题,有着广泛的应用。而现有的挖掘方法普遍存在多次扫描数据库或重复遍历复杂数据结构的问题。本文以频繁模式挖掘为切入点,系统地研究了频繁模式/效用频繁模式挖掘和动态维护的理论与方法。主要研究内容如下:1基于分享和继承策略的挖掘理论与方法从频繁模式构成的搜索空间入手,提出了贯穿全文的分享和继承挖掘策略。通过引进分享表结构,避免了由绝对的分而治之带来的重复遍历与计数,提高了挖掘效率;同时,在挖掘过程中根据数据集的局部子集特性动态地调整挖掘策略,给出了提高时间效率与节省空间消耗的优化方法。2效用频繁模式挖掘从分析现有频繁模式挖掘任务的局限性入手,提出了效用频繁模式挖掘模型。该模型同时考虑各项出现的次数及其对目标模型的不同影响程度,能够更好地处理实际的挖掘应用;拓展了频繁模式挖掘的任务。3频繁等价模式挖掘分析了频繁模式压缩表示的方法,提出频繁等价模式的概念和挖掘方法,它将频繁模式中具有等价关系的项集中在一个子空间内,在不丢失任何信息的同时极大地减少了频繁模式的冗余。通过与频繁闭合模式比较,表明其拥有更高的压缩率。4频繁模式的交互挖掘提出了基于分享表结构的交互挖掘方法。该方法可与分享和继承策略无缝地集成在一个框架下。通过尽量避免复杂数据结构的重建和充分利用已有的计算结果,极大地提升了挖掘的效率。5频繁模式的增量挖掘从分析增量挖掘机制入手,提出了基于分享和继承策略的增量挖掘方法。该方法可完全不依赖先前的挖掘方法,减少了大量的原库检索和计算,较好地解决了数据库发生变化下的频繁模式维护问题。6频繁模式在关联规则挖掘中的应用从分析关联规则挖掘入手,描述了频繁模式在关联规则挖掘中的作用;实现了规则生成算法,能够快速地由频繁模式生成规则。通过在数据集上的测试结果,验证了频繁模式挖掘的实际应用价值。本文还将交互挖掘与增量挖掘扩展到效用频繁模式挖掘中去,有效地解决了效用频繁模式的交互挖掘与增量挖掘问题。通过在不同数据集中与已有的各类算法做比较,证明了分享和继承策略的高效性,能较好地解决频繁模式/效用频繁模式挖掘中普遍存在重复扫描和遍历问题,提升了挖掘的效率。

论文目录

• 摘要
• ABSTRACT
• 目录
• CONTENTS
• 第一章 绪论
• 1.1 研究背景
• 1.2 频繁模式挖掘的主要问题
• 1.3 本文的工作
• 1.3.1 基于分享和继承策略的挖掘理论与方法
• 1.3.2 效用频繁模式挖掘
• 1.3.3 频繁等价模式挖掘
• 1.3.4 频繁模式的动态维护
• 1.3.5 频繁模式在关联规则挖掘中的应用
• 1.4 本文的结构
• 第二章 频繁模式挖掘技术综述
• 2.1 频繁模式挖掘
• 2.1.1 基于候选模式生成与测试的算法
• 2.1.2 基于模式增长的算法
• 2.2 频繁模式压缩
• 2.2.1 最大频繁模式
• 2.2.2 频繁闭合模式
• 2.3 效用频繁模式挖掘
• 2.4 频繁模式的交互挖掘
• 2.5 频繁模式的增量挖掘
• 2.6 关联规则挖掘
• 2.7 小结
• 第三章 基于分享和继承策略的挖掘算法
• 3.1 引言
• 3.2 频繁模式挖掘
• 3.2.1 问题的定义
• 3.2.2 模式构成的格
• 3.3 基于分享和继承策略的挖掘算法
• 3.3.1 频繁模式树FP-Tree
• 3.3.2 分享表Share-Table
• 3.3.3 Share-FPM算法
• 3.3.4 分享和继承策略
• 3.4 效用频繁模式挖掘
• 3.4.1 效用挖掘
• 3.4.2 效用频繁模式挖掘
• 3.4.3 基于分享和继承策略的效用频繁模式挖掘模型
• 3.5 效用频繁模式挖掘算法
• 3.5.1 Share-UFPM算法
• 3.5.2 算法分析
• 3.6 性能分析
• 3.6.1 试验数据集及特征
• 3.6.2 频繁模式挖掘实验结果
• 3.6.3 效用频繁模式挖掘实验结果
• 3.7 小结
• 第四章 频繁等价模式挖掘
• 4.1 引言
• 4.2 等价关系
• 4.3 问题的定义
• 4.4 频繁等价模式挖掘算法Share-FEPM
• 4.5 实验结果
• 4.6 小结
• 第五章 频繁模式的交互挖掘
• 5.1 引言
• 5.2 问题的定义
• 5.2.1 频繁模式的交互挖掘
• 5.2.2 效用频繁模式的交互挖掘
• 5.3 分享结构（Share-struct）的扩展
• 5.4 频繁模式的交互挖掘算法
• 5.4.1 Interactive-FPM算法
• 5.4.2 算法分析
• 5.5 效用频繁模式的交互挖掘算法
• 5.5.1 Interactive-UFPM算法
• 5.5.2 算法分析
• 5.6 实验结果
• 5.6.1 频繁模式交互挖掘实验结果
• 5.6.2 效用频繁模式交互挖掘实验结果
• 5.7 小结
• 第六章 频繁模式的增量挖掘
• 6.1 引言
• 6.2 问题的定义
• 6.2.1 频繁模式的增量挖掘
• 6.2.2 效用频繁模式的增量挖掘
• 6.3 频繁模式的增量挖掘算法
• 6.3.1 IM-FPM算法
• 6.3.2 算法分析
• 6.4 效用频繁模式的增量挖掘算法
• 6.4.1 IM-UFPM算法
• 6.4.2 算法分析
• 6.5 实验结果
• 6.6 小结
• 第七章 频繁模式在关联规则挖掘中的应用
• 7.1 引言
• 7.2 关联规则挖掘
• 7.3 关联规则挖掘算法
• 7.4 挖掘结果
• 7.5 小结
• 第八章 结论与展望
• 8.1 结论
• 8.2 工作展望
• 参考文献
• 致谢
• 研究成果及发表的学术论文
• 作者和导师简介
• 附件