数据挖掘Apriori算法C实现

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

2、 3) Ck = apriori_gen(Lk-1 ,min_sup);/ 调用 apriori_gen 方法生成候选频繁 k- 项集4) for each transaction t5) Ct = subset(Ck,t);6) for each candidate c7) c.count+; D /扫描事务数据库D Ct/ 统计候选频繁 k- 项集的计数8) (9) Lk =c Ck|c.count > min_sup/满足最小支持度的k-项集即为频繁 k-项集10) (11) return 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 0个，为找到元

4、素个数为10 0的频繁项集，如b 库100次，产生的候选项集总个数为：- 项集越大，重复扫描的次数就越多。这一过程耗时太 ，不利于实际应用。项集包含100个项，那么频繁2 - 项集就有 C21, b 2,，b 10 0,那么就要扫描数据举例：对于一个这样庞大的项集，计算机难以存储和计算，挖掘效率低下。二、算法的改进 11 、改进方法：性质1：频繁项集的所有非空子集都必须是频繁的。(Apri ori性质，记为性质1性质2:若频繁K -项集L k中各个项可以做链接产生 ，则L k中每个元素在 L k中出现的次数应大于或等于L k 1K，若小于K，则删除该项在 L k中所有的事务集11。(Aprio

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

6、化,输入数据源,得到原始数据集、频繁1项集void init(string fileName); /连接频繁k项集、并且直接剪枝，得到频繁k+1项集，加入到容器item_listvoid即ri_gen();连接频繁k项集、并且直接剪枝，得到频繁k+1项集，加入到频繁项集集合frequentvec中float calculateSup(vector<string> judge_item); /求候选项的支持度vector<string> mergeItem(vector<string> vect1,vector<string> vect2,int

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

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

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

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

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

12、am>#in elude <stri ng>#in elude <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 Aprioripublie:/初始化，输入数据源，得到原始数据集、

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

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

15、"<<endl;min sup = 0.05;minconf = 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(getli ne(file,temp) /一行一行读入数据trancoun t+;begi n=

16、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 n)!=stri ng: npos) /符的每一个事务中的项是以空格为分隔item.i nsert(temp.substr(begi n,en d-begi n); /将每一个项插入item中beg in=en d+1; item.i nse

17、rt(temp.substr(begi n);/datavec.push_back(item); /vector 中一个事务中的最后一项将一个事务中的所有项当成一个整体插入另一个大的item.clear(); /清空 itemcout<<temp<<e ndl;/统计各个项集的数目mapvstri ng,i nt> items_co unt;for(vector<set<stri ng> >:size_type ix= 0 ;ix !=datavec.size(); +ix)for(set<stri ng>:iterator i

18、y=datavecix.begi n( );iy!=datavecix.e nd();+iy) if (items_co un t.fi nd(*iy) = items_co un t.e nd()items_cou nt*iy=1; elseitems_cou nt*iy+; /该项集的计数加 1vector <stri ng> elem;vector<pair<vector<stri ng>,float>> can didatevec; /候选项集for (mapvstring,int>:iterator ix = items_coun

19、t.begin(); ix != items_count.end(); ix+ ) if ( (float(ix->sec on d)/tra ncount >= min sup)/判断候选频繁1项集中的各项，是否大于最小频繁度，如果是，则为频繁项集；elem.push_back(ix->first);can didatevec.push_back(make_pair(elem,(float(ix->sec on d)/tra ncoun t); elem.clear();/ 一定要清空if (!ca ndidatevec.empty()frequentvec.push

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

21、ctor<stri ng> vect;mapvstring,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+;elsev

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

23、;stri ng>:iterator iterBegi n = judgeVect.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 (ite

24、r = 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<vector<stri ng>»:size_type st = 0;vector<pair<vector<stri ng>,float>> tempVec;

25、vector<stri ng> tempitem;float fre = 0.0;while (st != freque ntvec.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

26、; iy != freque ntvecr oun d-1.size(); iy+)tempitem =mergeitem(freque ntvecr oun d-1.at(ix).first,freque ntvecr oun d-1.at(iy).first,ro un d);if (!tempitem.empty()fre = calculateSup(tempitem);if (fre >= min sup)tempVec.push back(make pair(templtem,fre);if (!tempVec.empty()/ 如果生成的频繁 round+1 项集frequ

27、e ntvec.push_back(tempVec);templtem.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 =

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

29、st2).first.size();st3+)std:cout << freque ntvecst1.at(st2).firstst3<<":"<<freque ntvecst1.at(st2).seco nd<<","std:cout << en dl;int mai n()time_t startTime,e ndTime;startTime= clock();stri ng in file name = "D:test.txt"Apriori calculati on;

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

31、de <fstream> #in elude <stri 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;/*最大数据集数量，置信度

32、阈值，*/ elass Aprioripublie:/初始化，输入数据源，得到原始数据集、频繁1项集void init(string fileName);/连接频繁k项集、并且直接剪枝，得到频繁 k+1项集，加入到容器item_list void apri_ge n();/判断候选项，是否为频繁项float calculateSup(vector <int> judge_item);vector<int>mergeltem(vect or<int>veet1,veetor <int>veet2,i ntroun d);/void showltem

33、();private:veetor<set< in t>> dataNumVee; 据map<stri ng,i nt> reflect ion;从1开始编号int trancount;判断两个项集是否可以合并(要求只有一项不同)成一个新的项集(做为候选集)/原始数据集转换出来的、数据项用代号来表示的数/原始数据中各个不同的元素的代号映射，数据元素频繁项集de集合/原始数据项数量veetor<veetor<pair<veet or<in t>,float>>> freque ntvec; / double mi

34、n sup; /设置最小支持度和最小置信度double minconf; /设置最小支持度和最小置信度;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

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

36、uot;)+1);/空格while(e nd=temp.fi nd(',',begi 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);i

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

38、or(vector<set< int> >:size_type ix= 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<p

39、air<vect or<in t>,float>> can didatevec; /候选项集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_

40、pair(elem,(float(ix->sec on d)/tra ncoun t); elem.clear();/ 一定要清空if (!ca ndidatevec.empty()frequentvec.push_back(candidatevec);/将得到的频繁1项集加入频繁项集集合中candidatevec.clear();/ 一定要清空/判断两个项集是否可以合并(要求只有一项不同)成一个新的项集(做为候选集)vector <int> Apriori:mergeltem(vect or<int> vect1,vect or<int> vect2

41、,i nt round)/cout<<"调用 mergeItem"<<endl;/剪枝工作 /int count=O;/统计两个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>:siz

42、e_type st=0;st<vect2.size();st+)tempMapvect2st+;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<<&q

43、uot;调用 judge"<<e ndl;int count = 0;vector<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 (

44、; iter != iterE nd; iter +)if (dataNumVecst.fi nd(*iter) = 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<

45、;in t>,float>»:size_type st = 0;vector<pair<vect or<in t>,float>> tempVec;vector<int> tempItem;float fre = 0.0;while (st != freque ntvec.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 =