北京公司网站制作流程,福州网站制作维护,长沙影楼网站建设,张店网络推广公司文章目录 0 赛题思路1 算法介绍2 FP树表示法3 构建FP树4 实现代码 0 赛题思路
#xff08;赛题出来以后第一时间在CSDN分享#xff09;
https://blog.csdn.net/dc_sinor?typeblog
1 算法介绍
FP-Tree算法全称是FrequentPattern Tree算法#xff0c;就是频繁模式树算法赛题出来以后第一时间在CSDN分享
https://blog.csdn.net/dc_sinor?typeblog
1 算法介绍
FP-Tree算法全称是FrequentPattern Tree算法就是频繁模式树算法他与Apriori算法一样也是用来挖掘频繁项集的不过不同的是FP-Tree算法是Apriori算法的优化处理他解决了Apriori算法在过程中会产生大量的候选集的问题而FP-Tree算法则是发现频繁模式而不产生候选集。但是频繁模式挖掘出来后产生关联规则的步骤还是和Apriori是一样的。
常见的挖掘频繁项集算法有两类一类是Apriori算法另一类是FP-growth。Apriori通过不断的构造候选集、筛选候选集挖掘出频繁项集需要多次扫描原始数据当原始数据较大时磁盘I/O次数太多效率比较低下。FPGrowth不同于Apriori的“试探”策略算法只需扫描原始数据两遍通过FP-tree数据结构对原始数据进行压缩效率较高。
FP代表频繁模式Frequent Pattern) 算法主要分为两个步骤FP-tree构建、挖掘频繁项集。
2 FP树表示法
FP树通过逐个读入事务并把事务映射到FP树中的一条路径来构造。由于不同的事务可能会有若干个相同的项因此它们的路径可能部分重叠。路径相互重叠越多使用FP树结构获得的压缩效果越好如果FP树足够小能够存放在内存中就可以直接从这个内存中的结构提取频繁项集而不必重复地扫描存放在硬盘上的数据。
一颗FP树如下图所示 通常FP树的大小比未压缩的数据小因为数据的事务常常共享一些共同项在最好的情况下所有的事务都具有相同的项集FP树只包含一条节点路径当每个事务都具有唯一项集时导致最坏情况发生由于事务不包含任何共同项FP树的大小实际上与原数据的大小一样。
FP树的根节点用φ表示其余节点包括一个数据项和该数据项在本路径上的支持度每条路径都是一条训练数据中满足最小支持度的数据项集FP树还将所有相同项连接成链表上图中用蓝色连线表示。
为了快速访问树中的相同项还需要维护一个连接具有相同项的节点的指针列表headTable每个列表元素包括数据项、该项的全局最小支持度、指向FP树中该项链表的表头的指针。
3 构建FP树
现在有如下数据 FP-growth算法需要对原始训练集扫描两遍以构建FP树。
第一次扫描过滤掉所有不满足最小支持度的项对于满足最小支持度的项按照全局最小支持度排序在此基础上为了处理方便也可以按照项的关键字再次排序。
第二次扫描构造FP树。
参与扫描的是过滤后的数据如果某个数据项是第一次遇到则创建该节点并在headTable中添加一个指向该节点的指针否则按路径找到该项对应的节点修改节点信息。具体过程如下所示 从上面可以看出headTable并不是随着FPTree一起创建而是在第一次扫描时就已经创建完毕在创建FPTree时只需要将指针指向相应节点即可。从事务004开始需要创建节点间的连接使不同路径上的相同项连接成链表。
4 实现代码
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 simpDatdef createInitSet(dataSet):retDict {}for trans in dataSet:fset frozenset(trans)retDict.setdefault(fset, 0)retDict[fset] 1return retDictclass treeNode:def __init__(self, nameValue, numOccur, parentNode):self.name nameValueself.count numOccurself.nodeLink Noneself.parent parentNodeself.children {}def inc(self, numOccur):self.count numOccurdef disp(self, ind1):print( * ind, self.name, , self.count)for child in self.children.values():child.disp(ind 1)def createTree(dataSet, minSup1):headerTable {}#此一次遍历数据集 记录每个数据项的支持度for trans in dataSet:for item in trans:headerTable[item] headerTable.get(item, 0) 1#根据最小支持度过滤lessThanMinsup list(filter(lambda k:headerTable[k] minSup, headerTable.keys()))for k in lessThanMinsup: del(headerTable[k])freqItemSet set(headerTable.keys())#如果所有数据都不满足最小支持度返回None, Noneif len(freqItemSet) 0:return None, Nonefor k in headerTable:headerTable[k] [headerTable[k], None]retTree treeNode(φ, 1, None)#第二次遍历数据集构建fp-treefor tranSet, count in dataSet.items():#根据最小支持度处理一条训练样本key:样本中的一个样例value:该样例的的全局支持度localD {}for item in tranSet:if item in freqItemSet:localD[item] headerTable[item][0]if len(localD) 0:#根据全局频繁项对每个事务中的数据进行排序,等价于 order by p[1] desc, p[0] descorderedItems [v[0] for v in sorted(localD.items(), keylambda p: (p[1],p[0]), reverseTrue)]updateTree(orderedItems, retTree, headerTable, count)return retTree, headerTabledef updateTree(items, inTree, headerTable, count):if items[0] in inTree.children: # check if orderedItems[0] in retTree.childreninTree.children[items[0]].inc(count) # incrament countelse: # add items[0] to inTree.childreninTree.children[items[0]] treeNode(items[0], count, inTree)if headerTable[items[0]][1] None: # update header tableheaderTable[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 itemsupdateTree(items[1:], inTree.children[items[0]], headerTable, count)def updateHeader(nodeToTest, targetNode): # this version does not use recursionwhile (nodeToTest.nodeLink ! None): # Do not use recursion to traverse a linked list!nodeToTest nodeToTest.nodeLinknodeToTest.nodeLink targetNodesimpDat loadSimpDat()
dictDat createInitSet(simpDat)
myFPTree,myheader createTree(dictDat, 3)
myFPTree.disp()上面的代码在第一次扫描后并没有将每条训练数据过滤后的项排序而是将排序放在了第二次扫描时这可以简化代码的复杂度。
控制台信息
