最近小编了解到了一个的概念: 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树
数据分析咨询请扫描二维码
《Python数据分析极简入门》 第2节 2 Pandas数据类型 Pandas 有两种自己独有的基本数据结构。需要注意的是,它固然有着两种数据 ...
2024-11-01《Python数据分析极简入门》 第2节 1 Pandas简介 说好开始学Python,怎么到了Pandas? 前面说过,既然定义为极简入门,我们只抓 ...
2024-10-31在当今数据驱动的世界中,数据科学与工程专业的重要性愈发凸显。无论是推动技术进步,还是在商业决策中提供精准分析,这一专业都 ...
2024-10-30在当今信息爆炸的时代,数据已成为企业决策和战略制定的核心资源。爬虫工程师因此成为数据获取和挖掘的关键角色。本文将详细介绍 ...
2024-10-30在当今数据驱动的世界中,数据分析是揭示商业洞察和推动决策的核心力量。选择合适的数据分析工具对于数据专业人士而言至关重要。 ...
2024-10-30能源企业在全球经济和环境保护双重压力下,正面临前所未有的挑战与机遇。数字化转型作为应对这些挑战的关键手段,正在深刻变革传 ...
2024-10-30近年来,随着数据科学的逐步发展,Python语言的使用率也越来越高,不仅可以做数据处理,网页开发,更是数据科学、机器学习、深度 ...
2024-10-30大数据分析师证书 针对不同知识,掌握程度的要求分为【领会】、【熟知】、【应用】三个级别,考生应按照不同知识要求进行学习。 ...
2024-10-30《Python数据分析极简入门》 附:Anaconda安装教程 注:分Windows系统下安装和MacOS系统安装 1. Windows系统下安装 第一步清华大 ...
2024-10-29拥抱数据分析的世界 - 成为一名数据分析工程师是一个充满挑战和机遇的职业选择。要成功地进入这个领域,你需要掌握一系列关键技 ...
2024-10-28降本增效:管理战略的关键 企业管理中的降本增效不仅是一项重要的战略举措,更是激发竞争力、提高盈利能力的关键。这一理念在当 ...
2024-10-28企业数字化是指利用数字技术和信息化手段,对企业的各个方面进行改造和优化,以提升生产效率、服务质量和市场竞争力的过程。实现 ...
2024-10-28数据科学专业毕业后,毕业生可以选择从事多种不同的岗位和领域。数据科学是一个快速发展且广泛应用的领域,毕业生在企业、学术界 ...
2024-10-28学习数据科学与大数据技术是当今职业发展中至关重要的一环。从基础到高级,以下是一些建议的课程路径: 基础课程: Python编程 ...
2024-10-28在信息技术和数据科学领域,数据架构师扮演着至关重要的角色。他们负责设计和管理企业中复杂的数据基础设施,以支持数据驱动的决 ...
2024-10-28进入21世纪以来,随着信息技术的迅猛发展,大数据已经成为全球最具影响力的技术之一,并成为企业数字化转型的核心驱动力。大数据 ...
2024-10-28随着科技的迅猛发展,数字化转型已成为现代企业保持竞争力和推动增长的关键战略之一。数字化不仅仅是技术的应用,它代表着一种全 ...
2024-10-28银行业正处于一个前所未有的数字化转型时期。在数字经济的驱动下,金融科技如大数据、人工智能、生物识别、物联网和云计算等技术 ...
2024-10-28数据分析可视化是一门艺术与科学相结合的技术,其主要目标是将复杂的数据变得更易于理解和分析。通过将数据以图表的形式呈现,我 ...
2024-10-28数据分析师在现代信息密集型的商业世界中扮演着至关重要的角色。他们通过专业的技能和敏锐的商业洞察力,帮助企业从大量数据中提 ...
2024-10-28