基于频繁模式树的最大频繁项目集挖掘算法研究

摘要

随着互联网技术的快速发展，数据挖掘领域受到了越来越多的关注。关联规则一直是该领域的研究热点，主要是为了发现数据之间的关联以及有趣的模式。挖掘最大频繁项目集作为关联规则的一个重要的研究内容，它不仅已经涵盖了所有的频繁项目集，而且某些数据挖掘应用仅需挖掘最大频繁项目集，因此挖掘最大频繁项目集意义重大。本文从三方面对最大频繁项目集挖掘算法进行研究，分别是对候选项目集降维的研究，超集检测方法的研究以及增量式更新算法的研究。
　　首先，为了解决算法DMFIA（Discover Maximum Frequent Itemsets Algorithm）中初始候选项目集维数较高且挖掘较短最大频繁项目集效率低下的问题，提出了一种改进的基于频繁模式树FP-Tree（Frequent Pattern Tree）的最大频繁项目集挖掘算法FP-EMFIA（Algorithm for Efficiently Mining Maximum Frequent Itemsets Based on FP-Tree）。该算法采用自上而下和自下而上的双向搜索策略，并对条件模式基中项目的计数特点进行了分析，将一定包含或一定不包含在最大频繁项目集中的项目进行过滤，从而降低候选项目集的初始值维数。并利用挖掘出的较短的非频繁项目集对候选项目集进行剪枝，从而提高算法的效率。
　　其次，为了解决最大频繁项目集挖掘算法中超集检测次数过多的问题，提出了一种基于索引链表的超集检测算法IL-SC（Superset Checking Algorithm Based on Index List）。该算法采用索引链表的存储结构，使得最大频繁项目集的存储变得有序化，减少不必要的超集检测操作，从而提高超集检测的效率。
　　最后，在FP-EMFIA的基础上，提出了一种增量式更新算法FP-EUMFIA（Update Maximum Frequent Itemsets Algorithm Based on FP-EMFIA），以便高效利用之前挖掘出的结果。这样，能够大幅度降低初始候选项目集的维数，整体上提高算法的执行效率。