概述
- 优点：一般要快于Apriori
- 缺点：实现比较困难，在某些数据集上性能会下降
- 适用数据类型：标称型数据
FP-growth算法将数据存储在一种称为FP树的紧凑数据结构中。FP代表频繁模式（Frequent Pattern）。
FP树与其他树结构类似。但它会把相似元素连接起来，被连起来的元素项可以看作是链表。如下图所示。
一个元素项可以在一棵FP树出现多次。
FP树会存储项集的出现频率，而每个项集会以路径的方式存储在树中。
相似项之间的链接即节点链接（node link），用于快速发现相似项的位置。
下面再简单说明一下。
| 事务ID | 事务中的元素项 | 最小支持度过滤后 |
|---|---|---|
| 001 | r,z,h,j,p | r,z |
| 002 | z,y,x,w,v,u,t,s | z,y,x,t,s |
| 003 | z | z |
| 004 | r,x,n,o,s | r,x,s |
| 005 | y,r,x,z,q,t,p | y,r,x,z,t |
| 006 | y,z,x,e,q,s,t,m | y,z,x,s,t |
上表是生成上面FP树的数据。第二列“事务中的元素项”是原数据，然后经过最小支持度（关于支持度可以看之前Apriori算法的文章）过滤后，留下频繁项集。
图1树中节点z:5说明元素项出现5次。从z:5出发，沿着路径x:3、y:3，说明{z,x,y}出现3次。z:5 -> r:1说明{z,r}出现1次。到这里两条路径，z一共被使用4次，所以剩下的一次就是它自身{z}。通过观察上表最后一列“最小支持度过滤后”，可以知道上述结论的正确性。以此类推，就能大概知道FP树和频繁项集的对应关系了。
构建FP树
FP树的数据结构
因为FP树比较复杂，所以定义一个类来保存节点信息。
class treeNode:
def __init__(self, name, count, parentNode):
self.name = name # 节点名字
self.count = count # 计数值
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树中一个给定类型的所有元素。如下图。
集合是无序的，假设有{z,x,y}和{y,z,x}，那么在FP树中只会表示一条路径。为了解决这个问题，在将集合添加到树前，先基于元素项的出现频率进行排序。如下表。
| 事务ID | 事务中的元素项 | 最小支持度过滤后 | 排序后 |
|---|---|---|---|
| 001 | r,z,h,j,p | r,z | z,r |
| 002 | z,y,x,w,v,u,t,s | z,y,x,t,s | z,x,y,s,t |
| 003 | z | z | z |
| 004 | r,x,n,o,s | r,x,s | x,s,r |
| 005 | y,r,x,z,q,t,p | y,r,x,z,t | z,x,y,r,t |
| 006 | y,z,x,e,q,s,t,m | y,z,x,s,t | z,x,y,s,t |
进行过滤和排序之后，就可以构建FP树了。从空集开始，不断添加频繁项集。如下图。
大致了解FP树构建过程后，接下来就是代码实现了。
def createTree(dataSet, minSup=1):
headerTable = {}
# 第一次遍历数据集，统计每个元素项出现的次数
for trans in dataSet:
for item in trans:
headerTable[item] = headerTable.get(item, 0) + dataSet[trans]
# 移除不满足最小支持度的项
for k in list(headerTable.keys()):
if headerTable[k] < minSup:
del(headerTable[k])
freqItemSet = set(headerTable.keys())
print('freqItemSet: ',freqItemSet)
# 没有满足最小支持度的项，则退出
if len(freqItemSet) == 0:
return None, None
# 扩展头指针表以便后面的链接
for k in headerTable:
headerTable[k] = [headerTable[k], None]
print('headerTable: ',headerTable)
# 创建树
retTree = treeNode('根节点', 0, None)
for tranSet, count in dataSet.items(): # 第二次遍历数据集，构建树
localD = {}
# 过滤频繁项集
for item in tranSet:
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)
return retTree, headerTable
def updateTree(items, inTree, headerTable, count):
# 检查items[0]是否已在子节点
if items[0] in inTree.children:
inTree.children[items[0]].inc(count) # 是的话直接增加count
else: # 否则items[0]加到inTree.children
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(items[1::], inTree.children[items[0]], headerTable, count)
def updateHeader(nodeToTest, targetNode):
while (nodeToTest.nodeLink != None):
nodeToTest = nodeToTest.nodeLink
nodeToTest.nodeLink = targetNode
第一个函数createTree()有两个参数，数据集和最小支持度。这里支持度的定义跟Apriori算法的不一样，是元素项出现的次数。树构建过程中一共遍历数据集两次。
为了FP树生长（growth），需调用updateTree()进行填充。也就是图3的过程。
updateHeader()函数用于更新头指针表，确保节点链接指向树中该元素项的每一个实例。
接下来，模拟一个简单数据集，并实际构建FP树。
def createSimpDat():
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 transToDict(dataSet):
retDict = {}
for trans in dataSet:
retDict[frozenset(trans)] = 1
return retDict
data = transToDict(createSimpDat())
FPTree, headerTable = createTree(data, 3)
看一下data
也就是前面表中的数据。
再看一下FP树
对照最开始的图1，可以发现是一样的结构。
构建好FP树后，就可以使用它来进行频繁项集挖掘了。
画图不易吖～都看到最后了，要不~点个赞？加波关注？
