2023国赛数学建模思路 - 案例:FPTree-频繁模式树算法
文章目录
- 算法介绍
- FP树表示法
- 构建FP树
- 实现代码
- 建模资料
## 赛题思路
(赛题出来以后第一时间在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-频繁模式树算法
文章目录 算法介绍FP树表示法构建FP树实现代码 建模资料 ## 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 算法介绍 FP-Tree算法全称是FrequentPattern Tree算法,就是频繁模式树算法,…...
GPT系列总结
1.GPT1 无监督预训练有监督的子任务finetuning https://cdn.openai.com/research-covers/language-unsupervised/language_understanding_paper.pdf 1.1 Unsupervised pre-training (1)基于一个transformer decoder,通过一个窗口的输入得…...
【福建事业单位-综合基础知识】05民法典
这里写自定义目录标题 一、民法概述概念原则总结 二、自然人概念总结 三、民事法律行为总结 民法考察2-4题(重点总则篇) 一、民法概述 概念原则 总结 二、自然人 概念 总结 三、民事法律行为 总结...
微服务篇
微服务篇 springcloud 常见组件有哪些 面试官: Spring Cloud 5大组件有哪些? 候选人: 早期我们一般认为的Spring Cloud五大组件是 Eureka:注册中心Ribbon:负载均衡Feign:远程调用Hystrix:…...
C++ 的关键字(保留字)完整介绍
1. asm asm (指令字符串):允许在 C 程序中嵌入汇编代码。 2. auto auto(自动,automatic)是存储类型标识符,表明变量"自动"具有本地范围,块范围的变量声明(如for循环体内的变量声明…...
C#小轮子:MiniExcel,快速操作Excel
文章目录 前言环境安装功能测试普通读写读新建Excel表格完全一致测试:成功大小写测试:严格大小写别名读测试:成功 写普通写别名写内容追加更新模板写 其它功能xlsx和CSV互转 前言 Excel的操作是我们最常用的操作,Excel相当于一个…...
Ribbon负载均衡
Ribbon与Eureka的关系 Eureka的服务拉取与负载均衡都是由Ribbon来实现的。 当服务发送http://userservice/user/xxxhtt://userservice/user/xxx请求时,是无法到达userservice服务的,会通过Ribbon会把这个请求拦截下来,通过Eureka-server转换…...
LeetCode--HOT100题(33)
目录 题目描述:148. 排序链表(中等)题目接口解题思路代码 PS: 题目描述:148. 排序链表(中等) 给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。 LeetCode做题链接࿱…...
【docker练习】
1.安装docker服务,配置镜像加速器 看这篇文章https://blog.csdn.net/HealerCCX/article/details/132342679?spm1001.2014.3001.5501 2.下载系统镜像(Ubuntu、 centos) [rootnode1 ~]# docker pull centos [rootnode1 ~]# docker pull ubu…...
韦东山-电子量产工具项目:业务系统
代码结构 所有代码都已通过测试跑通,其中代码结构如下: 一、include文件夹 1.1 common.h #ifndef _COMMON_H #define _COMMON_Htypedef struct Region {int iLeftUpX; //区域左上方的坐标int iLeftUpY; //区域左下方的坐标int iWidth; //区域宽…...
React(6)
1.React插槽 import React, { Component } from react import Child from ./compoent/Childexport default class App extends Component {render() {return (<div><Child><div>App下的div</div></Child></div>)} }import React, { Compon…...
RabbitMq-2安装与配置
Rabbitmq的安装 1.上传资源 注意:rabbitmq的版本必须与erlang编译器的版本适配 2.安装依赖环境 //打开虚拟机 yum install build-essential openssl openssl-devel unixODBC unixODBC-devel make gcc gcc-c kernel-devel m4 ncurses-devel tk tc xz3.安装erlan…...
论文笔记:Continuous Trajectory Generation Based on Two-Stage GAN
2023 AAAI 1 intro 1.1 背景 建模人类个体移动模式并生成接近真实的轨迹在许多应用中至关重要 1)生成轨迹方法能够为城市规划、流行病传播分析和交通管控等城市假设分析场景提供仿仿真数据支撑2)生成轨迹方法也是目前促进轨迹数据开源共享与解决轨迹数…...
redis实战-缓存数据解决缓存与数据库数据一致性
缓存的定义 缓存(Cache),就是数据交换的缓冲区,俗称的缓存就是缓冲区内的数据,一般从数据库中获取,存储于本地代码。防止过高的数据访问猛冲系统,导致其操作线程无法及时处理信息而瘫痪,这在实际开发中对企业讲,对产品口碑,用户评价都是致命的;所以企业非常重视缓存…...
【排序】选择排序
文章目录 选择排序时间复杂度空间复杂度稳定性 代码 选择排序 以从小到大为例进行说明。 选择排序就是定义出一个最小值下标,然后遍历整个剩下的数组选择出最小的放进最小值下标的位置。 时间复杂度 O(N) 遍历一次即可 空间复杂度 O(1) 稳定性 不稳定 代码 p…...
深入浅出Pytorch函数——torch.nn.init.trunc_normal_
分类目录:《深入浅出Pytorch函数》总目录 相关文章: 深入浅出Pytorch函数——torch.nn.init.calculate_gain 深入浅出Pytorch函数——torch.nn.init.uniform_ 深入浅出Pytorch函数——torch.nn.init.normal_ 深入浅出Pytorch函数——torch.nn.init.c…...
探索高级UI、源码解析与性能优化,了解开源框架及Flutter,助力Java和Kotlin筑基,揭秘NDK的魅力!
课程链接: 链接: https://pan.baidu.com/s/13cR0Ip6lzgFoz0rcmgYGZA?pwdy7hp 提取码: y7hp 复制这段内容后打开百度网盘手机App,操作更方便哦 --来自百度网盘超级会员v4的分享 课程介绍: 📚【01】Java筑基:全方位指…...
国外服务器怎么有效降低延迟
国外服务器怎么有效降低延迟?在全球化网络环境下,越来越多的企业和个人选择使用国外服务器来托管网站、应用程序或数据。然而,由于地理位置、网络连接等因素,使用国外服务器时可能会遇到延迟较高的问题。高延迟不仅影响用户体验,…...
AI百度文心一言大语言模型接入使用(中国版ChatGPT)
百度文心一言接入使用(中国版ChatGPT) 一、百度文心一言API二、使用步骤1、接口2、请求参数3、请求参数示例4、接口 返回示例 三、 如何获取appKey和uid1、申请appKey:2、获取appKey和uid 四、重要说明 一、百度文心一言API 基于百度文心一言语言大模型…...
vue 安装并配置vuex
1.安装vuex命令:npm i vuex3.6.2 2.全局配置 在main文件里边导入-安装-挂载 main.js页面配置的 import Vue from vue import App from ./App.vue import Vuex from vuex//导入 Vue.use(Vuex)//安装插件 // 创建store对象 const store new Vuex.Store({ }) // 挂载到vue对象上…...
有一种新型病毒在 3Ds Max 环境中传播,如何避免?
3ds Max渲染慢,可以使用渲云渲染农场: 渲云渲染农场解决本地渲染慢、电脑配置不足、紧急项目渲染等问题,可批量渲染,批量出结果,速度快,效率高。 此外3dmax支持的CG MAGIC插件专业版正式上线,…...
基于Java/springboot铁路物流数据平台的设计与实现
摘要 随着科学技术的飞速发展,社会的方方面面、各行各业都在努力与现代的先进技术接轨,通过科技手段来提高自身的优势,铁路物流数据平台当然也不能排除在外,从文档信息、铁路设计的统计和分析,在过程中会产生大量的、各…...
比较杂的html元素
abbr 表示缩写 time 踢动给浏览器或搜索引擎阅读的事件;看着没什么效果 b 以前是一个无语义元素,主要用于加粗字体,有了css之后,加粗就不需要b元素了。 现在作为提醒注意(Bring Attention To)元素&…...
Docker基本管理
前言一、Docker简介1.1 什么是docker1.2 docker的logo及其含义1.3 docker的设计宗旨1.4 容器的优点1.5 容器和虚拟机的区别1.6 docker容器的两个重要技术1.7 docker的核心概念 二、安装 Docker三、Docker 镜像操作1、搜索镜像2、获取镜像3、查看镜像信息4、查看下载的镜像文件信…...
.NET Core6.0使用NPOI导入导出Excel
一、使用NPOI导出Excel //引入NPOI包 HTML <input type"button" class"layui-btn layui-btn-blue2 layui-btn-sm" id"ExportExcel" onclick"ExportExcel()" value"导出" />JS //导出Excelfunction ExportExcel() {…...
用API接口获取数据的好处有哪些,电商小白看过来!
API接口获取数据有以下几个好处: 1. 数据的实时性:通过API接口获取数据可以实时获取最新的数据,保证数据的及时性。这对于需要及时更新数据的应用非常重要,比如股票行情、天气预报等。 2. 数据的准确性:通过API接口获…...
使用struct解析通达信本地Lday日线数据
★★★★★博文原创不易,我的博文不需要打赏,也不需要知识付费,可以白嫖学习编程小技巧,喜欢的老铁可以多多帮忙点赞,小红牛在此表示感谢。★★★★★ 在Python中,struct模块提供了二进制数据的打包和解包…...
浅谈早期基于模板匹配的OCR的原理
基于模板匹配的概念是一种早期的字符识别方法,它基于事先准备好的字符模板库来与待识别字符进行比较和匹配。其原理如下: 1. 字符模板库准备:首先,针对每个可能出现的字符,制作一个对应的字符模板。这些模板可以手工创…...
第6章 分布式文件存储
mini商城第6章 分布式文件存储 一、课题 分布式文件存储 二、回顾 1、理解Oauth2.0的功能作模式 2、实现mini商城项目的权限登录 三、目标 1、了解文件存储系统的概念 2、了解常用文件服务器的区别 3、掌握Minio的应用 四、内容 第1章 MinIO简介 官...
Spring(四):Spring Boot 的创建和使用
关于Spring之前说到,Spring只是思想(核心是IOC、DI和AOP),而具体的如何实现呢?那就是由Spring Boot 来实现,Spring Boot究竟是个啥呢? 什么是Spring Boot,为什么要学Spring Boot Sp…...
SpringCloud Gateway:status: 503 error: Service Unavailable
使用SpringCloud Gateway路由请求时,出现如下错误 yml配置如下: 可能的一种原因是:yml配置了gateway.discovery.locator.enabledtrue,此时gateway会使用负载均衡模式路由请求,但是SpringCloud Alibaba删除了Ribbon的…...
【产品规划】功能需求说明书概述
文章目录 1、瀑布流方法论简介2、产品需求文档(PRD)简介3、产品需求文档的基本要素4、编写产品需求文档5、优秀产品需求文档的特点6、与产品需求文档相似的其他文档 1、瀑布流方法论简介 2、产品需求文档(PRD)简介 3、产品需求文档…...
shell连接ubuntu
当使用aws的私钥连接时,老是弹出输入私钥密码,但是根本没有设置过密码,随便输入后,又提示该私钥无密码... 很早就使用过aws的ubuntu,这个问题也很早就遇到过,但是每次遇到都要各种找找找...索性这次记下来算了 此处用FinalShell连接为例 首先现在Putty连接工具: 点击官方下载 …...
华为将收取蜂窝物联网专利费,或将影响LPWAN市场发展
近日,华为正式公布了其4G和5G手机、Wi-Fi6设备和物联网产品的专利许可费率,其中包含了长距离通信技术蜂窝物联网。作为蜂窝物联网技术的先驱,华为是LTE Category NB (NB-IoT)、LTE Category M和其他4G物联网标准的主要贡献者。 在NB-IoT领域…...
【3Ds Max】图形合并命令的简单使用
示例(将文字设置在球体上) 1. 首先这里创建一个球体和一个文本 2. 选中球体,在复合对象中点击图形合并按钮 点击“拾取图形”按钮,然后选中文本,此时可以看到球体上已经投射出文本 3. 接下来是一些常用参数的介绍 当…...
Flink的常用算子以及实例
1.map 特性:接收一个数据,经过处理之后,就返回一个数据 1.1. 源码分析 我们来看看map的源码 map需要接收一个MapFunction<T,R>的对象,其中泛型T表示传入的数据类型,R表示经过处理之后输出的数据类型我们继续往…...
网络安全---负载均衡案例
一、首先环境配置 1.上传文件并解压 2.进入目录下 为了方便解释,我们只用两个节点,启动之后,大家可以看到有 3 个容器(可想像成有 3 台服务器就成)。 二、使用蚁剑去连接 因为两台节点都在相同的位置存在 ant.jsp&…...
解决nginx的负载均衡下上传webshell的问题
目录 环境 问题 访问的ip会变动 执行命令的服务器未知 上传大文件损坏 深入内网 解决方案 环境 ps :现在已经拿下服务器了,要解决的是负载均衡问题, 以下是docker环境: 链接: https://pan.baidu.com/s/1cjMfyFbb50NuUtk6JNfXNQ?pwd1aqw 提…...
vue 关闭prettier警告warn
这个就是我们创建vue cli的时候 把这个给默认上了 关闭这个只需在.eslintrc.js页面里边添加一行代码"prettier/prettier": "off"...
听GPT 讲Prometheus源代码--rules
Prometheus的rules目录主要包含规则引擎和管理规则的文件: engine.go 该文件定义了规则引擎的接口和主要结构,包括Rule,Record,RuleGroup等。它提供了规则的加载、匹配、评估和结果记录的功能。 api.go 定义了用于管理和查询规则的RESTful API,包括获取、添加、删除规则等方法。…...
TIA博途_通过EXCEL快速给PLC程序段添加注释信息的方法示例
通过EXCEL快速给PLC程序段添加注释信息的方法示例 如下图所示,以OB1为例,正常情况下,我们可以在博途中直接输入各个程序段的注释信息, 但是如果程序段较多的话,逐个输入的话效率不高,此时可以参考下面这种通过EXCEL进行快速添加的方法。 如下图所示,选中某个OB或FC、FB块…...
【力扣】496. 下一个更大元素 I <单调栈、模拟>
【力扣】496. 下一个更大元素 I nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。给你两个没有重复元素的数组 nums1 和 nums2 ,下标从 0 开始计数,其中nums1 是 nums2 的子集。 对于每个 0 < i <…...
Java调用https接口添加证书
使用InstallCert.Java生成证书 /** Copyright 2006 Sun Microsystems, Inc. All Rights Reserved.** Redistribution and use in source and binary forms, with or without* modification, are permitted provided that the following conditions* are met:** - Redistri…...
C++入门:函数缺省参数与函数重载
目录 1.函数缺省参数 1.1 缺省参数概念 1.2 缺省参数分类 2.函数重载 2.1 函数重载概念 2.2 C支持函数重载的原理 1.函数缺省参数 1.1 缺省参数概念 缺省参数是声明或定义函数时为函数的参数指定一个缺省值。在调用该函数时,如果没有指定实 参则采用该形参的…...
Android 场景Scene的使用
Scene 翻译过来是场景,开发者提供起始布局和结束布局,就可以实现布局之间的过渡动画。 具体可参考 使用过渡为布局变化添加动画效果 大白话,在 Activity 的各个页面之间切换,会带有过渡动画。 打个比方,使用起来类似…...
Python tkinter Notebook标签添加关闭按钮元素,及左侧添加存储状态提示图标案例,类似Notepad++页面
效果图展示 粉色框是当前页面,橙色框是鼠标经过,红色框是按下按钮,灰色按钮是其他页面的效果; 存储标识可以用来识别页面是否存储:例如当前页面已经保存用蓝色,未保存用红色,其他页面已经保存用…...
基于web网上订餐系统的设计与实现(论文+源码)_kaic
目录 1绪论 1.1课题研究背景 1.2研究现状 1.3主要内容 1.4本文结构 2网上订餐系统需求分析 2.1系统业务流程分析 2.2消费者用户业务流程分析 2.3商户业务流程分析 2.4管理员用户流程分析消费者用户用例分析 2.5系统用例分析 3网上订餐系统设计 3.1功能概述 3.2订单管理模块概要…...
C#生产流程控制(串行,并行混合执行)
开源框架CsGo https://gitee.com/hamasm/CsGo?_fromgitee_search 文档资料: https://blog.csdn.net/aa2528877987/article/details/132139337 实现效果 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37…...
【广州华锐视点】VR线上教学资源平台提供定制化虚拟现实学习内容
虚拟现实(VR)技术的出现为我们提供了一种全新的在线教学方式。由广州华锐视点开发的VR线上教学资源平台,作为一个综合性的学习工具,正在教育领域迅速发展,并被越来越多的教育机构和学生所接受。那么,VR线上…...
计算机视觉的应用11-基于pytorch框架的卷积神经网络与注意力机制对街道房屋号码的识别应用
大家好,我是微学AI,今天给大家介绍一下计算机视觉的应用11-基于pytorch框架的卷积神经网络与注意力机制对街道房屋号码的识别应用,本文我们借助PyTorch,快速构建和训练卷积神经网络(CNN)等模型,…...