数据挖掘Apriori算法C++实现

1、一、原Apriori算法1、算法原理：该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法（1）L1 = find_frequent_1-itemsets(D); / 挖掘频繁1-项集，比较容易（2）for (k=2;Lk-1 ;k+) （3）Ck = apri

2、ori_gen(Lk-1 ,min_sup); / 调用apriori_gen方法生成候选频繁k-项集（4）for each transaction t D / 扫描事务数据库D（5）Ct = subset(Ck,t);（6）for each candidate c Ct（7）c.count+; / 统计候选频繁k-项集的计数（8）（9）Lk =c Ck|c.countmin_sup / 满足最小支持度的k-项集即为频繁k-项集（10） （11） return L= k Lk; / 合并频繁k-项集（k>0）2、算法流程 首先单趟扫描数据集，计算各个一项集的支持度，根据给定的最小支持度闵

3、值，得到一项频繁集L1。 然后通过连接运算，得到二项候选集，对每个候选集再次扫描数据集，得出每个候选集的支持度，再与最小支持度比较。得到二项频繁集L2。 如此进行下去，直到不能连接产生新的候选集为止。 对于找到的所有频繁集，用规则提取算法进行关联规则的提取。3、算法的不足：（ ）数据库重复扫描的次数太多。在由 寻找 的过程中， 中的每一项都需要扫描事务数据库进行验证，以决定其是否加入 ，存在的频繁 项集越大，重复扫描的次数就越多。这一过程耗时太大，增加了系统 开销，处理效率低 ，不利于实际应用。（ ）产生的候选集可能过于庞大。如果一个频繁 项集包含个项，那么频繁 项集就有 个，为找到元素个数为

4、的频繁项集，如 ， ， ，那么就要扫描数据库次，产生的候选项集总个数为：举例：对于一个这样庞大的项集，计算机难以存储和计算，挖掘效率低下。二、算法的改进11、改进方法：性质：频繁项集的所有非空子集都必须是频繁的。（ 性质，记为性质 ）性质：若频繁 项集 中各个项可以做链接产生 ，则 中每个元素在 中出现的次数应大于或等于 ，若小于 ，则删除该项在 中所有的事务集 。（性质的推论，记为性质 ）改进的方法：在连接之后得到的候选频繁k项，直接进行最小支持度判断，并进行剪枝，从而直接得到频繁k项集，避免候选项集可能过大的问题；2、算法的流程 首先单趟扫描数据集，计算各个一项集的支持度，根据给定的最小支

5、持度阈值，得到一项频繁集L1。 然后通过连接运算，对于每个连接的到项直接进行最小支持度判断，如果大于最小支持度的加入频繁二项集，如果小于则舍弃，循环直到连接完毕；得到二项频繁集L2。 如此进行下去，直到不能连接产生新的频繁项集为止。3、代码实现的描述（详细描述文末附上）：使用C+，构造了一个Apriori类：class Aprioripublic:/初始化，输入数据源，得到原始数据集、频繁1项集void init(string fileName);/连接频繁k项集、并且直接剪枝，得到频繁k+1项集，加入到容器item_listvoid apri_gen();/连接频繁k项集、并且直接剪枝，得到

6、频繁k+1项集，加入到频繁项集集合frequentvec中float calculateSup(vector<string> judge_item); /求候选项的支持度vector<string> mergeItem(vector<string> vect1,vector<string> vect2,int round); /判断两个项是否可以合并成一个新的项集做为新的候选项，能则合并，不能的返回空容器void showItem();/输出频繁项集private:vector<set<string>> datavec;/

7、原始数据集int trancount;/原始数据项数量vector<vector<pair<vector<string>,float>>> frequentvec; /频繁项集的集合double minsup; /设置最小支持度和最小置信度double minconf; /设置最小支持度和最小置信度;运行结果：效果对比：数据集大小：9835数据元素多少：170置信度：0.05原始：频繁1项集28候选2项集228频繁2项集3改进后：频繁1项集28频繁2项集3算法的改进2第一次扫描数据库时，对于数据库中的数据，利用各项元素的数字编号来替换各数据元素的

8、名称；即将数据元素的名称字符传用数字来替换，从而减少在求各候选项的支持度时的资源消耗；代码中的改进之处，string类型的元素转为对应的int代号：储存频繁项集的容器由vector<vector<pair<vector<string>,float>>>变为vector<vector<pair<vector<int>,float>>>；然后对代码进行相应的调整，使得代码正常运行；代码的描述：class Aprioripublic:void init(string fileName); /初始化，输入数

