FP树与python实现

作者:青岛澄润国际贸易有限公司 来源:www.usabcc.com 发布时间:2017-09-09 10:17:28
FP树与python实现

FP-growth算法可以高效的发现频繁项集,但是该算法不能去发现关联规则,FP-growth算法 只需要对数据库进行两次扫描,采集软件,一般情况下其算法效率高于Apriori算法两个数量级。

一颗FP树是如下图1所示:



跟别的树没什么区别,只是增加了相似节点的链接。

FP树的定义:vcD4KPHA+PC9wPgo8cHJlIGNsYXNzPQ=="brush:java;">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)

disp()函数主要是以文本显示出树的结构。在实现中,我们需要一个头指针表来指向给定类型第一个实例,如下图2:



这个算法核心部分就是建立FP树,下面是建树代码:

def createTree(dataSet, minSup=1): #create FP-tree from dataset but don't mine headerTable = {} #go over dataSet twice for trans in dataSet:#first pass counts frequency of occurance for item in trans: headerTable[item] = headerTable.get(item, 0) + dataSet[trans] for k in headerTable.keys(): #remove items not meeting minSup if headerTable[k] < minSup: del(headerTable[k]) freqItemSet = set(headerTable.keys()) #print 'freqItemSet: ',freqItemSet if len(freqItemSet) == 0: return None, None #if no items meet min support -->get out for k in headerTable: headerTable[k] = [headerTable[k], None] #reformat headerTable to use Node link #print 'headerTable: ',headerTable retTree = treeNode('Null Set', 1, None) #create tree for tranSet, count in dataSet.items(): #go through dataset 2nd time localD = {} for item in tranSet: #put transaction items in order if item in freqItemSet: 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)#populate tree with ordered freq itemset return retTree, headerTable #return tree and header table def updateTree(items, inTree, headerTable, count): if items[0] in inTree.children:#check if orderedItems[0] in retTree.children inTree.children[items[0]].inc(count) #incrament count else: #add items[0] to inTree.children inTree.children[items[0]] = treeNode(items[0], count, inTree) if headerTable[items[0]][1] == None: #update header table 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): #this version does not use recursion while (nodeToTest.nodeLink != None): #Do not use recursion to traverse a linked list! nodeToTest = nodeToTest.nodeLink nodeToTest.nodeLink = targetNode参考着图2 我们可以比较清楚理解建树过程:headerTable就是头指针表,维护这张表是为了后面发现频繁项集中用到做准备。这里有一些实现细节东西,我们对所有的元素项先进行计数,如果不满足最低支持度,直接删掉不用加入FP树中。updateTree()函数时更新树,updateHeader()是维护headerTable头指针表 。

从一棵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) 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][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) 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 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 def ascendTree(leafNode,prefixPath): if leafNode.parent !=None: prefixPath.append(leafNode.name) ascendTree(leafNode.parent, prefixPath) def findPrefixPath(basePat,treeNode): condPats={} while treeNode != None: prefixPath = [] ascendTree(treeNode, prefixPath) if len(prefixPath) > 1: condPats[frozenset(prefixPath[1:])] = treeNode.count treeNode = treeNode.nodeLink return condPats 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(basePat, headerTable[basePat][1]) myCondTree,myHead = createTree(condPattBases, minSup) if myHead!= None: print 'conditional tree for: ',newFreqSet myCondTree.disp(1) mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList) if __name__ == "__main__": simpDat = loadSimpDat() print simpDat initSet = createInitSet(simpDat) print initSet myFPtree , myHeaderTab = createTree(initSet, 3) myFPtree.disp() print findPrefixPath('t', myHeaderTab['t'][1]) freqItems = [] mineTree(myFPtree, myHeaderTab, 3, set([]), freqItems) print freqItems
输出结果: [['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']] {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} 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 {frozenset(['y', 'x', 's', 'z']): 2, frozenset(['y', 'x', 'r', 'z']): 1} conditional tree for: set(['y']) Null Set 1 x 3 z 3 conditional tree for: set(['y', 'z']) Null Set 1 x 3 conditional tree for: set(['s']) Null Set 1 x 3 conditional tree for: set(['t']) Null Set 1 y 3 x 3 z 3 conditional tree for: set(['x', 't']) Null Set 1 y 3 conditional tree for: set(['z', 't']) Null Set 1 y 3 x 3 conditional tree for: set(['x', 'z', 't']) Null Set 1 y 3 conditional tree for: set(['x']) Null Set 1 z 3 [set(['y']), set(['y', 'x']), set(['y', 'z']), set(['y', 'x', 'z']), set(['s']), set(['x', 's']), set(['t']), set(['y', 't']), set(['x', 't']), set(['y', 'x', 't']), set(['z', 't']), set(['y', 'z', 't']), set(['x', 'z', 't']), set(['y', 'x', 'z', 't']), set(['r']), set(['x']), set(['x', 'z']), set(['z'])]


企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:武汉网络营销 https://www.feimao666.com

  • 上一篇:python中strip()函数的理解
  • 下一篇:最后一页
  •