李少华，吕志旺，车德勇，周　宁

(1.东北电力大学能源与动力工程学院，吉林 吉林 132012；2.东北电力大学信息工程学院，吉林 吉林 132012)

基于有序FP-tree的最大频繁项集挖掘算法

李少华1，吕志旺2，车德勇1，周宁2

(1.东北电力大学能源与动力工程学院，吉林 吉林 132012；2.东北电力大学信息工程学院，吉林 吉林 132012)

[摘要]通过分析有序FP-tree与MFI之间的关联关系，提出一种高效的MFI挖掘算法(MMFI)，使其在挖掘过程中不但避免了条件频繁模式树的构建，也省略了超集检测的过程.提出了两种预剪枝策略，该策略能够有效地缩短算法执行的时间复杂度.结合理论分析和实验数据发现MMFI算法比传统算法快速、合理.

[关键词]数据挖掘；FP-tree；最大频繁项集；关联规则

0引言

R.Agrawal和R.Srikant[1]提出了为布尔型关联规则挖掘频繁项集的Apriori算法.随后J.Han[2]将所要挖掘的事务数据库DB转化为FP-tree 结构，并设计了FP-Growth算法.FP-Growth和Apriori都是用于发现事务数据库中的全部频繁项，造成了算法的执行过程耗时较长.因此提出将挖掘频繁项集的问题转化为挖掘MFI.一方面是由于MFI集合中包括了所有的频繁项；另一方面由于MFI的数量远远低于频繁项的数量.然而，目前对于MFI的挖掘过程普遍存在以下问题：(1)需要递归构建条件模式树，增加了算法的时间复杂度；(2)算法对每次求出的频繁项需要检测其是否为MFI(超集检测).在项集数量较大、事务条数较多的情况下，以上2个问题的耗时会占整个挖掘过程的绝大部分时间，因此降低了算法的执行效率.

本文通过对文献[3]提出……