9、据源，得到原始数据集、频繁1项集void apri_gen();/连接频繁k项集、并且直接剪枝，得到频繁k+1项集，加入到频繁项集集合frequentvec中float calculateSup(vector<int> judge_item); /求候选项的支持度vector<int> mergeItem(vector<int> vect1,vector<int> vect2,int round); /判断两个项是否可以合并成一个新的项集做为新的候选项，能则合并，不能的返回空容器 void showItem();/输出频繁项集private:ve

10、ctor<set<int>> dataNumVec;/原始数据集转换出来的、数据项用代号来表示的数据map<string,int> reflection;/原始数据中各个不同的元素的代号映射,数据元素从1开始编号int trancount;/原始数据项数量vector<vector<pair<vector<int>,float>>> frequentvec; /频繁项集集合，储存各项以及其支持度double minsup; /设置最小支持度和最小置信度;运行结果：效果对比：改进后14.496；14.549；14

11、.577改进前20.165；20.463；20.383效率提升28.1%附：改进1的代码（改进2与改进1代码几乎相同，不同之处在于储存频繁项的数据类型，代码略）#include <iostream>#include <fstream>#include <string>#include <vector>#include <map>#include <cmath>#include <algorithm>#include <iomanip>#include <set>#include <

12、utility>#include <time.h>using namespace std;/*最大数据集数量，置信度阈值，*/class Aprioripublic:/初始化，输入数据源，得到原始数据集、频繁1项集void init(string fileName);/连接频繁k项集、并且直接剪枝，得到频繁k+1项集，加入到容器item_listvoid apri_gen();/判断候选项，是否为频繁项float calculateSup(vector<string> judge_item);vector<string> mergeItem(vecto

13、r<string> vect1,vector<string> vect2,int round); /判断两个项集是否可以合并(要求只有一项不同)成一个新的项集（做为候选集）void showItem();private:vector<set<string>> datavec;/原始数据集int trancount;/原始数据项数量vector<vector<pair<vector<string>,float>>> frequentvec; /频繁项集de集合double minsup; /设置最小支

14、持度和最小置信度double minconf; /设置最小支持度和最小置信度;void Apriori:init(string fileName)/std:cout<<"调用init"<<endl;minsup = 0.05;minconf = 0.5; trancount=0;ifstream file(fileName); /打开数据文件if(!file) /检查文件是否打开成功std:cout<<"Fail to open data file!"<<endl;elsestring temp;set&l

