FP-Growth算法简介
FP-Growth算法简介
由于Apriori算法在挖掘频繁模式时，需要多次扫描数据库，并且会产生大量的候选项集。所以Apriori算法的时间复杂度和空间复杂度相对都很高，算法执行效率不高。而FP-Growth算法在进行频繁模式挖掘时，只需要对数据库进行两次扫描，并且不会产生候选项集。它的效率相比于Apriori算法有很大的提高。
FP-Growth算法的主要思想是：将代表频繁项集的数据库压缩存储在频繁模式树中，每条事务数据中的项之间的关系被保留在频发模式树中。然后，将频繁模式树按照条件模式基拆分成一组条件FP树，并分别挖掘这些条件FP树。
FP-Growth算法的步骤：
- 第一次扫描数据库，寻找频繁1-项集，并按照由大到小的顺序排序。
- 创建FP模式树的根结点，记为“null”。
- 根据频繁1-项集的顺序对数据库中的每条事务数据进行排序，并存储在FP模式树中，并建立项头表。
- 为每一个频繁1-项集寻找前缀路径，组成条件模式基，并建立条件FP树。
- 递归挖掘条件FP树，获得频繁项集。
以表1中的数据解释说明FP-Growth算法，最小支持度为2。
首先，扫描表1中的数据，根据最小支持度，获得频繁1-项集。按照支持度计数大小进行排序得到项集L={{I2:7},{I1:6},{I3:6},{I4:2},{I5:2}}。
然后，创建FP树的根结点，记为“null”。第二次扫描数据库，根据项集L对每条事务数据进行排序。例如事务T001经排序后得到{{I2:1},{I1:1},{I5:1}}，并将每一项作为结点链接到FP树中，其中I2作为第一个结点链接到根结点，其他的结点按照顺序依次相互链接。接下来将排序好的T002事务数据{{I2:7},{I4:2}}链接到FP树中，为{{I2:7},{I4:2}}建立分支，同样I2作为第一个结点链接到根结点，I4与I2链接。但是，由于这个分支与FP树共享前缀I2，所以，将结点I2合并，并且计数加1，为I4建立新结点链接到结点I2。一般的，当为一个事务数据建立分支时，查看是否含有相同的前缀路径，若含有相同的前缀路径，则前缀路径合并，并且相应的结点计数加1，为前缀之后的项创建新结点并链接到共享前缀路径上。
建立项头表可以在今后快速地遍历FP树，，使每项通过一个结点链指向它在树中的位置。根据该链可以找到FP树中所有相同的结点。
根据表1数据建立的FP树和项头表如图1所示：
接下来为每一个频繁1-项集寻找所有前缀路径，组成条件模式基，然后建立条件FP树。例如I5在FP树中的前缀路径有{{I2:1},{I1:1}}和{{I2:1},{I1:1},{I3:1}}，组成I5的条件模式基。使用这些条件模式基建立I5的条件FP树，由于I3的支持度计数为1，小于最小支持度，所以I5的条件FP树只包含单个路径{{I2:2},{I1:2}}，如图2所示，该路径产生的频繁项集的所有组合为：{{I2:2},{I5:2}}、{{I5:2},{I1:2}}、{{I2:2},{I1:2},{I5:2}}
算法：FP-Growth。使用FP树，通过模式增长挖掘频繁模式。
输入：
D：事务数据库。
min_sup：最小支持度阈值。
输出：频繁模式全集。
方法：
1、按以下步骤构造FP树：
（a）扫描事物数据库一次。收集频繁项的集合F和它们的支持度计数。对F按照支持度计数排序，结果为频繁项列表L。
(b)创建FP树的根结点“null”，对于D中每一件transaction，执行：
选择transaction中的频繁项，并按照L中的次序排序。排序后的列表为[p|P]。其中p是第一个元素，P是剩余元素。调用inster_tree（[p|P]，T）。该过程的执行过程如下。如果T有子女N使得N.item-name = p.item-name，则N的计数增加1；否则，创建一个新的结点N，将其计数记为1，链接到它的父结点T，并且通过结点链结构将其链接到具有相同item-name的结点。如果P非空，则递归地调用inster_tree（P，N）。
2、FP树的挖掘通过调用FP-growth（FP_tree,null）实现。该过程实现如下。
Procedure FP_growth（Tree, α）
- if Tree 包含单个路径P then
- for 路径P中结点的每个组合（记作β）
- 产生模式β∪α，其支持度计数support_count等于β中结点的最小支持度计数；
- else for Tree的头表中的每个α_i {
5.产生一个模式β= α_i∪α，其支持度计数support_count = α_i.support_count；
6.构造β的条件模式基，然后构造β的条件FP树Tree_β；
7.if Tree_β != ∅ then
8.调用FP_growth(Tree_β，β)；
}
