• 数据挖掘实验（Apriori，fpgrowth）

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

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include 
    7. #include
    8. #include
    9. #include
    10. #include
    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;isize();++i){
    63.         while(tmp2[ite]size()-1) ite++;
    64.         if(tmp2[ite]==tmp1[i]){
    65.             //cout<
    66.             res.push_back(tmp1[i]);
    67.         }
    68.     }
    69.     return res;
    70. }
    71. vectorint>> v;
    72. vectorint>> v2;
    73. vector 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<<"共有"<size()<<"个频繁"<"项集\n";
    94.         // for(auto t:s){cout<
    95.         // cout<
    96.         v2.clear();
    97.         s2.clear();
    98.         for(int i=0;isize();++i){
    99.             for(int j=i+1;jsize();++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))<
    112.             }
    113.         }
    114.         v=v2;
    115.         s=s2;
    116.         if(v.size()==0){
    117.             break;
    118.         }
    119.         now_set_level+=1;
    120.     }
    121.     cout<<"共有"<"个频繁项集\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
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include 
    7. #include
    8. #include
    9. #include
    10. #include
    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. vectorint>> v;
    61. vector<int> head_table[MAX_ITEMID_NUM];
    62. int head_table_back[10*MAX_ITEMID_NUM];
    63. vectorint,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<<"节点 "<
    95. 			// cout<<"以前是"<
    96. 			res_chain.push_back({head_table_back[t.first]});
    97. 			//cout<<"现在是"<
    98. 			back(t.first,res_chain);
    99. 		}
    100. 	}
    101. }
    102. int res[MAX_ITEMID_NUM];
    103. vector<int> number_item;
    104. void dfs_son(vectorint>> &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
    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<
    136. 			// cout<
    137. 			v.push_back(tmp);
    138. 		}
    139. 	}
    140. 	// cout<
    141. 	long starttime = GetTickCount();
    142. 	for(auto t:v){
    143. 		build(0,-1,t,0);
    144. 	}
    145. 	for(int i=0;i
    146. 		if(mp[i]>=recordNum*support*0.01){
    147. 			res[1]+=1;
    148. 			number_item.push_back(i);
    149. 			//cout<
    150. 		}
    151. 	}
    152. 	
    153. 	
    154. 	for(auto t:number_item){
    155. 		for(int i=0;i
    156. 			tmp_dp[i]=0;
    157. 		}
    158. 		mapint>,int> map_vec;
    159. 		for(auto j:head_table[t]){
    160. 			//cout<
    161. 			vector<int> vt={};
    162. 			int value=fp_tree_value[j].second;
    163. 			back(j,vt);
    164. 			if(!vt.size()) continue;
    165. 			// vector> vs;
    166. 			// for(int k=0;k<(1<<(vt.size()));k++){
    167. 			// 	vector 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. 			vectorint> > 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<<"共有"<"个频繁"<"项集\n";
    203. 		}
    204. 		else{
    205. 			cout<<"共有"<"个频繁项集\n";
    206. 			break;
    207. 		}
    208. 	}
    209.  
    210. }

  • 相关阅读:
    JavaScript 基础笔记
    计算机网络——运输层作业5.2
    【intent-filter】AndroidManifest中＜intent-filter＞标签的 部分作用
    AUTOSARCAN-Tp协议
    使用Scrapy的调试工具和日志系统定位并解决爬虫问题
    [附源码]计算机毕业设计JAVAjsp医院药房管理系统
    【附代码】使用Shapely计算多边形外扩与收缩
    java计算机毕业设计基于springboo+vue的学生毕业离校系统
    RESTful API — 规范概念、URI 设计、映射 HTTP 方法、API 版本管理、API 命名、统一分页、过滤、排序、 搜索功能
    爬取某音乐榜单歌曲
  • 原文地址：https://blog.csdn.net/m0_61735576/article/details/138074366