基于 Apriori的问题进行改进，提出FP-Growth算法
相比Apriori算法需要多次扫描数据库，FPGrowth只需要对数据库扫描2次。
第1次扫描获得当个项目的频率，去掉不满足支持度要求的项，并对剩下的项排序。
第2次扫描建立一颗FP-Tree树。
二、构建FP-Growth的步骤
挖掘强关联规则是在满足一定支持度的情况下寻找置信度达到阈值的所有商品组合。
2.1、样本
2.2、对于每一条购买记录，按照频繁项集中的顺序重新排序
我们要找出哪些总是一起购买的商品，比如人们买薯片的时候通常也会买鸡蛋，则[薯片，鸡蛋]就是一条频繁模式(规律)。
第一步：扫描数据库，每项商品按频数递减排序，删除频数小于最小支持度MinSup的商品。(第一次扫描数据库）
薯片:7鸡蛋:7面包:7牛奶:6啤酒:4 （这里我们令MinSup=4）
以上结果就是频繁1项集，记为F1。
排序如下：
2.3、把第二步得到的各条记录插入到FP-Tree中。
2.3.1、插入第一条
2.3.2、插入第二条
2.3.3、插入第三条
2.3.4、最终
2.4、从FP-Tree中找出频繁项。
遍历表头项中的每一项（我们拿“牛奶：6”为例），对于各项都执行以下的操作：
2.4.1、从FP-Tree中找到所有的“牛奶”节点，向上遍历它的祖先节点，得到4条路径。
2.4.2、对于每一条路径上的节点，其count都设置为牛奶的count
2.4.3、因为每一项末尾都是牛奶，可以把牛奶去掉，得到条件模式基，此时的后缀模式是：(牛奶)。
三、事务数据库
3.1、频繁项集, 最小支持度为2
3.2、构建FP-Tree
3.3、从FP-Tree中找出频繁项集
3.3.1、考虑I5
3.3.1.1、得到条件模式基：
3.3.1.2、构建条件FP-Tree
由于I3小于最小支持度2,所以被删除
3.3.1.3、得到I5频繁项集： {{I2,I5:2},{I1,I5:2},{I2,I1,I5:2}}
3.3.2、考虑I4
得到I4频繁项集：{{I2,I4:2}}
3.3.3、考虑I3
3.3.3.1、I3的祖先路径
3.3.3.2、都设置为I3的count
3.3.3.3、删除I3， 就是条件模式基
3.3.3.4、通过条件模式基构建FP-Tree
由于此树不是单分支路径，因此需要递归挖掘I3
3.3.3.5、递归考虑I3，
此时得到I1条件模式基<(I2:2)>,即I1, I3的条件模式基为<(I2:2)>
3.3.3.6、得到I3的频繁项目集{{I2,I3:4},{I1,I3:4},{I2,I1,I3:2}}
3.3.4、考虑I1
3.3.4.1、最后考虑I1，得到条件模式基： <(I2:4)>
3.3.4.2、构造条件FP-tree
3.3.4.3、得到I1的频繁项目集：{{I2,I1:4}
四、优缺点
1、FPGROWTH算法只需对事务数据库进行二次扫描，并且避免产生的大量候选集。
2、由于该算法要递归生成条件数据库和条件FP-tree，所以内存开销大，而且只能用于挖掘单维的布尔关联规则。