2023年第四届“华数杯”数学建模思路 - 案例:FPTree-频繁模式树算法
## 赛题思路
(赛题出来以后第一时间在CSDN分享)
https://blog.csdn.net/dc_sinor?type=blog
算法介绍
FP-Tree算法全称是FrequentPattern Tree算法,就是频繁模式树算法,他与Apriori算法一样也是用来挖掘频繁项集的,不过不同的是,FP-Tree算法是Apriori算法的优化处理,他解决了Apriori算法在过程中会产生大量的候选集的问题,而FP-Tree算法则是发现频繁模式而不产生候选集。但是频繁模式挖掘出来后,产生关联规则的步骤还是和Apriori是一样的。
常见的挖掘频繁项集算法有两类,一类是Apriori算法,另一类是FP-growth。Apriori通过不断的构造候选集、筛选候选集挖掘出频繁项集,需要多次扫描原始数据,当原始数据较大时,磁盘I/O次数太多,效率比较低下。FPGrowth不同于Apriori的“试探”策略,算法只需扫描原始数据两遍,通过FP-tree数据结构对原始数据进行压缩,效率较高。
FP代表频繁模式(Frequent Pattern) ,算法主要分为两个步骤:FP-tree构建、挖掘频繁项集。
FP树表示法
FP树通过逐个读入事务,并把事务映射到FP树中的一条路径来构造。由于不同的事务可能会有若干个相同的项,因此它们的路径可能部分重叠。路径相互重叠越多,使用FP树结构获得的压缩效果越好;如果FP树足够小,能够存放在内存中,就可以直接从这个内存中的结构提取频繁项集,而不必重复地扫描存放在硬盘上的数据。
一颗FP树如下图所示:

通常,FP树的大小比未压缩的数据小,因为数据的事务常常共享一些共同项,在最好的情况下,所有的事务都具有相同的项集,FP树只包含一条节点路径;当每个事务都具有唯一项集时,导致最坏情况发生,由于事务不包含任何共同项,FP树的大小实际上与原数据的大小一样。
FP树的根节点用φ表示,其余节点包括一个数据项和该数据项在本路径上的支持度;每条路径都是一条训练数据中满足最小支持度的数据项集;FP树还将所有相同项连接成链表,上图中用蓝色连线表示。
为了快速访问树中的相同项,还需要维护一个连接具有相同项的节点的指针列表(headTable),每个列表元素包括:数据项、该项的全局最小支持度、指向FP树中该项链表的表头的指针。

构建FP树
现在有如下数据:

FP-growth算法需要对原始训练集扫描两遍以构建FP树。
第一次扫描,过滤掉所有不满足最小支持度的项;对于满足最小支持度的项,按照全局最小支持度排序,在此基础上,为了处理方便,也可以按照项的关键字再次排序。

第二次扫描,构造FP树。
参与扫描的是过滤后的数据,如果某个数据项是第一次遇到,则创建该节点,并在headTable中添加一个指向该节点的指针;否则按路径找到该项对应的节点,修改节点信息。具体过程如下所示:






