2023年亚太杯数学建模思路 - 案例:ID3-决策树分类算法
文章目录
- 0 赛题思路
- 1 算法介绍
- 2 FP树表示法
- 3 构建FP树
- 4 实现代码
- 建模资料
0 赛题思路
(赛题出来以后第一时间在CSDN分享)
https://blog.csdn.net/dc_sinor?type=blog
1 算法介绍
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构建、挖掘频繁项集。
2 FP树表示法
FP树通过逐个读入事务,并把事务映射到FP树中的一条路径来构造。由于不同的事务可能会有若干个相同的项,因此它们的路径可能部分重叠。路径相互重叠越多,使用FP树结构获得的压缩效果越好;如果FP树足够小,能够存放在内存中,就可以直接从这个内存中的结构提取频繁项集,而不必重复地扫描存放在硬盘上的数据。
一颗FP树如下图所示:

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

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

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

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






从上面可以看出,headTable并不是随着FPTree一起创建,而是在第一次扫描时就已经创建完毕,在创建FPTree时只需要将指针指向相应节点即可。从事务004开始,需要创建节点间的连接,使不同路径上的相同项连接成链表。
4 实现代码
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年亚太杯数学建模思路 - 案例:ID3-决策树分类算法
文章目录 0 赛题思路1 算法介绍2 FP树表示法3 构建FP树4 实现代码 建模资料 0 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 1 算法介绍 FP-Tree算法全称是FrequentPattern Tree算法,就是频繁模…...
C复习-输入输出函数+流
参考: 里科《C和指针》 perror 定义在stdio.h中。当一个库函数失败时,库函数会在一个外部整型变量errno(在errno.h中定义)中保存错误代码,然后传递给用户程序,此时使用perror,会在打印msg后再打…...
duplicate复制数据库单个数据文件复制失败报错rman-03009 ora-03113
duplicate复制数据库单个数据文件复制失败报错rman-03009 ora-03113 搭建dg过程中,发现有一个数据文件在复制过程中没有复制过来,在备库数据文件目录找不到这个数据文件 处理方法: 第一步:主库备份86#数据文件 C:\Users\Admi…...
golang 解析oracle 数据文件头
package mainimport ("encoding/binary""fmt""io""os" ) // Powered by 黄林杰 15658655447 // Usered for parser oracle datafile header block 1 .... // oracle 数据文件头块解析 // KCBlockStruct represents the structure of t…...
van-popup滑动卡顿并且在有时候在ios上经常性滑动卡顿的情况
解决”pc端页面可以滚动,移动端手势无法滚动“问题的一次经历 - 掘金 <van-popup v-model"studentclassShow" :lock-scroll"false" position"bottom" style"z-index: 3000" :style"{ height: 55% }"><d…...
YOLOv7独家原创改进:最新原创WIoU_NMS改进点,改进有效可以直接当做自己的原创改进点来写,提升网络模型性能精度
💡该教程为属于《芒果书》📚系列,包含大量的原创首发改进方式, 所有文章都是全网首发原创改进内容🚀 💡本篇文章为YOLOv7独家原创改进:独家首发最新原创WIoU_NMS改进点,改进有效可以直接当做自己的原创改进点来写,提升网络模型性能精度。 💡对自己数据集改进有效…...
ubuntu20.04中编译zlib1.2.11(源码编译)
1. 安装cmake-gui 2. 下载并解压zlib-1.2.11,在解压得到的文件夹内部创建一个“build”文件夹。 3. 打开cmake-gui,配置zlib1.2.11的configure文件(主要编辑build路径,安装路径,以及其他依赖选项)&#x…...
计算机毕业设计选题推荐-高校后勤报修微信小程序/安卓APP-项目实战
✨作者主页:IT研究室✨ 个人简介:曾从事计算机专业培训教学,擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Python…...
如何零基础自学AI人工智能
随着人工智能(AI)的快速发展,越来越多的有志之士被其强大的潜力所吸引,希望投身其中。然而,对于许多零基础的人来说,如何入门AI成了一个难题。本文将为你提供一份详尽的自学AI人工智能的攻略,帮…...
pm2使用
常用命令 pm2 delete/stop/restart/start/list/info/monit/log...
在Ubuntu或linux中为coreutils工具包的cp和mv命令添加进度条
1、查看当前最新的coreutils版本: http://ftp.gnu.org/gnu/coreutils/ 2、安装coreutils过程 # wget http://ftp.gnu.org/gnu/coreutils/coreutils-9.4.tar.xz # tar -xJf coreutils-9.4.tar.xz # cd coreutils-9.4/ 对照上面的,下载对应coreutils版本…...
力扣-58. 最后一个单词的长度
int lengthOfLastWord(char* s) {char* temp s;char* ret s;int count 0;/*返回的长度*/while (*temp){/*只记录空格后是字母的地址*/if ((*temp ) && (*(temp 1) ! \0) && (*(temp 1) ! )){ret temp 1;}temp;}while (*ret){if (isalpha(*ret) ! 0)…...
快递鸟荣获全球电子商务创业创新大赛总决赛一等奖
日前,以“开放、连接、协同、赋能”为主题,由商务部中国国际电子商务中心指导,浙江省商务厅、中共省委组织部、中共省委宣传部、中共省委网信办、省发展和改革委、省教育厅、省科技厅、省财政厅、省人力社保厅、团省委主办,湖州市…...
阶段七-Day02-SpringMVC
一、Restful请求格式 1. 介绍 Rest(Representational State Transfer:表现层状态转移)是一种软件架构风格,其核心是面向资源的一种设计。何为面向资源,意思是网络上的所有事物都可以抽象为资源,而每个资源都有唯一的资源标识&…...
YOLOv5独家原创改进:最新原创WIoU_NMS改进点,改进有效可以直接当做自己的原创改进点来写,提升网络模型性能精度
💡该教程为属于《芒果书》📚系列,包含大量的原创首发改进方式, 所有文章都是全网首发原创改进内容🚀 💡本篇文章为YOLOv5独家原创改进:独家首发最新原创WIoU_NMS改进点,改进有效可以直接当做自己的原创改进点来写,提升网络模型性能精度。 💡对自己数据集改进有效…...
【深度学习】pytorch快速得到mobilenet_v2 pth 和onnx
在linux执行这个程序: import torch import torch.onnx from torchvision import transforms, models from PIL import Image import os# Load MobileNetV2 model model models.mobilenet_v2(pretrainedTrue) model.eval()# Download an example image from the P…...
高防CDN安全防护系统在业务方面的应用
在当今数字化的时代,网络安全问题日益严峻,保护网站和数据免受攻击变得至关重要。CDN安全防护系统作为一种有效的解决方案,受到了广泛关注。小德将向您介绍CDN安全防护系统的原理、应用场景以及使用方法,助您更好地保障网络安全。…...
opencv(3):控制鼠标,创建 tackbar控件
文章目录 控制鼠标相关APIsetMouseCallbackcallback TrackBar 控件cv2.createTrackbarcv2.getTrackbarPos: 控制鼠标相关API setMouseCallback(winname, callback, userdata)callback(event, x, y, flags, userdata) setMouseCallback 在 OpenCV 中,s…...
UE4动作游戏实例RPG Action解析二:GAS系统播放武器绑定的技能,以及GE效果
一、GAS系统播放武器技能 官方实例激活技能通过装备系统数据激活,我先用武器数据资产直接激活 官方实例蒙太奇播放是自定义的AbilityTask,我先用更简单的方法实现效果 1.1、技能系统必要步骤: 1.1.1 插件启用AbilitySystem 1.1.2 PlayerCharacter绑定技能组件AbilitySy…...
做完这些_成为机器学习方面的专家
简单记个帖子, 用来记录学习机器学习的路线图 1. 数学分析, 高等代数, 概率论这三大件不多说, 基础中的基础. 2. 对于编程工具, b站上500集的python教程---python面向对象编程五部曲(从零到就业). 3. 对于机器学习的理论板块, 推荐b站up主---啥都会一点的研究生, 里面有一个吴恩…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...
基于Java+VUE+MariaDB实现(Web)仿小米商城
仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意:运行前…...
HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...
springboot 日志类切面,接口成功记录日志,失败不记录
springboot 日志类切面,接口成功记录日志,失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...
从物理机到云原生:全面解析计算虚拟化技术的演进与应用
前言:我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM(Java Virtual Machine)让"一次编写,到处运行"成为可能。这个软件层面的虚拟化让我着迷,但直到后来接触VMware和Doc…...