15、t;string> item; /项集的临时set int begin,end;while(getline(file,temp) /一行一行读入数据trancount+;begin=0;temp.erase(0,temp.find_first_not_of("rtn "); /去除字符串首部的空格temp.erase(temp.find_last_not_of("rtn")+1); /去除字符串尾部的空格while(end=temp.find(',',begin)!=string:npos) /每一个事务中的项是以空格为分隔符的it

16、em.insert(temp.substr(begin,end-begin); /将每一个项插入item中begin=end+1;item.insert(temp.substr(begin); /一个事务中的最后一项datavec.push_back(item); /将一个事务中的所有项当成一个整体插入另一个大的vector中item.clear(); /清空item/cout<<temp<<endl;map<string,int> items_count;/统计各个项集的数目for(vector<set<string> >:size

17、_type ix= 0 ;ix !=datavec.size(); +ix)for(set<string>:iterator iy=datavecix.begin();iy!=datavecix.end();+iy)if (items_count.find(*iy) = items_count.end()items_count*iy=1;elseitems_count*iy+; /该项集的计数加1vector <string> elem;vector<pair<vector<string>,float>> candidatevec;

18、/候选项集for (map<string,int>:iterator ix = items_count.begin(); ix != items_count.end(); ix+ )if ( (float(ix->second)/trancount >= minsup)/判断候选频繁1项集中的各项，是否大于最小频繁度，如果是，则为频繁项集；elem.push_back(ix->first);candidatevec.push_back(make_pair(elem,(float(ix->second)/trancount);elem.clear();/一定要

19、清空if (!candidatevec.empty()frequentvec.push_back(candidatevec);/将得到的频繁1项集加入频繁项集集合中candidatevec.clear();/一定要清空/判断两个项集是否可以合并(要求只有一项不同)成一个新的项集（做为候选集）vector<string> Apriori:mergeItem(vector<string> vect1,vector<string> vect2,int round) /cout<<"调用mergeItem"<<endl;/

20、剪枝工作/int count=0; /统计两个vector中相同的项的数目vector<string> vect;map<string,int> tempMap; /辅助判断两个vector中重复的项for(vector<string>:size_type st=0;st<vect1.size();st+)tempMapvect1st+;vect.push_back(vect1st);for(vector<string>:size_type st=0;st<vect2.size();st+)tempMapvect2st+;if(tem

21、pMapvect2st=2) /表示这两项相同count+;elsevect.push_back(vect2st);if(count+1)!=round) /要求两个项目集只有一个项目不相同，其他都相同vect.clear();sort(vect.begin(),vect.end();return vect;/判断一个项，是否为频繁项float Apriori:calculateSup(vector<string> judgeVect)/cout<<"调用judge"<<endl;int count = 0;vector<strin

22、g>:iterator iter;vector<string>:iterator iterBegin = judgeVect.begin();vector<string>:iterator iterEnd = judgeVect.end();for (vector<set<string>>:size_type st=0; st != datavec.size(); st+ )iter = iterBegin;for (; iter != iterEnd; iter +)if (datavecst.find(*iter) = datavecs

23、t.end()break;if (iter = iterEnd)count+;float frequent = (float)count/trancount;return frequent;void Apriori:apri_gen()/std:cout<<"调用apri_gen"<<endl;int round = 1;vector<vector<vector<string>>>:size_type st = 0;vector<pair<vector<string>,float>&g

24、t; tempVec;vector<string> tempItem;float fre = 0.0;while (st != frequentvec.size() /循环在达到频繁项集集合的末尾结束int i=0;if (frequentvecround-1.size() <2)/当前轮次的频繁round项集中想的个数小于2时，算法结束return;vector<vector<string>>:size_type ix , iy;for (ix = 0; ix != frequentvecround-1.size(); ix+)for (iy = i

25、x + 1; iy != frequentvecround-1.size(); iy+)tempItem = mergeItem(frequentvecround-1.at(ix).first,frequentvecround-1.at(iy).first,round);if (!tempItem.empty()fre = calculateSup(tempItem);if (fre >= minsup)tempVec.push_back(make_pair(tempItem,fre);if (!tempVec.empty()/如果生成的频繁round+1项集frequentvec.pu

26、sh_back(tempVec);tempItem.clear();tempVec.clear();round+;st+;elsereturn;void Apriori:showItem()std:cout << "支持度"<< minsup << " 置信度" << minconf << endl;for (vector<vector<pair<vector<string>,float>>>:size_type st1 = 0; st1 != f

27、requentvec.size(); st1+)std:cout << "频繁" << st1+1 << "项集：" << endl;for (vector<pair<vector<string>,float>>:size_type st2 =0; st2 != frequentvecst1.size(); st2+)for (vector<string>:size_type st3 = 0; st3 != frequentvecst1.at(st2).fir

28、st.size(); st3+)std:cout << frequentvecst1.at(st2).firstst3<<": "<<frequentvecst1.at(st2).second<<", "std:cout << endl;int main()time_t startTime,endTime;startTime= clock();string infilename = "D:test.txt"Apriori calculation;calculation.ini

29、t(infilename);calculation.apri_gen();calculation.showItem();endTime=clock();cout << "程序用时" << (double)(endTime - startTime)/CLOCKS_PER_SEC << "s" <<endl;system("pause");return 0;附：改进2代码#include <iostream>#include <fstream>#include <

30、;string>#include <vector>#include <map>#include <cmath>#include <bitset>#include <algorithm>#include <iomanip>#include <set>#include <utility>#include <time.h>using namespace std;/*最大数据集数量，置信度阈值，*/class Aprioripublic:/初始化，输入数据源，得到原始数据集、频繁1项集vo

31、id init(string fileName);/连接频繁k项集、并且直接剪枝，得到频繁k+1项集，加入到容器item_listvoid apri_gen();/判断候选项，是否为频繁项float calculateSup(vector<int> judge_item);vector<int> mergeItem(vector<int> vect1,vector<int> vect2,int round); /判断两个项集是否可以合并(要求只有一项不同)成一个新的项集（做为候选集）void showItem();private:vector&l

32、t;set<int>> dataNumVec;/原始数据集转换出来的、数据项用代号来表示的数据map<string,int> reflection;/原始数据中各个不同的元素的代号映射,数据元素从1开始编号int trancount;/原始数据项数量vector<vector<pair<vector<int>,float>>> frequentvec; /频繁项集de集合double minsup; /设置最小支持度和最小置信度double minconf; /设置最小支持度和最小置信度;void Apriori:i

33、nit(string fileName)/std:cout<<"调用init"<<endl;minsup = 0.05;minconf = 0.5; trancount=0;int elemNumber = 1;/用于元素代号的设定ifstream file(fileName); /打开数据文件if(!file) /检查文件是否打开成功std:cout<<"Fail to open data file!"<<endl;elsestring temp;string temp2;set<int> n

34、umItem;/项目集的临时代号setint begin,end;while(getline(file,temp) /一行一行读入数据trancount+;begin=0;temp.erase(0,temp.find_first_not_of("rtn "); /去除字符串首部的空格temp.erase(temp.find_last_not_of("rtn")+1); /去除字符串尾部的空格while(end=temp.find(',',begin)!=string:npos) /每一个事务中的项是以逗号为分隔符的temp2 =temp.

35、substr(begin,end-begin);if (reflection.find(temp2) = reflection.end()/如果这个元素是第一次出现，则加入到映射map中去reflectiontemp2 = elemNumber+;numItem.insert(reflectiontemp2);begin=end+1;temp2 = temp.substr(begin);if (reflection.find(temp2) = reflection.end()/如果这个元素是第一次出现，则加入到映射map中去reflectiontemp2 = elemNumber+;numIt

36、em.insert(reflectiontemp2);dataNumVec.push_back(numItem);/将一个事务中的所有项当成一个整体插入另一个大的vector中numItem.clear();/清空numItem/cout<<temp<<endl;map<int,int> items_count;/统计各个项集的数目for(vector<set<int> >:size_type ix= 0 ;ix !=dataNumVec.size(); +ix)for(set<int>:iterator iy=dataN

37、umVecix.begin();iy!=dataNumVecix.end();+iy)if (items_count.find(*iy) = items_count.end()items_count*iy=1;elseitems_count*iy+; /该项集的计数加1vector <int> elem;vector<pair<vector<int>,float>> candidatevec; /候选项集for (map<int,int>:iterator ix = items_count.begin(); ix != items_c

38、ount.end(); ix+ )if ( (float(ix->second)/trancount >= minsup)/判断候选频繁1项集中的各项，是否大于最小频繁度，如果是，则为频繁项集；elem.push_back(ix->first);candidatevec.push_back(make_pair(elem,(float(ix->second)/trancount);elem.clear();/一定要清空if (!candidatevec.empty()frequentvec.push_back(candidatevec);/将得到的频繁1项集加入频繁项集集

39、合中candidatevec.clear();/一定要清空/判断两个项集是否可以合并(要求只有一项不同)成一个新的项集（做为候选集）vector<int> Apriori:mergeItem(vector<int> vect1,vector<int> vect2,int round) /cout<<"调用mergeItem"<<endl;/剪枝工作/int count=0; /统计两个vector中相同的项的数目vector<int> vect;map<int,int> tempMap; /

40、辅助判断两个vector中重复的项for(vector<int>:size_type st=0;st<vect1.size();st+)tempMapvect1st+;vect.push_back(vect1st);for(vector<int>:size_type st=0;st<vect2.size();st+)tempMapvect2st+;if(tempMapvect2st=2) /表示这两项相同count+;elsevect.push_back(vect2st);if(count+1)!=round) /要求两个项目集只有一个项目不相同，其他都相同

41、vect.clear();sort(vect.begin(),vect.end();return vect;/判断一个项，是否为频繁项float Apriori:calculateSup(vector<int> judgeVect)/cout<<"调用judge"<<endl;int count = 0;vector<int>:iterator iter;vector<int>:iterator iterBegin = judgeVect.begin();vector<int>:iterator ite

42、rEnd = judgeVect.end();for (vector<set<int>>:size_type st=0; st != dataNumVec.size(); st+ )iter = iterBegin;for (; iter != iterEnd; iter +)if (dataNumVecst.find(*iter) = dataNumVecst.end()break;if (iter = iterEnd)count+;float frequent = (float)count/trancount;return frequent;void Apriori

43、:apri_gen()/std:cout<<"调用apri_gen"<<endl;int round = 1;vector<vector<pair<vector<int>,float>>>:size_type st = 0;vector<pair<vector<int>,float>> tempVec;vector<int> tempItem;float fre = 0.0;while (st != frequentvec.size() /循环在达到频繁项集集合的末尾结束int i=0;if (frequentvecround-1.size() <2)/当前轮次的频繁round项集中想的个数小于2时，算法结束return;vector<pair<vector<int>,float>>:size_type ix , iy;for (ix = 0; ix != frequentvec