从上面可以看出,headTable并不是随着FPTree一起创建,而是在第一次扫描时就已经创建完毕,在创建FPTree时只需要将指针指向相应节点即可。从事务004开始,需要创建节点间的连接,使不同路径上的相同项连接成链表。
实现代码
def loadSimpDat():simpDat = [['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 simpDatdef createInitSet(dataSet):retDict = {}for trans in dataSet:fset = frozenset(trans)retDict.setdefault(fset, 0)retDict[fset] += 1return retDictclass treeNode:def __init__(self, nameValue, numOccur, parentNode):self.name = nameValueself.count = numOccurself.nodeLink = Noneself.parent = parentNodeself.children = {}def inc(self, numOccur):self.count += numOccurdef disp(self, ind=1):print(' ' * ind, self.name, ' ', self.count)for child in self.children.values():child.disp(ind + 1)def createTree(dataSet, minSup=1):headerTable = {}#此一次遍历数据集, 记录每个数据项的支持度for trans in dataSet:for item in trans:headerTable[item] = headerTable.get(item, 0) + 1#根据最小支持度过滤lessThanMinsup = list(filter(lambda k:headerTable[k] < minSup, headerTable.keys()))for k in lessThanMinsup: del(headerTable[k])freqItemSet = set(headerTable.keys())#如果所有数据都不满足最小支持度,返回None, Noneif len(freqItemSet) == 0:return None, Nonefor k in headerTable:headerTable[k] = [headerTable[k], None]retTree = treeNode('φ', 1, None)#第二次遍历数据集,构建fp-treefor tranSet, count in dataSet.items():#根据最小支持度处理一条训练样本,key:样本中的一个样例,value:该样例的的全局支持度localD = {}for item in tranSet:if item in freqItemSet:localD[item] = headerTable[item][0]if len(localD) > 0:#根据全局频繁项对每个事务中的数据进行排序,等价于 order by p[1] desc, p[0] descorderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: (p[1],p[0]), reverse=True)]updateTree(orderedItems, retTree, headerTable, count)return retTree, headerTabledef updateTree(items, inTree, headerTable, count):if items[0] in inTree.children: # check if orderedItems[0] in retTree.childreninTree.children[items[0]].inc(count) # incrament countelse: # add items[0] to inTree.childreninTree.children[items[0]] = treeNode(items[0], count, inTree)if headerTable[items[0]][1] == None: # update header tableheaderTable[items[0]][1] = inTree.children[items[0]]else:updateHeader(headerTable[items[0]][1], inTree.children[items[0]])if len(items) > 1: # call updateTree() with remaining ordered itemsupdateTree(items[1:], inTree.children[items[0]], headerTable, count)def updateHeader(nodeToTest, targetNode): # this version does not use recursionwhile (nodeToTest.nodeLink != None): # Do not use recursion to traverse a linked list!nodeToTest = nodeToTest.nodeLinknodeToTest.nodeLink = targetNodesimpDat = loadSimpDat()
dictDat = createInitSet(simpDat)
myFPTree,myheader = createTree(dictDat, 3)
myFPTree.disp()
上面的代码在第一次扫描后并没有将每条训练数据过滤后的项排序,而是将排序放在了第二次扫描时,这可以简化代码的复杂度。
控制台信息:

相关文章:
2023年第四届“华数杯”数学建模思路 - 案例:FPTree-频繁模式树算法
## 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 算法介绍 FP-Tree算法全称是FrequentPattern Tree算法,就是频繁模式树算法,他与Apriori算法一样也是用来挖掘频繁项集的,…...
MySQL做分布式锁
分布式锁mysql实现方式 方式1:唯一索引 创建锁表,内部存在字段表示资源名及资源描述,同一资源名使用数据库唯一性限制。多个进程同时往数据库锁表中写入对某个资源的占有记录,当某个进程成功写入时则表示其获取锁成功其他进程由于…...
Python学习笔记:变量类型、字符串基本操作
1.注释 单行注释 # 单行注释 多行注释 """ 多行注释 """2.变量类型 # 基本变量类型 a 1 # integer b 1.5 # float c string # String d "string" # string e False # boolean # list\tuple\dictionar…...
JVM的组件、自动垃圾回收的工作原理、分代垃圾回收过程、可用的垃圾回收器类型
详细画的jvm模型图 https://www.processon.com/diagraming/64c8aa11c07d99075d934311 官方网址 https://www.oracle.com/webfolder/technetwork/tutorials/obe/java/gc01/index.html 相关概念 年轻代是所有新对象被分配和老化的地方。当年轻代填满时,这会导致m…...
【elementui】解决el-select组件失去焦点blur事件每次获取的是上一次选中值的问题
目录 【问题描述】 【问题摘要】 【分析问题】 【完整Test代码】 【封装自定义指令】 ↑↑↑↑↑↑↑↑↑↑↑↑ 不想看解决问题过程的可点击上方【封装自定义指令】目录直接跳转获取结果即可~~~ 【问题描述】 一位朋友遇到这么一个开发场景:在表格里面嵌入el-…...
通过了PMP考试,还有什么证书值得考?
自从7月24号公布了PMP成绩后,不少伙伴私信小编:通过PMP后还有哪些证书可以提升自己?一来是多份高含金量的证书可以多点竞争力,二来是加持自己的职业发展!今天小编就来给大家捋一捋! 一.NPDP认证 2016 年 4…...
页面技术基础-html
页面技术基础-html 环境准备:在JDBC中项目上完成代码定义 1. 新建一个 Module:filr->右键 -》Module -》Java-》next->名字(html_day1)->finish 2. 在 Moudle上右键-》第二个选项:add framework .. -> 选择JavaEE下第一个选项 Web Apllicat…...
/lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.28‘ not found
某项目中,我要给别人封装一个深度学习算法的SDK接口,运行在RK3588平台上,然后客户给我的交叉编译工具链是 然后我用他们给我的交叉编译工具链报下面的错误: aarch64-buildroot-linux-gnu-gcc --version /data/chw/aarch64/bin/cca…...
解决SVN或GIT忽略提交文件的问题
背景 使用IDEA 的SVN插件提交文件是总是会提交一些不需要提交的文件; 我们可以通过一些简单设置忽略这些文件。 git 在项目根目录新建文本文件,修改后缀为.gitignore 文件中添加内容 *.iml .project .gradle/ .idea/ target/ build/ .vscode/ .settings/ .facto…...
Django框架之路由用法
简介 路由简单的来说就是根据用户请求的 URL 链接来判断对应的处理程序,并返回处理结果,也就是 URL 与 Django 的视图建立映射关系。 Django 路由在 urls.py 配置,urls.py 中的每一条配置对应相应的处理方法。 Django 不同版本 urls.py 配…...
回文链表 LeetCode热题100
题目 给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。 思路 利用快慢指针找到链表中间节点,反转后半段链表。前半段从头节点开始与后半段比较。 注意当链表节点…...
如何在群晖NAS中使用cpolar内网穿透
如何在群晖nas中使用cpolar内网穿透 文章目录 如何在群晖nas中使用cpolar内网穿透 今天,我们来为大家介绍,如何在群晖系统中,使用图形化界面的cpolar。 cpolar经过图形化改造后,使用方法已经简便了很多,基本与其他应用…...
无头单向不循环链表和带头双向循环链表的创建
Lei宝啊:个人主页 愿所有美好不期而遇 前言: 接下来我们将会了解最基础的链表--->单链表 以及最方便也是最爽的链表--->带头双向循环链表。 若有看不懂之处,可画图或者借鉴这里:反转单链表,对于数据结构而言&am…...
超简单的fastapi链接websocket用例
main.py from typing import Listfrom fastapi import FastAPI, WebSocket, WebSocketDisconnectapp FastAPI()class ConnectionManager:def __init__(self):# 存放激活的ws连接对象self.active_connections: List[WebSocket] []async def connect(self, ws: WebSocket):# 等…...
MySQL详解
目录 一、MySQL 概述二、MySQL 安装和配置三、MySQL 基础语法四、MySQL 高级语法五、MySQL 性能优化六、MySQL 应用场景和实例七、MySQL 开发工具和插件八、MySQL 学习资源和社区 一、MySQL 概述 MySQL 是一种开源的关系型数据库管理系统,最初由瑞典的 MySQL AB 公…...
Vue [Day2]
指令修饰符 v-model.trim v-model.number 事件名.stop click.stop 事件名.prevent keyup.enter <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-w…...
【前端|Javascript第1篇】一文搞懂Javascript的基本语法
欢迎来到JavaScript的奇妙世界!作为前端开发的基石,JavaScript为网页增色不少,赋予了静态页面活力与交互性。如果你是一名前端小白,对编程一无所知,或者只是听说过JavaScript却从未涉足过,那么你来对了地方…...
【Linux命令200例】cp用于复制文件和目录(常用)
🏆作者简介,黑夜开发者,全栈领域新星创作者✌,阿里云社区专家博主,2023年6月csdn上海赛道top4。 🏆本文已收录于专栏:Linux命令大全。 🏆本专栏我们会通过具体的系统的命令讲解加上鲜…...
C高级_第二讲_shell指令和shell脚本_递归练习
思维导图 递归实现,输入一个数,输出这个数的每一位 int funh(int num){if(0 num){return 0;}else{funh(num/10);printf("%d\n", num%10);} }int main(int argc, const char *argv[]) {puts("请输入一个数");int num 0;scanf(&quo…...
静态路由综合实验
实验拓扑如下: 实验要求如下: 【1】R6为isp,接口IP地址均为公有地址;该设备只能配置IP地址,之后不能再对其进行任何配置 【2】R1~R5为局域网,私有IP地址192.168.1.0/24,请合理分配 【3】所有路由器上环回…...
网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
【JVM面试篇】高频八股汇总——类加载和类加载器
目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...
tomcat指定使用的jdk版本
说明 有时候需要对tomcat配置指定的jdk版本号,此时,我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...
【LeetCode】算法详解#6 ---除自身以外数组的乘积
1.题目介绍 给定一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O…...
