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()

上面的代码在第一次扫描后并没有将每条训练数据过滤后的项排序,而是将排序放在了第二次扫描时,这可以简化代码的复杂度。

控制台信息:

在这里插入图片描述

建模资料

资料分享: 最强建模资料
在这里插入图片描述
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/89877.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

消息队列(11) - 通信协议的设计

目录 通信协议设计代码实现 通信协议设计 对于我们客户端与服务器之间的通信协议我们约定如下&#xff1a; 具体的协议设计: 之后我们传递的参数也是这些 关于 type其实是在描述当前这个请求 、 响应是在调用那个API 约定如下 对于channel ,是tcp链接中的一个逻辑上的链接,…

液体神经网络:LNN是个啥概念?

一、说明 在在人工智能领域&#xff0c;神经网络已被证明是解决复杂问题的非常强大的工具。多年来&#xff0c;研究人员不断寻求创新方法来提高其性能并扩展其能力。其中一种方法是液体神经网络&#xff08;LNN&#xff09;的概念&#xff0c;这是一个利用动态计算功能的迷人框…

IDEA如何调试Stream API

Stream API现在在实际开发中应用非常广泛&#xff0c;经常会遇到需要调试Stream API的场景&#xff0c;这篇文章主要讲解如何使用IDEA调试Stream Testpublic void test(){Stream.of(10, 20, 30, 40, 50).mapToInt(e->e*10).filter(e->e>200).forEach(System.out::pri…

笔记04:全局内存

一、CUDA内存模型概述 寄存器、共享内存、本地内存、常量内存、纹理内存和全局内存 一个核函数中的线程都有自己私有的本地内存。 一个线程块有自己的共享内存&#xff0c;对同一个线程块中所有的线程都可见&#xff0c;其内容持续线程块的整个生命周期。 所有线程都可以访问…

12.Eclipse导入Javaweb项目

同事复制一份他的项目给我ekp.rar (懒得从SVN上拉取代码了)放在workspace1目录下 新建一个文件夹 workspace2&#xff0c;Eclipse切换到workspace2工作空间 选择Import导入 选择导入的项目(这里是放到workspace1里面) 拷贝一份到workspace2里面 例子 所有不是在自己电脑上开发…

搭建openGauss 5.0 一主一从复制集群

openGauss是一款支持SQL2003标准语法&#xff0c;支持主备部署的高可用关系型国产数据库。 多种存储模式支持复合业务场景&#xff0c;新引入提供原地更新存储引擎。NUMA化数据结构支持高性能。Paxos一致性日志复制协议&#xff0c;主备模式&#xff0c;CRC校验支持高可用。支…

数字孪生如何实现物理世界和数字世界之间的交互?

在当今数字化时代&#xff0c;技术的飞速发展正在引领着各行各业的变革与创新。其中&#xff0c;数字孪生作为一项令人振奋的前沿技术&#xff0c;正在以惊人的方式实现着物理世界与数字世界的无缝交互。它不仅为企业带来了全新的商机&#xff0c;也为科学研究、生产制造等领域…

打造企业或者个人IP引流法

打造企业或者个人IP引流法. 大家好&#xff0c;我是百收网SEO编辑&#xff1a;狂潮老师&#xff0c;今天给大家分享企业IP打造的方法 首先我们想让人知道你的企业叫什么&#xff0c;怎么找到你的企业 这个时候我们就需要去各大平台发布信息&#xff0c;客户想了解直接去搜索…

php webshell 免杀入门

webshell 查杀软件&#xff1a; d盾、安全狗、护卫神、Sangfor WebShellKill 在线查杀 百度WEBDIR https://scanner.baidu.com 河马 https://www.shellpub.com cloudwalker牧云 https://webshellchop.chaitin.cn 查杀技术 静态检测、动态检测、日志检查 静态检查&#xff1a…

OceanBase 4.1.0 clog 目录探究

