FP-growth算法发现频繁项集——发现频繁项集
上篇介绍了如何构建FP树,FP树的每条路径都满足最小支持度,我们需要做的是在一条路径上寻找到更多的关联关系。
抽取条件模式基
首先从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树
为了发现更多的频繁项集,对于每一个频繁项,都要创建一棵条件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)
控制台信息:
总结
本篇文章就到这了,本例可以发现两个频繁项集{z,x}和{x}。取得频繁项集后,可以根据置信度发现关联规则,这一步较为简单,可参考上篇的相关内容,不在赘述。希望能够给你带来帮助,也希望您能够多多关注猪先飞的其他精彩内容!
相关文章
- 作者:Sabine 【导读】本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序 using System; namespace BubbleSorter { public class Bubb...2020-06-25
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
- 这篇文章主要是介绍了.net C# 实现任意List的全组合算法实现代码,需要的朋友可以参考下...2020-06-25
同时兼容JS和C#的RSA加密解密算法详解(对web提交的数据加密传输)
这篇文章主要给大家介绍了关于同时兼容JS和C#的RSA加密解密算法,通过该算法可以对web提交的数据进行加密传输,文中通过图文及示例代码介绍的非常详细,需要的朋友们可以参考借鉴,下面来一起看看吧。...2020-06-25图文详解Heap Sort堆排序算法及JavaScript的代码实现
这篇文章以图文详解Heap Sort堆排序算法及JavaScript的代码实现,堆排序算法基于类二叉树的堆数据结构,需要的朋友可以参考下...2016-05-05- 这篇文章主要介绍了C#常用数据结构和算法,这里我们总结了一些知识点,可以帮助大家理解这些概念。...2020-06-25
- 这篇文章主要介绍了JS实现的随机排序功能算法,结合具体实例形式分析了javascript常用的排序算法实现技巧,需要的朋友可以参考下...2017-06-15
- 这篇文章主要介绍了c# 如何实现位图算法(BitMap),文中讲解非常细致,帮助大家更好的理解和学习,感兴趣的朋友可以了解下...2020-11-03
- 这篇文章主要介绍了C++实现的O(n)复杂度内查找第K大数算法,结合实例形式分析了算法的原理以及具体实现方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要给大家介绍了关于Vue虚拟Dom与diff算法的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-08-26
- 在本篇文章里小编给大家整理的是一篇关于R语言关于随机森林算法的知识点详解内容,有兴趣的朋友们可以跟着学习下。...2021-05-13
- 这篇文章主要介绍了C++并查集亲戚(Relations)算法,实例分析了并查集亲戚算法的原理与实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-04-25
- 这篇文章主要为大家详细介绍了C/C++实现八大排序算法汇总,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 本篇文章介绍了,稀疏图上的Johnson算法的详解。需要的朋友参考下...2020-04-25
- 这篇文章主要介绍了C# URL短地址压缩算法及短网址原理解析,本文重点给出了算法代码,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了VC++实现选择排序算法简单示例,代码简洁易懂,有助于读者对数据结构与算法的学习,需要的朋友可以参考下...2020-04-25
- 在本篇文章里小编给大家整理的是一篇关于php回溯算法计算组合总和的实例代码,有需要的朋友们可以学习参考下。...2021-07-14
- 在开发项目的过程中,我们经常会需要关于javascript数组的一些算法,比方说数组去重、数组求交集、数组扰乱等等。今天就把个人的汇总整理的算法分享给大家。...2016-02-18
- 这篇文章主要介绍了C++基于递归算法解决汉诺塔问题与树的遍历功能,简单描述了递归算法的原理,并结合实例形式分析了基于递归算法解决汉诺塔问题与数的遍历相关操作技巧,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了c++11新增的便利算法,主要有用于判断、查找、数组、序列等的操作算法,非常具有实用价值,需要的朋友可以参考下...2020-04-25