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

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

2、i_ge n( Lk-1 ,min _sup);/调用apriori_gen方法生成候选频繁k-项集(4)for each tran sact ion tD /扫描事务数据库D(5)Ct = subset(Ck,t);(6)for each can didate cCt(7)c.co un t+;/统计候选频繁k-项集的计数(8)(9)Lk =c Ck|c.count> m/n_满足最小支持度的k-项集即为频繁k-项集(10) (11)retur n L=U k Lk;/合并频繁k-项集（k>0 ）2、算法流程首先单趟扫描数据集然后通过连接运算,计算各个一项集的支持度，根据给定的最

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

4、 0个项，那么频繁2 项集就有 C210 0 个，为找到元素个数为 10 0的频繁项集，口 b 1 , b 2 ,，b 10 0 ,那么就要扫描数 据库10 0次，产生的候选项集总个数为：举例：对于一个这样庞大的项集，计算机难以存储和计算，挖掘效率低下。二、算法的改进11、改进方法：性质1:频繁项集的所有非空子集都必须是频繁的。(Apriori性质，记为性质1 )性质2：若频繁K 项集L k中各个项可以做链接产生L k +1，则L k中每个元素在 L k中出现的次数应大于或等于K ,若小于K ,则删除该项在 L k中所有的事务集 11 °(Apriori 性质的推论，记为性质2 )改

5、进的方法：在连接之后得到的候选频繁 k项，直接进行最小支持度判断，并进行剪枝，从而直接得到频繁k项集， 避免候选项集可能过大的问题 ；2、算法的流程 首先单趟扫描数据集，计算各个一项集的支持度，根据给定的最小支持度阈值，得到一项频繁集L1。 然后通过连接运算，对于每个连接的到项直接进行最小支持度判断，如果大于最小支持度的加入频繁二项集如果小于则舍弃，循环直到连接完毕；得到二项频繁集L2。 如此进行下去，直到不能连接产生新的频繁项集为止。3、代码实现的描述(详细描述文末附上)：使用C+，构造了一个Apriori类：class Aprioripublic:/初始化，输入数据源，得到原始数据集、频繁

6、1项集void init(string fileName); II连接频繁k项集、并且直接剪枝，得到频繁k+1项集，加入到容器item_listvoid apri_gen(); 连接频繁k项集、并且直接剪枝，得到频繁k+1项集，加入到频繁项集集合frequentvec中float calculateSup(vector<stri ng> judge_item); II求候选项的支持度vector<stri ng> mergeItem(vector<stri ng> vect1,vector<stri ng> vect2,i nt roun d);

7、 II判断两个项是否可以合并成一个新的项集做为新的候选项，能则合并，不能的返回空容器void showltem();输出频繁项集private:vector<set<string>> datavec;II 原始数据集int trancount;II原始数据项数量vector<vector<pair<vector<string>,float>>> frequentvec;II 频繁项集的集合double min sup;II设置最小支持度和最小置信度double minconf; II设置最小支持度和最小置信度;运行结果：效

8、果对比：数据集大小：9835数据元素多少：170置信度:0.05原始：频繁1项集28候选2项集2A28频繁2项集3改进后：频繁1项集28频繁2项集3算法的改进2第一次扫描数据库时，对于数据库中的数据，利用各项元素的数字编号来替换各数据元素的名称；即将数据元素的名称字符传用数字来替换，从而减少在求各候选项的支持度时的资源消耗；代码中的改进之处，string类型的元素转为对应的int代号：储存频繁项集的容器由vector<vector<pair<vector<string>,float>>>变为vector<vector<pair<

9、vector<int>,float>>>；然后对代码进行相应的调整，使得代码正常运行；代码的描述:class Aprioripublic:void init(string fileName); / 初始化，输入数据源，得到原始数据集、频繁1项集void apri_gen(); 连接频繁k项集、并且直接剪枝，得到频繁k+1项集，加入到频繁项集集合frequentvec中float calculateSup(vector<i nt> judge_item); /求候选项的支持度vector<i nt> mergeltem(vector<i

10、 nt> vect1,vector<i nt> vect2,i nt rou nd); /判断两个项是否可以合并成一个新的项集做为新的候选项，能则合并，不能的返回空容器void showltem(); 输出频繁项集private:vector<set<int>> dataNumVec;/原始数据集转换出来的、数据项用代号来表示的数据mapvstring,int> reflection;/原始数据中各个不同的元素的代号映射，数据元素从1开始编号int trancount;/原始数据项数量vector<vector<pair<vec

