12.2 构建FP树

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

12.2.1　创建FP树的数据结构

本章的FP树要比书中其他树更加复杂，因此要创建一个类来保存树的每一个节点。创建文件fpGrowth.py并加入下列程序中的代码。

程序清单12-1　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树中节点的类定义。类中包含用于存放节点名字的变量和1个计数值，nodeLink变量用于链接相似的元素项（参考图12-1中的虚线）。类中还使用了父变量parent来指向当前节点的父节点。通常情况下并不需要这个变量，因为通常是从上往下迭代访问节点的。本章后面的内容中需要根据给定叶子节点上溯整棵树，这时就需要指向父节点的指针。最后，类中还包含一个空字典变量，用于存放节点的子节点。

程序清单12-1中包括两个方法，其中inc对count变量增加给定值，而另一个方法disp用于将树以文本形式显示。后者对于树构建来说并不是必要的，但是它对于调试非常有用。

运行一下如下代码：

>>> import fpGrowth
>>> rootNode = fpGrowth.treeNode(\'pyramid\',9, None)    
  

这会创建树中的一个单节点。接下来为其增加一个子节点：

>>> rootNode.children[\'eye\']=fpGrowth.treeNode(\'eye\', 13, None) 
  

为显示子节点，输入：

>>> rootNode.disp
    pyramid 9
        eye 13  
  

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

>>> rootNode.children[\'phoenix\']=fpGrowth.treeNode(\'phoenix\', 3, None)
>>> rootNode.disp
    pyramid 9
        eye 13
        phoenix 3   
  

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

12.2.2　构建FP树

除了图12-1给出的FP树之外，还需要一个头指针表来指向给定类型的第一个实例。利用头指针表，可以快速访问FP树中一个给定类型的所有元素。图12-2给出了一个头指针表的示意图。

图12-2　带头指针表的FP树，头指针表作为一个起始指针来发现相似元素项

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

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

表12-2　将非频繁项移除并且重排序后的事务数据集

在对事务记录过滤和排序之后，就可以构建FP树了。从空集（符号为Ø）开始，向其中不断添加频繁项集。过滤、排序后的事务依次添加到树中，如果树中已存在现有元素，则增加现有元素的值；如果现有元素不存在，则向树添加一个分枝。对表12-2前两条事务进行添加的过程显示在图12-3中。

图12-3　FP树构建过程的一个示意图，图中给出了使用表12-2中数据构建FP树的前两步。

通过上面的叙述，我们大致了解了从事务数据集转换为FP树的基本思想，接下来我们通过代码来实现上述过程。打开fpGrowth.py文件，加入下面的代码。

程序清单12-2　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 headerTable.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)
    for tranSet, count in dataSet.items:
        localD = {}
        #❸（以下三行）根据全局频率对每个事务中的元素进行排序 
        for item in tranSet:
            if item in freqItemSet:
                localD[item] = headerTable[item][
        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):
    if items[0] in inTree.children:
        inTree.children[items[0]].inc(count)
    else:
        inTree.children[items[0]] = treeNode(
        if headerTable[items[0]][1] == None:
            headerTable[items[0]][1] = inTree.
        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.nodeLink
    nodeToTest.nodeLink = targetNode
  

上述代码中包含3个函数。第一个函数createTree使用数据集以及最小支持度作为参数来构建FP树。树构建过程中会遍历数据集两次。第一次遍历扫描数据集并统计每个元素项出现的频度。这些信息被存储在头指针表中。接下来，扫描头指针表删掉那些出现次数少于minSup的项❶。如果所有项都不频繁，就不需要进行下一步处理❷。接下来，对头指针表稍加扩展以便可以保存计数值及指向每种类型第一个元素项的指针。然后创建只包含空集合Ø的根节点。最后，再一次遍历数据集，这次只考虑那些频繁项❸。这些项已经如表12-2所示那样进行了排序，然后调用updateTree方法❹。接下来讨论函数updateTree。

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

1. 这就是FP-growth中的growth（生长）一词的来源。

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

在运行上例之前，还需要一个真正的数据集。这可以从本书附带的代码库中获得，或者直接手工输入。loadSimpDat函数会返回一个事务列表。这和表12-1中的事务相同。后面构建树时会使用createTree函数，而该函数的输入数据类型不是列表。其需要的是一部字典，其中项集为字典中的键，而频率为每个键对应的取值。createInitSet用于实现上述从列表到字典的类型转换过程。将下列代码添加到fpGrowth.py文件中。

程序清单12-3　简单数据集及数据包装器

 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
  

好了，下面看看实际的效果。将程序清单12-3中的代码加入文件fpGrowth.py之后，在Python提示符下输入命令：

>>> reload(fpGrowth)
<module \'fpGrowth\' from \'fpGrowth.py\'>
  

首先，导入数据库实例：

>>> simpDat = fpGrowth.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\']]
  

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

>>> initSet = fpGrowth.createInitSet(simpDat)
>>> initSet
{frozenset([\'e\', \'m\', \'q\', \'s\', \'t\', \'y\', \'x\', \'z\']): 1, frozenset([\'x\',\'s\', \'r\', \'o\', \'n\']): 1, frozenset([\'s\', \'u\', \'t\', \'w\', \'v\', \'y\', \'x\',\'z\']): 1, frozenset([\'q\', \'p\', \'r\', \'t\', \'y\', \'x\', \'z\']): 1,frozenset([\'h\', \'r\', \'z\', \'p\', \'j\']): 1, frozenset([\'z\']): 1}  
  

于是可以通过如下命令创建FP树：

>>> myFPtree, myHeaderTab = fpGrowth.createTree(initSet, 3)     
  

使用disp方法给出树的文本表示结果：

>>> myFPtree.disp
Null Set 1
  x   1
    s   1
      r   1
  z   5
    x   3
      y   3
        s   2
          t   2
        r   1
          t   1
    r   1 
  

上面给出的是元素项及其对应的频率计数值，其中每个缩进表示所处的树的深度。读者可以验证一下这棵树与图12-2中所示的树是否等价。

现在我们已经构建了FP树，接下来就使用它进行频繁项集挖掘。