字数

1391 字

阅读时间

6 分钟

FP-Growth算法设计思路

FP-Growth（Frequent Pattern Growth）是一种高效的频繁项集挖掘算法，通过构建压缩事务数据库的FP-tree结构，避免了Apriori算法中反复生成候选集的问题。以下是上述代码实现的设计思路和关键流程。

---

1. 算法核心思想

FP-Growth算法通过以下两步实现频繁项集挖掘：

1. 构建FP树：
   • 压缩事务数据库，将频繁项以树结构存储。
   • 在树中存储项之间的关联关系，减少数据扫描次数。
2. 递归挖掘频繁项集：
   • 按频繁项生成条件模式基。
   • 通过递归构造条件FP树挖掘频繁项集。

---

2. 代码设计与主要功能

类设计

1. FPTreeNode：

   • 表示FP树的节点，包含以下属性：
     • item：当前节点对应的项。
     • parent：父节点指针，用于回溯路径。
     • count：项的计数。
     • children：字典存储子节点。

2. FPTree：

   • 表示整个FP树，提供以下功能：
     • 构建FP树：通过add_transaction方法将事务逐项插入树中。
     • 条件模式基提取：通过conditional_pattern_base方法找到特定项的条件模式基。
     • 构造条件FP树：通过conditional_tree方法基于条件模式基创建新的FP树。

---

步骤一：构建FP树

1. 计算频繁项

   • 遍历事务，统计每项的支持度。
   • 移除不满足最小支持度的项，形成频繁项集。

2. 重排序事务

   • 对每个事务，根据项的支持度降序排序，确保高频项优先插入FP树。
   • 移除不在频繁项集中的项，形成有序事务列表。

3. 构建FP树

   • 遍历有序事务列表，逐项插入FP树。
   • 若节点已存在，增加计数；否则，创建新节点并与父节点连接。

---

步骤二：递归挖掘频繁项集

1. 条件模式基提取

   • 对于每个频繁项，从FP树中提取所有路径（即条件模式基）。
   • 路径中存储项和计数，用于构造条件FP树。

2. 构造条件FP树

   • 基于条件模式基，重新构建FP树。
   • 用条件FP树递归挖掘条件频繁项集。

3. 合并结果

   • 对每个频繁项，将其与条件频繁项集合并，形成完整频繁项集。

---

关联规则生成

1. 规则构造

   • 遍历所有频繁项集，枚举可能的关联规则：X -> Y，其中X ∪ Y = 项集且X ∩ Y = ∅。
   • 计算规则的置信度：conf(X -> Y) = 支持度(X ∪ Y) / 支持度(X)。

2. 规则筛选

   • 保留置信度大于等于最小置信度的规则。

---

FP树可视化

代码中提供了FP树的可视化功能，使用NetworkX绘制树结构，便于理解FP树的层次关系和节点间的连接。

---

3. 算法流程总结

以下是FP-Growth算法的核心步骤：

1. 输入事务数据集和最小支持度。
2. 构建FP树：
   • 统计各项支持度，筛选频繁项集。
   • 按支持度降序排列事务，逐项插入FP树。
3. 递归挖掘频繁项集：
   • 从FP树中提取条件模式基。
   • 构建条件FP树，递归挖掘频繁项集。
4. 生成关联规则：
   • 基于频繁项集计算规则的置信度，筛选强关联规则。
5. 输出频繁项集和关联规则。

---

4. 示例输出

输入数据集

dataset = [
    ['A', 'C', 'D'],
    ['B', 'C', 'E'],
    ['A', 'B', 'C', 'E'],
    ['B', 'E']
]

频繁项集

频繁项集：
{'C'}, 支持度：3
{'E'}, 支持度：3
{'B'}, 支持度：3
{'C', 'E'}, 支持度：2
{'C', 'B'}, 支持度：2
{'B', 'E'}, 支持度：3
{'C', 'B', 'E'}, 支持度：2

关联规则

关联规则：
{'C'} -> {'E'}, 置信度：0.67
{'E'} -> {'C'}, 置信度：0.67
{'B'} -> {'E'}, 置信度：1.00
...

FP树可视化

生成的FP树直观地展示事务间的公共前缀关系，便于理解数据结构：

Root -> C -> B -> E
            -> E
      -> B -> E
      -> E

---

5. 优缺点

优点

• 高效性：通过树结构存储数据，减少事务扫描次数。
• 空间节约：共享事务的公共前缀，显著减少存储空间。
• 剪枝优化：通过条件模式基递归构造条件FP树，减少不必要的候选集生成。

缺点

• 树结构开销：FP树的构建在高维数据上可能占用较多内存。
• 难以并行化：递归式挖掘不易并行处理。

优化方法可以包括：压缩数据存储、分区挖掘和并行化设计等。

贡献者

freeway348

文件历史

最后编辑于 25 天前查看完整历史

7c53a-ddddd