本文所采用图片均来自清华大学计算机系王建勇老师的课程《数据挖掘：原理与算法》
http://dbgroup.cs.tsinghua.edu.cn/wangjy/DM/DataMining.html
(Han, Pei and Yin @SIGMOD'00)
Apriori算法的一个主要瓶颈在于，为了获得较长的频繁模式，需要生成大量的候选短频繁模式。FP-Growth算法是针对这个瓶颈提出来的全新的一种算法模式。目前，在数据挖掘领域，Apriori和FP-Growth算法的引用次数均位列三甲。
FP的全称是Frequent Pattern，在算法中使用了一种称为频繁模式树（Frequent Pattern Tree）的数据结构。FP-tree是一种特殊的前缀树，由频繁项头表和项前缀树构成。所谓前缀树，是一种存储候选项集的数据结构，树的分支用项名标识，树的节点存储后缀项，路径表示项集。
FP-tree的生成方法：
第二步根据支持度对频繁项进行排序是本算法的关键。第一点是，通过将支持度高的项排在前面，使得生成的FP-tree中，出现频繁的项更可能被共享，从而有效地节省算法运行所需要的空间。另一点是，通过这种排序，可以对FP-tree所包含的频繁模式进行互斥的空间拆分，得到相互独立的子集，而这些子集又组成了完整的信息。
FP-tree子集分割方法
如上图，求p为前缀的投
http://dbgroup.cs.tsinghua.edu.cn/wangjy/DM/DataMining.html
(Han, Pei and Yin @SIGMOD'00)
Apriori算法的一个主要瓶颈在于，为了获得较长的频繁模式，需要生成大量的候选短频繁模式。FP-Growth算法是针对这个瓶颈提出来的全新的一种算法模式。目前，在数据挖掘领域，Apriori和FP-Growth算法的引用次数均位列三甲。
FP的全称是Frequent Pattern，在算法中使用了一种称为频繁模式树（Frequent Pattern Tree）的数据结构。FP-tree是一种特殊的前缀树，由频繁项头表和项前缀树构成。所谓前缀树，是一种存储候选项集的数据结构，树的分支用项名标识，树的节点存储后缀项，路径表示项集。
FP-tree的生成方法：
第二步根据支持度对频繁项进行排序是本算法的关键。第一点是，通过将支持度高的项排在前面，使得生成的FP-tree中，出现频繁的项更可能被共享，从而有效地节省算法运行所需要的空间。另一点是，通过这种排序，可以对FP-tree所包含的频繁模式进行互斥的空间拆分，得到相互独立的子集，而这些子集又组成了完整的信息。
FP-tree子集分割方法
如上图，求p为前缀的投