devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据挖掘实验（Apriori，fpgrowth）

作者：知新_RL | 2024-04-23 15:01:25

赞

踩

数据挖掘实验（Apriori，fpgrowth）

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

  1. #include<iostream>
  2. #include<bits/stdc++.h>
  3. #include<cstring>
  4. #include<set>
  5. #include<map>
  6. #include <unordered_set>
  7. #include<string>
  8. #include<vector>
  9. #include<windows.h>
  10. #include<time.h>
  11. #define DATA_NAME R"(D:\Cpan\Download\.vscode\retail.dat)"
  12. #define N 100000
  13. #define MAX_RECORD_NUM 88162 + 1
  14. #define MAX_ITEMID_NUM 16470 + 1
  15. using namespace std;
  16.  
  17. int recordNum = 0; 
  18. int mp[MAX_ITEMID_NUM];
  19. vector<int> items[N];
  20.  
  21. double support;
  22. void fastRead(){
  23.     char c;
  24.     bool lastIsNum = false;
  25.     uint16_t num;
  26.     FILE* fp = fopen(DATA_NAME, "r");
  27.     while (~(c = fgetc(fp))) {
  28.         if (c >= '0' && c <= '9') {
  29.             if(lastIsNum){
  30.                 num *= 10;
  31.                 num += c - '0';
  32.             }
  33.             else{
  34.                 num = c - '0';
  35.             }
  36.             lastIsNum = true;
  37.         }
  38.         else {
  39.             if (lastIsNum){
  40.                 items[num].push_back(recordNum);
  41.                 mp[num]++;
  42.             }
  43.             if (c == '\n'){
  44.                 recordNum++;
  45.             }
  46.             lastIsNum = false;
  47.         }
  48.     }
  49.     if (lastIsNum) {
  50.         items[num].push_back(recordNum);
  51.         mp[num]++;
  52.     }
  53.     if (c != '\n') {
  54.         recordNum++;
  55.     }
  56.     fclose(fp);
  57. }
  58. vector<int> same_number(vector<int> &tmp1,vector<int> &tmp2){
  59.  
  60.     int ite=0;
  61.     vector<int> res={};
  62.     for(int i=0;i<tmp1.size();++i){
  63.         while(tmp2[ite]<tmp1[i] && ite<tmp2.size()-1) ite++;
  64.         if(tmp2[ite]==tmp1[i]){
  65.             //cout<<tmp2[ite]<<"*"<<tmp1[i]<<" "<<ite<<" "<<i<<endl;
  66.             res.push_back(tmp1[i]);
  67.         }
  68.     }
  69.     return res;
  70. }
  71. vector<vector<int>> v;
  72. vector<vector<int>> v2;
  73. vector<string> s,s2;
  74. int total;
  75. void cal(){
  76.     total=0;
  77.     s.clear();
  78.     v.clear();
  79.     for(int i=0;i<=MAX_ITEMID_NUM;++i){
  80.         if(mp[i]>=recordNum*support*0.01){
  81.             string tri=to_string(i);
  82.             int tmp_len=tri.size();
  83.             for(int j=1;j<=5-tmp_len;j++){
  84.                 tri="0"+tri;
  85.             }
  86.             s.push_back(tri);
  87.             v.push_back(items[i]);
  88.         }
  89.     }
  90.     int now_set_level=1;
  91.     while(1){
  92.         total+=s.size();
  93.         cout<<"共有"<<s.size()<<"个频繁"<<now_set_level<<"项集\n";
  94.         // for(auto t:s){cout<<t<<" ";}
  95.         // cout<<endl;
  96.         v2.clear();
  97.         s2.clear();
  98.         for(int i=0;i<s.size();++i){
  99.             for(int j=i+1;j<s.size();++j){
  100.                 if(s[i].substr(0,s[i].size()-5)==s[j].substr(0,s[i].size()-5)){
  101.                     int num_end=stol(s[j].substr(s[i].size()-5,5));
  102.                     vector<int> tmp1=v[i];
  103.                     vector<int> tmp2=items[num_end];
  104.                     vector<int> same_vector=same_number(tmp1,tmp2);
  105.                     if(same_vector.size()>=recordNum*support*0.01){
  106.                         v2.push_back(same_vector);
  107.                         string new_tmp_string=s[i]+s[j].substr(s[i].size()-5,5);
  108.                         s2.push_back(new_tmp_string);
  109.                     }
  110.                 }
  111.                 //cout<<(s[i].substr(s[i].size()-5,5))<<endl;
  112.             }
  113.         }
  114.         v=v2;
  115.         s=s2;
  116.         if(v.size()==0){
  117.             break;
  118.         }
  119.         now_set_level+=1;
  120.     }
  121.     cout<<"共有"<<total<<"个频繁项集\n";
  122. }
  123. signed main(){
  124.     cout<<"请输入置信度（单位%）\n";
  125.     cin>>support;
  126.     fastRead();
  127.  
  128.     long starttime = GetTickCount();
  129.     cal();
  130.  
  131.     long endtime = GetTickCount();
  132.     long time_cost = endtime - starttime;
  133.     cout << "timecost  " << time_cost << " ms" << endl;
  134.     cout<<"请输入操作\n";
  135.     cout<<" 1:更改置信度\n";
  136.     int oper;
  137.     cin>>oper;
  138.     if(oper==1){
  139.         cout<<"请输入置信度\n";
  140.         cin>>support;
  141.         cal();
  142.     }
  143. }

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

  1. #include<iostream>
  2. #include<bits/stdc++.h>
  3. #include<cstring>
  4. #include<set>
  5. #include<map>
  6. #include <unordered_set>
  7. #include<string>
  8. #include<vector>
  9. #include<windows.h>
  10. #include<time.h>
  11. #define DATA_NAME R"(D:\Cpan\Download\.vscode\retail.dat)"
  12. #define N 100000
  13. #define MAX_RECORD_NUM 88162 + 1
  14. #define MAX_ITEMID_NUM 16470 + 1
  15. using namespace std;
  16.  
  17. int recordNum = 0; 
  18. int mp[MAX_ITEMID_NUM];
  19. vector<int> items[N];
  20.  
  21. double support;
  22. void fastRead(){
  23.     char c;
  24.     bool lastIsNum = false;
  25.     uint16_t num;
  26.     FILE* fp = fopen(DATA_NAME, "r");
  27.     while (~(c = fgetc(fp))) {
  28.         if (c >= '0' && c <= '9') {
  29.             if(lastIsNum){
  30.                 num *= 10;
  31.                 num += c - '0';
  32.             }
  33.             else{
  34.                 num = c - '0';
  35.             }
  36.             lastIsNum = true;
  37.         }
  38.         else {
  39.             if (lastIsNum){
  40.                 items[recordNum].push_back(num);
  41.                 mp[num]++;
  42.             }
  43.             if (c == '\n'){
  44.                 recordNum++;
  45.             }
  46.             lastIsNum = false;
  47.         }
  48.     }
  49.     if (lastIsNum) {
  50.         items[recordNum].push_back(num);
  51.         mp[num]++;
  52.     }
  53.     if (c != '\n') {
  54.         recordNum++;
  55.     }
  56.     fclose(fp);
  57. }
  58.  
  59. int node_number;
  60. vector<vector<int>> v;
  61. vector<int> head_table[MAX_ITEMID_NUM];
  62. int head_table_back[10*MAX_ITEMID_NUM];
  63. vector<pair<int,int>> fp_tree[10*MAX_ITEMID_NUM];
  64. pair<int,int> fp_tree_value[10*MAX_ITEMID_NUM];
  65.  
  66. bool cmp(int &a,int &b){
  67. 	return mp[a]>mp[b];
  68. }
  69. void build(int son,int fa,vector<int> &value,int index){
  70. 	if(index==value.size()) return;
  71. 	bool exi=0;
  72. 	for(auto t:fp_tree[son]){
  73. 		if(t.first!=fa && fp_tree_value[t.first].first==value[index]){
  74. 			fp_tree_value[t.first].second+=1;
  75. 			exi=1;
  76. 			build(t.first,son,value,index+1);
  77. 		}
  78. 	}
  79. 	if(exi==0){
  80. 		node_number+=1;
  81. 		head_table[value[index]].push_back(node_number);
  82. 		head_table_back[node_number]=value[index];
  83. 		fp_tree_value[node_number]={value[index],1};
  84. 		fp_tree[son].push_back({node_number,1});
  85. 		fp_tree[node_number].push_back({son,-1});
  86. 		build(node_number,son,value,index+1);
  87. 	}
  88. }
  89. int tmp_dp[10*MAX_ITEMID_NUM];
  90. void back(int number,vector<int> &res_chain){
  91. 	if(number==0 && fp_tree_value[number].second==0) return ;
  92. 	for(auto t:fp_tree[number]){
  93. 		if(t.second==-1 && fp_tree_value[t.first].second!=0){
  94. 			// cout<<"节点 "<<t.first<<"  ";
  95. 			// cout<<"以前是"<<tmp_dp[t.first]<<"   ";
  96. 			res_chain.push_back({head_table_back[t.first]});
  97. 			//cout<<"现在是"<<tmp_dp[t.first]<<"\n";
  98. 			back(t.first,res_chain);
  99. 		}
  100. 	}
  101. }
  102. int res[MAX_ITEMID_NUM];
  103. vector<int> number_item;
  104. void dfs_son(vector<vector<int>> &res_son,vector<int> &value,vector<int> tmp,int index,int now_number){
  105. 	if(index==value.size()){
  106. 		if(tmp.size()!=0){
  107. 			res_son.push_back(tmp);
  108. 		}
  109. 		return ;
  110. 	}
  111. 	if(now_number<=3){
  112. 		tmp.push_back(value[index]);
  113. 		dfs_son(res_son,value,tmp,index+1,now_number+1);
  114. 		tmp.pop_back();
  115. 		dfs_son(res_son,value,tmp,index+1,now_number);
  116. 	}
  117. 	else{
  118. 		dfs_son(res_son,value,tmp,index+1,now_number);
  119. 	}
  120. }
  121. signed main(){
  122.     cout<<"请输入置信度（单位%）\n";
  123.     cin>>support;
  124.     fastRead();
  125.     for(int i=0;i<recordNum;++i){
  126. 		vector<int> tmp;
  127. 		for(auto t:items[i]){
  128. 			if(mp[t]>=recordNum*support*0.01){
  129. 				tmp.push_back(t);
  130. 			}
  131. 		}
  132. 		if(tmp.size()==0) continue;
  133. 		else{
  134. 			sort(tmp.begin(),tmp.end(),cmp);
  135. 			// for(auto t:tmp){cout<<t<<" ";}
  136. 			// cout<<endl<<"**************************\n";
  137. 			v.push_back(tmp);
  138. 		}
  139. 	}
  140. 	// cout<<v.size()<<endl;
  141. 	long starttime = GetTickCount();
  142. 	for(auto t:v){
  143. 		build(0,-1,t,0);
  144. 	}
  145. 	for(int i=0;i<MAX_ITEMID_NUM;++i){
  146. 		if(mp[i]>=recordNum*support*0.01){
  147. 			res[1]+=1;
  148. 			number_item.push_back(i);
  149. 			//cout<<i<<"*\n";
  150. 		}
  151. 	}
  152. 	
  153. 	
  154. 	for(auto t:number_item){
  155. 		for(int i=0;i<MAX_ITEMID_NUM;++i){
  156. 			tmp_dp[i]=0;
  157. 		}
  158. 		map<vector<int>,int> map_vec;
  159. 		for(auto j:head_table[t]){
  160. 			//cout<<j<<"*";
  161. 			vector<int> vt={};
  162. 			int value=fp_tree_value[j].second;
  163. 			back(j,vt);
  164. 			if(!vt.size()) continue;
  165. 			// vector<vector<int>> vs;
  166. 			// for(int k=0;k<(1<<(vt.size()));k++){
  167. 			// 	vector<int> resson;
  168. 			// 	for(int o=0;o<=vt.size()-1;o++){
  169. 			// 		if((k>>o)&1){
  170. 			// 			resson.push_back(vt[o]);
  171. 			// 		}
  172. 			// 	}
  173. 			// 	if(resson.size()){
  174. 			// 		vs.push_back(resson);
  175. 			// 	}
  176. 			// }
  177. 			// for(auto t:vs){
  178. 			// 	map_vec[t]+=value;
  179. 			// }
  180. 			vector<vector<int> > res_son={};
  181. 			vector<int> tmp2={};
  182. 			dfs_son(res_son,vt,tmp2,0,1);
  183. 			for(auto t:res_son){
  184. 				map_vec[t]+=value;
  185. 			}
  186. 		}
  187. 		for(auto t:map_vec){
  188. 			if(t.second>=recordNum*support*0.01){
  189. 				res[t.first.size()+1]+=1;
  190. 			}
  191. 		}
  192. 	}
  193.  
  194.     long endtime = GetTickCount();
  195. 	long time_cost = endtime - starttime;
  196.     cout << "timecost  " << time_cost << " ms" << endl;
  197.  
  198. 	int total=0;
  199. 	for(int i=1;i<=MAX_ITEMID_NUM;++i){
  200. 		if(res[i]!=0){
  201. 			total+=res[i];
  202. 			cout<<"共有"<<res[i]<<"个频繁"<<i<<"项集\n";
  203. 		}
  204. 		else{
  205. 			cout<<"共有"<<total<<"个频繁项集\n";
  206. 			break;
  207. 		}
  208. 	}
  209.  
  210. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/474502
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号