FP-growth算法是一种高效发现频繁集的算法，比Apriori算法高效，但是不能用于发现关联规则。FP-growth算法只需要对数据即信两次扫描，而Apriori算法对于每个潜在的频繁项集都会扫描数据集判定给定模式是否是频繁，所以FP-growth更快。FP-growth算法主要分为两个过程：
构建FP树；从FP树中挖掘频繁项集。FP代表频繁模式（Frequent Pattern）,它和数据结构中的其它树特别相似，但是在FP树中，一个元素项可以出现多次，如下图所示：
图1
如图1所示，FP树会存储项集的出现频率，而每个项集会以路径的方式存储在树中。从最上面的空集合开始，每一条路径就是一个项集，这里要除过去带箭头的那些路径链接，因为带箭头的的链接是相似项之间的链接，叫节点链接，是用于快速发现相似项的位置（至于相似项是什么，看后面就知道其含义了）。
这棵树可以分为纵向和横向的，纵向的就是每个项集的集合，横向的就是相似项，用于方便元素的查找。
为了挖掘频繁项集，我们首先要构建FP树。我们需要对数据扫描两遍。第一遍对所有元素项的出现次数进行统计，根据Apriori原理，如果某元素不是频繁的，那么包含该元素的超集也是不频繁的，所以就不需要考虑这些超集，第二遍扫描值考虑哪些频繁元素。
首先给出FP树的节点的结构：
class treeNode: def __init__(self, nameValue, numOccur, parentNode): self.name = nameValue self.count = numOccur self.nodeLink = None self.parent = parentNode #needs to be updated self.children = {} def inc(self, numOccur): self.count += numOccur def disp(self, ind=1): print ' '*ind, self.name, ' ', self.count for child in self.children.values(): child.disp(ind+1)
我们看一下这个节点的结构，name就是节点元素，count是当前节点元素出现次数（经过这个节点的路径的次数），nodeLink用来指向相似元素（维护横向结构），parent父节点，从构造方法上来看，我们每次将传入的parentNode节点作为当前节点的父节点，children就是存放节点的子节点。另外也提供了增加自身数量的计数器，和子节点的遍历函数。
下面先给出最终的FP树的一个形式：
图2
如图2所示，头指针表来放FP树中每个元素出现的总数，用来表示横向的关系，方便查找相似元素。
第一次遍历的时候，去掉不满足最小支持度的元素项。下一步构建的时候，读入每个项集并将其添加到一条已经存在的路径中。如果该路径不存在，则创建一条新路径。我们知道在FP树中，每个项集都是一个无序的组合，但是又需要将某些有重复元素的集合放到同一条路径上，为了解决这个问题，我们 就需要对每个结合进行排序，排序是基于每个项集中元素项的绝对出现频率来进行的。
图3
如图3所示，将非频繁项移除后并且排序后的事物数据集。如001号事务，由于h,j,p的最小支持度没有满足最小支持度，所以把这个元素项去掉了，留下的z,r由于z的出现次数比r多，所以z在r前面。为什么这么排，因为在FP树中，越是靠近根节点的元素是最靠前的，并且其出现次数也是最多的，也就是被共用次数最多的。
下面我们就可以构建FP树了，从空集合开始，向其中不断添加频繁集。过滤、排序后的事物一次添加到树中，如果树中已存在现有的元素，则增加现有元素的值；如果现有元素不存在，则向树添加一个分枝，如图4所示：
图4
下面我们结合代码看一下具体的过程：
def createTree(dataSet, minSup=1): #create FP-tree from dataset but don't mine headerTable = {} #go over dataSet twice for trans in dataSet:#first pass counts frequency of occurance for item in trans: headerTable[item] = headerTable.get(item, 0) + dataSet[trans] for k in headerTable.keys(): #remove items not meeting minSup if headerTable[k] < minSup: del(headerTable[k]) freqItemSet = set(headerTable.keys()) #print 'freqItemSet: ',freqItemSet if len(freqItemSet) == 0: return None, None #if no items meet min support -->get out for k in headerTable: headerTable[k] = [headerTable[k], None] #reformat headerTable to use Node link #print 'headerTable: ',headerTable retTree = treeNode('Null Set', 1, None) #create tree for tranSet, count in dataSet.items(): #go through dataset 2nd time localD = {} for item in tranSet: #put transaction items in order if item in freqItemSet: localD[item] = headerTable[item][0] if len(localD) > 0: orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: p[1], reverse=True)] updateTree(orderedItems, retTree, headerTable, count)#populate tree with ordered freq itemset return retTree, headerTable #return tree and header table def updateTree(items, inTree, headerTable, count): if items[0] in inTree.children:#check if orderedItems[0] in retTree.children inTree.children[items[0]].inc(count) #incrament count else: #add items[0] to inTree.children inTree.children[items[0]] = treeNode(items[0], count, inTree) if headerTable[items[0]][1] == None: #update header table headerTable[items[0]][1] = inTree.children[items[0]] else: updateHeader(headerTable[items[0]][1], inTree.children[items[0]]) if len(items) > 1:#call updateTree() with remaining ordered items updateTree(items[1::], inTree.children[items[0]], headerTable, count) def updateHeader(nodeToTest, targetNode): #this version does not use recursion while (nodeToTest.nodeLink != None): #Do not use recursion to traverse a linked list! nodeToTest = nodeToTest.nodeLink nodeToTest.nodeLink = targetNode从createTree函数看起。参数dataSet是数据集，minSup是集合中元素最少出现的次数，第一个for循环就是统计数据集中每个元素出现的次数，将其放到headerTable的数据字典中，然后第二个循环就是去掉次数小于minSup的单元素集合，然后将其放到freqItemSet（所有出现次数满足minSup的单个元素的集合）中。
第3个for循环，就是初始化headerTable，这里我们用来存储FP树中的横向结构，包括该元素出现的次数，以及第一个对应的相似节点的位置（当然初始化这个位置都是空None），如：{'s': [3, None], 'r': [3, None], 't': [3, None], 'y': [3, None], 'x': [4, None], 'z': [5, None]}所示。下来就是声明一个空节点作为根节点。
从第4个for循环开始正式构建FP树。次循环是遍历传入的dataSet中的值。正如循环中的所示，tranSet是频繁项集，count是该集合对应的次数。然后我们看内循环就是将tranSet中的元素以及其出现的次数提取出来，并且以字典的形式将其放到localD中如（{z,5},{r,3}）的形式，主要是将传入的集合中可能有一些已经在第一步去掉的单元素频繁项，然后判断他们是否在freqItemSet(所有出现次数满足minSup的单个元素的集合)。如果len(locakD)的长度大于0，说明有满足minSup的元素。orderedItems就是此次满足minSup的元素按照出现的次数进行倒序排列，如形式：<type 'list'>: ['z', 'x', 'y', 's', 't']，然后调用updateTree函数。其实这一步就是从样本数据的每条项目中找出满足minSup的元素集合，下面就是将找出来的元素集合放到FPtree中。
updateTree函数。items就是需要往已有的FPtree中增加的list，如<type 'list'>: ['z', 'x', 'y', 's', 't']，inTree就是当前树，headerTable就是横向的存放每个元素及其出现次数和第一个相似元素位置的，count可以看作是items集合出现的次数。这个函数是自己调用自己的一个递归的过程，先看第一个if items[0] in inTree.children判断items第一个元素是否是当前树的子节点，如果是，说明items[0]已经有了，只需要将其计数增加1即可。先不看else，看最后面的if len(items)>1就是如果items不止一个元素的时候，就去掉当前已经判断过的第一个元素，将后面的元素作为items继续调用自己，如第一次判断了z，然后此时就是将xyst作为items到updateTree中，此时x就作为第一个元素判断，一次递归。然后我们看else中的内容，就是没有在当前树根节点的子节点中出现，说明我们要开辟新的子节点分枝了。然后就简单了，生成新节点，然后放到当前树根节点的字典中。然后我们需要更新横向的headerTable,中间调用了updateHeader函数，就是当headerTable中的相似节点已经有的时候，不断向下找，直到最后，然后将当前新生成的点放到最后一个相似节点上。其实就是产生nodeLink的过程。
其实如果对递归熟悉的话，这个过程还是比较简单的。至此我们已经构建好了这个FP树了。
上面的过程是我们根据样本数据构建好的一颗FP树，下来就是我们需要从这棵树中发现频繁项集。
从FP树种抽取频繁项集的单个基本步骤如下：
从FP树种获得条件基；利用条件模式基，构建一个条件FP树；迭代重复步骤（1）和（2），直到树包含一个元素项为止接下来我们就需要抽取条件模式基。条件模式基是什么，就是一系列的倒回到根节点的路径。我们还记得headerTable中存的是每个元素出现次数，以及其相似元素出现的第一个位置（也就是其出现的第一个位置），然后参考图2，这个元素可能在这个树中出现了多次，然后从每次出现的位置开始，倒着向数的根节点，然后就得到了一系列的频繁集，如r的前缀路线有{x,s},{z,x,y},{z},每条前缀路径都有一个计数值关联，然后我们给出图5所示的结果：
图5
前缀路径将被用于构建条件FP树。然后我们参考以下代码:
def ascendTree(leafNode, prefixPath): #ascends from leaf node to root if leafNode.parent != None: prefixPath.append(leafNode.name) ascendTree(leafNode.parent, prefixPath) def findPrefixPath(basePat, treeNode): #treeNode comes from header table condPats = {} while treeNode != None: prefixPath = [] ascendTree(treeNode, prefixPath) if len(prefixPath) > 1: condPats[frozenset(prefixPath[1:])] = treeNode.count treeNode = treeNode.nodeLink return condPats
先看函数findPrefixPath，如名所示就是为了找到对应的素有的前缀路径。basePat是我们传入的单个元素，如x，treeNode是我们传入的一个节点，就是headerTable中第一个相似节点，也就是x第一次出现的位置，上述函数相对比较简单，就不展开说了。找到所有的前缀路径之后，我们就需要创建条件FP树。
我们先看一个例子，看t的条件树：
图6
通过图2所示，我们可以看出t的两个条件模式基，然后用这个条件模式基重复了之前的建树的过程，然后结果就是可以看作是所有包含t的频繁集。但是我们可以看到对于t来说我们是去掉了s和r，为什么？因为我们这里的最小支持度为3，而在t的条件模式基中，s和r是不频繁，虽然在没有t的条件限制下，他是频繁的，所以对其来说{t,r}和{t,s}是不频繁的。接下来对集合{t,z}、{t,x}以及{t,y}来挖掘对应的条件数。该过程不断重复进行，知道条件数中没有元素位置，然后就可以停止了。下面先看代码：
def mineTree(inTree, headerTable, minSup, preFix, freqItemList): bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p: p[1])]#(sort header table) for basePat in bigL: #start from bottom of header table newFreqSet = preFix.copy() newFreqSet.add(basePat) freqItemList.append(newFreqSet) condPattBases = findPrefixPath(basePat, headerTable[basePat][1]) myCondTree, myHead = createTree(condPattBases, minSup) if myHead != None: #3. mine cond. FP-tree mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)
这个函数还是比较复杂的函数，是一个不断递归的过程。preFix第一次传入的就是t，bigL就是headerTable中所有的单元素key的集合。condPattBases就是t对应的条件模式基，然后再用这些条件模式基和minSup生成一颗树，返回的结果是在这些条件基下的树和对应的headerTable即myHead，这里给出一个例子：{'x': [3, <fpGrowthBak.treeNode instance at 0x035747B0>], 'z': [3, <fpGrowthBak.treeNode instance at 0x03599C10>]，'y': [3, <fpGrowthBak.treeNode instance at 0x03546A35>]}。如果myHead不为空，说明树还不为空，然后再调用mineTree函数，此时bigL就变成了[‘z’,’x’,’y’]，其中newFreqSet就变成了[‘t’,’z’],freqItemList就成为了[[‘t’],[‘t’,’z’]],再递归就是[[‘t’],[‘t’,’z’]，,[‘t’,’z’,’x’]]，因为有循环就这样递归找到所有的可能。
FP-growth算法理解起来因为用到了好多递归的过程，所以比较不太好了解，所以还是需要仔细阅读代码去理解其思想的。
