挖掘正相关的频繁项集

论文摘要

数据挖掘的任务是发现大型数据集中隐藏的、预先未知的知识。关联规则的挖掘是数据挖掘研究的重要问题之一。该问题自1993年被R．Agrawal等人提出以来，一直受到广泛关注和重视。通常，关联规则的挖掘分两步：（1）挖掘所有的频繁项集；（2）由频繁项集产生强关联规则。其中第一步的时间复杂度远高于第二步。从频繁项集产生关联规则的方法是简单的，但是可能导致无意义的关联规则的产生。一些研究者注意到这一问题，提出在产生关联规则时利用提升度判断规则前、后件之间的正相关性，进一步过滤掉一些无意义的规则。但是，这种做法仍然存在两个问题：（1）不能减少挖掘频繁项集的时间开销。（2）不能保证规则前件（后件）中的项是正相关的，当规则的前件或后件内部存在负相关的项时，仍然可能产生无意义的关联规则。针对以上问题，本文基于数学期望，引进正相关的频繁项集的概念，并给出一种挖掘正相关的频繁项集的算法。本文的算法可以直接在FP-树中挖掘正相关的频繁项集，将正相关性的判断推进到了挖掘频繁项集的过程中。这样，不仅可以大幅度地减少产生频繁项集的数量，显著地提高挖掘频繁项集的效率，而且在由频繁项集产生关联规则时，可以有效地避免产生无意义的关联规则。此外，在挖掘频繁项集时，本文的算法还通过提取公共项，进一步降低了递归地构造条件FP-树的时间开销。在UCI机器学习基准数据集上实验表明，本文算法可以大幅度地减少产生频繁项集的数量，显著地提高挖掘频繁项集的效率，具有很好的性能，对于大型、稠密数据集尤其如此。

论文目录

• 摘要
• ABSTRACT
• 目录
• 第一章 绪论
• 1.1 课题研究背景
• 1.2 本文的主要工作
• 1.3 课题的研究价值和意义
• 1.4 本文的内容组织
• 第二章 数据挖掘和关联规则
• 2.1 数据挖掘和KDD
• 2.1.1 数据挖掘和KDD的概念
• 2.1.2 数据挖掘的分类
• 2.1.3 数据挖掘面临的挑战
• 2.1.4 数据挖掘研究的热点
• 2.2 关联规则的基本概念
• 2.3 关联规则的分类
• 2.3.1 基于规则中处理的变量类别分类
• 2.3.2 基于规则中数据的抽象层次分类
• 2.3.3 基于规则中涉及到的数据维数分类
• 2.4 关联规则的发展方向
• 2.5 由关联挖掘到相关分析
• 第三章 频繁项集的挖掘算法
• 3.1 频繁项集挖掘的基本策略
• 3.1.1 频繁项集生成中解空间的类型
• 3.1.2 频繁项集生成中的搜索方法和剪枝策略
• 3.1.3 数据库的表示方法
• 3.1.4 数据压缩技术
• 3.2 APRIORI挖掘算法
• 3.2.1 Apriori核心算法
• 3.2.2 挖掘频繁项集的优化方法
• 3.3 频繁模式增长算法
• 3.4 CLOSET和CLOSET+算法
• 3.5 MAXMINER算法
• 第四章 挖掘正相关的频繁项集
• 4.1 问题提出
• 4.2 兴趣度度量标准
• 4.2.1 客观度量
• 4.2.2 主观度量
• 4.3 正相关频繁项集的概念
• 4.4 算法思想
• 4.4.1 改进的FP-树
• 4.4.2 公共项的处理
• 4.4.3 相关性判断
• 4.4.4 算法描述
• 第五章 实验结果和分析
• 5.1 实验环境
• 5.2 实验数据
• 5.3 实验分析
• 5.4 进一步讨论
• 5.4.1 零事务问题
• 5.4.2 遗漏的频繁项集
• 第六章 总结和展望
• 6.1 全文总结
• 6.2 工作展望
• 参考文献
• 致谢
• 攻读硕士学位期间发表论文情况