基于OceanBase 4.x 版本如何统计租户每日 clog 日志生成量的背景下&#xff0c;探究以及如何查看租户 clog 的使用情况。 作者&#xff1a;姜宇 爱可生 DBA 团队成员&#xff0c;擅长数据库故障排查和处理。对技术抱有热忱&#xff0c;实践是检验真理的唯一标准~ 本文来源&…

高忆管理:爆仓是什么意思?

爆仓是指在金融商场中&#xff0c;持有的某种资产价格大幅下跌&#xff0c;导致出资者的保证金不足以支持持仓&#xff0c;被逼平仓的现象。在股票、期货、外汇等商场中均或许呈现爆仓现象。在本文中&#xff0c;咱们将从多个视点分析爆仓的含义、原因和影响。 一、爆仓的含义 …

Azure概念介绍

云计算定义 云计算是一种使用网络进行存储和处理数据的计算方式。它通过将数据和应用程序存储在云端服务器上&#xff0c;使用户能够通过互联网访问和使用这些资源&#xff0c;而无需依赖于本地硬件和软件。 发展历史 云计算的概念最早可以追溯到20世纪60年代的时候&#x…

IDEA创建项目常见问题

1.IDEA修改maven路径无效 创建spring项目&#xff0c;Maven导入报错&#xff0c;无法正常导入jar报&#xff0c;发现setting中设置的maven路径不是自己下载的路径&#xff0c;修改后无效。运行之后maven路径又恢复为其默认的路径 解决方案&#xff1a; 删除.mvn文件&#xff0…

Grafana监控 Redis Cluster

Grafana监控 Redis Cluster 主要是使用grafana来实现监控&#xff0c;grafana可以对接多种数据源&#xff0c;在官网中可以找到Redis数据源&#xff0c;需要安装redis data source插件。当然也可以利用Prometheus来做数据源&#xff0c;下面分别记录一下这两种数据源的安装配置…

SQL-每日一题【1251. 平均售价】

题目 Table: Prices Table: UnitsSold 编写SQL查询以查找每种产品的平均售价。average_price 应该四舍五入到小数点后两位。 查询结果格式如下例所示&#xff1a; 解题思路 1.题目要求查询每种产品的平均售价。给出了两个表&#xff0c;我们用聚合查询来解决此问题。 2.首先我…

免费AI学习文档(二)

国内绘画midjourney网站 http://aijiaolian.chat优质提示词分解教学 https://q3iylvv7qj.feishu.cn/docx/UGMzdPVGjo1fHcxu1kjcuXFcnff?fromfrom_copylink设计图AI实战&#xff0c;如何用AI提高83%的出图效率&#xff1f;https://q3iylvv7qj.feishu.cn/docx/Fsxxd3MncowFUix5…

前后端分离------后端创建笔记(上)

本文章转载于【SpringBootVue】全网最简单但实用的前后端分离项目实战笔记 - 前端_大菜007的博客-CSDN博客 仅用于学习和讨论&#xff0c;如有侵权请联系 源码&#xff1a;https://gitee.com/green_vegetables/x-admin-project.git 素材&#xff1a;https://pan.baidu.com/s/…

html练习

html练习 工具代码运行结果 工具 HBuilder X 代码 <!DOCTYPE html> <html><head><meta charset"utf-8"><title>图灵之家</title></head><body><h1>图灵之家</h1><br><br><h2>我的…

监控Kubernetes Node组件的关键指标

所有的 Kubernetes 组件&#xff0c;都提供了 /metrics 接口用来暴露监控数据&#xff0c;Kube-Proxy 也不例外。通过 ss 或者 netstat 命令可以看到 Kube-Proxy 监听的端口&#xff0c;一个是 10249&#xff0c;用来暴露监控指标&#xff0c;一个是 10256 &#xff0c;作为…

2023年新学期12306高铁火车学生票如何在线核验享受优惠?

2023学年优惠资质核验已开始&#xff0c;完成学生优惠资质核验后&#xff0c;您可以在线购买2022年10月1日至2023年9月30日的学生优惠票。&#xff08;注&#xff1a;非该时间段需要重新核验&#xff0c;可享受学生优惠票&#xff09;&#xff1b; 『扩展阅读』 1、美团外卖红…