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

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

控制台信息:

在这里插入图片描述

建模资料

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

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

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

相关文章

任意注册漏洞

目录 一漏洞介绍 二实战演示 三漏洞修复 本文由掌控安全学院 - 小博 投稿 一漏洞介绍 1.未验证邮箱/手机号 情景&#xff1a;应用为了方便用户记录用户名&#xff0c;使用邮箱和手机号作为用户名&#xff08;因此很多应用在注册的时候就要求用户填写&#xff0c;多数时候…

安卓:打包apk时出现Execution failed for task ‘:app:lintVitalRelease

Execution failed for task :lintVitalRelease 程序可以正常运行&#xff0c;但是打包apk的时候报Execution failed for task ‘:app:lintVitalRelease导致打包失败&#xff0c;原因是执行lintVitalRelease失败了&#xff0c;存在错误。解决办法&#xff1a;在app模块的build.…

万宾科技内涝积水监测仪效果,预警城市积水

当城市之中出现强降雨或者大暴雨&#xff0c;可能会导致雨水不断堆积到城市排水管网之中&#xff0c;可能还会淹没城市的排水系统时&#xff0c;这种现象被称为城市之中的内涝&#xff0c;并且在许多城市之中内涝问题日益引起人们的关注。 内涝积水监测仪的出现成为了希望的灯塔…

Android Studio的代码笔记--JSON解析学习2

JSON学习2 生成JSON解析JSON java解析json字符串和合成json字符串 json字符串 {"type":"getConfig","ip":"192.168.1.100"}使用 String ss groupJS("Config","192.168.1.100"); splitJS(ss);回显 I/lxh: group…

arcgis--NoData数据处理

方法一&#xff1a;利用【栅格计算器】可以对NoData的值进行修改。【Spatial Analyst工具】-【地图代数】-【栅格计算器】&#xff0c;将NoData修改为某一个值。 方法二&#xff1a;先对原始数据进行重分类&#xff0c;分成1类&#xff0c;将NoData赋值为2,。然后&#xff0c;将…

2023.11.11通过html内置“required-star“添加一个红色的星号来表示必填项

2023.11.11通过html内置"required-star"添加一个红色的星号来表示必填项 在HTML中&#xff0c;可以使用标签来为元素添加说明。同时可以通过添加一个红色的星号来表示必填项。 <!DOCTYPE html> <html lang"en"> <head><meta charse…

GoLong的学习之路,进阶,语法之并发(并发错误处理)补充并发三部曲

这篇文章主要讲的是如何去处理并发的错误。 在Go语言中十分便捷地开启goroutine去并发地执行任务&#xff0c;但是如何有效的处理并发过程中的错误则是一个很棘手的问题。 文章目录 recovererrgroup recover 哦对&#xff0c;似乎没写错误处理的文章。后面补上。 首先&…

一文懂得电源模块过温保护测试方法 ate测试软件助力测试

过温保护测试是电源模块保护功能测试项目之一&#xff0c;也是电源模块测试的重要测试指标&#xff0c;以保证电源模块过温保护功能正常&#xff0c;确保电源模块不受损坏。用ate测试软件测试电源模块过温保护&#xff0c;不仅可以保证测试结果的准确性&#xff0c;还可以多维度…

[Linux] dns域名解析服务

一、DNS 1.1 DNS简介 域名解析&#xff1a;&#xff08;英文&#xff1a;Domain Name System&#xff0c;缩写&#xff1a;DNS&#xff09;是互联网的一项服务。它作为将域名和IP地址相互映射的一个分布式数据库&#xff0c;能够使人更方便地访问互联网。DNS使用udp53和tcp53…

SQLite3 数据库学习(一):数据库和 SQLite 基础

参考引用 SQL 必知必会SQLite 权威指南&#xff08;第二版&#xff09;关系型数据库概述 1. 数据库基础 1.1 什么是数据库 数据库&#xff08;database&#xff09;&#xff1a;保存有组织的数据的容器&#xff08;通常是一个文件或一组文件&#xff09; 可以将其想象为一个文…

C语言仅凭自学能到什么高度?

