数据挖掘实验（Apriori，fpgrowth）

news/2024/5/18 12:49:53

Apriori：这里做了个小优化，比如abcde和adcef自连接出的新项集abcdef，可以用abcde的位置和f的位置取交集，这样第n项集的计算可以用n-1项集的信息和数字本身的位置信息计算出来，只需要保存第n-1项集的位置信息就可以提速

#include<iostream>
#include<bits/stdc++.h>
#include<cstring>
#include<set>
#include<map>
#include <unordered_set>
#include<string>
#include<vector>
#include<windows.h>
#include<time.h>
#define DATA_NAME R"(D:\Cpan\Download\.vscode\retail.dat)"
#define N 100000
#define MAX_RECORD_NUM 88162 + 1
#define MAX_ITEMID_NUM 16470 + 1
using namespace std;int recordNum = 0; 
int mp[MAX_ITEMID_NUM];
vector<int> items[N];double support;
void fastRead(){char c;bool lastIsNum = false;uint16_t num;FILE* fp = fopen(DATA_NAME, "r");while (~(c = fgetc(fp))) {if (c >= '0' && c <= '9') {if(lastIsNum){num *= 10;num += c - '0';}else{num = c - '0';}lastIsNum = true;}else {if (lastIsNum){items[num].push_back(recordNum);mp[num]++;}if (c == '\n'){recordNum++;}lastIsNum = false;}}if (lastIsNum) {items[num].push_back(recordNum);mp[num]++;}if (c != '\n') {recordNum++;}fclose(fp);
}
vector<int> same_number(vector<int> &tmp1,vector<int> &tmp2){int ite=0;vector<int> res={};for(int i=0;i<tmp1.size();++i){while(tmp2[ite]<tmp1[i] && ite<tmp2.size()-1) ite++;if(tmp2[ite]==tmp1[i]){//cout<<tmp2[ite]<<"*"<<tmp1[i]<<" "<<ite<<" "<<i<<endl;res.push_back(tmp1[i]);}}return res;
}
vector<vector<int>> v;
vector<vector<int>> v2;
vector<string> s,s2;
int total;
void cal(){total=0;s.clear();v.clear();for(int i=0;i<=MAX_ITEMID_NUM;++i){if(mp[i]>=recordNum*support*0.01){string tri=to_string(i);int tmp_len=tri.size();for(int j=1;j<=5-tmp_len;j++){tri="0"+tri;}s.push_back(tri);v.push_back(items[i]);}}int now_set_level=1;while(1){total+=s.size();cout<<"共有"<<s.size()<<"个频繁"<<now_set_level<<"项集\n";// for(auto t:s){cout<<t<<" ";}// cout<<endl;v2.clear();s2.clear();for(int i=0;i<s.size();++i){for(int j=i+1;j<s.size();++j){if(s[i].substr(0,s[i].size()-5)==s[j].substr(0,s[i].size()-5)){int num_end=stol(s[j].substr(s[i].size()-5,5));vector<int> tmp1=v[i];vector<int> tmp2=items[num_end];vector<int> same_vector=same_number(tmp1,tmp2);if(same_vector.size()>=recordNum*support*0.01){v2.push_back(same_vector);string new_tmp_string=s[i]+s[j].substr(s[i].size()-5,5);s2.push_back(new_tmp_string);}}//cout<<(s[i].substr(s[i].size()-5,5))<<endl;}}v=v2;s=s2;if(v.size()==0){break;}now_set_level+=1;}cout<<"共有"<<total<<"个频繁项集\n";
}
signed main(){cout<<"请输入置信度（单位%）\n";cin>>support;fastRead();long starttime = GetTickCount();cal();long endtime = GetTickCount();long time_cost = endtime - starttime;cout << "timecost  " << time_cost << " ms" << endl;cout<<"请输入操作\n";cout<<" 1:更改置信度\n";int oper;cin>>oper;if(oper==1){cout<<"请输入置信度\n";cin>>support;cal();}
}

Fpgrowth的算法，我没有递归建树，只建了一次树，所以速度比完整的fpgrowth要慢（当知道还要建其他树的时候实在不知道我这屎山代码怎么在继续写下去，所以直接后面直接暴力了），建了一次树后直接拿链过去爆搜子集计数了，速度主要慢在我的链最长有10左右，fpgrowth最后剪完只有3-4，通过链获取子集的复杂度是2^{len}链的长度，所以会慢，如果有一些方法能把无用节点去掉，这种做法也会快，（以后有缘再回来改吧

#include<iostream>
#include<bits/stdc++.h>
#include<cstring>
#include<set>
#include<map>
#include <unordered_set>
#include<string>
#include<vector>
#include<windows.h>
#include<time.h>
#define DATA_NAME R"(D:\Cpan\Download\.vscode\retail.dat)"
#define N 100000
#define MAX_RECORD_NUM 88162 + 1
#define MAX_ITEMID_NUM 16470 + 1
using namespace std;int recordNum = 0; 
int mp[MAX_ITEMID_NUM];
vector<int> items[N];double support;
void fastRead(){char c;bool lastIsNum = false;uint16_t num;FILE* fp = fopen(DATA_NAME, "r");while (~(c = fgetc(fp))) {if (c >= '0' && c <= '9') {if(lastIsNum){num *= 10;num += c - '0';}else{num = c - '0';}lastIsNum = true;}else {if (lastIsNum){items[recordNum].push_back(num);mp[num]++;}if (c == '\n'){recordNum++;}lastIsNum = false;}}if (lastIsNum) {items[recordNum].push_back(num);mp[num]++;}if (c != '\n') {recordNum++;}fclose(fp);
}int node_number;
vector<vector<int>> v;
vector<int> head_table[MAX_ITEMID_NUM];
int head_table_back[10*MAX_ITEMID_NUM];
vector<pair<int,int>> fp_tree[10*MAX_ITEMID_NUM];
pair<int,int> fp_tree_value[10*MAX_ITEMID_NUM];bool cmp(int &a,int &b){return mp[a]>mp[b];
}
void build(int son,int fa,vector<int> &value,int index){if(index==value.size()) return;bool exi=0;for(auto t:fp_tree[son]){if(t.first!=fa && fp_tree_value[t.first].first==value[index]){fp_tree_value[t.first].second+=1;exi=1;build(t.first,son,value,index+1);}}if(exi==0){node_number+=1;head_table[value[index]].push_back(node_number);head_table_back[node_number]=value[index];fp_tree_value[node_number]={value[index],1};fp_tree[son].push_back({node_number,1});fp_tree[node_number].push_back({son,-1});build(node_number,son,value,index+1);}
}
int tmp_dp[10*MAX_ITEMID_NUM];
void back(int number,vector<int> &res_chain){if(number==0 && fp_tree_value[number].second==0) return ;for(auto t:fp_tree[number]){if(t.second==-1 && fp_tree_value[t.first].second!=0){// cout<<"节点 "<<t.first<<"  ";// cout<<"以前是"<<tmp_dp[t.first]<<"   ";res_chain.push_back({head_table_back[t.first]});//cout<<"现在是"<<tmp_dp[t.first]<<"\n";back(t.first,res_chain);}}
}
int res[MAX_ITEMID_NUM];
vector<int> number_item;
void dfs_son(vector<vector<int>> &res_son,vector<int> &value,vector<int> tmp,int index,int now_number){if(index==value.size()){if(tmp.size()!=0){res_son.push_back(tmp);}return ;}if(now_number<=3){tmp.push_back(value[index]);dfs_son(res_son,value,tmp,index+1,now_number+1);tmp.pop_back();dfs_son(res_son,value,tmp,index+1,now_number);}else{dfs_son(res_son,value,tmp,index+1,now_number);}
}
signed main(){cout<<"请输入置信度（单位%）\n";cin>>support;fastRead();for(int i=0;i<recordNum;++i){vector<int> tmp;for(auto t:items[i]){if(mp[t]>=recordNum*support*0.01){tmp.push_back(t);}}if(tmp.size()==0) continue;else{sort(tmp.begin(),tmp.end(),cmp);// for(auto t:tmp){cout<<t<<" ";}// cout<<endl<<"**************************\n";v.push_back(tmp);}}// cout<<v.size()<<endl;long starttime = GetTickCount();for(auto t:v){build(0,-1,t,0);}for(int i=0;i<MAX_ITEMID_NUM;++i){if(mp[i]>=recordNum*support*0.01){res[1]+=1;number_item.push_back(i);//cout<<i<<"*\n";}}for(auto t:number_item){for(int i=0;i<MAX_ITEMID_NUM;++i){tmp_dp[i]=0;}map<vector<int>,int> map_vec;for(auto j:head_table[t]){//cout<<j<<"*";vector<int> vt={};int value=fp_tree_value[j].second;back(j,vt);if(!vt.size()) continue;// vector<vector<int>> vs;// for(int k=0;k<(1<<(vt.size()));k++){// 	vector<int> resson;// 	for(int o=0;o<=vt.size()-1;o++){// 		if((k>>o)&1){// 			resson.push_back(vt[o]);// 		}// 	}// 	if(resson.size()){// 		vs.push_back(resson);// 	}// }// for(auto t:vs){// 	map_vec[t]+=value;// }vector<vector<int> > res_son={};vector<int> tmp2={};dfs_son(res_son,vt,tmp2,0,1);for(auto t:res_son){map_vec[t]+=value;}}for(auto t:map_vec){if(t.second>=recordNum*support*0.01){res[t.first.size()+1]+=1;}}}long endtime = GetTickCount();long time_cost = endtime - starttime;cout << "timecost  " << time_cost << " ms" << endl;int total=0;for(int i=1;i<=MAX_ITEMID_NUM;++i){if(res[i]!=0){total+=res[i];cout<<"共有"<<res[i]<<"个频繁"<<i<<"项集\n";}else{cout<<"共有"<<total<<"个频繁项集\n";break;}}}


http://www.mrgr.cn/p/11543218

相关文章

如何使用 Apifox 请求 gRPC 接口？

如何使用 Apifox 请求 gRPC 接口？

使用 Apifox 发送 gRPC 接口Apifox 支持基于 .proto 文件的 gRPC 调试，包括一元调用和流式调用。在创建项目时「选择 gRPC 项目」-->「导入 .proto 文件」，无需写代码即可直接调用 gRPC 接口。创建 gRPC 在调试 gRPC 接口之前，也需要先导入作为 API 定义的 .proto 文件。…
阅读更多...
字节面试：如何解决MQ消息积压问题？

字节面试：如何解决MQ消息积压问题？

MQ（Message Queue）消息积压问题指的是在消息队列中累积了大量未处理的消息，导致消息队列中的消息积压严重，超出系统处理能力，影响系统性能和稳定性的现象。 1.消息积压是哪个环节的问题？ MQ 执行有三大阶段：消息生产阶段。 消息存储阶段。 消息消费阶段。很显然，消息堆…
阅读更多...
一篇文章带您了解操作系统的体系结构

一篇文章带您了解操作系统的体系结构

操作系统的体系结构有哪些&#xff1f; 我们可以利用时钟中断实现计时功能。 原语是一种特殊的程序&#xff0c;具有原子性。也就是说&#xff0c;这段程序的运行必须一气呵成&#xff0c;不能中断。 内核是操作系统最基本&#xff0c;最核心的部分。 实现操作系统内核功能的…
阅读更多...
Practice

Practice

18.链表只能一个接着一个遍历，不允许通过随机访问7.链表的地址是连续的，通过内部的指针来进行访问//假设该链表只给出了头指针 head。在不改变链表的前提下，请设计一个尽可能高效的算法， //查找链表中倒数第k(k为正整数)个位置上的结点。若查找成功，算法输出该结点的 data…
阅读更多...
五种服务异步通信（MQ）-详解、代码案例

五种服务异步通信（MQ）-详解、代码案例

简介&#xff1a;本篇文章主要是介绍了常用的异步通信原理&#xff0c;主要是RabbitMQ技术 目录 1、初始MQ&#xff08;异步通讯&#xff09; 1.1 同步通讯 1.2 异步通讯 1.3 MQ常见框架 2、RabbitMQ快速入门 2.1 RabbitMQ概述和安装 2.2 常见消息模型 2.3 快速入门 3、…
阅读更多...
ssm071北京集联软件科技有限公司信息管理系统+jsp

ssm071北京集联软件科技有限公司信息管理系统+jsp

北京集联软件科技有限公司信息管理系统 摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本信息管理系统就是在这样的大环境下诞生&#xff0c;其可以帮助管理…
阅读更多...
记一个简单工作流引擎的变更历史

记一个简单工作流引擎的变更历史

第1关 一天，老板找到我，说要做个简单的工作流引擎。 我查了一天啥是工作流，然后做出了如下版本：按顺序添加任意个审批人组成一个链表，最后加一个结束节点 记录当前审批人，当审批完后，审批人向后移动一位 当审批人对应结束节点时，流程结束老板：简陋了点。 第2关 老板又…
阅读更多...
笔试题：查找链表中倒数第k（k为正整数）个位置上的结点

笔试题：查找链表中倒数第k（k为正整数）个位置上的结点

数据结构 链表 笔试题：(1)算法的基本设计思想：定义两个结构体指针FPhead和SPhead，其中，FPhead需要从头遍历链表，当FPhead和SPhead之间的距离相差k-1，则调动SPhead开始遍历链表，从而确定倒数第k个位置上的结点。 (2)算法的详细实现步骤：定义一个整型变量用来储存两个结构…
阅读更多...
E-MapReduce极客挑战赛季军方案

E-MapReduce极客挑战赛季军方案

前一段时间我参加了E-MapReduce极客挑战赛&#xff0c;很幸运的获得了季军。在这把我的比赛攻略给大家分享一下&#xff0c;希望可以抛砖引玉。 赛题分析与理解 赛题背景&#xff1a; 大数据时代&#xff0c;上云已成为越来越多终端客户大数据方案的落地选择&#xff0c;阿里…
阅读更多...
Elastic学习之旅 (12) .NET 6应用集成ES - 下

Elastic学习之旅 (12) .NET 6应用集成ES - 下

本篇，我们l来了解下如何在ASP.NET 6应用中对ES中的数据进行查询 和 聚合，通过使用这些查询我们可以在应用中实现一些报表功能。到此，本系列的学习之旅就要跟大家说声再见了，12篇说多不多，持续输出就是坚持，希望对你学习ElasticSearch有所帮助。大家好，我是Edison。 上一…
阅读更多...
Linux使用Docker部署DashDot访问本地服务器面板

Linux使用Docker部署DashDot访问本地服务器面板

文章目录 1. 本地环境检查1.1 安装docker1.2 下载Dashdot镜像 2. 部署DashDot应用 本篇文章我们将使用Docker在本地部署DashDot服务器仪表盘&#xff0c;并且结合cpolar内网穿透工具可以实现公网实时监测服务器系统、处理器、内存、存储、网络、显卡等&#xff0c;并且拥有API接…
阅读更多...
【C++】学习笔记——类和对象_4

【C++】学习笔记——类和对象_4

文章目录 二、类和对象13.运算符重载赋值运算符重载 14. 日期类的实现Date.h头文件Date.cpp源文件test.cpp源文件 未完待续 二、类和对象 13.运算符重载 赋值运算符重载 我们之前学了一个拷贝构造函数&#xff0c;本质上就是创建一个对象&#xff0c;该对象初始化为一个已经…
阅读更多...
全国省市区地址查询API：简单易用的地址查询服务

全国省市区地址查询API：简单易用的地址查询服务

在现代社会，我们经常需要使用地址信息进行各类操作。然而，对于普通用户来说，经纬度坐标和结构化地址可能并不是很好理解，这就给我们的日常生活带来了一些困扰。 为了解决这个问题，WAPI平台推出了一款全国省市区地址查询API。这个API能够将用户输入的地理位置信息转换为高德…
阅读更多...
单元测试必备：Asp.Net Core代码覆盖率实战，打造可靠应用 !

单元测试必备：Asp.Net Core代码覆盖率实战，打造可靠应用 !

引言 在前几章我们深度讲解了单元测试和集成测试的基础知识，这一章我们来讲解一下代码覆盖率,代码覆盖率是单元测试运行的度量值,覆盖率通常以百分比表示，用于衡量代码被测试覆盖的程度，帮助开发人员评估测试用例的质量和代码的健壮性。常见的覆盖率包括语句覆盖率（Line Co…
阅读更多...
028——从GUI-＞Client-＞Server-＞driver实现对SR04的控制

028——从GUI-＞Client-＞Server-＞driver实现对SR04的控制

目录 1、修改GUI 2、修改数据处理和发送缓冲区的帧 3、修改server中对SR04的处理 4、添加SR04的dirver_handle 5、验证 6、遇到问题及解决方法 7、 项目管理操作 1、修改GUI 2、修改数据处理和发送缓冲区的帧 添加对SR04按键事件处理 添加对接收数据的处理 3、修改serv…
阅读更多...
蓝桥杯2024年第十五届省赛

蓝桥杯2024年第十五届省赛

E:宝石组合 根据给的公式化简后变为gcd(a,b,c)根据算数基本定理&#xff0c;推一下就可以了 然后我们对1到mx的树求约数&#xff0c;并记录约数的次数&#xff0c;我们选择一个最大的且次数大于等3的就是gcd int mx; vector<int> g[N]; vector<int> cnt[N]; int…
阅读更多...
体验下，大厂在使用功能的API网关！

体验下，大厂在使用功能的API网关！

作者：小傅哥 博客：https://bugstack.cn沉淀、分享、成长，让自己和他人都能有所收获！😄大家好，我是技术UP主小傅哥。 还是在22年的时候，小傅哥做了一套基于 Netty 协议转换和通信的 API网关，分享给伙伴们学习使用，增加一些业务开发以外的知识积累。不过很多伙伴都问过…
阅读更多...
通过ORPO技术微调 llama3大模型(Fine-tune Llama 3 with ORPO)

通过ORPO技术微调 llama3大模型(Fine-tune Llama 3 with ORPO)

1f45bd1e8577af66a05f5e3fadb0b29 通过ORPO对llama进行微调 前言 ORPO是一种新颖的微调技术，它将传统的监督微调和偏好对齐阶段整合到一个过程中。这减少了训练所需的计算资源和时间。此外，经验结果表明，ORPO在各种模型大小和基准测试中都超过了其他对齐方法。 在本文中，我…
阅读更多...
数据结构系列-堆排序

数据结构系列-堆排序

&#x1f308;个人主页&#xff1a;羽晨同学 &#x1f4ab;个人格言:“成为自己未来的主人~” 昨天我们实现的堆的搭建&#xff0c;我们今天实现以下堆的排序&#xff0c; 堆的排序的最大的优点就是提高的效率&#xff0c;减小了时间复杂度&#xff0c;在这个里面我们有一个…
阅读更多...
【多态】底层原理

【多态】底层原理

博主首页&#xff1a; 有趣的中国人 专栏首页&#xff1a; C进阶 本篇文章主要讲解 多态底层原理 的相关内容 1. 多态原理 1.1 虚函数表 先看一下这段代码&#xff0c;计算一下sizeof(Base)是多少&#xff1a; class Base { public:virtual void Func1(){cout << &quo…
阅读更多...
推荐文章

Copyright @ 2022~2023