2.4.2 FP-growth算法
1994年，R.Agrawal和R.Srikant提出了Apriori算法。Apriori算法是一种在关系数据库上频繁进行项目集挖掘和关联规则学习的算法。通过识别数据库中频繁出现的单个项目并将它们扩展到越来越大的项目集，可确定频繁项目集。Apriori算法的目标是明确数据库总体趋势的关联规则。Apriori算法的命名源于使用了频繁项目集属性的先验知识，主要采用迭代方法或逐级搜索，通过k个频繁项目集来查找k+1个项目集。为了提高生成频繁项目集的效率，使用了一个称为Apriori的重要属性，该属性有助于减少搜索空间。但Apriori算法存在一些实际问题，例如，在每个步骤中都必须构建候选集，为了构建候选集，Apriori算法必须重复扫描数据库，这些问题不可避免地会使Apriori算法变慢。
为了克服这些冗余步骤，业界开发了一种新的频繁项目集挖掘算法，称为频繁模式增长（FP-growth）算法。FP-growth算法是对Apriori算法的改进，FP-growth算法减少了对频繁项目集的搜索，使用频繁模式树（Frequent Pattern Tree）或FP树的形式来表示数据库，这种树结构能够保持项目集之间的关联。
FP-growth算法的步骤如下：
（1）扫描数据库，以查找数据库中出现的项目集。此步骤与Apriori算法的第一步相同，数据库中每个项目集的计数称为支持计数（Support Count）或1-项目集（1-itemset）频率。例如，事务-项目清单列表如表2.5所示。
表2.5 事务-项目清单列表
对于表2.5所示的项目集来说，计数的阈值为50%，即0.5×6=3，意味着最小的支持min_sup=3。计算每个项目集，可得到项目-计数列表，如表2.6所示。
表2.6 项目-计数列表
按降序对项目集进行排序，可得到降序排列的项目-计数列表，如表2.7所示。
表2.7 降序排列的项目-计数列表
（2）创建FP树，如图2.12所示。
图2.12 FP树
①创建树的根，用Null表示。
②事务（Transaction）T1的第1次扫描：包含I1、I2、I3三个项，即计数为{I1:1}、{I2:1}、{I3:1}，其中I2作为子级连接到根，I1连接到I2，I3连接到I1。
③T2：包含I2、I3和I4，其中I2连接到根，I3连接到I2，I4连接到I3，此分支将共享T1中已使用的I2节点。
④I2的计数加1，I3作为子级连接到I2，I4作为子级连接到I3；计数为{I2:2}、{I3:1}、{I4:1}。
⑤T3：包括I4、I5，在创建子级时，具有I5的新分支连接到I4。
⑥T4：包括I1、I2、I4，顺序为I2、I1、I4，I2已连接到根节点，因此将增加1；类似地，由于I1已与T1中的I2连接，因此I1将增加1，计数为{I2:3}、{I1:2}、{I4:1}。
⑦T5：包括I1、I2、I3、I5，顺序为I2、I1、I3、I5，因此计数为{I2:4}、{I1:3}、{I3:2}、{I5:1}。
⑧T6：包括I1、I2、I3、I4，顺序为I2、I1、I3、I4，因此计数为{I2:5}、{I1:4}、{I3:3}、{I4:1}。
（3）再次扫描数据库并检查事务。检查第一个事务并找出其中的项目集，具有最大计数的项目集位于顶部，具有较小计数的项目集位于其次，依次类推。也就是说，FP树的分支由事务项目集按计数的降序排列。
（4）检查数据库中的下一个事务。项目集按计数的降序排列，如果此事务的任何项目集已经存在于另一个分支中，则该事务分支将为根共享一个公共前缀（Common Prefix），也就是说，公共项目集在此事务中连接到另一个项目集的新节点。
（5）项目集的计数会随着事务的发生而增加，在创建事务以及连接公共节点和新节点时，它们的数量都会增加1。
（6）挖掘创建的FP树。检查最低节点以及最低节点的连接，最低节点表示频率模式长度1，由此，遍历FP树中的路径，此路径称为条件模式库。条件模式库是一个子数据库，由FP树中带有最低节点的前缀路径组成。
（7）构造条件FP树，该FP树由路径中的一组项目集形成；在条件FP树中考虑满足阈值支持的项目集。
（8）从条件FP树生成频繁模式，如表2.8所示。
表2.8 从条件FP树生成频繁模式
总之，与Apriori算法相比，FP-growth算法的速度更快，并且对于挖掘长期和短期频繁模式而言都是有效且可扩展的。FP-growth算法的缺点是它比Apriori算法更加烦琐且难以构建，当数据库很大时无法共享内存。