FP GROWTH发现频繁项集FP-growth发现频繁项集

附实践代码：

# -*- coding:utf8 -*-

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 updateHeader(nodeToTest, targetNode):

    while nodeToTest.nodeLink != None:

        nodeToTest = nodeToTest.nodeLink

    nodeToTest.nodeLink = targetNode

def updateFPtree(items, inTree, headerTable, count):

    if items[0] in inTree.children:

        # 判断items的第一个结点是否已作为子结点

        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:

        updateFPtree(items[1::], inTree.children[items[0]], headerTable, count)

def createFPtree(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] # element: [count, node]

    retTree = treeNode('Null Set', 1, None)

    for tranSet, count in dataSet.items():

        # dataSet：[element, count]

        localD = {}

        for item in tranSet:

            if item in freqItemSet: # 过滤，只取该样本中满足最小支持度的频繁项

                localD[item] = headerTable[item][0] # element : count

        if len(localD) > 0:

            # 根据全局频数从大到小对单样本排序

            orderedItem = [v[0] for v in sorted(localD.items(), key=lambda p:p[1], reverse=True)]

            # 用过滤且排序后的样本更新树

            updateFPtree(orderedItem, retTree, headerTable, count)

    return retTree, headerTable

# 数据集

def loadSimpDat():

    simDat = [['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 simDat

# 构造成 element : count 的形式

def createInitSet(dataSet):

    retDict={}

    for trans in dataSet:

        key = frozenset(trans)

        if retDict.has_key(key):

            retDict[frozenset(trans)] += 1

        else:

            retDict[frozenset(trans)] = 1

    return retDict

simDat = loadSimpDat()

initSet = createInitSet(simDat)

myFPtree, myHeaderTab = createFPtree(initSet, 3) # 最小支持度3

myFPtree.disp()