fp树生成的过程中有遗漏


from numpy import *


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)


def createTree(dataSet, minSup=1):
    headerTable = {}
    for trans in dataSet:
        for item in trans:
            headerTable[item] = headerTable.get(item, 0) + dataSet[trans]  # get函数找到item键的值
    for k in list(headerTable.keys()):
        if headerTable[k] < minSup:
            del (headerTable[k])
    freqItemSet = set(headerTable.keys())  # 频繁项集,set创建集合无序无法索引，要转成列表后索引
    # 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][0]  # 键的值是headerTable键的值的第一个元素
        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(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


def loadSimDat():
    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



import fpGrowth

#rootNode= fpGrowth.treenode('py',9,None)
#rootNode.children['eye']=fpGrowth.treenode('eye',13,None)
#rootNode.disp()
simpDat=fpGrowth.loadSimDat()
#print(simpDat)
iniSet=fpGrowth.createInitSet(simpDat)
#print(iniSet)
mytree,myheader=fpGrowth.createTree(iniSet,3)
mytree.disp()

程序输出的fp树为什么和书上的不一样

img


我生成的树

不知道你这个问题是否已经解决, 如果还没有解决的话:
  • 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7758914
  • 我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：功能点(FP)分析详细解释
  • 除此之外, 这篇博客: 数据挖掘入门中的 3.3.1 构建FP树 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
    1. 支持度排序：扫描一次数据集，确定每个项的支持度计数。丢弃非频繁项，而将频繁项按照支持度的递减排序。L = {a:8, b:7, c:6, d:5, e:3}

    2. 构建FP树：第二次扫描数据集，读入第一个事务{a, b}之后，创建标记为a和b的结点。然后形成null->a->b路径。该路径上的所有结点的频度计数为1。

      读入第二个事务{b,c,d}之后，为项b,c和d创建新的结点集。然后，连接结点null->b->c->d，形成一条代表该事务的路径。该路径上的每个结点的频度计数也等于1.

    注意：尽管前两个事务具有一个共同项b，但是它们的路径不相交，因为这两个事务没有共同的前缀.


如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^