在我们日常生活中，使用搜索引擎时，输入一个单词或者单词的一部分，就会自动补全查询词项
FP-growth算法，不同于Apriori算法生成候选项集再检查是否频繁的”产生-测试“方法，但是基于Apriori构建，但在完成相同任务时采用了一些不同的技术.这里的任务是将数据集存储在一个特定的称作FP树的结构之后发现频繁项集或频繁项对，即常在一块出现的元素项的集合FP树.这种做法是的算法的执行速度要快于Apriori,通常性能要好两个数量级以上.
FP-growth 算法是一种用于发现数据集中频繁模式的有效方法，利用Apriori 原理，只对数据集扫描两次，运行更快。在算法中，数据集存储在 FP 树中，构建完树后，通过查找元素项的条件基及构建条件 FP 树来发现频繁项集。重复进行直到FP树只包含一个元素为止。
优点：一般要快于 Apriori 算法。
缺点：实现比较困难，在某些数据集上性能会下降。
适用数据类型：离散型数据。
应用领域：在多种文本文档中查找频繁单词；购物交易；医学诊断；大气研究等。
一、FpTree
FP代表频繁模式（Frequent Pattern）。一棵FP树看上去与[计算机科学中的其他树结构类似，但是它通过链接（link）来连接相似元素，被连起来的元素项可以看成一个链表。
FP树看上去就是一棵前缀树，根节点是空集，结点上是单个元素，保存了它在数据集中的出现次数，出现次数越多的元素越接近根。此外，结点之间通过链接（link）相连，只有相似元素会被连起来，连起来的元素又可以看成链表。同一个元素可以在FP树中多次出现，根据位置不同，对应着不同的频繁项集。可以为FP树设置最小支持度，过滤掉出现次数太少的元素。
下面这个数据集构造FP树如下图所示。
假设最下支持度为3，即低于3的元素项被认为是不频繁的，不会出现在树中，例如p,q
这棵树每个结点上都是一个单独的元素，及其在路径中的出现次数，例如"z:5"表示集合{z}出现了5次，而"x:3"表示集合{z,x}出现了3次，这是路径相关的。
FP-growth算法的工作流程：首先构建FP树，然后利用它来挖掘频繁项集。为构建FP树，需要对原始数据集扫描两遍。第一遍对所有元素项的出现次数进行计数。数据库的第一遍扫描用来统计出现的频率，而第二遍扫描中只考虑那些频繁元素。
FP-growth算法还需要一个称为头指针表的数据结构，其实很简单，就是用来记录各个元素项的总出现次数的数组，再附带一个指针指向FP树中该元素项的第一个节点。这样每个元素项都构成一条单链表。这个header除了指向指定元素的第一个结点外，还可以保存该元素在数据集中的总出现次数。
这里使用Python字典作为数据结构，来保存头指针表。以元素项名称为键，保存出现的总次数和一个指向第一个相似元素项的指针。
首先，遍历一次数据集，统计每个元素出现的次数，然后把出现次数较小的滤掉（例如选取最小支持度3，将出现次数小于3的元素滤除），然后对每个样本按照元素出现次数重排序。上面给出的数据集样例中，出现次数不小于3的元素有：z、r、x、y、s、t，滤除并重排后的样本如下所示。
元素项排序：FP树会合并相同的频繁项集（或相同的部分）。因此为判断两个项集的相似程度需要对项集中的元素进行排序（不过原因也不仅如此，还有其它好处）。排序基于元素项的绝对出现频率（总的出现次数）来进行。在第二次遍历数据集时，会读入每个项集（读取），去掉不满足最小支持度的元素项（过滤），然后对元素进行排序（重排序）。
对示例数据集进行过滤和重排序的结果如下：
二、构造fp树
在对事务记录过滤和排序之后，就可以构建FP树了。从根节点∅开始，将过滤并排序后的样本一个个加入树中，若FP树不存在现有元素则添加分支，若存在则增加相应的值。如果现有元素不存在，则向树添加一个分支。下图给出了从根节点∅开始依次添加三个样本（过滤且排序）后FP的情况。
那么对于单个样本，FP树应该怎么生长呢？自然而然地想到递归。因为每个样本都是排序过的，频数高的频繁项集在前面，它总是更接近根结点，所以也可以把每个样本看成一棵子树，而我们要做的就是把子树添加到FP树里。因此每次只需判断第一个结点是否是根的儿子，若是则增加计数，若不是则增加分枝，然后递归调用构造FP树，传入第二个元素开始的子树即可。比如上例中往根节点∅增加样本(z,r)时，根没有z这个儿子，因此增加分支z。接着，只需递归地构造FP树，传入(r)，发现当前FP树∅-z也没有r这个儿子，因此增加分支r。最终递归返回，引入样本(z,r)后构造的FP树就是∅-z-r。
下图详细地描述了这个过程，代码中updateFPtree()函数实现了这个功能。
三、从FP树提取条件模式基
条件模式基（conditional pattern base）定义为以所查找元素为结尾的所有前缀路径（prefix path）的集合。我们要做的就是从header列表开始，针对每一个频繁项，都查找其对应的条件模式基。举个例子，如下图所示，元素"r"的前缀路径是{z}、{z,x,y}和{x,s}。同时，每一个路径要与起始元素的计数值关联，该计数值等于起始元素项的计数值，该计数值给了每条路径上r的数目。
下面为每一个频繁项的所有前缀路径。
四、创建条件FP树
对每一个频繁项，都建立一棵条件FP树。上面我们对每一个频繁项提取了条件模式基，现在就用它作为输入数据，即把每一个前缀路径当成一个样本，调用createFPtree()构造一棵FP树，即条件FP树。然后，对这个条件FP树，递归地挖掘。由于createFPtree()中含有过滤的功能，因此最终总能获得所有满足最小支持度的频繁项，即我们所需要的频繁项集。
重复进行，直到条件数中没有元素为止。
五、实例(上述的Python实现）
导入数据库中的数据
import fpGrowth
simpDat=fpGrowth.loadSimpDat()
simpDat
为了createTree函数，对上面数据进行格式化处理
initSet = fpGrowth.createInitSet(simDat)
initSet
创建FP树
myFPtree, myHeaderTab = fpGrowth.createTree(initSet, 3)
给出树的文本表示结果
myFPtree.disp()
提取条件模式基
fpGrowth.findPrefixPath('z', myHeaderTab['z'][1]),fpGrowth.findPrefixPath('r', myHeaderTab['r'][1]),fpGrowth.findPrefixPath('x', myHeaderTab['x'][1])
生成条件树
freqItems = [] #建立空列表，存储所有频繁项集
fpGrowth.mineTree(myFPtree, myHeaderTab, 3, set([]), freqItems)
检查一下返回的项集是否与条件树相匹配
freqItems
显示相匹配
