数据挖掘 关联规则挖掘 Apriori算法 C++实现_用c++实现apriori算法求解频繁项集和关联规则

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

本文只是基于课程作业的相关理解，请谨慎参考，如有不妥，欢迎各位批评指正。

一、Apriori是什么，大致步骤？

示例：Apriori算法是一种最有影响的布尔关联规则频繁项集的算法，Apriori 使用一乘坐逐层扫描的迭代方法，“K-1”项集用于搜索“K”项集。
大致步骤：首先找出频繁一项集的集合，该集合记为L1。L1用于找频繁2项集的集合L2,继续用L2找频繁3项集，如此下去，用Lk-1项集找Lk项集。

二、全部代码

全部代码

代码如下（示例）：

#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <map>
#include <algorithm>
#include <ctime>
#include <cstring>
#include<set>
#include<list>
#include<omp.h> 
#define maxn 90000
using namespace std;
int ss[17000][17000]={0}; //用于寻找频繁二项集 
double minsupport;//定义最小支持度 
int minsupportnum;//将最小支持度乘以源数据库的行数得到最小支持度的整数形式 
int rescount;//源数据库的行数 
vector<vector<int>> res;//源数据库 
map<int,int> onemap;//用于统计一项集的次数 
vector<pair<vector<int>,int>> pa;//存放上一个频繁项集 
set<set<int>> CK;//存放上一个的频繁项集 
bool v[maxn],v1[maxn];//两个标志数组，example如果源数据库的一行不包含任何一个频繁一项集，那么这个源数据库的一行肯定不包含任何一个频繁二项集 
int ans=0;//存放最后结果的个数 
bool panduan1(vector<int>& a1, vector<int>& a2)//判断两个项集可不可以连接 ，如果除了最后一个元素都是相同的，则可以连接 
{
	int size=a1.size();
	for(int i=0;i<size-1;i++)
	if(a1[i]!=a2[i])return 0;
	return 1;
}
int main(){
	cout << "输入最小支持度\n";
	cin >> minsupport;//输入最小支持度 
	double time=clock();//定义一个时钟，统计时间 
	ifstream fin("retail.dat");//读文件 
	ofstream fout("aprio_out.txt");//写文件 
	if(fin.is_open())//读取文件 
	{
		rescount=0;
		string s;
		while(getline(fin,s)){
			rescount++;
			int i=0;
			vector<int>temp;
			while(s[i]!='\0'){
				if(isdigit(s[i])){
					int sum=0;
					for(;isdigit(s[i]);i++){
						sum=sum*10+s[i]-'0';
					}
					onemap[sum]++;
					//初始化寻找频繁二项集的二维数组 
					int ll=temp.size();
					for(int i=0;i<ll;i++)
						ss[temp[i]][sum]++;
					temp.push_back(sum);
				}
				else
					i++;
			}
			res.push_back(temp);	
		}
	}
	else{
		cout<<"can not open file";
		exit(0);
	}
	//读文件结束 
	minsupportnum=ceil(minsupport*rescount);
	cout<<"行数为"<<res.size()<<endl<<"最小支持度为"<<minsupportnum<<"\n";
			
	#pragma omp parallel for
	//进行频繁一项集的工作 
	for(auto it :onemap){//遍历用onemap统计的频繁一项集 
		if(it.second>=minsupportnum){//将频繁一项集装入pa，CK计算单元 
			vector<int> temp;//定义替换容器 
			set<int> temp2;//定义替换的容器 
			temp.push_back(it.first);
			temp2.insert(it.first);
			pa.push_back(make_pair(temp,it.second));
			CK.insert(temp2);
		}
	}
	//	#pragma omp parallel for
	//进行标志数组的初始化 
	int res_size=res.size();
	#pragma omp parallel for
	for(int i=0;i<res_size;i++){//如果源数据库的某一行数据包括频繁一项集，则将他的标志数组置为1，其他置为0 
		for(auto it : res[i] ){
			if(onemap[it]>=minsupportnum){
				v[i]=1;
				break;
			}
		}
	}
	int xiangji=1;//定义项集数，标志该代码段，处理到第几项集 
	//将频繁一项集输入到out.txt文件中 
	if(pa.size()>0){
		ans+=pa.size();
		fout<<"**************************\n";
		fout<<xiangji<<"项集:个数为"<<pa.size()<<endl;
//		for(auto it :pa){
//			for(auto iter : it.first)
//				fout<<iter<<" ";
//			fout<<"个数为"<<it.second<<"\n";
//		}
	}
	//处理频繁二项集
	 memset(v1,0,sizeof(v1));//将v1标志数组初始化为0 
		vector<pair<vector<int>,int>> pa21;
		set<set<int>>CK21;//定义替换容器，pa21和CK21 
		int pa_size1=pa.size();
		for(int i=0;i<pa_size1;i++){
			int numm;//定义频繁二项集的出现次数 
			
			for(int j=0;j<pa_size1;j++){//自联结，产生候补二项集合 
				numm=ss[pa[i].first[0]][pa[j].first[0]];
				
				if(numm>=minsupportnum){
					vector<int> tempp;
					tempp.push_back(pa[i].first[0]);
					tempp.push_back(pa[j].first[0]);
					set<int> tempp1(tempp.begin(),tempp.end());
					CK21.insert(tempp1);
					pa21.push_back(make_pair(tempp,numm));
				}	
			}
			
		}
		pa=pa21;
		CK=CK21;
		xiangji++;		      
	if(pa.size()>0){
		ans+=pa.size();
		fout<<"**************************\n";
	//fout<<xiangji<<"项集:\n";
	fout<<xiangji<<"项集:个数为"<<pa.size()<<endl;
//		for(auto it:pa){
//			for(auto iter : it.first)
//				fout<<iter<<" ";
//			fout<<"个数为"<<it.second<<"\n";
//		}
	}
	//频繁二相机处理结束 
	while(!pa.empty()){
		cout<<"用时"<<double(clock()-time)/CLOCKS_PER_SEC<<endl;

		
		//自联结
		memset(v1,0,sizeof(v1));
		vector<pair<vector<int>,int>> pa2;
		set<set<int>>CK2;//用于替换过程中的pa和CK 
		int pa_size=pa.size();
		for(int i=0;i<pa_size;i++){
			for(int j=i+1;j<pa_size;j++){
				vector<int> temp;
				if(panduan1(pa[i].first,pa[j].first)){
					temp=pa[i].first;//直接将第一个插入，第二个的最后一个字母放在后面 
					temp.push_back(pa[j].first.back());
					set<int> temp2(temp.begin(),temp.end());
					//裁剪 
				bool biaozhi=true;
				for(set<int>::iterator it=temp2.begin();it!=temp2.end();it++){
					int num1=*it;
					set<int> temp1(temp2.begin(),temp2.end());
					temp1.erase(num1);
					if(!CK.count(temp1)){ 
						biaozhi=false;
						break;
					} 
				}
				//裁剪后看是否保存	
					if(biaozhi){
						//int num=numcount(temp);
				//统计初始项集次数 
					int num=0;
	int size=temp.size();
	for(int i=0;i<rescount;i++){
		if(v[i]==0) continue;
		int size1=res[i].size();
		if(size>size1) continue;
		int i1,i2;
		for( i1=0,i2=0;i1<size&&i2<size1;){
			if(temp[i1]==res[i][i2]) i1++;
			i2++;
		}
		if(i1==size){//判断该候选项集是否是频繁的 
			num++;
			v1[i]=true;
		}
	}
//	***
	//将不符合条件的 
						if(num>=minsupportnum){
							pa2.push_back(make_pair(temp,num));
							CK2.insert(temp2);
						}
					}
				}
			}
		}
		pa=pa2;
		CK=CK2;
		memcpy(v,v1,sizeof(v));
		xiangji++;//显示到几项集
	//将频繁项集输入到文价夹中 
	if(pa.size()>0){
		ans+=pa.size();
		fout<<"**************************\n";
		//fout<<xiangji<<"项集:\n";
		fout<<xiangji<<"项集:个数为"<<pa.size()<<endl;
//		for(auto it:pa){
//			for(auto iter : it.first)
//				fout<<iter<<" ";
//			fout<<"个数为"<<it.second<<"\n";
//		}
	} 
		 
	}
	cout<<"最后的所有频繁项集总数"<<ans<<endl;
	cout<<"最后的总用时"<<double(clock()-time)/CLOCKS_PER_SEC<<endl;
	//system("pause");
	return 0;	
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225

总结

本文只是初步对于该算法的理解，后续还会进行更新，谢谢大家。