FP-growth算法以及代码实现

FP-growth算法以及代码实现

FP-growth算法介绍
FP-growth算法，它被用于挖掘频繁项集，它把数据集存储为一个叫FP树的数据结构里，这样可以更高效地发现频繁项集或频繁项对。

FP树
FP即Frequent Pattern，FP树看上去就是一棵前缀树，根节点是空集，结点上是单个元素，保存了它在数据集中的出现次数，出现次数越多的元素越接近根。此外，结点之间通过链接（link）相连，只有相似元素会被连起来，连起来的元素又可以看成链表。同一个元素可以在FP树中多次出现，根据位置不同，对应着不同的频繁项集。可以为FP树设置最小支持度，过滤掉出现次数太少的元素。
FP树每个结点上都是一个单独的元素，及其在路径中的出现次数。

构建FP树
1.遍历一次数据集，统计每个元素出现的次数，然后把出现次数较小的滤掉，然后对每个样本按照元素出现次数重排序
2.构造FP树。从根节点∅开始，将过滤并排序后的样本一个个加入树中，若FP树不存在现有元素则添加分支，若存在则增加相应的值。

每个样本都是排序过的，频数高的频繁项集在前面，它总是更接近根结点，所以也可以把每个样本看成一棵子树，而我们要做的就是把子树添加到FP树里

FP树构建实例

根据此数据集构造的FP树为：

从FP树挖掘频繁项集
步骤如下：
1.从FP树提取条件模式基
2.用条件模式基构造FP树
3.重复1和2直到树只包含一个元素
提取条件模式基
条件模式基（conditional pattern base）定义为以所查找元素为结尾的所有前缀路径（prefix path）的集合。我们要做的就是从header列表开始，针对每一个频繁项，都查找其对应的条件模式基。
上述实例路径：

频繁项集：

代码实现

classtreeNode:def__init__(self, nameValue, numOccur, parentNode):
        self.name= nameValue
        self.count= numOccur
        self.nodeLink=None
        self.parent= parentNode
        self.children={}definc(self, numOccur):
        self.count+= numOccurdefdisp(self, ind=1):print('  '* ind, self.name,' ', self.count)for childin self.children.values():
            child.disp(ind+1)# 当出现两个或两个以上的相似项时，找到最后一个相似项的实例，让该实例的self.nodeLink属性保存新出现的相似项# 效果如同是在一条链的最后一个节点后再接入一个节点，这些链就是self.nodeLinkdefupdateHeader(nodeToTest, targetNode):while nodeToTest.nodeLink!=None:
        nodeToTest= nodeToTest.nodeLink
    nodeToTest.nodeLink= targetNode# 接收处理好的事务列表，画出FP树defupdateFPtree(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]])# 递归iflen(items)>1:
        updateFPtree(items[1::], inTree.children[items[0]], headerTable, count)# 输入字典格式的事务和最小支持度，返回FP树和项头表defcreateFPtree(dataSet, minSup=3):
    headerTable={}for transin dataSet:for itemin trans:
            headerTable[item]= headerTable.get(item,0)+ dataSet[trans]for kinlist(headerTable.keys()):if headerTable[k]< minSup:del(headerTable[k])# 删除不满足最小支持度的元素
    freqItemSet=set(headerTable.keys())# 满足最小支持度的频繁项集iflen(freqItemSet)==0:returnNone,Nonefor kin headerTable:
        headerTable[k]=[headerTable[k],None]# element: [count, node]
    retTree= treeNode('Null Set',1,None)for tranSet, countin dataSet.items():
        localD={}for itemin tranSet:if itemin freqItemSet:# 过滤，只取该样本中满足最小支持度的频繁项
                localD[item]= headerTable[item][0]# element : countiflen(localD)>0:# 根据全局频数从大到小对单样本排序
            orderedItem=[v[0]for vinsorted(localD.items(), key=lambda p: p[1], reverse=True)]#print('orderItems=', orderedItem)# 用过滤且排序后的样本更新树
            updateFPtree(orderedItem, retTree, headerTable, count)return retTree, headerTable# 构造成 element : count 的形式，以字典形式输出defcreateInitSet(dataSet):
    retDict={}for transin dataSet:
        trans="".join(trans).split('，')
        key=frozenset(trans)if keyin retDict:
            retDict[frozenset(trans)]+=1else:
            retDict[frozenset(trans)]=1return retDict# 递归回溯，找到给定节点往上回溯到根节点的路径，并把路径存到列表中defascendFPtree(leafNode, prefixPath):if leafNode.parent!=None:
        prefixPath.append(leafNode.name)
        ascendFPtree(leafNode.parent, prefixPath)# 找到给定元素名称的条件模式基，以字典格式存贮deffindPrefixPath(basePat, myHeaderTab):
    treeNode= myHeaderTab[basePat][1]# basePat在FP树中的第一个结点
    condPats={}while treeNode!=None:
        prefixPath=[]
        ascendFPtree(treeNode, prefixPath)# prefixPath是倒过来的，从treeNode开始到根iflen(prefixPath)>1:
            condPats[frozenset(prefixPath[1:])]= treeNode.count# 关联treeNode的计数
        treeNode= treeNode.nodeLink# 下一个basePat结点return condPatsdefmineFPtree(inTree, headerTable, minSup, preFix, freqItemList):# 最开始的频繁项集是headerTable中的各元素
    bigL=[v[0]for vinsorted(headerTable.items(), key=lambda p: p[1][0])]# 根据频繁项的总频次排序#print("bigL:  ",bigL)for basePatin bigL:# 对每个频繁项
        newFreqSet= preFix.copy()
        newFreqSet.add(basePat)
        freqItemList.append(newFreqSet)
        condPattBases= findPrefixPath(basePat, headerTable)# 当前频繁项集的条件模式基
        myCondTree, myHead= createFPtree(condPattBases, minSup)# 构造当前频繁项的条件FP树if myHead!=None:
            mineFPtree(myCondTree, myHead, minSup, newFreqSet, freqItemList)# 递归挖掘条件FP树if __name__=='__main__':
    parsedDat=[line.split()for lineinopen('FPGrowth_datasets/shopping_cart.csv').readlines()]
    initSet= createInitSet(parsedDat)
    myFPtree, myHeaderTab= createFPtree(initSet)
    myFPtree.disp()
    myFreqList=[]
    mineFPtree(myFPtree, myHeaderTab,3,set([]), myFreqList)print("频繁项集的数量是: %s"%len(myFreqList))for itemin myFreqList:print(item)