
最近小编了解到了一个的概念: FP-growth,废话就不多说了,直接把整理的FP-growth的干货分享给大家。
一、FP-growth是什么
FP-Growth(频繁模式增长)算法是由韩家炜老师在2000年提出的关联分析算法,它的分治策略为:将提供频繁项集的数据库压缩到一棵频繁模式树(FP-Tree),但仍保留项集关联信息。
FP-growth算法通常被用来挖掘频繁项集,即从已给的多条数据记录中,挖掘出哪些项是频繁一起出现的。这种算法算法适用于标称型数据,也就是离散型数据。其实我们经常能接触到FP-growth算法,就比如,我们在百度的搜索框内输入某个字或者词,搜索引擎就会会自动补全查询词项,往往这些词项都是与搜索词经常一同出现的。
FP-growth算法源于Apriori的,是通过将数据集存储在FP(Frequent Pattern)树上发现频繁项集,但缺点是,不能发现数据之间的关联规则。与Apriori相比,FP-growth算法更为高效,因为FP-growth算法只需要对数据库进行两次扫描,而Apriori算法在求每个潜在的频繁项集时都需要扫描一次数据集。
二、FP-Tree算法基本结构
FPTree算法的基本数据结构,包含一个一棵FP树和一个项头表,每个项通过一个结点链指向它在树中出现的位置。基本结构如下所示。需要注意的是项头表需要按照支持度递减排序,在FPTree中高支持度的节点只能是低支持度节点的祖先节点。
FP-Tree:即上面的那棵树,是把事务数据表中的各个事务数据项按照支持度排序后,把每个事务中的数据项按降序依次插入到一棵以NULL为根结点的树中,同时在每个结点处记录该结点出现的支持度。
条件模式基:包含FP-Tree中与后缀模式一起出现的前缀路径的集合。即同一个频繁项在PF树中的所有节点的祖先路径的集合。例如I3在FP树中总共出现了3次,其祖先路径分别是{I2.I1:2(频度为2)},{I2:2}和{I1:2}。这3个祖先路径的集合就是频繁项I3的条件模式基。
条件树:将条件模式基按照FP-Tree的构造原则形成的一个新的FP-Tree。比如上图中I3的条件树就是。
三、FP-growth算法
FP-growth算法挖掘频繁项集的基本过程分为两步:
(1)构建FP树。
首先构造FP树,然后利用它来挖掘频繁项集。在构造FP树时,需要对数据集扫描两边,第一遍扫描用来统计频率,第二遍扫描至考虑频繁项集。
(2)从FP树中挖掘频繁项集。
首先,获取条件模式基。条件模式基是以所查找元素项为结尾的路径集合,表示的是所查找的元素项与树根节点之间的所有内容。
其次,构建条件模式基。对于每一个频繁项,都需要创建一棵条件FP树,使用创建的条件模式基作为输入,采用相同的建树代码来构建树,相应的递归发现频繁项、发现条件模式基和另外的条件树。
四、python代码实现
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 updateHeader(nodeToTest, targetNode): while nodeToTest.nodeLink != None: nodeToTest = nodeToTest.nodeLink nodeToTest.nodeLink = targetNode def updateFPtree(items, inTree, headerTable, count): if items[0] in inTree.children: # 判断items的第一个结点是否已作为子结点 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: updateFPtree(items[1::], inTree.children[items[0]], headerTable, count) def createFPtree(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] # element: [count, node] retTree = treeNode('Null Set', 1, None) for tranSet, count in dataSet.items(): # dataSet:[element, count] localD = {} for item in tranSet: if item in freqItemSet: # 过滤,只取该样本中满足最小支持度的频繁项 localD[item] = headerTable[item][0] # element : count if len(localD) > 0: # 根据全局频数从大到小对单样本排序 orderedItem = [v[0] for v in sorted(localD.items(), key=lambda p:p[1], reverse=True)] # 用过滤且排序后的样本更新树 updateFPtree(orderedItem, retTree, headerTable, count) return retTree, headerTable def loadSimpDat(): simDat = [['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 simDat # 构造成 element : count 的形式 def createInitSet(dataSet): retDict={} for trans in dataSet: key = frozenset(trans) if retDict.has_key(key): retDict[frozenset(trans)] += 1 else: retDict[frozenset(trans)] = 1 return retDict # 数据集 def loadSimpDat(): simDat = [['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 simDat # 构造成 element : count 的形式 def createInitSet(dataSet): retDict={} for trans in dataSet: key = frozenset(trans) if retDict.has_key(key): retDict[frozenset(trans)] += 1 else: retDict[frozenset(trans)] = 1 return retDict # 递归回溯 def ascendFPtree(leafNode, prefixPath): if leafNode.parent != None: prefixPath.append(leafNode.name) ascendFPtree(leafNode.parent, prefixPath) # 条件模式基 def findPrefixPath(basePat, myHeaderTab): treeNode = myHeaderTab[basePat][1] # basePat在FP树中的第一个结点 condPats = {} while treeNode != None: prefixPath = [] ascendFPtree(treeNode, prefixPath) # prefixPath是倒过来的,从treeNode开始到根 if len(prefixPath) > 1: condPats[frozenset(prefixPath[1:])] = treeNode.count # 关联treeNode的计数 treeNode = treeNode.nodeLink # 下一个basePat结点 return condPats def mineFPtree(inTree, headerTable, minSup, preFix, freqItemList): # 最开始的频繁项集是headerTable中的各元素 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) # 当前频繁项集的条件模式基 myCondTree, myHead = createFPtree(condPattBases, minSup) # 构造当前频繁项的条件FP树 if myHead != None: # print 'conditional tree for: ', newFreqSet # myCondTree.disp(1) mineFPtree(myCondTree, myHead, minSup, newFreqSet, freqItemList) # 递归挖掘条件FP树
数据分析咨询请扫描二维码
若不方便扫码,搜微信号:CDAshujufenxi
CDA 数据分析师:就业前景广阔的新兴职业 在当今数字化时代,数据已成为企业和组织决策的重要依据。数据分析师作为负责收集 ...
2025-06-30探秘卷积层:为何一个卷积层需要两个卷积核 在深度学习的世界里,卷积神经网络(CNN)凭借其强大的特征提取能力 ...
2025-06-30探索 CDA 数据分析师在线课程:开启数据洞察之旅 在数字化浪潮席卷全球的当下,数据已成为企业决策、创新与发展的核心驱 ...
2025-06-303D VLA新范式!CVPR冠军方案BridgeVLA,真机性能提升32% 编辑:LRST 【新智元导读】中科院自动化所提出BridgeVLA模型,通过将 ...
2025-06-30LSTM 为何会产生误差?深入剖析其背后的原因 在深度学习领域,LSTM(Long Short-Term Memory)网络凭借其独特的记忆单元设 ...
2025-06-27LLM进入拖拽时代!只靠Prompt几秒定制大模型,效率飙升12000倍 【新智元导读】最近,来自NUS、UT Austin等机构的研究人员创新 ...
2025-06-27探秘 z-score:数据分析中的标准化利器 在数据的海洋中,面对形态各异、尺度不同的数据,如何找到一个通用的标准来衡量数据 ...
2025-06-26Excel 中为不同柱形设置独立背景(按数据分区)的方法详解 在数据分析与可视化呈现过程中,Excel 柱形图是展示数据的常用工 ...
2025-06-26CDA 数据分析师会被 AI 取代吗? 在当今数字化时代,数据的重要性日益凸显,数据分析师成为了众多企业不可或缺的角色 ...
2025-06-26CDA 数据分析师证书考取全攻略 在数字化浪潮汹涌的当下,数据已成为企业乃至整个社会发展的核心驱动力。数据分析师作 ...
2025-06-25人工智能在数据分析的应用场景 在数字化浪潮席卷全球的当下,数据以前所未有的速度增长,传统的数据分析方法逐渐难以满足海 ...
2025-06-25评估模型预测为正时的准确性 在机器学习与数据科学领域,模型预测的准确性是衡量其性能优劣的核心指标。尤其是当模型预测结 ...
2025-06-25CDA认证:数据时代的职业通行证 当海通证券的交易大厅里闪烁的屏幕实时跳动着市场数据,当苏州银行的数字金融部连夜部署新的风控 ...
2025-06-24金融行业的大数据变革:五大应用案例深度解析 在数字化浪潮中,金融行业正经历着深刻的变革,大数据技术的广泛应用 ...
2025-06-24Power Query 中实现移动加权平均的详细指南 在数据分析和处理中,移动加权平均是一种非常有用的计算方法,它能够根据不同数据 ...
2025-06-24数据驱动营销革命:解析数据分析在网络营销中的核心作用 在数字经济蓬勃发展的当下,网络营销已成为企业触达消费者 ...
2025-06-23随机森林模型与 OPLS-DA 的优缺点深度剖析 在数据分析与机器学习领域,随机森林模型与 OPLS-DA(正交偏最小二乘法判 ...
2025-06-23CDA 一级:开启数据分析师职业大门的钥匙 在数字化浪潮席卷全球的今天,数据已成为企业发展和决策的核心驱动力,数据分析师 ...
2025-06-23透视表内计算两个字段乘积的实用指南 在数据处理与分析的过程中,透视表凭借其强大的数据汇总和整理能力,成为了众多数据工 ...
2025-06-20CDA 一级考试备考时长全解析,助你高效备考 CDA(Certified Data Analyst)一级认证考试,作为数据分析师领域的重要资格认证, ...
2025-06-20