作者：Mai Shawkat, Mahmoud Badawi, Sally El-ghamrawy, Reham Arnous, Ali El-desoky

发表期刊：The Journal of Supercomputing

发表日期：2021年

一、背景

关联规则挖掘定义与重要性
关联规则挖掘(ARM)是发现数据集关联的数据挖掘技术，通过支持度和置信度评估规则有效性。
传统算法及局限性
Apriori算法需多次扫描数据库，影响挖掘速度；复杂候选项生成导致过多项集产生，这两个问题是频繁项集挖掘(FIM)效率的瓶颈。
FP-growth算法的进步与问题
FP-growth压缩信息在树结构中，避免候选生成，但仍需递归构建条件FP树，消耗大量时间和内存。
大数据时代的挑战
数据爆炸式增长使传统算法适用性降低，直接从海量数据发现所需规则变得困难。

二、创新点

这篇论文提出了一种改进的FP-growth(MFP-growth)算法，旨在通过避免重复创建条件子树来提高FP-growth的效率。提出的算法使用头表配置来减少整个频繁模式树的复杂性。
MFP-growth算法的主要创新点：
1、使用地址表布局来表示MFP树中的频繁项集，这减少了MFP树的映射复杂性
2、提出了MFP树挖掘方法的结构，避免了构建条件模式基的需求，简化了MFP树的配置
3、与基于FP-growth的算法相比，通过使用头部地址表和FP-tree*，提出的算法具有更低的内存需求和更高的效率

三、MFP-growth算法

MFP-tree结构：
MFP-tree是一个前缀树，具有节点布局和频繁项地址表；包含三个字段：一个字段由频繁项的节点列表表示，而其他两个字段携带项目和每个节点在整个节点列表中的总频繁计数。它还维护项集之间的数据。
MFP-tree结构的主要优势：
1、无需像FP-growth那样重建条件FP树，节省了内存使用；
2、FP-tree的构建很快，因为不需要额外的成本来消除不频繁项。

1、首先通过扫描数据库一次找到频繁项集
2、降序排列项目频率
3、再次扫描数据库并构建MFP树
4、MFP-growth采用混合方法进行频繁项集挖掘。每当发现新的频繁项集时，频繁项集(P)就是输出
5、通过执行MFP-growth挖掘程序，从MFP-growth树中生成所有频繁项集
6、MFP树中探索的频繁项集使用”自下而上”的方法从最后到第一个

四、实验

实验一、分类器处理时间

实验使用了来自加州大学欧文分校(UCI)的12个不同数据集，包括Glass、Iris、Tic-tac、Breast、Zoo、Heart、Diabetes、Pima、Vote、Balance scale、Mushroom和Led。这些数据集具有不同的大小和类别数量。

实验评估了MFP-growth算法在分类任务中的性能，并与CBA和APR算法进行了比较。在所有实验中，最小支持度和最小置信度分别设置为2%和30%。

实验结果显示，MFP-growth在所有数据集上都比CBA和APR需要更少的分类器构建时间。这种性能优势主要归因于MFP-growth的剪枝程序，它避免了条件子树的生成。

虽然APR分类器比CBA需要较少的执行时间，但MFP-growth仍然显示了最佳性能，特别是在包含大量数据的”Mushroom”和”Led”数据集上。

实验二、执行时间评估

实验在Spark平台上评估了MFP-growth与PFP、PAPT-growth、DFIMA和YAFIM等最新频繁项集挖掘算法的性能，主要测试处理大规模数据库的执行时间。

实验使用了多种真实和合成数据集，包括Mushroom、Accidents、KddCup99、Kosarak(真实数据集)以及T10I4D100K和T40I10D100K(合成数据集)。

对于每个数据集，实验在不同的最小支持度水平下运行所有算法。结果显示，MFP-growth在所有数据集上都优于其他算法。基于MFP-tree的MFP-growth在频繁项集挖掘的时间成本上优于其他算法，即使在减少最小支持度的情况下也能提供有效的方法。

实验三、内存消耗评估

这个实验对比了六种频繁项集挖掘算法(MFP-growth、Apriori TID、H-Mine、Apriori、ECLAT和FP-growth)在Zoo数据集上的内存使用情况。

实验结果证明了MFP-growth算法在内存消耗方面的优越性。FP-growth在内存使用上次之，这是由于构建了紧凑小型的FP-tree。相比之下，Apriori和Apriori TID是内存使用最昂贵的算法，因为它们在每次传递期间需要存储大量候选生成并进行多次数据库扫描。

实验四、生成的关联规则数量

这个实验调查了社会安全事件的关联规则，比较了MFP-growth、PSOFP-growth、标准Apriori和FP-growth算法的性能，以确认MFP-growth算法的优越性并分析输出的关联规则。

实验结果显示，通过调整支持度值并使用数据过滤器来满足特定要求的关联规则，MFP-growth算法探索的关联规则比Apriori和FP-growth算法少约29%。

这种减少是由于删除了一些不相关的规则，从而减少了内存空间需求，使得从海量数据集中更容易找到有用的规则。

此外，实验还比较了算法的运行时间。

结果表明，MFP-growth算法比PSOFP-growth、Apriori和FP-growth传统算法需要更少的时间。支持度设置越高，算法的执行时间越短，表明支持度水平对算法性能有显著影响。在时间成本方面，使用MFP-tree的MFP-growth在关联规则挖掘上优于其他算法。

六、总结

这篇论文提出了一种新方案，用于发现数据集中各种关系的关联。此外，这篇论文还开发了一种改进的MFP-growth算法，通过结合FP-tree*挖掘方法和FP-growth的头表来发现频繁关联。

MFP-growth和MFP-tree的主要优势在于它们消除了重建条件模式基、子树的需求，并简化了树构建功能。

在不同类型数据集上的广泛工作流实验表明，MFP-growth明显改进了最近的挖掘速度FIM算法，以及在各种支持级别和置信度阈值下生成的关联规则。