# coding:utf-8 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 createTree(dataSet, minSup=1): #根据数据创建FP树，minSup为出现次数的阈值 headerTable = {} #字母表，需要存储两个信息：1.该字母的出现次数，2.指向该字母出现在FP树上的头指针 # 统计每个字母出现的次数 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()) #将符合条件的字母放到一个set中，即freqItemSet if len(freqItemSet) == 0: return None, None # if no items meet min support -->get out for k in headerTable: #为headerTable开辟多一个位置，存放头指针 headerTable[k] = [headerTable[k], None] # reformat headerTable to use Node link retTree = treeNode(‘Null Set‘, 1, None) # 创建根节点 for tranSet, count in dataSet.items(): # 将每一条数据插进FP树中，期间需要去除掉数据中出现次数低于阈值的字母，且数据中字母需要按照字典序排序 localD = {} #用于存放该数据中符合条件的字母 for item in tranSet: # 枚举这条数据的每个字母 if item in freqItemSet: #如果该字母符合条件，则放进localD中 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) # 然后将其插入FP树中 return retTree, headerTable # 返回FP树和字母表 def updateTree(items, inTree, headerTable, count): #将一条数据插进FP树中，类似于将一条字符串插进Trie树中 if items[0] in inTree.children: # 若首字母的结点存在，则直接更细该节点的计数器 inTree.children[items[0]].inc(count) # incrament 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: # call updateTree() with remaining ordered items updateTree(items[1::], inTree.children[items[0]], headerTable, count) def updateHeader(nodeToTest, targetNode): # 将新建的字母结点加入到字母表链的链尾，但个人认为头插法更优 while (nodeToTest.nodeLink != None): # Do not use recursion to traverse a linked list! nodeToTest = nodeToTest.nodeLink nodeToTest.nodeLink = targetNode def ascendTree(leafNode, prefixPath): #在FP树，从一个结点开始，上溯至根节点，并记录路径。这样就找到了频繁项的一个前缀路径 if leafNode.parent != None: prefixPath.append(leafNode.name) ascendTree(leafNode.parent, prefixPath) def findPrefixPath(treeNode): # 在FP树，找出某个字母所有的前缀路径，即找到对应的条件模式基 condPats = {} #存储前缀路径，为何要用字典的形式？因为还要记录每条前缀路径的出现次数，然后又用来创建FP树 while treeNode != None: prefixPath = [] #保存当前的前缀路径 ascendTree(treeNode, prefixPath) if len(prefixPath) > 1: #因为该节点也被加进了路径当中，所以需要路径的长度大于1 condPats[frozenset(prefixPath[1:])] = treeNode.count #将前缀路径并其出现次数存起来 treeNode = treeNode.nodeLink #沿着字母表链，走向下一个结点，继续寻找前缀路径 return condPats ‘‘‘递归地从FP树中挖掘频繁项集，headerTable为字母表，preFix为当前频繁项集合的前缀， freqItemList用于存储频繁项3‘‘‘ def mineTree(inTree, headerTable, minSup, preFix, freqItemList): bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p: p[1])] # 对字母表进行排序（根据出现次数），但为什么 要排序呢? for basePat in bigL: # 枚举字母表中的每一个字母 newFreqSet = preFix.copy() newFreqSet.add(basePat) #将该字母加入到“当前频繁项集合的前缀”中，形成新的频繁项集 freqItemList.append(newFreqSet) #保存新的频繁项集 condPattBases = findPrefixPath(headerTable[basePat][1]) #在当前FP树中找到该字母的条件模式基 # 然后利用条件模式基创建新的FP树，这棵“新”的FP树只不过是在当前的FP树的基础上，以basePat的父节点为叶子结点作裁剪 myCondTree, myHead = createTree(condPattBases, minSup) if myHead != None: # 如果裁剪过后的FP树仍不为空，则将新的频繁项集作为“当前频繁项集合的前缀”，然后在裁剪过后的FP树上继续挖掘频繁项集 mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)
《机器学习实战》学习笔记第十二章 —— FP-growth算法
原文：https://www.cnblogs.com/DOLFAMINGO/p/9534558.html