基于单向FP-树的最大频繁项集挖掘

摘要

数据挖掘是一门新兴的交叉学科，涉及到数据库技术、机器学习、统计学、模式识别、神经网络、人工智能、数据可视化等多个领域。目前它已成为数据库研究中最活跃、最令人兴奋的领域之一。 关联规则是数据挖掘研究中一个重要的研究课题，其主要的研究目的是从大型数据库中发现属性间存在的隐藏的、有趣的关系。频繁项集挖掘是关联规则挖掘的第一步，也是影响总体性能最关键的一步。因此，本文的研究重点放在了频繁项集挖掘上，研究内容主要包括以下几个部分： 1．深入研究了两个频繁项集挖掘算法。一个是经典FP-growth算法，它是基于FP-树的无候选项集产生算法，开辟了有效挖掘频繁模式的新途径。另一个是范明提出的基于单向FP-树的频繁项集挖掘算法，该算法在挖掘过程中不生成条件模式树。本文对比分析了FP-树和单向FP-树两种树结构，总结了FP-growth算法存在的问题，以及单向FP-树及其算法的优势。 2．在第一部分研究的基础上，参考最大频繁项集挖掘算法FP-Max，设计了基于单向FP-树的最大频繁项集挖掘算法Unid_FP-Max。该算法是一个深度优先算法。从算法分析和实验比较显示：对于密集型数据，Unid FP-Max算法在时间和空间开销上均小于FP-Max算法。 3．参考频繁闭项集挖掘算法CLOSET，设计了基于单向FP-树的频繁闭项集挖掘算法Unid FP-FCI。该算法是一个深度优先算法。经初步分析可知：Unid FP-FCI算法的效率会优于CLOSET算法。

目录

文摘

英文文摘

关于学位论文独立完成和内容创新的声明及著作权使用授权书

第1章绪论

1.1数据挖掘和关联规则概述

1.1.1数据挖掘

1.1.2关联规则

1.2频繁项集挖掘概述

1.2.1挖掘频繁项集的经典算法

1.2.2频繁项集挖掘存在的问题

1.3最大频繁项集与频繁闭项集挖掘概述

1.3.1挖掘最大频繁项集的经典算法

1.3.2挖掘频繁闭项集的经典算法

1.3.3最大频繁项集、频繁闭项集和频繁项集之间的关系

1.4本文的主要研究内容

1.4.1 FP-树与单向FP-树对比

1.4.2最大频繁项集挖掘算法Unid_FP-Max

1.4.3频繁闭项集挖掘算法Unid_FP-FCI

1.5本章小结

第2章FP-树和单向FP-树

2.1 FP-树与FP-growth算法

2.1.1频繁项集

2.1.2 Apriori类算法挖掘频繁项集存在的问题

2.1.3 FP-树

2.1.4 FP-growth算法

2.1.5 FP-growth算法的贡献

2.2单向FP-树与基于被约束子树的挖掘算法

2.2.1单向FP-树

2.2.2基于被约束子树的频繁项集挖掘算法

2.3 FP-树与单向FP-树对比

2.3.1 FP-growth算法存在的问题

2.3.2单向FP-树的优点

2.4本章小结

第3章基于单向FP-树的最大频繁项集挖掘算法

3.1基于FP-树的最大频繁项集挖掘算法

3.1.1基础理论

3.1.2基于FP-树的最大频繁项集挖掘算法

3.2基于单向FP-树的最大频繁项集挖掘算法

3.2.1基础理论

3.2.2 Unid_FP-Max算法

3.2.3算法分析和实验对比

3.3本章小结

第4章基于单向FP-树的频繁闭项集挖掘算法

4.1基于FP-树的频繁闭项集挖掘算法

4.1.1基础理论

4.1.2 CLOSET算法

4.2基于单向FP-树的频繁闭项集挖掘算法

4.2.1基础理论

4.2.2 Unid_FP-FCI算法

4.3本章小结

总结与展望

致谢

参考文献

攻读硕士学位期间发表的论文及参加的科研项目