基于FP-树的最大频繁模式挖掘算法研究

【作者】 冯志新；

【导师】 钟诚；

【作者基本信息】 广西大学 ， 控制理论与控制工程， 2003， 硕士

【摘要】 从大型数据库中挖掘关联规则是数据挖掘领域中非常重要的研究课题。其中，最大频繁模式挖掘问题在关联规则挖掘任务中扮演着重要的角色，具有广泛的应用前景。 FP-树是算法FP-growth中提出的新的数据结构。借助于FP-树结构，算法FP-growth采用不同于Apriori系列算法的候选产生测试方法而采取模式增长方法挖掘频繁模式，取得了很好效果。 本文主要在以下几个方面对基于FP-树的最大频繁模式挖掘问题进行研究：第一是提出了基于FP-树的最大频繁模式挖掘算法FP-Max。在该算法中，我们首先介绍了FP-树的定义和构造过程，并分析了基于FP-树进行挖掘的可行性和完整性；然后我们提出基于FP-树的最大频繁模式挖掘算法FP-Max，试验表明算法FP-Max在挖掘密集型、频繁模式较长的大数据集时是有效的。第二是提出FP-树驻留磁盘的最大频繁模式挖掘算法FP-Max-Disk。算法FP-Max运行的前提是构造的FP-树能够驻留内存，但是当事务数据库TDB很大或者设置的最小支持度阀值min＿sup很小时，那么构造驻留内存的FP-树将是不现实的。为此，我们首先将原事务数据库TDB划分为一系列投影数据库，然后将每个投影数据库构造为能够装入内存的条件FP-树，最后基于这些条件FP-树挖掘最大频繁模式。第三是研究探讨了基于FP一树的最大频繁模式并行挖掘问题。借助于多局部频繁模式树和并行投影技术，本文提出了两种基于共享内存计算模型的最大频繁模式并行挖掘算法。根据理论分析，这两种并行算法在采用了新的数据结构和简单的动态负载平衡技术后，可以实现各处理器独立异步运行、较小的1／O开销以及良好的负载平衡。更多还原