【Python机器学习】FP-growth算法——构建FP树

在第二次扫描数据集时会构建一棵FP树。为构建一棵树，需要一个容器来保存树。

创建FP树的数据结构

FP树要比书中其他树更加复杂，因此需要创建一个类来保存树的每一个节点：

class treeNode:def __init__(self,nameValue,numOccur,parentNode):self.name=nameValueself.count=numOccurself.nodeLink=Noneself.parent=parentNodeself.children={}def inc(self,numOccur):self.count=self.count+numOccurdef disp(self,ind=1):print(' '*ind,self.name,' ',self.count)for child in self.children.values():child.disp(ind+1)

上面的程序给出了FP树中节点的类定义。类中包含用于存放节点名字的变量和1个计数值，nodeLink变量用于链接相似的元素项。类中还使用了父变量parent来指向当前节点的父节点。通常情况下并不需要这个变量，因为通常是从上向下迭代访问节点的。之后还需要根据给定叶子节点上溯整棵树，这是就需要指向父节点的指针。最后，类中还包括一个空字典变量，用于存放节点的子节点。

上述代码还包括两个方法，其中inc()对count变量增加给定值，另一个方法disp()用于将树以文本形式显示。后者对于树构建来说并不是必要的，但它对调试非常有用。

创建一棵树的一个单节点，之后为其增加一个子节点：

rootNode=treeNode('pyramid',9,None)
rootNode.children['eye']=treeNode('eye',13,None)
print(rootNode.disp())

再添加一个节点看一下两个子节点的展示效果：

rootNode.children['phoenix']=treeNode('phoenix',3,None)
print(rootNode.disp())

现在FP树所需的数据结构已经建好，之后就可以构建FP树了。

构建FP树

FP树中，需要一个头指针来指向给定类型的第一个实例。利用头指针表，可以快速访问FP树中一个给定类型的所有元素，比如：

这里使用一个字典作为数据结构，来保存头指针表。除了存放指针外，头指针表还可以用来保存FP树中每个元素的总数。

第一次遍历数据集会获得每个元素项的出现频率。接下来，去掉不满足最小支持度的元素项。再下一步构建FP树。在构建时，读入每个项集并将其添加到一条已经存在的路径中。如果该路径不存在，则创建一条新路径。每个事务就是一个无序集合。假设有集合{z,x,y}和{y,z,r}，那么在FP树中，相同项会只表示一次。为了解决这个问题，在将集合添加到树之前，需要对每个集合进行排序。排序基于元素项的绝对出现频率来进行。使用上图中的头指针节点值，对数据进行过滤、重排序的数据如下：

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

对上表前两条事务进行添加的过程：

接下来是代码实现上述过程：

def createTree(dataSet,minSup=1):headerTable={}for trans in dataSet:for item in trans:headerTable[item]=headerTable.get(item,0)+dataSet[trans]#移除不满足最小支持度的元素项#print('keys：',list(headerTable.keys()))for k in list(headerTable.keys()):if headerTable[k]<minSup:del(headerTable[k])freqItemSet=set(headerTable.keys())#如果没有元素项满足要求，退出，返回Noneif len(freqItemSet)==0:return None,Nonefor k in headerTable:headerTable[k]=[headerTable[k],None]retTree=treeNode('Null set',1,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,headerTabledef updateTree(items,inTree,headerTable,count):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):while (nodeToTest.nodeLink != None):nodeToTest=nodeToTest.nodeLinknodeToTest.nodeLink=targetNode

上述代码包含3个函数。第一个函数createTree()使用数据集以及最小支持度作为参数构建FP树。树构建过程中会遍历数据集两次。第一次遍历扫描数据集并统计每个元素项出现的频度。所有所有项都不频繁，就不需要进行下一步处理。接下来，对头指针表稍加扩展以便可以保存计数值及指向每种类型第一个元素项的指针。然后创建只包含空集合的根节点。最后，再一次遍历数据集，这次只考虑哪些频繁项。这些项已经进行了排序，然后调用updateTree()方法。

为了让FP树生长，需调用updateTree，其中的输入参数为一个项集。该函数首先测试事务中的第一个元素项是否作为子节点存在。如果存在的话，则更新该元素项的计数；如果不存在，则创建一个新的treeNode并将其作为一个子节点添加到树中。这是，头指针表也要更新以指向新的节点。更新头指针表需要调用函数updateHeader()。updateTree()完成的最后一件事是不断迭代调用自身，每次调用时会去掉列表中第一个元素。

最后一个函数是updateHeader()，它确保节点链接指向树中该元素项的每一个实例。从头指针的nodeLink开始，一直沿着nodeLink直到到达链表末尾。这就是一个链表。当处理树的时候，一种很自然的反应就是迭代完成每一件事。当以相同方式处理链表时可能会遇到一些问题，原因是如果链表很长可能会遇到迭代调用的次数限制。

下面，创建一个真正的数据集，用来运行上面的函数，查看运行效果：

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)]=1return retDict

下面，实际运行，首先导入数据库实例，然后对数据进行格式化处理：

simpDat=loadSimpDat()
print(simpDat)

接下来，为了函数createTree，需要对上面的数据进行格式化处理：

initSet=createInitSet(simpDat)
print(initSet)

创建FP树：

myFPtree,myHeaderTab=createTree(initSet,3)
print(myFPtree.disp())

上面给出的是元素项及其对应的频率计数值，其中每个缩进表示所处的数的深度。