您好,登录后才能下订单哦!
这篇文章主要讲解了“用FP-growth算法发现频繁项集”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“用FP-growth算法发现频繁项集”吧!
首先从FP树头指针表中的单个频繁元素项开始。对于每一个元素项,获得其对应的条件模式基(conditional pattern base),单个元素项的条件模式基也就是元素项的关键字。条件模式基是以所查找元素项为结尾的路径集合。每一条路径其实都是一条前辍路径(perfix path)。简而言之,一条前缀路径是介于所査找元素项与树根节点之间的所有内容。
下图是以{s:2}或{r:1}为元素项的前缀路径:
{s}的条件模式基,即前缀路径集合共有两个:{{z,x,y,t}, {x}};{r}的条件模式基共三个:{{z}, {z,x,y,t}, {x,s}}。
寻找条件模式基的过程实际上是从FP树的每个叶子节点回溯到根节点的过程。我们可以通过头指针列表headTable开始,通过指针的连接快速访问到所有根节点。下表是上图FP树的所有条件模式基:
为了发现更多的频繁项集,对于每一个频繁项,都要创建一棵条件FP树。可以使用刚才发现的条件模式基作为输入数据,并通过相同的建树代码来构建这些树。然后,递归地发现频繁项、发现条件模式基,以及发现另外的条件树。
以频繁项r为例,构建关于r的条件FP树。r的三个前缀路径分别是{z},{z,x,y,t},{x,s},设最小支持度minSupport=2,则y,t,s被过滤掉,剩下{z},{z,x},{x}。y,s,t虽然是条件模式基的一部分,但是并不属于条件FP树,即对于r来说,它们不是频繁的。如下图所示,y→t→r和s→r的全局支持度都为1,所以y,t,s对于r的条件树来说是不频繁的。
过滤后的r条件树如下:
重复上面步骤,r的条件模式基是{z,x},{x},已经没有能够满足最小支持度的路径, 所以r的条件树仅有一个。需要注意的是,虽然{z,x},{x}中共存在两个x,但{z,x}中,z是x的父节点,在构造条件FP树时不能直接将父节点移除,仅能从子节点开始逐级移除。
代码如下:
def ascendTree(leafNode, prefixPath): if leafNode.parent != None: prefixPath.append(leafNode.name) ascendTree(leafNode.parent, prefixPath) def findPrefixPath(basePat, headTable): condPats = {} treeNode = headTable[basePat][1] 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=1, preFix=set([]), freqItemList=[]): # order by minSup asc, value asc bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p: (p[1][0],p[0]))] for basePat in bigL: newFreqSet = preFix.copy() newFreqSet.add(basePat) freqItemList.append(newFreqSet) # 通过条件模式基找到的频繁项集 condPattBases = findPrefixPath(basePat, headerTable) myCondTree, myHead = createTree(condPattBases, minSup) if myHead != None: print('condPattBases: ', basePat, condPattBases) myCondTree.disp() print('*' * 30) mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList) simpDat = loadSimpDat() dictDat = createInitSet(simpDat) myFPTree,myheader = createTree(dictDat, 3) myFPTree.disp() condPats = findPrefixPath('z', myheader) print('z', condPats) condPats = findPrefixPath('x', myheader) print('x', condPats) condPats = findPrefixPath('y', myheader) print('y', condPats) condPats = findPrefixPath('t', myheader) print('t', condPats) condPats = findPrefixPath('s', myheader) print('s', condPats) condPats = findPrefixPath('r', myheader) print('r', condPats) mineTree(myFPTree, myheader, 2)
控制台信息:
感谢各位的阅读,以上就是“用FP-growth算法发现频繁项集”的内容了,经过本文的学习后,相信大家对用FP-growth算法发现频繁项集这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是亿速云,小编将为大家推送更多相关知识点的文章,欢迎关注!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。