数据挖掘实验三应用-Apriori-算法挖掘频繁项集

实验三、应用Apriori算法挖掘频繁项集学院计算机科学与软件学院•实验目的：（1）熟悉VC++编程工具和Apriori频繁项集挖掘算法。（2）根据管理层的需求，确定数据挖掘的任务，明确数据挖掘的功能，也就是明确要挖掘什么。（3）由确定的数据挖掘任务，从实验一处理后的结果中，采用切块或切片等联机分析处理技术，选择出挖掘任务相关数据。（4）用VC++编程工具编写Apriori算法的程序，对任务相关数据运行Apriori算法，挖掘出所有的频繁项集。1.写出实验报告。•实验原理：1、Apriori算法Apriori使用一种称作逐层搜索的迭代方法，k项集用于探索（k+1）项集。首先，通过扫描数据库，累计每个项的计数，并收集满足最小支持度的项，找出频繁1项集的集合。该集合记作L1。然后，L1用于找频繁2项集的集合L2，L2用于找L3，如此下去，直到不能再找到频繁k项集。找每个Lk需要一次数据库全扫描。2、提高频繁项集逐层产生的效率Apriori性质：频繁项集的所有非空子集也必须是频繁的。三、实验内容：1、实验内容在给定的数据中提取统一购物篮购买的商品信息，由这些数据构成事务数据库D，挖掘其中的频繁项集L。挖掘频繁项集的算法描述如下：Apriori算法：使用逐层迭代找出频繁项集输入：事务数据库D；最小支持度阈值。输出：D中的频繁项集L。（1）L1=find_frequent_1-itemsets(D);//挖掘频繁1-项集，比较容易（2）for(k=2;Lk-1≠Φ;k++){（3）Ck=apriori_gen(Lk-1,min_sup);//调用apriori_gen方法生成候选频繁k-项集分为两步：合并、减枝（4）foreachtransactiont∈D{//扫描事务数据库D（5）Ct=subset(Ck,t);（6）foreachcandidatec∈Ct（7）c.count++;//统计候选频繁k-项集的计数（8）}（9）Lk={c∈Ck|c.count≥min_sup}//满足最小支持度的k-项集即为频繁k-项集（10）}（11）returnL=∪kLk;//合并频繁k-项集（k0）算法在根据频繁k-1项集生成频繁K项集过程中要计算频繁K项集中每个元素的支持度，并计算K项集中每个k-1项子集是否在Fk-1中，上述两条任何一条不满足，则删去这个K项集中的元素。2、实验过程1、打开试验用数据，读取出同一流水号的商品ID并取前5位，生成以行为单位生成事务数据集transitions;2、ind_frequent_1-itemsets生成频繁一项集for（eachtransactionintransitions）{for(eachitemintransaction）{oneItemSet；oneItemSet.count++；//对1项集进行计数}}3、apriori-gen(Lk-1)候选集产生算法Forallitemsetp∈Lk-1doForallitemsetq∈Lk-1doIfp.item1=q.item1,p.item2=q.item2,…,p.itemk-2=q.itemk-2,p.itemk-1!=q.itemk-1thenbeginc=p∞q//p、q合并后任意的Lk-1子集ifhas_infrequent_subset(c,Lk-1)thendeletec//存在c不属于Lk-1剪枝elseaddctoCkEndReturnCk4、has_infrequent_subset(c,Lk-1）判断候选集的元素Forall(k-1)-subsetsofcdoIfNot(S∈Lk-1)THENreturnTRUE;ReturnFALSE;1.流程图4、主要程序代码1、//产生事务数据库代码（加注释）#includeiostream#includestring#includefstream#includealgorithmusingnamespacestd;classSales_n{public:stringserial;intmarket;chardate[10];intsn;intid;floatnum;floatprice;};intmain(){//////////打开并创建txt文件//////////////////////////////////charname1[50],name2[50];ifstreaminfile;cout选择要打开的文件：1019n.txt1020n.txt1021n.txtendl;cinname1;infile.open(name1,ios::in);/*stringcontents;*/if(infile.fail()){couterroropen!endl;}cout要保存的文件名：endl;cinname2;ofstreamoutfile(name2,ios::out);if(!outfile){coutopeneror!endl;exit(1);}//////////////////////访问预处理文件/////////////////////////////////////////////Sales_nsal[10000];intsal_size=0;intser_size=0;intm=0,n=1;intnew1[3400][20]={0};//暂时储存商品IDwhile(!infile.eof()){infilesal[sal_size].serialsal[sal_size].marketsal[sal_size].datesal[sal_size].snsal[sal_size].idsal[sal_size].numsal[sal_size].price;sal_size++;}///////////////取统一流水的商品ID前三位按升序无重复的保存起来/////////////////////////new1[0][0]=sal[0].id/10000;for(inti=1;isal_size;i++){if(sal[i].serial==sal[i-1].serial){new1[m][n]=sal[i].id/10000;//////流水号相同n++;//outfilesal[i].id/100'\t';}else{///////排序//////////for(intk=0;kn;k++){for(intj=0;jn-k-1;j++){if(new1[m][j]new1[m][j+1]){intt=new1[m][j];new1[m][j]=new1[m][j+1];new1[m][j+1]=t;}}}for(intl=0;ln;l++){if(new1[m][l-1]!=new1[m][l])outfilenew1[m][l]'\t';}outfileendl;m++;n=0;new1[m][n]=sal[i].id/10000;n++;}}infile.close();//关闭文件outfile.close();//关闭文件system(PAUSE);}2、//Apriori算法挖掘频繁项集support=2（加注释）#includeiostream#includefstream#includestring#includevector#includemap#includecmath#includebitset#includealgorithm#includeiomanipusingnamespacestd;constintminsup=2;//设置最小支持度mapstring,intitems_count;//统计各个项集的数目vectorstringmergeItem(vectorstringvect1,vectorstringvect2,intround);//合并生成新的候选项集intisExist(vectorstringitem,vectorvectorstringitems);//判断项集item是否已经存在候选项集集合items中,存在则返回vectorstringmergeItem(vectorstringvect1,vectorstringvect2,intround)//判断两个项集是否可以合并(要求只有一项不同)成一个新的项集（做为候选集）{////////////////////////////////////////////剪枝工作////intcount=0;//统计两个vector中相同的项的数目vectorstringvect;mapstring,inttempMap;//辅助判断两个vector中重复的项for(vectorstring::size_typest=0;stvect1.size();st++){tempMap[vect1[st]]++;vect.push_back(vect1[st]);}for(intst=0;stvect2.size();st++){tempMap[vect2[st]]++;if(tempMap[vect2[st]]==2)//表示这两项相同{count++;}else{vect.push_back(vect2[st]);}}if((count+1)!=round)//要求两个项目集只有一个项目不相同，其他都相同{vect.clear();}returnvect;}intisExist(vectorstringitem,vectorvectorstringitems)//判断项集item是否已经存在候选项集集合items中,存在则返回{intcount;//统计相同的项的数目if(!items.empty()){for(vectorvectorstring::size_typeix=0;ix!=items.size();ix++){count=0;for(vectorstring::size_typeiy=0;iy!=items[ix].size();iy++){for(vectorstring::size_typeiz=0;iz!=item.size();iz++){if(item[iz]==items[ix].at(iy)){count++;}}}if(count==item.size())//表示存在{return1;}}}return0;}intmain(){vectorvectorstringdatavec;//原始数据项集vectorvectorstringcandidatevec;//候选项集vectorvectorstringfrequentvec;//频繁项集vectormapstring,intbitmap;//判断某个项目在某一个事务中是否存在，存在则值为1，反之为0longtrancount=0;//原始事务总数charname1[50];ifstreamfile;cout选择要打开的文件：new1.txtnew2.txtnew3.txtendl;cinname1;file.open(name1,ios::in);//打开数据文件if(!file)//检查文件是否打开成功{coutFailtoopendatafile!endl;return1;}else{stringtemp;vectorstringitem;//项集的临时vectorintbegin,end;while(getline(file,temp))//一行一行读入数据{trancount++;begin=0;temp.erase(0,temp.find_first_not_of(\r\t\n