FP-Grouth算法学习小总结 By Assassin

学习FP-Grouth花了不少时间，但是觉得理解还是有一些偏差，这里分享一些好的资源吧！！！

首先我个人认为学习FP-Grouth理论的比较好的网站是下面的 FP-Grouth理论学习传送门

然后就是找到了一个python实现的FP-Grouth算法，代码用到了类，对于我这种水平的菜逼还是费了不少功夫的。。。下面将代码分享出来，具体的请见代码来源~ 代码来源

资料库 http://blog.****.net/bone_ace/article/details/46746727 http://blog.****.net/javastart/article/details/50521453 http://www.2cto.com/kf/201604/501816.html http://blog.****.net/javastart/article/details/50521453 http://wenku.baidu.com/link?url=lVuuWcxpa534YaAhdmNwWMnKBtZu9DjXznhdY6AcSW5_Be14xrIspegrCTce--DYXUSaubeuxyvW490JHf31jPzXaA_KOZAEN0kE4tDGtjO http://blog.****.net/lulin60/article/details/52255242 #__init__.py # -*- coding:utf-8 -*- import tree_builder import tree_miner routines = [ ['A','B','E'], ['A','C','D'], ['A','D','C','E'], ['C','D'] ] #数据来源 min_sup=2 #最小支持度 headerTable={} #头节点表，用来存放各个项的索引 treeBuilder= tree_builder.Tree_builder(routines=routines,min_sup=min_sup,headerTable=headerTable) #建造FP_growth,注意headerTable放进去了实际上在函数内对其进行了赋值！！！ tree_miner.Tree_miner(Tree=treeBuilder.tree, min_sup=min_sup, headerTable=headerTable) #对FP_Tree进行频繁项集的挖掘 #tree_builder.py 建FP树 # -*- coding:utf-8 -*- import tree_building class Tree_builder(object): """tree_builder类。 作用:根据事务数据集进行数据准备及构造树.""" def __init__(self,routines,min_sup=-1,counts=[],headerTable={}): self.routines=routines #数据集 self.counts=counts #不知道是啥 self.min_sup=min_sup #最小支持度 self.items = self.getItems(self.routines) #统计每一项及其出现频率 self.sortedItems = self.getSortedItems(self.items) #统计出现在最小度以上的项到一个队列中 self.itemTable = self.initItemsTable(headerTable) #创造头节点 ,注意在调用的时候 headerTable也跟着变化了 #注意这个地方有个坑，return事实上是返回地址，浅复制，所以headerTable和self.itemTable被绑定起来了！！！ self.tree = self.treeBuilding(self.counts) #递归建树，关键位置 def getItems(self,routines): """功能:扫描事务数据集,返回它的项集即各项的计数""" items={} for routine in routines: for elem in routine: items.setdefault(elem,0) #如果集合中没有，那么将之加入集合并且赋值为0 items[elem] += 1 return items def getSortedItems(self,items=None): """功能:对项集进行排序,并删去非频繁项,得到频繁1-项集""" sortedItems = [] temp = sorted(items.iteritems(),key=lambda asd:asd[1],reverse=True) #lambda的基本用法如果输入的是asd，因为之前items是一个集合集，那么这个asd[1]就是出现的次数,反向排序变成由大到小 for elem in temp: if elem[1]>=self.min_sup: #选择大于等于最小支持度的 sortedItems.append(elem[0]) return sortedItems def initItemsTable(self,itemsTable): #headerTable指定itemsTable，itemsTable指定self.itemTable！！ """功能:头结点表的初始化""" for item in self.sortedItems: itemsTable.setdefault(item,[]) #如果没有当前值，那么将之加入队列，赋值空集合[] return itemsTable def getSortedRoutine(self,routine): """功能:根据排序好的频繁1-项集对某一条事务routine进行排序""" sortedRoutine = [] for elem in self.sortedItems: if elem in routine: sortedRoutine.append(elem) #相当于我从排好序的标准中从1号向后找，如果在数据中压入，最后压入的数据相当于筛选了一遍且一定有序！ return sortedRoutine def treeBuilding(self,counts): """功能:逐条取出事务,控制FP_Tree树的构造""" tree = tree_building.Tree(itemTable=self.itemTable) for routine in self.routines: sortedRoutine = self.getSortedRoutine(routine) if counts: count =counts.pop(0) #在搜索的时候用到的 else : count =1 tree.addRoutine(routine=sortedRoutine,Rroot=tree.root,count=count) return tree #tree_building.py # -*- coding:utf-8 -*- class Node(object): """Node类. 作用:开辟一个树节点""" def __init__(self,data=-1,count = 0,parent=None): """Node类的初始化, 一个节点信息包括:项的值,计数,父亲节点,所有孩子节点""" self.data=data #数据 self.count=count #初始的数量是0 self.parent=parent #父节点 self.children={} #子节点的内容 class Tree(object): """tree_growth类. 作用:建造树""" def __init__(self,data = -1,parent=None,itemTable=None): """tree_growth类的初始化,开辟一个树根""" self.root=Node(data='null',parent=self) self.itemTable=itemTable def addRoutine(self,routine,Rroot,count): """功能:根据事务routine递归构造树, Rroot是树的根节点, count是routine出现的次数(构造条件FP_tree的时候有用)""" if len(routine)<= 0: #如果没有直接结束 return elem=routine.pop(0) #如果不是空的那么弹出第一个值 if elem in Rroot.children: #如果子节点中有这些数，那么下一个节点就是这个子节点 nextNode = Rroot.children[elem] else : #如果没有，那么新创建一个节点，相当于一个分支 newNode = Node(data = elem,parent=Rroot) Rroot.children.setdefault(elem,newNode) #根节点的子节点更新 nextNode=newNode nextNode.count += count if nextNode not in self.itemTable[elem]: #如果下一个节点不在子节点信息中，加入 self.itemTable[elem].append(nextNode) self.addRoutine(routine=routine,Rroot=nextNode,count=count) #不管怎么样，只要是routine不空就递归建树 return #tree_miner.py 迭代挖掘代码 # -*- coding:utf-8 -*- import tree_builder import copy class Tree_miner(object): """tree_miner类. 作用:对Tree进行频繁项集的挖掘""" def __init__(self, Tree=None, min_sup=-1, headerTable={}): """tree_miner的初始化. Tree即为构造好的FP_Tree, min_sup是最小支持度计数, headerTable是FP_Tree的头结点表""" self.min_sup = min_sup #设置最小支持度 self.tree_mining(Tree=Tree, headerTable=headerTable) def tree_mining(self, Tree, A=[], headerTable={}): """功能: 递归实现对树Tree频繁项集的挖掘. A相当于伪代码中的α，B相当于β""" B = [] allElem = {} #用来保存单个路径情况时，路径上的所有节点 node = Tree.root #node取得树的根节点 while len(node.children) > 0: #判断是否是单个路径 if len(node.children) != 1: #如果路径上的某个节点的孩子数不止一个，则它不是单个路径 break node = node.children.values()[0] #node取得下一个节点 allElem.setdefault(node.data,node.count) #记录路径上的节点，如果是单个路径的话会用到 if len(node.children) < 1: #Tree只包含单个路径 L = self.getL(items=allElem, min_sup=self.min_sup, A=A) #L即为我们要求的频繁项集 self.showResult(L) #对结果进行输出 return else: for item in headerTable: #对于头结点表中的元素，逐个找以其结尾的频繁项集 if A: #产生项目集B for elem in A: if elem != []: temp = copy.copy(elem) B.append(temp) B.append([item]+temp) PRint B else: B.append([item]) pattem,counts = self.findPattemBase(item, headerTable) #得到以项item结尾的所以条件模式基,counts存放条件模式基的计数 myHeaderTable = {} conditionTree_builder = tree_builder.Tree_builder(routines=pattem, counts=counts, headerTable=myHeaderTable) #新建一个Tree_builder对象，用它来构造条件FP-Tree if conditionTree_builder.tree.root.children: #如果构造的条件FP-树不空 self.tree_mining(Tree=conditionTree_builder.tree, A=B, headerTable=myHeaderTable) #递归调用求值 B = [] return def findPattemBase(self, item, headerTable):#找到的是以该点为最底层的路径数和数值大小 """功能: 根据树的头结点表去搜索树中item的条件模式基""" itemPattem = [] #存放项item的所有模式基 counts = [] #存放模式基的计数 addressTable = headerTable[item] #头节点表中item链上所以节点的地址，可能多个！ for itemNode in addressTable: #对头结点表表中存放的每个item节点 itemInPattem = [] #用来存放item模式基中的各项 nodeInPattem = itemNode.parent #item模式基的项，用它来回溯到树根，即为一条模式基 if nodeInPattem.data == 'null': #如果父亲节点就是树根，则跳过 continue while nodeInPattem.data != 'null': #如果还没到树根，则一直回溯 itemInPattem.append(nodeInPattem.data) #把它压进item的模式基 nodeInPattem = nodeInPattem.parent #让当前节点跳到它的父亲节点，进行回溯 itemInPattem = tuple(itemInPattem) itemPattem.append(itemInPattem) #找完了一条item的模式基了 counts.append(itemNode.count) #模式基的计数 return itemPattem,counts def showResult(self, result=[[]]): """功能: 将挖掘到的频繁项集进行展示""" for elem in result: num = elem.pop() #频繁项集的计数 #print tuple(elem),':',num return def combiner(self, myList, n): """功能: 对list列表里的所有元素进行排列组合,生成n个元组组合在一起的列表""" answers = [] one = [0] * n #从myList1-n开始选择 def next_c(li = 0, ni = 0): #li表示选择的起点，ni表示已经选择的长度 if ni == n: answers.append(copy.copy(one)) #结束压入数据 return for lj in xrange(li, len(myList)): #赋值后进一步工作 one[ni] = myList[lj] next_c(lj + 1, ni + 1) #继续搜索 next_c() return answers def findMinimum(self, items, elem): """功能: 根据items字典找出elem列表中各项计数的最小值""" minimum = items[elem[0]] for a in elem: if items[a] < minimum: #如果某元素的计数更小，则记录它的计数 minimum = items[a] return minimum def getL(self, items, min_sup=-1, A=[]): """功能: 对于只含单路径的树,进行生成频繁项集""" tempResult = [] finnalResult = [] nodes = items.keys() #取得items字典的键，即单路径上的所有节点放到了队列之中 for i in range(1,len(nodes)+1): #对nodes，即路径上的所有节点生成各种组合,长度为1-n tempResult += self.combiner(myList=nodes, n=i) for elem in tempResult[::-1]: #elem逆序对dearResult访问，因为接下来会删除元素，逆序好操作 elemMinimum = self.findMinimum(items, elem) #找出elem里面的最小计数--是数值！！！ if elemMinimum < min_sup: #如果组合elem的最小计数小于最小支持度计数，则删除. tempResult.remove(elem) else: #否则把它压入结果列表中进行输出，但它只是条件模式基，要加上最后一个项构成频繁项集，同时把最小计数也加上 for Aelem in A: #A可能含有多项 if Aelem: temp = elem temp += Aelem temp.append(elemMinimum) finnalResult.append(temp) #将挖掘出的频繁项集保存在finnalResult列表 return finnalResult

具体还是多看看网上的资料吧~