FP-growth算法：将数据集存储在一个特定的称为FP树的结构之后发现频繁项集或者频繁项对，即常在一起出现的元素项的集合FP树。
工作流程：
1、构建FP树：需要扫描两遍数据集，第一遍对所有元素项的出现次数进行计数，第二遍扫描时只关注频度满足要求的元素项。
2、抽取条件模式基
3、创建条件FP树，在条件FP树的创建过程中就可以找出频繁项集。
创建FP树的节点数据结构，用来保存节点信息：
class treeNode:
def __init__(self, nameValue, numOccur, parentNode):
self.name = nameValue
self.count = numOccur
self.nodeLink = None
self.parent = parentNode
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)
构建FP树需要头指针表，头指针表是字典，键是元素名称，值是元素出现的总次数和指向的该元素的第一个节点组成的列表。
第一次遍历数据集会获得每种元素的出现频度，去除不满足最小频度要求的元素项（过滤），再构建FP树。
构建过程：读入每个项集并把该项集添加到一条已经存在的路径中。如果该路径不存在，则创建一条新路径。每个事务就是一个无序集合，相同项只表示一次，也就是说相同的元素项集虽然元素的顺序不同，但是在FP树中只有一条路径来表示这种元素项集，例如元素项集（a,b,c,d）和（d,c,b,a）在FP树中只能对应同一条路径。所以在将集合（元素项集）添加到树之前，需要对集合里的元素排序。排序是基于元素的绝对出现频度来进行的。
在对事务记录过滤和排序之后，构建FP树：从空集开始，向其中依次添加频繁项集。如果树中已经存在现有元素，则增加现有元素的值；如果现有元素不存在，则向树添加一个分枝。
FP树构建函数：
伪代码：
输入：数据集、最小频度
输出：FP树、头指针表
1. 遍历数据集，统计各元素项出现次数，创建头指针表
2. 移除头指针表中不满足最小值尺度的元素项
3. 第二次遍历数据集，创建FP树。对每个数据集中的项集：
3.1 初始化空FP树
3.2 对每个项集进行过滤和重排序
3.3 使用这个项集更新FP树，从FP树的根节点开始：
3.3.1 如果当前项集的第一个元素项存在于FP树当前节点的子节点中，则更新这个子节点的计数值
3.3.2 否则，创建新的子节点，更新头指针表
3.3.3 对当前项集的其余元素项和当前元素项的对应子节点递归3.3的过程
代码：
def createTree(dataSet, minSup=1):
# 第一次遍历数据集，创建头指针表
headerTable = {}
for trans in dataSet:
for item in trans:
headerTable[item] = headerTable.get(item, 0) + dataSet[trans]
# 移除不满足最小支持度的元素项
headerTableCopy=headerTable.copy() #浅拷贝，拷贝第一层
for k in headerTableCopy.keys():
if headerTable[k] < minSup:
del(headerTable[k])
freqItemSet = set(headerTable.keys()) # 如果所有的元素频度都不满足最小频度要求，返回空
if len(freqItemSet) == 0:
return None, None
for k in headerTable: # 增加一个数据项，用于存放指向相似元素项指针
headerTable[k] = [headerTable[k], None]
retTree = treeNode('Null Set', 1, None) # 根节点
# 第二次遍历数据集，创建FP树
for tranSet, count in dataSet.items():
localD = {} # 对一个项集tranSet，记录其中每个元素项的全局频率，用于排序（基于绝对出现频率排序）
for item in tranSet:
if item in freqItemSet:
localD[item] = headerTable[item][0] #[0]表示对应元素的频度，[1]表示指向的节点
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) # 更新FP树
return retTree, headerTable
def updateTree(items, inTree, headerTable, count): #元素项集，FP树，头指针表，事务的出现次数
if items[0] in inTree.children: #元素项集的第一个元素存在于树的第一级叶节点时
inTree.children[items[0]].inc(count) #增加频度
else:
# 没有这个元素项时创建一个新节点
inTree.children[items[0]] = treeNode(items[0], count, inTree)
# 更新头指针表或前一个相似元素项节点的指针指向新节点
if headerTable[items[0]][1] == None:
headerTable[items[0]][1] = inTree.children[items[0]]
else:
updateHeader(headerTable[items[0]][1], inTree.children[items[0]])
if len(items) > 1:
# 对剩下的元素项迭代调用updateTree函数
updateTree(items[1::], inTree.children[items[0]], headerTable, count)
def updateHeader(nodeToTest, targetNode): #改变当前节点的指向节点为targetNode
while (nodeToTest.nodeLink != None):
nodeToTest = nodeToTest.nodeLink
nodeToTest.nodeLink = targetNode
从一棵FP树中挖掘频繁项集
从FP树中获得频繁项集的三个基本步骤：
1、从FP树中获得条件模式基
2、利用条件模式基，构建一个条件FP树
3、迭代步骤1和2，直到树只包含一个元素为止
条件模式基：是以所要查找的元素为结尾的路径集合。每一条路径其实都是一条前缀路径。简而言之，一条前缀路径是介于所查找元素与树根节点之间的所有内容。
前缀路径用于构建条件FP树。前缀路径的实现方法：头指针表包含相同类型元素链表的起始指针。一旦到达了每一个元素项，就可以上溯这棵树直到根节点为止。
前缀路径发现代码：
def findPrefixPath(basePat, treeNode):
condPats = {}
while treeNode != None:
prefixPath = []
ascendTree(treeNode, prefixPath)
if len(prefixPath) > 1:
condPats[frozenset(prefixPath[1:])] = treeNode.count
treeNode = treeNode.nodeLink
return condPats
def ascendTree(leafNode, prefixPath):
if leafNode.parent != None:
prefixPath.append(leafNode.name)
ascendTree(leafNode.parent, prefixPath)
创建条件FP树：在递归创建FP树的过程中会找到频繁项集
伪代码：
输入：我们有当前数据集的FP树（inTree，headerTable）
1. 初始化一个空列表preFix表示前缀
2. 初始化一个空列表freqItemList接收生成的频繁项集（作为输出）
3. 对headerTable中的每个元素basePat（按计数值由小到大），递归：
3.1 记basePat + preFix为当前频繁项集newFreqSet
3.2 将newFreqSet添加到freqItemList中
3.3 计算t的条件FP树（myCondTree、myHead）
3.4 当条件FP树不为空时，继续下一步；否则退出递归
3.4 以myCondTree、myHead为新的输入，以newFreqSet为新的preFix，外加freqItemList，递归这个过程
代码：
def mineTree(inTree, headerTable, minSup, preFix, freqItemList):
# for i in headerTable.items():
# print(i[1])
# print('********************************')
bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p:str(p[1]))] #因为p[1]中第一个元素是int，第二个是treeNode对象，当第一个相等时会比较第二个
for basePat in bigL:
#print('basePat:',basePat)
#print('preFix:',preFix)
newFreqSet = preFix.copy()
newFreqSet.add(basePat)
freqItemList.append(newFreqSet)
condPattBases = findPrefixPath(basePat, headerTable[basePat][1])
#print('条件模式基:',condPattBases)
myCondTree, myHead = createTree(condPattBases, minSup)
print('myHead:',myHead)
if myHead != None:
# 用于测试
print('基于%s的条件树:'%newFreqSet)
myCondTree.disp()
mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)
辅助函数：原始数据集是字典，键是事务（记录），值是此记录出现的次数
def loadSimpDat():
simpDat = [['r', 'z', 'h', 'j', 'p'],
['z', 'y', 'x', 'w', 'v', 'u', 't', 's'],
['z'],
['r', 'x', 'n', 'o', 's'],
['y', 'r', 'x', 'z', 'q', 't', 'p'],
['y', 'z', 'x', 'e', 'q', 's', 't', 'm']]
return simpDat
def createInitSet(dataSet): #产生初始数据集
retDict = {}
for trans in dataSet:
retDict[frozenset(trans)] = 1
return retDict
测试：
if __name__=='__main__':
simpData = loadSimpDat()
initSet = createInitSet(simpData)
myFPtree, myHeaderTab = createTree(initSet, 3)
freqItems = []
mineTree(myFPtree, myHeaderTab, 3, set([]), freqItems)
print(freqItems)
输出：
基于{'s'}的条件树:
Null Set 1
x 3
基于{'y'}的条件树:
Null Set 1
x 3
z 3
基于{'y', 'z'}的条件树:
Null Set 1
x 3
基于{'t'}的条件树:
Null Set 1
y 3
x 3
z 3
基于{'z', 't'}的条件树:
Null Set 1
x 3
y 3
基于{'y', 'z', 't'}的条件树:
Null Set 1
x 3
基于{'x', 't'}的条件树:
Null Set 1
y 3
基于{'x'}的条件树:
Null Set 1
z 3
[{'r'}, {'s'}, {'x', 's'}, {'y'}, {'y', 'z'}, {'y', 'x', 'z'}, {'y', 'x'}, {'t'}, {'z', 't'}, {'x', 'z', 't'}, {'y', 'z', 't'}, {'y', 'x', 'z', 't'}, {'y', 't'}, {'x', 't'}, {'x', 't', 'y'}, {'x'}, {'x', 'z'}, {'z'}]
递归过程：
总结：FP-growth算法是一种用于发现数据集中频繁模式的有效方法。FP-growth算法利用Apriori原则，执行更快。Apriori算法用来产生候选项集，然后扫描数据集来检查它们是否频繁。由于只对数据集扫描两次，因此FP-growth算法执行更快。在FP-growth算法中，数据集存储在一个称为FP树的结构中。FP树构建完成后，可以通过查找元素项的条件基及构建条件FP树来发现频繁项集。该过程不断以更多元素作为条件重复进行，直到FP树只包含一个元素为止。
使用FP树来存储数据，包括每个候选频繁元素的链接，后续使用这些链接来寻找前缀路径，在用前缀路径在生成条件FP树来找到频繁项集。
由原始数据集得来的FP树包含两方面的重要信息：每个元素的链接，用来迅速查找元素的所有前缀路径；每个元素所在的路径，用来表明元素和其他哪些元素同时出现。