FP-Growth

FP-Growth可以高效地发现频繁项集

发现事务数据中的公共模式

FP-Growth与Apriori相比，是基于Apriori的构建，但是将数据集存储在FP树，这样使得算法的执行速度快于Apriori，通常性能要好两个数量级以上。

FP-Growth只需要对数据库进行两次扫描，而Apriori对每个潜在的频繁项集都会扫描数据集判定给定模式是否频繁。FP过程如下：

1）构建FP树

2）从FP树中挖掘频繁项集

FP树

同搜索树不同的是，一个元素项可以在一颗FP树中出现多次，FP树会存储项集出现的频率，相似元素的集合会共享树的一部分，只有当集合间完全不同时才会分叉

在FP树中Z出现了5次，集合{r,z}出现了1次，那么可以推出一定是z本身或者其他符号一起出现了4次。

FP-growth的工作流程是，首先建立FP树，然后利用它来挖掘频繁项集。为构建FP树需要对原始数据扫描两遍，第一遍对所有元素项的出现次数进行计数，如果某元素是不频繁的，那么包含该元素的超级也是不频繁的，所以就不用考虑这些元素的超级。

第一遍扫描统计出现的频率，第二遍扫描只考虑那些频繁的元素

第一次遍历数据集会获得每个元素项的出现频率。接下来，去掉不满足最小支持度的元素项。再下一步构建FP树。在构建时，读人每个项集并将其添加到一条已经存在的路径中。如果该路径不存在，则创建一条新路径。每个事务就是一个无序集合。假设有集合{z，x，y}和比{y,z,r} ,那么在FP树 , 相同项会只表示一次。

为了解决此问题，在将集合添加到树之前，需要对每个集合进行排序。排序基于元素项的绝对出现频率来进行。使用图12-2中的头指针节点值，对表12-1中数据进行过滤、重排序后的数据显示在表12-2中

对事务记录进行过滤和排序之后就可以构建FP树了，从空集开始，向其中不断添加频繁项集，过滤、排序后的事务添加到树中，如果树中已存在现有元素，则增加现有元素值，否则则添加分支

----从一颗FP树中挖掘频繁项集

1. 从FP树中获得条件模式基

2. 利用条件模式基，构建一个条件FP树

3. 迭代重复1）2）直到树只包含一个元素

--条件模式基

---创建条件FP树