基于频繁模式树的关联规则算法研究

论文摘要

数据挖掘是近年来迅速发展的信息处理技术,从大量的、不完全的、有噪声的、模糊的、随机的数据中,提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。它涉及数据库、人工智能、机器学习、模式识别、知识工程、面向对象、信息检索和可视化等一系列技术。关联规则挖掘作为数据挖掘领域的一个重要研究分支,它的任务是发现所有满足支持度阈值和置信度阈值的强关联规则。关联规则挖掘算法是关联规则挖掘研究的主要内容,迄今为止已经提出了许多高效的关联规则挖掘算法。本文对经典的Apriori和AprioriTid算法以及不产生候选集的FP-Growth算法进行了分析和研究。FP-Growth算法比Apriori算法在性能上有了很大提高,它仅需要扫描数据库两次,并且避免了产生大量的候选项集。但FP-Growth算法主要的瓶颈之一就是空间开销大。为了节省空间,提高频繁项的发现效率,本文对传统的频繁模式树和项头表进行了优化,采用动态构造哈希链地址的方法来构造项头表,FP-Tree的每个结点只存储该项在项头表中的地址,避免了在地址上出现空指针,节省了存储空间的开销,同时增加树结点的域实现了方便的双向遍历。此外还通过对事务数据库按一定的规则进行了划分,得到若干个数据库子集,然后分别对每个数据库子集进行数据挖掘,因而占用内存小,解决了内存无法装入频繁模式树的问题,使数据挖掘得以顺利进行。最后通过实验对基于频繁模式树的关联规则挖掘的优化算法与传统的频繁模式树的FP-Growth算法进行了比较,实验结果表明在挖掘大量数据信息时更有效。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 论文研究的背景及意义
• 1.2 国内外研究现状
• 1.3 论文的主要工作
• 1.4 论文的组织结构
• 第2章 相关技术介绍
• 2.1 数据挖掘和知识发现
• 2.1.1 数据挖掘目的和方法
• 2.1.2 数据挖掘过程
• 2.1.3 数据挖掘分类
• 2.1.4 数据挖掘对象
• 2.2 关联规则挖掘技术
• 2.2.1 关联规则的基本概念
• 2.2.2 关联规则的分类
• 2.3 本章小结
• 第3章 关联规则挖掘算法
• 3.1 层次迭代算法
• 3.1.1 Apriori算法
• 3.1.2 Apriori算法实例与分析
• 3.1.3 AprioriTid算法
• 3.1.4 Apriori算法的改进算法
• 3.2 最大频繁项目集挖掘算法
• 3.2.1 深度优先算法
• 3.2.2 宽度优先算法
• 3.3 本章小结
• 第4章 基于频繁模式树的关联规则挖掘算法
• 4.1 不产生候选集挖掘频繁项集的算法
• 4.1.1 频繁模式增长算法
• 4.1.2 频繁模式增长算法应用实例与分析
• 4.2 基于频繁模式树和项头表的优化
• 4.2.1 项头表的优化
• 4.2.2 频繁模式树的优化
• 4.3 基于事务数据库的优化
• 4.3.1 优化的理论基础
• 4.3.2 优化的思想方法
• 4.3.3 事务数据库划分算法
• 4.4 本章小结
• 第5章 实验与性能分析
• 5.1 实验环境及事务数据库
• 5.2 算法测试和分析
• 5.2.1 算法在census数据库上的测试
• 5.2.2 算法在accidents数据库上的测试
• 5.2.3 算法测试结果分析
• 5.3 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的论文和取得的科研成果
• 致谢