
最近小编了解到了一个的概念: 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
PowerBI 累计曲线制作指南:从 DAX 度量到可视化落地 在业务数据分析中,“累计趋势” 是衡量业务进展的核心视角 —— 无论是 “ ...
2025-08-15Python 函数 return 多个数据:用法、实例与实战技巧 在 Python 编程中,函数是代码复用与逻辑封装的核心载体。多数场景下,我们 ...
2025-08-15CDA 数据分析师:引领商业数据分析体系构建,筑牢企业数据驱动根基 在数字化转型深化的今天,企业对数据的依赖已从 “零散分析” ...
2025-08-15随机森林中特征重要性(Feature Importance)排名解析 在机器学习领域,随机森林因其出色的预测性能和对高维数据的适应性,被广 ...
2025-08-14t 统计量为负数时的分布计算方法与解析 在统计学假设检验中,t 统计量是常用的重要指标,其分布特征直接影响着检验结果的判断。 ...
2025-08-14CDA 数据分析师与业务数据分析步骤 在当今数据驱动的商业世界中,数据分析已成为企业决策和发展的核心驱动力。CDA 数据分析师作 ...
2025-08-14前台流量与后台流量:数据链路中的双重镜像 在商业数据分析体系中,流量数据是洞察用户行为与系统效能的核心依据。前台流量与 ...
2025-08-13商业数据分析体系构建与 CDA 数据分析师的协同赋能 在企业数字化转型的浪潮中,商业数据分析已从 “可选工具” 升级为 “核 ...
2025-08-13解析 CDA 数据分析师:数据时代的价值挖掘者 在数字经济高速发展的今天,数据已成为企业核心资产,而将数据转化为商业价值的 ...
2025-08-13解析 response.text 与 response.content 的核心区别 在网络数据请求与处理的场景中,开发者经常需要从服务器返回的响应中提取数 ...
2025-08-12MySQL 统计连续每天数据:从业务需求到技术实现 在数据分析场景中,连续日期的数据统计是衡量业务连续性的重要手段 —— 无论是 ...
2025-08-12PyTorch 中 Shuffle 机制:数据打乱的艺术与实践 在深度学习模型训练过程中,数据的呈现顺序往往对模型性能有着微妙却关键的影响 ...
2025-08-12Pandas 多列条件筛选:从基础语法到实战应用 在数据分析工作中,基于多列条件筛选数据是高频需求。无论是提取满足特定业务规则的 ...
2025-08-12人工智能重塑 CDA 数据分析领域:从工具革新到能力重构 在数字经济浪潮与人工智能技术共振的 2025 年,数据分析行业正经历着前所 ...
2025-08-12游戏流水衰退率:计算方法与实践意义 在游戏行业中,流水(即游戏收入)是衡量一款游戏商业表现的核心指标之一。而游戏流水衰退 ...
2025-08-12CDA 一级:数据分析入门的基石 在当今数据驱动的时代,数据分析能力已成为职场中的一项重要技能。CDA(Certified Data Anal ...
2025-08-12破解游戏用户流失困局:从数据洞察到留存策略 在游戏行业竞争白热化的当下,用户流失率已成为衡量产品健康度的核心指标。一款游 ...
2025-08-11数据时代的黄金入场券:CDA 认证解锁职业新蓝海 一、万亿级市场需求下的数据分析人才缺口 在数字化转型浪潮中,数据已成为企业核 ...
2025-08-11DBeaver 实战:实现两个库表结构同步的高效路径 在数据库管理与开发工作中,保持不同环境(如开发库与生产库、主库与从库)的表 ...
2025-08-08t 检验与卡方检验:数据分析中的两大统计利器 在数据分析领域,统计检验是验证假设、挖掘数据规律的重要手段。其中,t 检验和卡 ...
2025-08-08