基于FP-Tree的最大频繁项集挖掘算法研究

摘要

关联规则作为数据挖掘的重要研究领域之一，主要解决的是数据之间的关联和许多其他有趣的模式。最大频繁项集挖掘算法作为关联规则算法中的一类经典算法，包含了所有的频繁项集的信息，而且某些数据挖掘应用仅需挖掘最大频繁项集。因此挖掘最大频繁项集具有十分重要的意义。但是经典的最大频繁项集挖掘算法存在一些问题:递归地产生大量条件频繁模式树;每次存储当前挖掘出的频繁项集之前都需要超集检验;更新数据库后需要重新运行挖掘算法。
　　 本文在广泛查阅国内外关联规则挖掘算法基础上，针对算法的空间效率和时间效率，提出了三方面的改进，并通过实验验证。本文的主要研究内容如下:
　　 (1)提出了单向有序的FP-Tree(OWSFP-Tree)。主要研究了OWSFP-Tree的性质、构建流程以及构造实例。另外，通过和传统的FP-Tree比较，我们可以发现该树具有以下优点:a）节约了空间资源;b）减少了算法递归的次数;c）为避免每次存储当前挖掘出的频繁项集之前都需要超集检验提供基础。
　　 (2)提出了基于OWSFP-Tree和项目表格的最大频繁项集挖掘算法(NCFP-Max算法)。主要研究了NCFP-Max算法的性质、策略、算法流程以及算法实例。通过实验验证在相同的环境下NCFP-Max算法的挖掘时间比FP-Max算法减少了50％左右。
　　 (3)提出了基于降维的最大频繁项集增量式更新算法。主要针对的是偶然间向事务数据库中增加新的数据集时，如何利用已经生成的最大频繁项集和OWSFP-Tree产生新的最大频繁项集。提出了基于降维的最大频繁项集的增量式更新算法的性质、算法过程以及算法实例，通过实验证明当事务数据库增加新的数据集时（新增加的数据集小于原事务数据集），基于降维的最大频繁项集增量式更新算法的挖掘时间要优于FP-Max和NCFP-Max算法。
　　 最后，论文对所做工作进行了总结，并提出了未来的研究方向。

目录

声明

摘要

第一章 绪论

1．1 研究背景

1．2 国内外研究现状

1．3 现有算法存在的问题

1．4 论文的研究内容和创新点

1．4．1 论文的研究内容

1．4．2 论文的创新点

1．5 论文的组织结构

第二章 数据挖掘的相关理论研究

2．1 数据挖掘

2．1．1 数据挖掘的过程

2．1．2 数据挖掘的功能

2．1．3 数据挖掘的国内外发展情况

2．2 关联规则

2．2．1 关联规则基本概念

2．2．2 关联规则的分类

2．3 关联规则挖掘算法

2．3．1 基于候选项集的Apriori算法

2．3．2 基于Apriori算法的改进算法

2．3．3 基于FP-Tree的FP-Growth算法

2．4 本章小结

第三章 最大频繁项集挖掘算法与改进的FP-Tree的研究

3．1 相关概念和FP-Max算法

3．1．1 相关概念

3．1．2 FP-Max算法

3．2 OWSFP-Tree的研究

3．2．1 OWSFP-Tree的相关理论基础

3．2．2 OWSFP-Tree的构建过程

3．2．3 OWSFP-Tree的构建实例

3．3 本章小结

第四章 基于项目表格的最大频繁项集挖掘算法

4．1 算法概述

4．1．1 相关定理

4．1．2 挖掘策略

4．1．3 算法描述

4．2 算法实例

4．3 NCFP-Max算法性能测试

4．4 本章小结

第五章 基于降维的最大频繁项目集更新算法

5．1 增量式更新算法的概述

5．1．1 增量式更新算法的分类

5．1．2 增量式更新算法的研究现状

5．1．3 FUP算法

5．2 基于降维的增量式更新算法

5．2．1 相关性质

5．2．2 算法流程

5．3 算法实例

5．4 算法分析

5．5 本章小结

第六章 总结和展望

6．1 本文工作总结

6．2 未来工作展望

参考文献

致谢

攻读硕士学位期间参加的科研项目

攻读硕士学位期间发表的学术论文目录