11、tor<int>,float>>> frequentvec;/ 频繁项集集合，储存各项以及其支持度double min sup;/设置最小支持度和最小置信度;运行结果：效果对比：改进后 14.496 ； 14.549 ； 14.577改进前 20.165 ； 20.463 ； 20.383效率提升28.1%，代码略）附：改进1的代码（改进2与改进1代码几乎相同，不同之处在于储存频繁项的数据类型#in elude <iostream>#in elude <fstream>#in elude <stri ng>#in elude &

12、lt;veetor>#in elude <map>#in elude <emath>#i nclude <algorithm>#i nclude <ioma nip>#in elude <set>#in elude <utility>#in elude <time.h>using n amespaee std;/*最大数据集数量，置信度阈值，*/elass Aprioripublic:/初始化，输入数据源，得到原始数据集、频繁1项集void init(string fileName);/连接频繁k项集、并

13、且直接剪枝，得到频繁k+1项集，加入到容器item_listvoid apri_ge n();/判断候选项，是否为频繁项float calculateSup(vector<stri ng> judge_item);/判断两vector<stri ng> mergeltem(vector<stri ng> vect1,vector<stri ng> vect2,i nt roun d);个项集是否可以合并(要求只有一项不同)成一个新的项集(做为候选集)void showltem();private:vector<set<string&g

14、t;> datavec;/ 原始数据集int trancount;/原始数据项数量vector<vector<pair<vector<string>,float>>> frequentvec;/ 频繁项集 de 集合double min sup;/设置最小支持度和最小置信度double minconf; /设置最小支持度和最小置信度;void Apriori:init(string fileName)std:cout<<"调用 init"<<endl;min sup = 0.05;minconf

