赵 阳，吴廖丹

(江南计算技术研究所，江苏 无锡 214083)

一种自底向上的最大频繁项集挖掘方法

赵 阳，吴廖丹

(江南计算技术研究所，江苏 无锡 214083)

频繁项集挖掘是关联规则挖掘中最关键的步骤。最大频繁项集是一种常用的频繁项集简化表示方法。自顶向下的最大频繁项集挖掘方法在最大频繁项集维度远小于频繁项数时往往会产生过多的候选频繁项集。已有的自底向上的最大频繁项集挖掘方法或者需多次遍历数据库，或者需递归生成条件频繁模式树，而预测剪枝策略有进一步提升的空间。为此，提出了基于最小非频繁项集的最大频繁项集挖掘算法(BNFIA)，采用基于DFP-tree的存储结构，通过自底向上的方式挖掘出最小非频繁项集，利用最小非频繁项集的性质进行预测剪枝，以缩小搜索空间，再通过边界频繁项集快速挖掘出最大频繁项集。验证实验结果表明，提出算法的性能较同类算法有较为明显的提升。

最大频繁项集；关联规则挖掘；FP-tree；最小非频繁项集；边界频繁项集

0 引 言

关联规则挖掘的概念由Agrawal等于1993年提出[1-3]，用于发现大量数据中项目或项目集之间有趣的关联或相关关系，同时提出了经典的关联规则挖掘算法—Apriori。此后众多学者对Apriori算法进行了改进。但Apriori系列算法需要多次扫描数据集的固有缺陷，使其在处理大型数据集时面临无法容忍的时间开销。针对这一问题，Han等[4]提出用FP-tree对数据进行压缩存储以及基于FP-tree的频繁模式挖掘方法—FP-growth。该算法只需扫描数据集两次，避免了Apriori算法需多次扫描数据集的缺陷。……