免规则采集器列表算法(FP-growth算法挖掘频繁项集的过程及过程分析！！)

　　免规则采集器列表算法(FP-growth算法挖掘频繁项集的过程及过程分析！！)

　　在上一篇文章中，我们介绍了 Apriori 算法，但是我们可以分析一下，Apriori 算法可能受到两个非平凡开销的影响：可能需要生成大量的候选项目集；它可能需要重复扫描整个数据库，通过模式匹配检查大量候选。检查数据库中的每个事务以确定候选项目集的支持度是非常昂贵的。

　　是否有可能设计一种方法来挖掘所有频繁项集而无需这种代价高昂的候选生成过程？尝试这样做的一种方法称为频繁模式增长

　　(Frequent-Pattern Growth, FP-growth

　　)。它采用以下分治策略：首先，将表示频繁项集的数据库压缩成一个频繁模式树（FP树），该树仍然保留了项集的相关信息。然后，将压缩后的数据库划分为一组条件数据库，每个数据库关联一个频繁项或模式段，并分别挖掘每个条件数据库。对于每个“模式片段”，您只需要检查其关联的数据集。因此，随着被调查模型的“增长”，这种方法可以显着减少被搜索数据集的大小。

　　FP-growth算法的基本思想如下：

　　* 扫描事务数据库一次，找到频繁1-项的集合，标记为L，按支持度降序排列。

　　* 基于L，再次扫描事务数据库，构造一个代表事务数据库中项集关联的FP树。

　　* 递归查找FP树上的所有频繁项集。

　　* 最后，在所有频繁项集中生成强关联规则。

　　下面举例介绍FP-grow算法挖掘频繁项集的过程：

　　交易数据库如表1所示：

　　表一

　　数据库的第一次扫描与Apriori算法相同。它导出频繁 1 项集的集合并获得它们的支持计数。设最小支持计数为2.频繁项集合按支持计数降序排列。结果集或表用L表示。有L={{I2:7},

　　{I1:6}、{I3:6}、{I4:2}、{I5:2}}。

　　那么，FP树结构如下： 首先创建树的根节点，并用“null”标记。第二次扫描数据库 D。每个事务中的项目按照 L 中的顺序进行处理（即按支持计数递减排序），并为每个事务创建一个分支。例如，第一笔交易“T100:I1,

　　I2, I5" 收录三个项（I2、I1、I5） 在 L 中的顺序，通向收录三个节点的树的第一个分支，1>，其中 I2 链接到root 作为根大写的孩子，I1 链接到 I2，I5 链接到 I1。第二个事务 T200 收录项目 I2 和 I4 的 L 顺序，这导致分支，其中 I2 链接到根，I4 是链接到I2。但是，分支应该与T100的现有路径共享前缀I2。因此，节点I2的计数增加1，并创建一个新节点1>，作为子链接到。一般，考虑为一个事务添加分支时，沿公共前缀的每个节点的计数加1，为前缀后的项创建节点和链接。

　　为了方便树的遍历，创建一个item头表，让每个item通过一个节点链指向它在编号中的位置。扫描所有交易后得到的树如图1所示，有相关的节点链。这样就将数据库中频繁模式挖掘问题转化为FP树挖掘问题。

　　图1 存储压缩频繁模式信息的FP树

　　FP树的挖掘过程如下：从一个长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式库（一个“子数据库”，由出现的前缀路径组成FP树中的后缀模式）集合组合）。然后，构造它的（有条件的）FP 树，并在树上递归挖掘。模式增长是通过连接后缀模式和条件FP树生成的频繁模式来实现的。

　　FP树的挖掘过程总结在表2中，具体如下。首先考虑I5，它是L中的最后一项，而不是第一项。随着FP树挖掘过程的解释，从表的后端开始的原因将变得清晰。 I5出现在图1中FP树的两个分支中，这些分支形成的路径为I1、I5：1>和1>。因此，考虑形成 I5 的条件基。使用这些条件模式库作为事务数据库，构造I5的条件FP树，其中只收录一条路径2>；不包括 I3，因为 I3 的支持计数为 1，小于最小支持计数。这条单一路径产生了所有频繁模式的组合：{I2, I5: 2}, {I1, I5: 2}, {I2, I1, I5: 2}。

　　表 2 通过创建条件（子）模式库挖掘 FP 树

　　对于I4，它的两个前缀构成条件模式基{{I2, I1:1}​​, {I2:1}}，生成单节点条件FP树，导出频繁模式{I2, I4:2 }.

　　与上面的分析类似，I3的条件模态基为{{I2, I1: 2}, {I2: 2}, {I1: 2}}。它的条件 FP 树有两个分支和 sum。它产生了一个模式集：{{I2, I3: 4}, {I1, I3: 4}, {I2, I1, I3: 2}}，如图2所示。 最后，I1的条件模式基为{ {I2: 4}}，它的FP树只收录一个节点，只生成一个频繁模式{I2, I1: 4}。

　　图 2 与条件节点 I3 关联的 FP 树

　　FP-growth 方法将寻找长频繁模式的问题转化为在较小的条件数据库中递归搜索一些较短的模式，然后将后缀连接起来。它使用最不频繁的项目作为后缀，提供更好的 Selective。这种方法显着降低了搜索开销。

　　FP-growth算法的框架如下：

　　输入：交易数据库D，最小支持阈值min_sup，最小置信阈值min_conf 输出：强关联规则集RS方法：过程描述如下：

　　扫描 D 找到频繁的 1 项集 L； L 中的项按支持计数递减排序；创建FP树的根节点null； //为（D t中的每个事务）创建FP树{

　　找到t中的频繁1项集tt（即删除t中的不频繁项得到tt）；按L的顺序对tt中的项目进行排序；插入-FP(tt, null); //创建事务分支tt

　　} LS=Search-FP(FP, null) //找出所有频繁项集，利用上面描述的关联规则生成算法从LS生成强关联规则集RS；

　　构造FP树的算法如下：

　　算法：Insert-FP算法(tt,root) 输入：排序的频繁1项集L，FP（子）树的根节点输出：FP树方法：其描述如下：if

　　(tt不为空)​​ {取出tt中的第一项i; if (root 的一个子节点是 i) Node.sup_count=Node.sup_count+1;

　　else {创建Tr的子节点Node as i; node.sup_count=1;将 Node 添加到项目列表链；} 从 L 中删除项目 i；插入-FP(L,

　　节点); }

　　FP-growth 方法的性能研究表明，它在挖掘长频繁模式和短频繁模式方面是有效且可扩展的，并且比 Apriori 算法快一个数量级左右。

　　参考资料：《数据挖掘概念与技术（原书第 3 版）》