今日话题&#xff0c;C语言仅凭自学能到什么高度&#xff1f;学习C语言的决定我确实非常推荐&#xff0c;毕竟它是编程领域的“通用工具”&#xff0c;初学者可以尝试并在发现编程的乐趣后制定长期学习计划。至于能够达到何种高度&#xff0c;这实在无法准确回答。即使是经验丰…

NtripShare Mos地铁自动化监测终端盒子硬件设计

自动化监测产品到目前为止做了接近一年&#xff0c;在软件层面上&#xff0c;控制终端软件、平台软件、网平差算法都已解决&#xff0c;硬件盒子始终是心里过不去的坎&#xff0c;最终还是没有耐住性子自己做了一把。 选型如下&#xff1a; 1、主板:瑞芯微RK3568主板。 2、外…

主流接口测试框架对比,究竟哪个更好用

公司计划系统的开展接口自动化测试&#xff0c;需要我这边调研一下主流的接口测试框架给后端测试&#xff08;主要测试接口&#xff09;的同事介绍一下每个框架的特定和使用方式。后端同事根据他们接口的特点提出一下需求&#xff0c;看哪个框架更适合我们。 需求 1、接口编写…

Windows系统下使用docker部署redis

使用虚拟机部署redis&#xff0c;虚拟机很占用电脑资源&#xff0c;所以选择使用docker对redis进行部署。 一、安装docker 安装链接&#xff1a;https://docker.p2hp.com/ 二、配置redis.conf文件 下载配置文件&#xff1a;https://download.redis.io/redis-stable/redis.con…

rabbitMq创建交换机,以及路由键绑定队列教程

创建交换机&#xff1a; 创建队列&#xff1a; 创建路由&#xff0c;绑定到交换机&#xff1a; 补充&#xff1a; 创建新用户后&#xff0c;记得点进用户中&#xff0c;那两个set都点击一下&#xff1b; 还有配置代码连接的时候&#xff0c;连的端口为5672&#xff0c;可不…

【JavaEE】Servlet(创建Maven、引入依赖、创建目录、编写及打包、部署和验证、smart Tomcat)

一、什么是Servlet&#xff1f; Servlet 是一种实现动态页面的技术. 是一组 Tomcat 提供给程序猿的 API, 帮助程序猿简单高效的开发一个 web app 1.1 Servlet能干什么&#xff1f; &#x1f695;允许程序猿注册一个类, 在 Tomcat 收到某个特定的 HTTP 请求的时候, 执行这个类…

Azure 机器学习 - 机器学习中的企业安全和治理

目录 限制对资源和操作的访问网络安全性和隔离数据加密数据渗透防护漏洞扫描审核和管理合规性 在本文中&#xff0c;你将了解可用于 Azure 机器学习的安全和治理功能。 如果管理员、DevOps 和 MLOps 想要创建符合公司策略的安全配置&#xff0c;那么这些功能对其十分有用。 通过…

Linux必备基础命令,JAVA程序员必备

目录 一、了解基本的左侧栏什么意思​编辑 二、ls&#xff0c;ll&#xff08;list&#xff0c;查找目录内容) 三、cd(change directory&#xff0c;切换目录) 小技巧&#xff0c;我们在查找东西的时候&#xff0c;可以使用tab进行智能补全。 四、touch&#xff08;建立文件…

R程序 示例4.3.2版本包 在centos进行编译部署

为了在CentOS上下载和编译R语言4.3.2包&#xff0c;可以按照以下步骤进行操作&#xff1a; 1.首先&#xff0c;需要安装一些必要的依赖项。可以使用以下命令安装它们&#xff1a; sudo yum install -y epel-release sudo yum install -y gcc gcc-c gcc-gfortran readline-dev…

RTSP/Onvif安防平台EasyNVR批量禁用/启用通道接口的详细操作步骤

TSINGSEE青犀视频安防监控平台EasyNVR可支持设备通过RTSP/Onvif协议接入&#xff0c;并能对接入的视频流进行处理与多端分发&#xff0c;包括RTSP、RTMP、HTTP-FLV、WS-FLV、HLS、WebRTC等多种格式。在智慧安防等视频监控场景中&#xff0c;EasyNVR可提供视频实时监控直播、云端…