关联规则学习 (ARL)：第二部分 - FPGrowth 算法
5.00/5 (5投票s)
如何使用 FPGrowth 算法执行 ARL。
目录
引言
在上一篇文章《关联规则学习 (ARL)：第 1 部分 - Apriori 算法》中，我们讨论了 Apriori 算法，它能够基于寻找统计趋势和洞察的过程，快速有效地执行关联规则挖掘，例如特定项目在给定交易集中出现的概率，以及从一个或多个实时数据流中获取的数据所表现出的其他模式。
具体来说，使用 Apriori 算法进行关联规则挖掘完全依赖于填充大量新规则候选的过程，这些候选基于已存在的规则集生成，并通过使用各种指标（如“支持度”或“置信度”）来确定每个新规则的“兴趣度”。显然，新规则候选的生成是一个复杂的计算任务，因为随着数据集潜在大小的成比例增加，执行的操作数量呈指数级增长。此外，根据 Apriori 算法，新的关联规则是基于特定项目集而不是交易集进行挖掘的。通常，项目集的大小比交易集本身更大。这使得关联规则挖掘过程消耗更多的 CPU 和系统内存资源。这是 Apriori 和 ECLAT 关联规则学习算法的主要缺点。
事实上，Apriori 和 ECLAT 算法（最初由 Agrawal 和 Srikant 提出）与经典的暴力算法相比，可以将关联规则挖掘过程的计算复杂度降低到仅 \(\begin{aligned}O(|i|^2)\end{aligned}\)，其中 \(\begin{aligned}|i|\end{aligned}\) 是集合中所有事务中唯一项目的总数。
为了在潜在的巨大数据集中执行高效的关联规则挖掘，我们需要一个不同的算法，而不是上面提到的那些算法。
FPGrowth（频繁模式增长）是著名的 Apriori 和 ECLAT 算法的另一个替代方案，它进一步降低了关联规则挖掘过程的计算复杂度。根据 FPGrowth 算法，我们不再需要通过迭代给定数据集 k 次来生成新规则候选集。相反，我们将构建一个紧凑的层次数据结构，称为“FP-Tree”，然后通过执行简单的“深度优先”搜索，基于“分而治之”的方法直接从 FP-Tree 中提取频繁项集。
使用 FP-Tree 数据结构的主要优点是它保留了用于频繁模式挖掘的整个数据，从不对现有数据进行任何修改，也从不截断任何交易的长模式。此外，FPGrowth 允许通过仅从 FP-Tree 中过滤出最频繁的模式来消除最不频繁的项和项集。FP-Tree 中的所有模式都按频率降序排列，这极大地降低了频繁模式提取过程的复杂性。
由于上述多项优化，FPGrowth 算法提供了关联挖掘过程的完整计算复杂度，可以估计为 \(\begin{aligned}p≤O(2*|T|^2+|T|)≤O(|i|^2)\end{aligned}\)，其中 \(\begin{aligned}|T|\end{aligned}\) 是正在处理的事务总数。这是算法两个阶段的总复杂度，例如构建 FP-Tree \(\begin{aligned}O(2*|T|^2 )\end{aligned}\) 或执行频繁模式挖掘 \(\begin{aligned}O(|T|)\end{aligned}\)。请注意，事务总数 \(\begin{aligned}|T|\end{aligned}\) 通常远小于正在处理的特定项数 \(\begin{aligned}|i|\end{aligned}\)，即 \(\begin{aligned}|T|≪|i|\end{aligned}\)。
然而，FPGrowth 算法主要用于对存储在数据库中的数据进行关联规则挖掘，而不是对从实时数据流中获取的数据进行分析。为了解决以下问题，我们将讨论如何将实时数据流转换为规范数据库，该数据库可以用作关联规则挖掘过程（即 FPGrowth 算法）的输入数据集。
在本文中，我们将阐述原始的 FPGrowth 算法，并讨论其使用 C++11 编程语言的实现。
背景
将实时数据流转换为规范数据库
为了能够使用 FPGrowth 算法对数据进行关联规则挖掘，我们首先必须将实时数据流转换为规范数据库，如下所示：
假设我们有一个从实时数据流中获取的事务集 \(\begin{aligned}T={t_1,t_2,t_3,...,t_(n-1),t_n }\end{aligned}\)。
| TID | 事务 |
| 1 | 引擎、车辆、转向、CPU、刹车、主板、机器、电器 |
| 2 | CPU、车轮、油箱、主板、座椅、摄像头、冷却器、电脑、机器、电器 |
| 3 | 主板、转向、显示器、刹车、引擎、车辆、机器、电器 |
| 4 | CPU、转向、刹车、冷却器、显示器、GPU、电脑、机器、电器 |
| 5 | 车辆、冷却器、CPU、转向、刹车、车轮、油箱、引擎、机器、电器 |
| 6 | 电脑、CPU、主板、GPU、冷却器、引擎、机器、电器 |
| 7 | 刹车、车辆、油箱、引擎、CPU、转向、机器、电器 |
| 8 | 钢笔、墨水、铅笔、书桌、打字机、刷子、办公室、电器 |
| 9 | 墨水、打字机、铅笔、书桌、办公室、电器 |
以及一组预定义的类别 \(\begin{aligned}C={c_1,c_2,c_3,…,c_(m-1),c_m}\end{aligned}\)，如下所示
| ID | 类 |
| 1 | 电器 |
| 2 | 机器 |
| 3 | 车辆 |
| 4 | 电脑 |
| 5 | Office |
整个事务集必须转换为规范数据库，格式如下：
| TID | 事务 |
| 1 | 电器、机器、车辆、CPU、刹车、引擎、主板、转向 |
| 2 | 电器、机器、电脑、CPU、主板、冷却器、GPU、油箱、车轮、摄像头、座椅 |
| 3 | 电器、机器、车辆、刹车、引擎、主板、转向、显示器 |
| 4 | 电器、机器、电脑、CPU、刹车、主板、转向、冷却器、GPU、显示器 |
| 5 | 电器、机器、车辆、CPU、刹车、引擎、转向、冷却器、油箱、车轮 |
| 6 | 电器、机器、电脑、CPU、引擎、主板、冷却器、GPU |
| 7 | 电器、机器、车辆、CPU、刹车、引擎、转向、油箱 |
| 8 | 电器、办公室、书桌、墨水、铅笔、打字机、刷子、钢笔 |
| 9 | 电器、办公室、书桌、墨水、铅笔、打字机 |
正如您从上图可以看到的，规范数据库与“原始”数据流非常相似，唯一的区别是每个事务的项集中的特定项按其出现频率降序排序。在这种情况下，出现频率估计为特定项在以下事务集中出现的次数。
为了执行以下转换，我们必须使用如下算法：
- 找到出现在每个事务 \(\begin{aligned}t_s \in T\end{aligned}\) 的项集 \(\begin{aligned}I=\{\forall i_k | i_k \in t_s, t_s \in T\};\end{aligned}\) 中的项集；
- 计算项集 \(\begin{aligned}I=\{(\forall i_k,count(\forall i_k )) | i_k \in t_s,t_s \in T\};\end{aligned}\) 中每个项 \(\begin{aligned}\forall i_k\end{aligned}\) 的出现频率；
- 将项集 \(\begin{aligned}I\end{aligned}\) 中的所有项 \(\begin{aligned}\forall i_k \in I\end{aligned}\) 按其出现频率降序排列；
- 对于每个“类别” \(\begin{aligned}\forall c_j \in C\end{aligned}\)，在 \(\begin{aligned}I\end{aligned}\) 中找到所有代表该“类别”的项，并将它们添加到项集 \(\begin{aligned}I_c=\{(\forall i_k,count(\forall i_k )) | i_k=c_j,c_j \in C\};\end{aligned}\) 中；
- 从 \(\begin{aligned}I\end{aligned}\) 中修剪所有代表“类别”的项 \(\begin{aligned}\forall i_k \in I_c \in I;\end{aligned}\)；
- 将代表“类别”的项集 \(\begin{aligned}\forall i_k \in I_c\end{aligned}\) 按出现频率降序排列；
- 将包含类别的项集 \(\begin{aligned}I_c\end{aligned}\) 附加到项集 \(\begin{aligned}I\end{aligned}\) 的顶部 \(\begin{aligned}(I \leftarrow I_c);\end{aligned}\)；
- 对于每个事务 \(\begin{aligned}t_s \in T\end{aligned}\) 的项集，将所有项按 \(\begin{aligned}I\end{aligned}\) 中频率降序排列；
根据上面列出的算法，我们首先必须找到一个项集 I，其中包含从每个事务 \(\begin{aligned}t_s \in T\end{aligned}\) 的项集中检索到的所有项。与 Apriori 算法不同，我们不仅需要检索“唯一”项，还需要检索那些在多个事务项集中出现的项，然后计算每个检索到的特定项在 T 中的出现频率。在执行完特定计算后，项集 I 将包含“项 - 计数”对值。在算法讨论期间，我们将考虑以下出现频率将代表每个项的“支持计数”指标。最后，我们必须按支持计数降序对项集 I 进行排序。例如：根据上面列出的算法，我们首先必须找到一个项集 I，其中包含从每个事务 \(\begin{aligned}t_s \in T\end{aligned}\) 的项集中检索到的所有项。与 Apriori 算法不同，我们不仅需要检索“唯一”项，还需要检索那些在多个事务项集中出现的项，然后计算每个检索到的特定项在 T 中的出现频率。在执行完特定计算后，项集 I 将包含“项 - 计数”对值。在算法讨论期间，我们将考虑以下出现频率将代表每个项的“支持计数”指标。最后，我们必须按支持计数降序对项集 I 进行排序。例如：
| TID | 事务 |
| 1 | 引擎、车辆、机器、电器 |
| 2 | CPU、主板、座椅、电脑、机器、电器 |
| 3 | 转向、刹车、引擎、车辆、机器、电器、主板 |
| 4 | CPU、冷却器、显示器、GPU、电脑、机器、电器、转向 |
| 5 | 打字机、办公室、铅笔 |
| … | … |
| ID | 项目 | 支持度计数 |
| 1 | 电器 | 4 |
| 2 | 机器 | 4 |
| 3 | 车辆 | 2 |
| 4 | 电脑 | 2 |
| 5 | Office | 1 |
| 5 | Engine | 2 |
| 6 | CPU | 2 |
| 7 | 座位 | 1 |
| 8 | 转向 | 2 |
| 9 | 刹车 | 1 |
| 10 | 冷却器 | 1 |
| 11 | 显示器 | 1 |
| 12 | GPU | 1 |
| 13 | 主板 | 2 |
| 14 | 打字机 | 1 |
| 15 | 铅笔 | 1 |
为了获得上图所示的项集，我们必须遍历类别集 C，并为每个类别在项集 \(\begin{aligned}I\end{aligned}\) 中找到当前类别 \(\begin{aligned}(\forall i_k,count(\forall i_k )) | \forall i_k=c_j\end{aligned}\) 的所有出现。然后，我们将每个类别出现添加到项集 \(\begin{aligned}I_c\end{aligned}\) 中，并从项集 \(\begin{aligned}I\end{aligned}\) 中删除每个出现 \(\begin{aligned}\forall i_k \in I_c \in I\end{aligned}\)。此外，我们必须按出现频率降序对新项集 \(\begin{aligned}I_c\end{aligned}\) 进行排序。
由于我们已经从项集 \(\begin{aligned}I\end{aligned}\) 中过滤掉了所有类别，现在我们可以通过将项集 \(\begin{aligned}I_c\end{aligned}\) 附加到项集 \(\begin{aligned}I\end{aligned}\) 的顶部来简单地合并这两个项集 \(\begin{aligned}I\end{aligned}\) 和 \(\begin{aligned}I_c\end{aligned}\)。这通常是为了优先处理那些代表类别的项，这些项必须首先出现在每个事务项集 \(\begin{aligned}t_s\end{aligned}\) 中。
数据流转换过程实际上是一个多维任务。执行以下任务通常会导致获得各种数据集，其中项按其特定顺序排列。由于我们只对获得下面所示的一个结果数据集感兴趣，因此我们定义了一组类别 C，以减少以下任务的维度，从而使以下过程更加有限。
最后，我们必须遍历事务集 \(\begin{aligned}T\end{aligned}\)，对于每个事务 \(\begin{aligned}t_s\end{aligned}\)，我们必须通过按频率降序对其项集中的项进行排序来重新排列它们，使其完全匹配 \(\begin{aligned}I\end{aligned}\) 中项的顺序。为此，我们遍历项集 \(\begin{aligned}I\end{aligned}\)，并对每个项执行线性搜索，以查找当前事务 \(\begin{aligned}t_s\end{aligned}\) 中项 \(\begin{aligned}\forall i_k\end{aligned}\) 的位置。找到位置值后，我们必须将该位置的项与事务项集开头下一个位置的项进行交换。对于每个事务 \(\begin{aligned}t_s \in T\end{aligned}\)，都会执行以下计算。通过执行这些计算，我们将获得以下事务规范数据库：
| TID | 事务 |
| 1 | 电器、机器、车辆、引擎、座椅 |
| 2 | 电器、机器、电脑、CPU、主板、座椅 |
| 3 | 电器、机器、车辆、引擎、转向、主板、刹车 |
| 4 | 电器、机器、电脑、CPU、转向、冷却器、显示器 |
| 5 | 办公室、打字机、铅笔 |
| … | … |
FPGrowth 算法
在这一段中，我们将简要介绍 FP-Growth 算法的一种变体，并详细讨论其一些阶段和特征。正如我们之前已经讨论过的，FPGrowth 算法作为著名的 Apriori 和 ECLAT 算法的替代方案，为关联规则挖掘过程提供了更高的效率。
该算法不再执行广度优先遍历来生成所有可能的关联规则候选，而是允许构建一个紧凑的数据结构，称为 FP-Tree，并直接从树中提取最有趣和最有意义的关联规则，使整个规则挖掘过程更加智能。以 FPGrowth 算法形式化的关联规则挖掘的整个过程基本上分为两个主要阶段：
- 构建一个紧凑的层次数据结构，称为 FP-Tree；
- 直接从树中提取有趣的关联规则；
在第一阶段，我们将根据存储在给定事务集中的数据构建特定的 FP-Tree。以下阶段的主要目的是揭示事务数据上表现出的所有最频繁模式，并且显然，构建一个 FP-Tree，表示特定项目与挖掘到的最频繁模式之间的关系。我们将“模式”视为在给定事务集中最频繁出现的项目的一个特定子集。与其他算法类似，FPGrowth 完全依赖于这样的假设：根据反单调性原则，与数据集中最频繁模式一起出现的项目也是最频繁的。特定频繁模式与其他项目的组合假装成为最有趣的关联规则的候选。
在接下来的过程中，我们实际上将从特定的事务集中过滤掉所有最频繁的模式，并将它们映射到 FP-Tree 上的特定路径，以便在此过程结束时，所有最频繁的模式都位于树的根部附近。根据 FP-Tree 构建算法，这些频繁模式节点与其他项目（即 FP-Tree 的“叶子”）相互连接。
正如您可能已经知道的，整个关联规则挖掘算法类最明显的问题是，在执行关联规则挖掘时，用于决策过程的信息可能“缺乏”。这正是为什么我们通常需要通过互连特定的相似项来扩展已构建的 FP-Tree，这使得后续的计算过程更加灵活。此外，我们使用一组预定义的类来降低此过程的维度，使其更快、更有限。事实上，构建的 FP-Tree 实际上是专门用于关联规则挖掘的决策树的一种变体。
我们认为构建的 FP-Tree 是一种紧凑的数据结构，因为我们从不扩展以下树的水平宽度，这可能会导致不可预测的挖掘结果。相反，我们“增长”以下树的高度，使其垂直“高大”，以便在执行此过程结束时，我们获得一个完整的 FP-Tree，可以可靠地用于直接从树中提取最有趣的关联。
与其他算法一样，FPGrowth 主要基于每个模式的支持度计数估计。具体来说，我们只提取那些支持度计数超过特定阈值样本值的模式。与 Apriori 和 ECLAT 不同，我们不使用“置信度”或其他指标，而是使用 FPGrowth 算法的“支持度”指标。这使我们能够大大简化有趣规则的挖掘过程。
基于压缩到 FP-Tree 中的数据提取有趣的关联规则是 FPGrowth 的另一个阶段，在此阶段我们将执行简单的“深度优先”搜索，使用支持度计数指标来查找所有最有趣和最有意义的规则。在此阶段，我们使用“分而治之”的方法对 FP-Tree 节点进行全面遍历。与传统的“深度优先”搜索不同，我们执行所谓的“自下而上”遍历，从代表特定类别的节点开始，以查找所有属于特定类别的子集。最后，我们将所有找到的子集合并到给定类别的整个项目集中。
在本文接下来的段落中，我们将详细讨论上面简要介绍的所有 FPGrowth 算法阶段。
步骤 1：构建 FP-Tree
在这一段中，我们将讨论如何构建一个紧凑的数据结构，称为“FP-Tree”，以层次化地表示最频繁的关联规则模式。在此过程中，我们将主要处理整个事务集 T，而不是前几段中讨论的包含该事务集中所有项的项集 I。
FP-Tree 是一个有向无环图 G=(P,E)，其中 P 是树的“节点”集，每个节点代表一个特定的“前缀”或“项”，E 是连接特定“节点”形成层次树的“边”集。那些没有“子”节点的“节点”称为“叶子”，代表与特定“前缀”关联的特定“项”。
为了找出那些前缀具体是什么，让我们仔细看看上面显示的事务集。“前缀”是项目的一个子集，它在多个事务项目集的开头部分重叠。
例如，事务 t_1={"Appliances","Machines","Vehicle","Engine","Seats"} 和 t_3={"Appliances","Machines","Vehicle","Engine","Steering","Motherboard","Brakes"} 有一个重叠的子集 {"Appliances","Machines","Vehicle","Engine"}，这被认为是这两个事务项集的共同“前缀”。
在讨论过程中，我们将演示如何构建一个“FP-Tree”，它可以表示为一组节点，每个节点都引用一个“父节点”和多个“相邻节点”。要构建这棵树，我们实际上必须使用以下算法从事务集 T 中检索所有前缀。
初始化
首先，我们必须初始化正在构建的 FP-Tree。为此，我们必须向集合中添加一个初始的“根”节点。与其他将要添加的节点不同，这个节点最初没有对“父节点”或“相邻节点”的引用。
之后，我们需要从集合 T 中检索第一个事务 t_1，并从之前添加的“根”节点开始，将每个项逐个附加到树中。这意味着对于事务 t_1 中的每个项，我们都会向树中添加一个特定的节点，该节点引用前一个项节点（即“父节点”）或一组后续项节点（即“相邻节点”）。此外，添加到树中的每个新节点都将具有特定的支持计数。最初，每个新节点的支持计数都等于 0。
在这种情况下，树中的每个节点将只有一个相邻节点，代表后续项节点。此外，我们必须创建一个单独的前缀集 P'，在其中存储通过向树中添加特定项节点而获得的每个前缀，如下表所示。在这种情况下，以下前缀与集合 P 中特定节点的索引相关联。P' 中的每个前缀都是通过将每个后续项与所有先前项连接而构建的，如下表所示。在这种特定情况下，节点索引实际上代表当前前缀的最后一个项的索引。此外，我们必须确保前缀集 P' 中没有重复项。重复的前缀被简单地修剪掉。
以下操作等同于创建项的双向链表。执行以下操作后，我们将获得以下树：
| ID | 前缀 | 物品编号 |
| 1 | 电器 | 1 |
| 2 | 电器，**机器** | 2 |
| 3 | 电器，机器，**车辆** | 3 |
| 4 | 电器，机器，车辆，**引擎** | 4 |
向 FP-Tree 添加新节点
由于我们已用第一个事务中的项初始化了树，我们必须遍历事务集 T，从第二个事务 t_2 开始，并对每个事务 t_s∈T 在前导事务子集中执行线性搜索，以找到与 t_s 具有最长公共前缀的事务 t_k。如果找到这样的事务 t_k，则我们在前缀集 P^' 中执行查找以找到该前缀，并获取一个特定节点的索引，所有其他新的非重叠项节点将附加到该节点。
最后，我们一个接一个地添加每个非重叠节点，类似于我们已经在初始化阶段所做的那样，从特定的前缀节点开始。否则，如果没有找到重叠的事务 t_k，那么我们直接将新节点附加到树的根节点。此外，对于已经发生过的重复事务，我们实际上不需要向树中添加新节点，而只需增加每个已存在节点的支持计数，如下面详细讨论的。
如何查找前缀
要查找两个或更多事务项集的前缀，我们必须使用以下算法。假设我们有两个事务项集 t_s 和 t_k。要查找前缀（如果存在），我们必须遍历 t_s 和 t_k 中的每个项，并检查 t_s 中的当前项是否等于 t_k 中的当前项。如果是，我们必须将 t_s 中的当前项入队到一个单独的前缀项集中，并处理下一对项，否则终止该过程。
在执行此操作结束时，前缀项集将包含在 t_s 和 t_k 项集中重叠（即存在）的所有项。检索到的以下项目子集被认为是这两个项集的前缀。此操作与查找两个项集 t_s∪t_k 的并集非常相似，唯一的区别是我们必须保留重叠项在两个项集中存在的顺序和方向。具体来说，我们从每个项集的开头查找两个项集的并集，因此 t_s 中的项必须与 t_k 中相等项的顺序匹配 (t_s⨃t_k)。
累积支持度计数
对于每个重叠的项节点，我们还必须将支持计数的值增加 1，通过从最后一个重叠项节点到树的根节点迭代每个重叠项节点。例如，如果“Appliances”和“Machines”这些重叠项节点的支持计数等于 1，那么在执行以下计算后，这些项中的每一个的支持计数将增加到 2，而其余所有非重叠项（如 Vehicle、Engine、Computer、CPU 等）的支持计数将等于 1。我们必须更新正在构建的数据模型，以便在执行这些计算结束时，完整 FP-Tree 的每个节点都将关联一个适当的支持计数。
交叉引用
正如您可能从上图已经注意到的，正在构建的 FP-Tree 也可能包含重复项，我们需要为这些重复项添加双向交叉引用。这通常通过迭代节点集 P 来完成，并对每个节点 ∀p_i 在后续节点子集中执行线性搜索以找到具有相同项值 ∀p_j 的节点。如果找到这样的节点，则我们将此节点 j 的索引添加到 ∀p_i 的相邻节点集，反之亦然。在这种情况下，执行这些计算的结果是，我们将获得以下树和一组特定的前缀：
| ID | 前缀 | 物品编号 |
| 1 | 电器 | 1 |
| 2 | 电器，**机器** | 2 |
| 3 | 电器，机器，**车辆** | 3 |
| 4 | 电器，机器，车辆，**引擎** | 4 |
| 5 | 电器、机器、车辆、引擎、**座椅** | 5 |
| 6 | 电器、机器、**电脑** | 6 |
| 7 | 电器、机器、电脑、**CPU** | 7 |
| 8 | 电器、机器、电脑、CPU、**主板** | 8 |
| 9 | 电器、机器、电脑、CPU、主板、**座椅** | 9 |
| 10 | Office | 10 |
| 11 | 办公室、**打字机** | 11 |
| 12 | 办公室、打字机、**铅笔** | 12 |
由于我们已完成 FP-Tree 的构建过程，我们将获得以下节点集：
| ID | 项目 | Parent | 相邻 | 支持度计数 |
| 1 | 根 | 0 | {2} | 0 |
| 2 | 电器 | 1 | {3} | 2 |
| 3 | 机器 | 2 | {4,5} | 2 |
| 4 | 车辆 | 3 | {6} | 2 |
| 5 | 电脑 | 3 | {8} | 2 |
| 6 | Engine | 4 | {7,11} | 2 |
| 7 | 座位 | 6,10 | {10} | 1 |
| 8 | CPU | 5 | {9,14} | 2 |
| 9 | 主板 | 8 | {10,12} | 1 |
| 10 | 座位 | 9 | {7} | 1 |
| 11 | 转向 | 6 | {12,14} | 1 |
| 12 | 主板 | 11 | {9,13} | 1 |
| 13 | 刹车 | 12 | {} | 1 |
| 14 | 转向 | 8 | {11,15} | 1 |
| 15 | 冷却器 | 14 | {16} | 1 |
| 16 | 显示器 | 15 | {} | 1 |
| 17 | Office | 1 | {18} | 1 |
| 18 | 打字机 | 17 | {19} | 1 |
| 19 | 铅笔 | 18 | {} | 1 |
既然我们已经成功构建了一个完整的 FP-Tree，在下一段中，我们将详细讨论如何使用这种层次数据结构，通过执行简单的“深度优先”搜索，根据表示为 FP-Tree 的数据模型，找到最有趣和最有意义的关联规则。
步骤 2：直接从 FP-Tree 中提取频繁模式
既然我们已经成功构建了 FP-Tree 并计算了事务集中每个特定项的支持计数，现在是时候从树中提取所有可能的频繁模式，以便能够找到那些有趣且有意义的关联规则。为此，我们必须遍历支持计数集 I_s，并为每个特定项在具有最大支持计数值的 P 集中找到对应的节点（即“叶子”）∀p_k。之后，从获得的特定项节点 ∀p_k 开始，我们必须通过“自下而上”迭代每个父节点来找到前缀路径，直到我们最终到达树的根节点。对于那些具有多个父节点的节点，我们选择支持计数值最大的节点。在每次迭代中，我们必须将特定项添加到表示最频繁前缀的项集中。
最后，既然已经找到特定的最频繁前缀，我们就必须从以下前缀项集中修剪掉所有不频繁的项。为此，我们必须将以下项集与类别集 C 合并。同时，我们必须找到合并集与通过执行“自下而上”遍历获得的前缀集的交集。代数上，这可以表示为 B=A∩(A∪C)，其中 A – 前缀项集，C – 类别集。
之后，对于 B 中的每个项，我们必须基于当前前缀 A 和当前项的值的连接来创建一个项子集 B^'。最后，我们必须计算项集 B 在事务集 T 中出现的次数的值，并检查该值是否小于最小支持计数阈值。最小支持计数值是一个样本常数比率值，对于通常巨大的数据集，它等于 supp_count{min}=0.07，即整个数据集的 7%。为了获得所需的支持计数值，我们只需将该比率乘以事务集 T 中的事务数量。
步骤 3：寻找有趣且有意义的关联规则
在构建 FP-Tree 并提取所有频繁模式（即频繁前缀）之后，是时候检索所有可能的关联规则了。在这种情况下，这通常通过合并在前面讨论的阶段中获得的所有项集来完成。为了合并所有获得的项集，我们必须遍历类别集 C，并对于每个类别 ∀c_i，找到所有包含当前类别的结果项集，并将它们添加到单独的结果集中。之后，我们只需找到所有这些项集的交集，并将它们合并到一个与当前类别关联的单个集中。最后，由于我们已经获得了合并的项集，我们必须将其添加到结果集中，在该结果集中，每个类别都映射到属于它的特定项集。上面讨论的算法阶段是最终阶段，执行之后我们无需执行任何额外的数据处理。
使用代码
// fpgrowth_cpp.cpp : This file contains the 'main' function.
// Program execution begins and ends there.
//
#include <iostream>
#include <vector>
#include <string>
#include <iterator>
#include <algorithm>
#include <fstream>
#include <omp.h>
#include <pstl algorithm="">
#include <pstl execution="">
#pragma warning(disable:2586)
std::string filename = "\0";
const std::string cs_filename = "classes.csv";
namespace utils {
std::vector<std::string> union_vec(
const std::vector<std::string>& v1,
const std::vector<std::string>& v2)
{
// Declare a resultant union vector
std::vector<std::string> union_vector;
// Iterate through the input vector v1
for (auto it = v1.begin(); it != v1.end(); it++)
// For each element in v1, find an element
// with the same value in the input vector v2
if (std::find_if(pstl::execution::par_unseq, v2.begin(), v2.end(), \
[&](const std::string& str) { return str == *it; }) != v2.end())
// If value of the current element in v1 is found in v2,
// then add this value to the resultant union vector
union_vector.push_back(*it);
// Return the vector of union elements
return union_vector;
}
std::vector<std::string> intersect_vec(
const std::vector<std::string>& v1,
const std::vector<std::string>& v2)
{
// Declare a resultant intersection vector
std::vector<std::string> intersect_vector;
// Find a union of two vectors v1 and v2
std::vector<std::string> union_vector = union_vec(v1, v2);
// Declare vector v and fill it with element of vector v1
std::vector<std::string> v(v1);
// Insert elements of vector v2 into vector v
v.insert(v.end(), v2.begin(), v2.end());
// Sort elements of the vector v
std::sort(pstl::execution::par_unseq, v.begin(), v.end());
// Prune all duplicate elements in vector v
v.erase(std::unique(pstl::execution::par_unseq, v.begin(), v.end()), v.end());
// Iterate through the vector v
for (auto it = v.begin(); it != v.end(); it++)
// For each element in v, find an element
// with the same value in the union vector
if (std::find_if(pstl::execution::par_unseq,
union_vector.begin(), union_vector.end(),
[&](const std::string& str)
{ return str == *it; }) == union_vector.end())
// If value of the current element in v is found
// in the union vector then add this value to
// the resultant intersection vector
intersect_vector.push_back(*it);
// Return the intersection vector
return intersect_vector;
}
std::vector<std::string> append_vec(
const std::vector<std::string>& v1,
const std::vector<std::string>& v2)
{
// Declare vector v and fill it with element of vector v1
std::vector<std::string> v(v1);
// Insert elements of vector v2 into vector v
v.insert(v.end(), v2.begin(), v2.end());
// Sort elements of the vector v
std::sort(pstl::execution::par_unseq, v.begin(), v.end());
// Prune all duplicate elements in vector v
v.erase(std::unique(pstl::execution::par_unseq, v.begin(), v.end()), v.end());
// Return the resultant vector v
return v;
}
};
namespace ARL
{
const std::double_t min_supp = 0.06;
// Declare a structure to hold a string value of
// class or item and its identifier
typedef struct tagFpTreeNode
{
std::uint64_t m_count;
std::string m_item;
std::vector<std::int64_t> m_parent;
std::vector<std::uint64_t> m_adj;
} FPTREE_NODE;
typedef struct tagFpPrefix
{
std::uint64_t m_leaf;
std::vector<std::string> m_prefix;
} FP_PREFIX;
typedef struct tagFpSuppCount
{
std::uint64_t m_count = 0L;
std::string m_item;
} FP_SUPP_COUNT;
typedef struct tagFpClassItem
{
std::string m_class;
std::vector<std::string> m_items;
} FP_CLASS_ITEM;
std::vector<std::string>
read_sl_csv_file(const std::string filename)
{
// Create an file input stream
std::ifstream ifs(filename, \
std::ifstream::in | std::ifstream::ate);
// Declare a vector of entities
std::vector<std::string> v_ent;
// Get the file size
std::size_t file_size = (std::size_t)ifs.tellg();
// Allocate a buffer to store the data from file
char* buf = (char*)malloc(++file_size);
// Read a single-line data from file
ifs.seekg(ifs.beg); ifs.getline(buf, ++file_size);
const char* delim = ",";
// Find first token in buffer
char* token = std::strtok(buf, delim);
// Extract all tokens separated by ',' character
while (token != nullptr)
{
std::uint32_t ci = 0L;
// Allocate buffer to store an entity data
char* m_value_buf = (char*)malloc(256 * sizeof(char));
// Extract the data from the entity formatted string
if (sscanf(token, "%[^:]:%d", m_value_buf, &ci) > 0)
{
// Add the entity object to the vector of entities
// and extract the next token from the string data
v_ent.push_back(std::string(m_value_buf));
token = std::strtok(nullptr, delim);
}
}
// Deallocate buffer and close the input file stream
free(buf); ifs.close();
// Return the resultant vector of entities
return v_ent;
}
std::vector<std::vector<std::string>> \
read_data_from_csv_file(const std::string filename)
{
// Declare a vector of transactions
std::vector<std::vector<std::string>> trans_v;
// Create an input file stream
std::ifstream ifs(filename, std::ifstream::in);
// Allocate buffer for each line of file
char* buf = (char*)malloc(sizeof(char) * 4096);
// Perform a check if this is not the end of file
while (ifs.eof() == false && ifs.peek() >= 0)
{
// Declare a tokens buffer
std::vector<std::string> tokens_v;
// Read the current line from file
const char* delim = ","; ifs.getline(buf, 4096);
// Extract the first token from the current string
char* token = std::strtok(buf, delim);
// Extract all tokens separated by ',' character
while (token != nullptr)
{
// Add the current token (i.e. item) to the vector of tokens
tokens_v.push_back(std::string(token));
// Extract the next token
token = std::strtok(nullptr, delim);
}
// Add all items in the current vector to the vector of transactions
trans_v.push_back(tokens_v);
}
// Deallocate buffer and close the input file stream
free(buf); ifs.close();
// Return the vector of transactions
return trans_v;
}
std::vector<std::string> fp_get_prefix(\
std::vector<std::string>& v1, \
std::vector<std::string>& v2)
{
std::uint64_t index = 0;
std::vector<std::string> fp_prefix;
// Iterate thorough the vectors of items
// For each pair of items perform a check if these items
// are identical. If so, append the current item from the
// first vector into the vector of prefix items, otherwise
// terminate the loop execution
while (index < v1.size() && \
index < v2.size() && (v1[index] == v2[index]))
fp_prefix.push_back(v1[index++]);
// Return a prefix found
return fp_prefix;
}
std::vector<std::string> get_items(
const std::vector<std::vector<std::string>>& T)
{
std::vector<std::string> items;
// Iterate through the set of transactions
for (auto it = T.begin(); it != T.end(); it++)
// For the current transaction append each item to the
// vector of items
items.insert(items.end(), it->begin(), it->end());
// Sort the resultant vector of items to find duplicates
std::sort(pstl::execution::par_unseq, items.begin(), items.end());
// Remove all duplicates from the resultant vector of items
items.erase(std::unique(pstl::execution::par_unseq,
items.begin(), items.end()), items.end());
// Return vector of items
return items;
}
std::vector<fp_supp_count> fp_get_supp_count(\
std::vector<std::string> fp_items, \
const std::vector<std::vector<std::string>>& T)
{
std::vector<fp_supp_count> fp_supp_count;
// Iterate through the set of items
for (auto it = fp_items.begin(); it != fp_items.end(); it++)
{
std::uint64_t count = 0L;
// For each current item iterate through the set of transactions
for (auto tr_it = T.begin(); tr_it != T.end(); tr_it++)
// Compute the number of items occurrences
// and accumulate this value in count variable
count += std::count_if(pstl::execution::par_unseq,
tr_it->begin(), tr_it->end(),
[&](const std::string& item) { return item == *it; });
FP_SUPP_COUNT fp_supp_item;
fp_supp_item.m_count = count;
fp_supp_item.m_item = std::string(*it);
// Add the support count for the current item
// to the vector of support counts
fp_supp_count.push_back(fp_supp_item);
}
// Sort the vector of support counts in the descending order
std::sort(pstl::execution::par_unseq,
fp_supp_count.begin(), fp_supp_count.end(),
[&](const FP_SUPP_COUNT& item1, const FP_SUPP_COUNT& item2) {
return (item1.m_count > item2.m_count);
});
// Return the vector of support counts
return fp_supp_count;
}
void fp_convert_stream(\
std::vector<fp_supp_count> fp_supp_counts, \
std::vector<std::vector<std::string>>& T, \
std::vector<std::string>& C)
{
std::vector<fp_supp_count> classes;
// Iterate through the input set of classes
for (auto it = C.begin(); it != C.end(); it++)
{
// Find the current class in the support count vector
auto c_it = std::find_if
(pstl::execution::par_unseq, fp_supp_counts.begin(), \
fp_supp_counts.end(), [&](const FP_SUPP_COUNT& fp_supp) {
return fp_supp.m_item == *it; });
// If the class is found
if (c_it != fp_supp_counts.end())
{
// Add the class to the separate vector of classes
classes.push_back(*c_it);
// Remove the entry of the current class
// from the vector of support counts
fp_supp_counts.erase(c_it);
}
}
// Sort vector of class entries in the descending order
std::sort(pstl::execution::par_unseq, classes.begin(), classes.end(),
[&](const FP_SUPP_COUNT& item1, const FP_SUPP_COUNT& item2) {
return (item1.m_count > item2.m_count);
});
// Insert the class entries vector to the top of the support counts vector
fp_supp_counts.insert(fp_supp_counts.begin(), \
classes.begin(), classes.end());
// Iterate through the vector of transactions
for (auto it = T.begin(); it != T.end(); it++)
{
std::uint64_t cpos = 0L;
// Iterate through the support counts vector
auto supp_it = fp_supp_counts.begin();
while (supp_it != fp_supp_counts.end())
{
// For each item in the support counts vector, find the following item
// in the vector of items for the current transaction
auto item_it = std::find(pstl::execution::par_unseq, it->begin(), \
it->end(), supp_it->m_item);
// If the item was found, swap this item with another item located
// at the next position from beginning of the current transaction set
if (item_it != it->end())
std::iter_swap(item_it, (it->begin() + cpos++));
supp_it++;
}
}
}
std::vector<fptree_node> fp_init_tree(\
std::string item, std::uint64_t count)
{
FPTREE_NODE node;
// Initialize the FP-Tree by adding the rooted item to the
// FP-Tree's nodes vector
node.m_count = count;
node.m_parent.push_back(-1L); node.m_item = std::string(item);
// Return the FP-Tree initialized
return std::vector<fptree_node>(1, node);
}
std::uint64_t fp_add_node(std::vector<fptree_node>& fp_tree, \
std::uint64_t parent, std::string item, std::uint64_t count)
{
FPTREE_NODE node;
// Construct a new node object
node.m_count = count;
node.m_parent.push_back(parent); node.m_item = std::string(item);
// Insert the following node object to the bottom of the FP-Tree constructed
auto it = fp_tree.insert(fp_tree.end(), node);
// Compute the index of the new node being inserted
std::uint64_t node_index = std::distance(fp_tree.begin(), it);
// Add the index to the vector adjacents of the parent node
fp_tree[parent].m_adj.insert(fp_tree[parent].m_adj.end(), node_index);
// Return the new node index
return node_index;
}
std::vector<fptree_node> fp_init(std::vector<fp_prefix>& fp_prefixes, \
const std::vector<std::vector<std::string>> T)
{
// Construct FP-Tree
std::vector<fptree_node> tree = \
std::vector<fptree_node>(fp_init_tree(std::string("null"), 0L));
FP_PREFIX fp_prefix;
// Construct a new prefix object
fp_prefix.m_leaf = 0;
fp_prefix.m_prefix.push_back(tree[0].m_item);
// Add the new prefix object to the vector of prefixes
fp_prefixes.push_back(fp_prefix);
fp_prefix.m_prefix = std::vector<std::string>();
std::uint64_t curr_node = 0;
// Iterate thorough the vector of the first transaction
for (auto it = T[0].begin(); it != T[0].end(); it++)
{
// For each item, construct a node object and append it to the tree
curr_node = fp_add_node(tree, curr_node, *it, 1L);
// Construct a new prefix object and add it to the vector of prefixes
fp_prefix.m_leaf = curr_node;
fp_prefix.m_prefix.push_back(*it);
fp_prefixes.push_back(fp_prefix);
}
// Return the initialized FP-Tree
return tree;
}
template<class _init="">
bool fp_is_duplicate_trans(_InIt _First, _InIt _Pos)
{
// Find a transaction in the subset of previous transactions
// If such transaction is found, then true, otherwise false
return std::find_if(pstl::execution::par_unseq, _First, _Pos - 1, \
[&](const std::vector<std::string>& trans) { \
return std::equal(pstl::execution::par_unseq, trans.begin(), trans.end(), \
_Pos->begin(), _Pos->end()); }) != _Pos - 1;
}
template<class _init="">::iterator>
_OutIt fp_find_prefix(_InIt _First, _InIt _Last, \
_PrefIt _PrefFirst, _PrefIt _PrefLast)
{
// Find a prefix in the vector of prefixes.
// If prefix is found, return the iterator of the following prefix
return std::find_if(pstl::execution::par_unseq,
_First, _Last, [&](FP_PREFIX fp_prefix) { \
return std::equal(pstl::execution::par_unseq,
fp_prefix.m_prefix.begin(), \
fp_prefix.m_prefix.end(), _PrefFirst, _PrefLast); });
}
template<class _init="">
bool fp_prefix_exists(_InIt _First, _InIt _Last, \
const FP_PREFIX fp_prefix)
{
// Find a prefix in the vector of prefix. If the prefix is found return true
return std::find_if(pstl::execution::par_unseq, _First, _Last, \
[&](FP_PREFIX fpp) { return std::equal(
pstl::execution::par_unseq, fpp.m_prefix.begin(), \
fpp.m_prefix.end(), fp_prefix.m_prefix.begin(), \
fp_prefix.m_prefix.end()); }) != _Last;
}
void fp_update_model(std::uint64_t leaf_n, \
std::vector<fptree_node>& fp_tree)
{
std::uint64_t fp_leaf = leaf_n;
// Iterate thorough each parent node in the FP-Tree
while (fp_tree[fp_leaf].m_parent[0] != -1)
{
// Increment the support count value for the current node by 1
fp_tree[fp_leaf].m_count++;
fp_leaf = fp_tree[fp_leaf].m_parent[0];
}
}
void fp_build_tree(\
std::vector<fptree_node>& fp_tree, \
std::vector<std::vector<std::string>> T)
{
std::vector<fp_prefix> fp_prefixes;
// Initialize the FP-Tree
fp_tree = fp_init(fp_prefixes, T);
// Iterate thorough the vector of transactions
for (auto it = T.begin() + 1; it != T.end(); it++)
{
// For each transaction perform a check if the current
// transaction is duplicate. If so, just update the support counts
// and proceed with the next transaction in the set
if (fp_is_duplicate_trans(T.begin(), it))
fp_update_model(fp_find_prefix(\
fp_prefixes.begin(), fp_prefixes.end(), \
it->begin(), it->end())->m_leaf, fp_tree);
else {
// If the current transaction is not duplicate,
// proceed with building the FP-Tree
std::size_t max_size = 0L;
std::uint64_t fp_leaf = 0L;
std::vector<std::string> prefix;
std::vector<std::string> ts = *it;
std::vector<std::string> curr_prefix;
std::int64_t index = it - T.begin();
// Iterate through the subset of preceeding transactions to
// find a transaction with the longest occurence of prefix that
// overlapps in both transactions
while (--index >= 0)
{
// Compute the prefix for a pair of transactions
curr_prefix = fp_get_prefix(*it, *(T.begin() + index));
// If the current prefix length is the maxima so far
if (curr_prefix.size() > max_size)
{
// Accumulate the current transaction length
max_size = curr_prefix.size();
prefix = curr_prefix;
}
}
// If the length of the current prefix found is more than zero
if (prefix.size() > 0)
// Find the node index for the current prefix
// in the vector of prefixes
fp_leaf = fp_find_prefix(fp_prefixes.begin(), \
fp_prefixes.end(), prefix.begin(), prefix.end())->m_leaf;
// Otherwise obtain the node index of the first prefix in the vector
else fp_leaf = fp_prefixes[0].m_leaf;
FP_PREFIX fp_prefix;
// Iterate thorough the vector of items for the current transaction
for (auto ts_it = ts.begin(); ts_it != ts.end(); ts_it++)
{
// Perform a check if the position of current item is greater than
// the length of the prefix or prefix size is equal to 0.
if ((ts_it >= ts.begin() + prefix.size()) || (prefix.size() == 0))
// If so, construct a new node object based on
// the value of current item and append it to the tree
fp_leaf = fp_add_node(fp_tree, fp_leaf, *ts_it, 0L);
fp_prefix.m_leaf = fp_leaf;
// Construct a new prefix object
fp_prefix.m_prefix.push_back(*ts_it);
// Perform a check if the prefix object already exists
if (!fp_prefix_exists(fp_prefixes.begin(), \
// If not, add the current prefix object
// to the vector of prefixes
fp_prefixes.end(), fp_prefix))
fp_prefixes.push_back(fp_prefix);
}
// Update the FP-Tree's model
fp_update_model(fp_leaf, fp_tree);
}
}
// Add cross-refences between identical items
// Iterate through the FP-tree nodes vector
for (auto t_it = fp_tree.begin(); \
t_it != fp_tree.end(); t_it++)
{
auto s_it = t_it;
bool adj_found = false;
// For each item, find an identical item in the subset of succeeding items
while ((++s_it != fp_tree.end()) && (!adj_found))
if (t_it->m_item == s_it->m_item)
{
adj_found = true;
// Add an index of the node being found to
// the vector of parent nodes for the current FP-Tree node
t_it->m_parent.push_back(\
std::distance(fp_tree.begin(), s_it));
}
}
}
std::vector<std::vector<std::string>> \
fp_extract_prefix_paths( \
std::vector<std::vector<std::string>> T, \
std::vector<std::string> C)
{
std::vector<arl::fptree_node> fp_tree;
std::vector<std::vector<std::string>> fp_itemsets;
// Compute the items support counts vector
std::vector<arl::fp_supp_count> fp_items_supp \
= ARL::fp_get_supp_count(ARL::get_items(T), T);
// Convert the "raw" data stream into canonical database
ARL::fp_convert_stream(fp_items_supp, T, C);
// Build an FP-Tree
ARL::fp_build_tree(fp_tree, T);
#pragma omp parallel for
// Iterate through the vector of support counts
for (auto it = fp_items_supp.begin(); \
it != fp_items_supp.end(); it++)
{
std::uint64_t index = 0L;
// For each item in the following vector find the
// item node with the largest support count value
auto n_it = fp_tree.begin(); std::uint64_t supp_max = 0L;
while ((n_it = std::find_if
(pstl::execution::par_unseq, n_it, fp_tree.end(),
[&](const ARL::FPTREE_NODE& node) {
return node.m_item == it->m_item; })) != fp_tree.end())
{
if (n_it->m_count > supp_max)
{
index = std::distance(fp_tree.begin(), n_it);
supp_max = n_it->m_count;
}
n_it++;
}
bool done = false;
std::uint64_t node = index;
std::vector<std::string> itemset;
// Iterate through each parent node starting at
// the "leaf" node being found during the previous step
while ((fp_tree[node].m_item != "null") && (done == false))
{
// For each node, perform a check if the current item already
// exists in the resultant set of items
if (std::find(pstl::execution::par_unseq,
itemset.begin(), itemset.end(), \
fp_tree[node].m_item) == itemset.end())
// If not, add the current item to the resultant set of items
itemset.push_back(fp_tree[node].m_item);
// Perform a check if the current node has only one parent node
if (fp_tree[node].m_parent.size() == 1)
// If so, obtain the value of the parent node
node = fp_tree[node].m_parent[0];
else {
// Otherwise, assign the first parent node index
// to the parent1 variable
std::uint64_t parent1 = fp_tree[node].m_parent[0];
// Assign the second parent node index to the parent2 variable
std::uint64_t parent2 = fp_tree[node].m_parent[1];
// Find a parent node with the largest support count
// and assign its index value to the node variable
node = (fp_tree[parent1].m_count >= \
fp_tree[parent2].m_count) ? parent1 : parent2;
}
}
// Find a union of the resultant itemset and the vector of classes
std::vector<std::string> prefix = utils::union_vec(itemset, C);
// Find an intersection of the resultant itemset and the vector of classes
std::vector<std::string> items = utils::intersect_vec(itemset, prefix);
#pragma omp parallel for schedule(dynamic, 4)
// Iterate through the vector of items
for (auto it2 = items.begin(); it2 != items.end(); it2++)
{
// Copy the prefix vector to the subset vector
std::vector<std::string> subset = prefix;
// Append the current item value to the subset vector
subset.push_back(*it2);
// Compute the number of occurrences of the current subset vector
// in the set of transactions
std::uint64_t count = std::count_if(
pstl::execution::par_unseq, T.begin(), T.end(),
[&](std::vector<std::string>& trans) {
return utils::union_vec(trans, subset).size() == subset.size();
});
// Perform a check if the number of occurrences is
// less than the minima support value. If so, simply prune the
// following item from the itemset since it's an infrequent item
if (count <= ARL::min_supp * T.size())
itemset.erase(std::find(pstl::execution::par_unseq, \
itemset.begin(), itemset.end(), *it2));
}
// Add the itemset of the current tree prefix path
// to the vector of path itemsets
fp_itemsets.push_back(itemset);
}
// Return the vector of paths
return fp_itemsets;
}
std::vector<fp_class_item> fp_growth( \
std::vector<std::vector<std::string>> T, \
std::vector<std::string> classes)
{
std::vector<arl::fp_class_item> results;
std::vector<std::vector<std::string>> rules;
if (T.size() > 1000)
{
std::uint64_t th_max = T.size() / 1000;
th_max = (th_max > omp_get_max_threads()) ? \
omp_get_max_threads() : th_max;
omp_set_num_threads(th_max);
#pragma omp parallel
{
std::uint64_t tid = omp_get_thread_num();
std::uint64_t start = tid * 1000;
std::uint64_t end = (tid + 1) * 1000;
if (end > T.size()) end = T.size();
std::vector<std::vector<std::string>> trans_chunk;
trans_chunk.insert(trans_chunk.end(), \
T.begin() + start, T.begin() + end);
// Extract the prefixes directly from the tree
// Find the resultant set of association rules mined
std::vector<std::vector<std::string>> \
itemsets = ARL::fp_extract_prefix_paths(trans_chunk, classes);
rules.insert(rules.end(), itemsets.begin(), itemsets.end());
}
}
else {
// Perform the association rules mining
std::vector<std::vector<std::string>> \
itemsets = ARL::fp_extract_prefix_paths(T, classes);
rules.insert(rules.end(), itemsets.begin(), itemsets.end());
}
// Merge the association rules mining results
// Iterate through the vector of classes starting at the second class
#pragma omp parallel for
for (auto c_it = classes.begin() + 1; c_it != classes.end(); c_it++)
{
std::vector<std::vector<std::string>> itemsets;
// Iterate through the resultant vector of rules
for (auto t_it = rules.begin(); t_it != rules.end(); t_it++)
// For each rule, perform a check if the current class is
// contained in the current rule
if (std::find(pstl::execution::par_unseq, \
t_it->begin(), t_it->end(), *c_it) != t_it->end())
// If so, add the current rule to the vector of itemsets
itemsets.push_back(*t_it);
std::vector<std::string> merged = *itemsets.begin();
// Iterate through the vector of itemsets
for (auto t_it = itemsets.begin() + 1; t_it != itemsets.end(); t_it++)
{
// For each itemset compute the intersection of the merged
// resultant vector so far with the current itemset
std::vector<std::string> isect_items = \
utils::intersect_vec(merged, *t_it);
// Append the intersected items vector and the current itemset vector
merged = utils::append_vec(*t_it, isect_items);
}
ARL::FP_CLASS_ITEM fp_class_items;
// Construct a rules object and add it to the resultant set of rules
fp_class_items.m_items = merged;
fp_class_items.m_class = std::string(*c_it);
results.push_back(fp_class_items);
}
return results;
}
}
int main()
{
std::cout << "FPGrowth Algorithm Demo v1.00a by Arthur V. Ratz\n";
std::cout << "================================================\n\n";
std::cout << "\n Enter dataset filename (*.csv): "; std::cin >> filename;
// Read classes.csv file
std::vector<std::string> classes = \
ARL::read_sl_csv_file(cs_filename);
// Read dataset file
std::vector<std::vector<std::string>> T = \
ARL::read_data_from_csv_file(filename);
std::cout << "\n Classes: " << classes.size() << " items" << "\n";
std::cout << " Transactions: " << T.size() << " items" << "\n\n";
// Perform the association rules mining
std::vector<arl::fp_class_item> \
results = ARL::fp_growth(T, classes);
// Print out all classes and items beloning to it
for (auto rl_it = results.begin(); rl_it != results.end(); rl_it++)
{
std::cout << rl_it->m_class << " => " << "[ ";
for (auto it = rl_it->m_items.begin(); \
it != rl_it->m_items.end(); it++)
std::cout << *it << " ";
std::cout << " ]\n";
}
std::cin.get();
std::cin.get();
std::cout << "*\n";
}
结论
在本文中，我们详细讨论了 FPGrowth 算法，它作为著名的 Apriori 和 ECLAT 算法的有效替代方案。与这些算法相比，FPGrowth 是一种有所不同的算法，提供了更多的算法级性能优化，使得整个关联规则挖掘过程更快。具体来说，它避免了需要生成通常数量巨大的规则候选以找到潜在有趣的关联规则的情况。相反，关联规则可以直接从树中提取特定的前缀路径来找到。这极大地简化了关联规则挖掘过程，因此，可以充分提高后续过程的性能。
在算法讨论中，我们的目标是演示如何使用 FPGrowth 算法在通常包含超过 10^6 个事务的巨大“原始”数据集中执行关联规则挖掘，这些事务来自实时数据流，而不是条件数据库，这在大量文档和指南中已经讨论过。为此，除了算法级优化，我们还使用了 Intel Parallel Studio XE 开发工具来提高用 C++11 编写的实现 FPGrowth 算法的顺序遗留代码的性能。
历史
- 2019 年 7 月 20 日 - 首次发布