15、= 0.5;trancoun t=0;ifstream file(fileName); / 打开数据文件if(!file)/检查文件是否打开成功std:cout<<"Fail to ope n data file!"<<e ndl;elsestri ng temp;set<string> item;/ 项集的临时 setint beg in,end;while(getline(file,temp)/ 一行一行读入数据trancoun t+;begi n=0;/去除字符串首部的空格temp.erase(0,temp.fi nd_first_

16、 no t_of("rtn ");/去除字符串尾部的空格while(e nd=temp.fi nd(',',begi n)!=stri ng: npos)/每一个事务中的项是以空格为分隔符的item.i nsert(temp.substr(begi n,e nd-begi n);/将每一个项插入item中beg in=en d+1;item.i nsert(temp.substr(begi n);/ 一个事务中的最后一项datavec.push_back(item);/将一个事务中的所有项当成一个整体插入另一个大的vectortemp.erase(temp.

17、fi nd_last_ no t_of("rt n")+1);item.clear(); / 清空 item/cout<<temp<<e ndl;/统计各个项集的数目map<stri ng,i nt> items_co unt;for(vector<set<stri ng> >:size_type ix= 0 ;ix !=datavec.size(); +ix)for(set<stri ng>:iterator iy=datavecix.begi n( );iy!=datavecix.e nd();+i

18、y)if (items_co un t.fi nd(*iy) = items_co un t.e nd()items_co un t*iy=1;elseitems_count*iy+;II 该项集的计数加 1vector <stri ng> elem;vector<pair<vector<stri ng>,float>> can didatevec;II候选项集for (map<string,int>:iterator ix = items_count.begin(); ix != items_count.end(); ix+ )是否

19、大于最if ( (float(ix->sec on d)Itra ncou nt >= min sup)II 判断候选频繁 1 项集中的各项，小频繁度，如果是，则为频繁项集；elem.push_back(ix->first);can didatevec.push_back(make_pair(elem,(float(ix->sec on d)Itra ncoun t);elem.clear();II 一定要清空if (!ca ndidatevec.empty()freque ntvec.push_back(ca ndidatevec);II将得到的频繁1项集加入频繁项集

20、集合中can didatevec.clear();II 一定要清空/判断两个项集是否可以合并(要求只有一项不同)成一个新的项集(做为候选集)vector<stri ng> Apriori:mergeltem(vector<stri ng> vect1,vector<stri ng> vect2,i nt round) /cout<<"调用 mergeItem"<<endl;/剪枝工作 /int count=O;/统计两个vector中相同的项的数目vector<stri ng> vect;mapvstr

21、ing,int> tempMap;/辅助判断两个vector中重复的项for(vector<stri ng>:size_type st=0;st<vect1.size();st+)tempMapvect1st+;vect.push_back(vect1st);for(vector<stri ng>:size_type st=0;st<vect2.size();st+)tempMapvect2st+;if(tempMapvect2st=2) / 表示这两项相同coun t+;elsevect.push_back(vect2st);，其他都相同if(cou

22、 nt+1)!=rou nd)/要求两个项目集只有一个项目不相同vect.clear();sort(vect.beg in(), vect.e nd();return vect;/判断一个项，是否为频繁项float Apriori:calculateSup(vector<stri ng> judgeVect)cout<<"调用 judge"<<endl;int count = 0;vector<string>:iterator iter;vector<stri ng>:iterator iterBegi n = j

23、udgeVect.begi n();vector<stri ng>:iterator iterE nd = judgeVect.e nd();for (vector<set<stri ng»:size_type st=0; st != datavec.size(); st+ )iter = iterBegi n;for (; iter != iterE nd; iter +)if (datavecst.fi nd(*iter) = datavecst.e nd() break;if (iter = iterE nd)coun t+;float freque n

24、t = (float)co unt/trancount;retur n freque nt;void Apriori:apri_ge n()/std:cout<<"调用 apri_gen"<<endl;int round = 1;vector<vector<vector<stri ng>»:size_type st = 0; vector<pair<vector<stri ng>,float>> tempVec; vector<stri ng> tempItem;flo

25、at fre = 0.0;while (st != frequentvec.size()/循环在达到频繁项集集合的末尾结束int i=0;if (frequentvecround-1.size() <2)/当前轮次的频繁round项集中想的个数小于 2时，算法结束return;vector<vector<stri ng»:size_type ix , iy;for (ix = 0; ix != freque ntvecro un d-1.size(); ix+)for (iy = ix + 1; iy != freque ntvecr oun d-1.size();

26、 iy+)tempItem =mergeltem(freque ntvecr oun d-1.at(ix).first,freque ntvecr oun d-1.at(iy).first,ro un d);if (!tempItem.empty()fre = calculateSup(templtem);if (fre >= min sup)tempVec.push_back(make_pair(templtem,fre);if (!tempVec.empty() / 如果生成的频繁 round+1 项集freque ntvec.push_back(tempVec);templtem.

27、clear();tempVec.clear();roun d+;st+;elsereturn;void Apriori:showltem()std:cout << " 支持度"<< min sup << "置信度"<< minconf << en dl;for (vector<vector<pair<vector<stri ng>,float>»:size_type st1 = 0; st1 != freque ntvec.size(); st1+)

28、std:cout << " 频繁"<< st1+1 << " 项集："<< endl;for (vector<pair<vector<stri ng>,float»:size_type st2 =0; st2 != freque ntvecst1.size(); st2+)for (vector<string>:size_type st3 = 0; st3 != frequentvecst1.at(st2).first.size(); st3+)std:cout

29、 << frequentvecst1.at(st2).firstst3<<": "<<frequentvecst1.at(st2).second<<",II.5std:cout << en dl;int mai n()time_t startTime,e ndTime;startTime= clock();stri ng in file name = "D:test.txt"Apriori calculati on;calculati on .i nit(i nfile name);c

30、alculati on .apri_ge n();calculati on. showltem();en dTime=clock();cout << " 程序用时"<< (double)(endTime - startTime)/CLOCKS_PER_SEC << "s" <<endl; system("pause");return 0;附：改进2代码#in elude <iostream>#in elude <fstream>#in elude <stri

31、 ng>#in elude <veetor>#in elude <map>#in elude <emath>#in elude <bitset>#i nclude <algorithm>#i nclude <ioma nip>#in elude <set>#in elude <utility>#in elude <time.h>using n amespaee std;/*最大数据集数量，置信度阈值，*/elass Aprioripublic:/初始化，输入数据源，得到原始数据集、

32、频繁1项集void init(string fileName);/连接频繁k项集、并且直接剪枝，得到频繁k+1项集，加入到容器item_listvoid apri_ge n();/判断候选项，是否为频繁项float calculateSup(vector <int> judge_item);vector<i nt> mergeltem(vector<i nt> vect1,vector<i nt> vect2,i nt roun d);/判断两个项集是否可以合并（要求只有一项不同）成一个新的项集（做为候选集）void showltem();pri

33、vate:vector<set< in t>> dataNumVec;/原始数据集转换出来的、数据项用代号来表示的数据map<stri ng,i nt> reflectio n;/原始数据中各个不同的元素的代号映射数据元素从1开始编号int trancount;/原始数据项数量/频繁项集de集合vector<vector<pair<vect or<in t>,float>>> freque ntvec;double min sup;/设置最小支持度和最小置信度double minconf; /设置最小支持度和最

34、小置信度;void Apriori:init(string fileName)std:cout<<"调用 init"<<endl;min sup = 0.05;minconf = 0.5;trancoun t=0;int elemNumber = 1; /用于元素代号的设定ifstream file(fileName); / 打开数据文件if(!file)/检查文件是否打开成功std:cout<<"Fail to ope n data file!"<<e ndl;elsestri ng temp;strin

35、g temp2;set<int> numItem;/项目集的临时代号 setint beg in,end;/去除字符串首部的/去除字符串尾/每一个事务中的项是/如while(getline(file,temp)/ 一行一行读入数据trancoun t+;begi n=0;temp.erase(O,temp.fi nd_first_ no t_of("rtn ");空格temp.erase(temp.fi nd_last_ no t_of("rt n")+1);部的空格while(e nd=temp.fi nd(',',begi

36、 n)!=stri ng: npos)以逗号为分隔符的temp2 =temp.substr(beg in,en d-begi n);if (reflectio n.fin d(temp2) = reflectio n.e nd()/如果这个元素是第一次出现，则加入到映射map中去reflection temp2 = elemNumber+;nu mltem.i nsert(reflectio ntemp2);beg in=en d+1;temp2 = temp.substr(begi n);if (reflectio n.fin d(temp2) = reflectio n.e nd()果这个

37、元素是第一次出现，则加入到映射map中去reflect ion temp2 = elemNumber+;nu mItem.i nsert(reflectio ntemp2);dataNumVec.push_back( nu mltem);/ 将一个事务中的所有项当成一个整体插入另一个大的 vector中numltem.clear(); / 清空 numltemcout<<temp<<e ndl;map<int,int> items_count;/统计各个项集的数目for(vector<set< int> >:size_type ix=

38、 0 ;ix !=dataNumVec.size(); +ix)for(set<i nt>:iteratoriy=dataNumVecix.begi n( );iy!=dataNumVecix.e nd();+iy)if (items_co un t.fi nd(*iy) = items_co un t.e nd()items_co un t*iy=1;elseitems_cou nt*iy+;/ 该项集的计数加 1vector <int> elem;vector<pair<vect or<in t>,float>> can dida

39、tevec;/候选项集for (map<int,int>:iterator ix = items_count.begin(); ix != items_count.end();ix+ )if ( (float(ix->seco nd)/tra ncou nt >= min sup)/ 判断候选频繁 1 项集中的各项，是否大于最小频繁度，如果是，则为频繁项集；elem.push_back(ix->first);can didatevec.push_back(make_pair(elem,(float(ix->sec on d)/tra ncoun t);ele

40、m.clear(); / 一定要清空if (!ca ndidatevec.empty()freque ntvec.push_back(ca ndidatevec);/将得到的频繁1项集加入频繁项集集合中can didatevec.clear();/ 一定要清空/判断两个项集是否可以合并(要求只有一项不同)成一个新的项集(做为候选集)vector <int> Apriori:mergeltem(vect or<int> vect1,vect or<int> vect2,i nt round)/cout<<"调用 mergeltem&quo

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

42、;/表示这两项相同if(tempMapvect2st=2) coun t+;elsevect.push_back(vect2st);，其他都相同if(cou nt+1)!=rou nd)/要求两个项目集只有一个项目不相同vect.clear();sort(vect.beg in(), vect.e nd();return vect;/判断一个项，是否为频繁项float Apriori:calculateSup(vect or<int> judgeVect)cout<<"调用 judge"<<endl;int count = 0;vecto

43、r<in t>:iterator iter;vector<in t>:iterator iterBegi n = judgeVect.beg in();vector<in t>:iterator iterE nd = judgeVect.e nd();for (vector<set< in t»:size_type st=0; st != dataNumVec.size(); st+ ) iter = iterBegi n;for (; iter != iterE nd; iter +)if (dataNumVecst.fi nd(*i

44、ter) = dataNumVecst.e nd() break;if (iter = iterE nd)coun t+;float freque nt = (float)co unt/trancount;retur n freque nt;void Apriori:apri_ge n()/std:cout<<"调用 apri_gen"<<endl;int round = 1;vector<vector<pair<vect or<in t>,float>>>:size_type st = 0;vecto

45、r<pair<vect or<in t>,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<vect or<in t>,float>>:size_type ix , iy;for (ix = 0; ix != freque