APRIORI算法实验报告

题目Apriori算法实现学生姓名学生学号专业班级指导教师2014-12-27实验一Apriori算法实现一、实验目的1.加强对Apriori算法的理解；2.锻炼分析问题、解决问题并动手实践的能力。二、实验要求使用一种你熟悉的程序设计语言，如C++或Java，实现Apriori算法，至少在两种不同的数据集上比较算法的性能。三、实验环境Win7旗舰版+VisualStudio2010语言：C++四、算法描述1、Apriori算法说明在Apriori算法中，寻找频繁项集的基本思想是：A.简单统计所有含一个元素项目集出现的频率，找出不小于最小支持度的项目集,即频繁项集；B.从第二步开始，循环处理直到再没有最大项目集生成。循环过程是:第k步中,根据第k-1步生成的频繁(k-1)项集产生侯选k项集。根据候选k项集，算出候选k项集支持度，并与最小支持度比较,找到频繁k项集。下文中遇到的以下符号,分别代表相应的内容k-itemsetk项集Lk频繁k项集Ck侯选k项集2、Apriori算法描述数据结构说明doubleminsup;//设置最小支持度mapstring,intitems_count;//统计各个项集的数目vectorvectorstringdatavec;//原始数据项集vectorvectorstringcandidatevec;//候选项集vectorvectorstringfrequentvec;//频繁项集ofstreamoutFile;intround=1;//生成项集轮次longtrancount=0;//原始事务总数//判断某个项目在某一个事务中是否存在，存在则值为1，反之为0vectormapstring,boolbitmap;Apriori算法的第一步是简单统计所有含一个元素的项集出现的频率，来决定频繁1项集。在第k步,分两个阶段：1，用函数genCanItemsetK，通过第(k-1)步中生成的频繁(k-1)项集来生成侯选k项集；2.计算侯选k项集的支持度，并找出频繁k项集。Apriori算法描述如下getOriData();//获取原始数据集，并统计事务个数genCanItemset1();//产生输出候选1项集genFreItemset1();//产生频繁项集if(!frequentvec.empty())//根据频繁1项集，执行程序{do{genCanItemsetK();//生成并输出候选k项集genFreItemsetK();//计算并输出频繁k项集}while(!frequentvec.empty());//频繁项集不为空,则循环继续}其中，产生候选k项集函数genCanItemsetK中涉及两个重要函数，项集合并函数mergeItem和剪枝函数cutNotCanItemsetK。3、函数方法说明//获取原始数据集，并统计事务个数voidgetOriData();//合并生成新的候选项集vectorstringmergeItem(vectorstringvect1,vectorstringvect2,intround);//判断项集item是否已经存在候选项集集合items中,存在则返回1intisExist(vectorstringitem,vectorvectorstringitems);//产生并输出候选1项集voidgenCanItemset1();//产生并输出频繁1项集voidgenFreItemset1();//产生并输出候选k-项集（k=2）voidgenCanItemsetK();//产生并输出频繁k-项集（k=2）voidgenFreItemsetK();//剪枝：剪去合并后项集中含有非频繁项集中的项voidcutNotCanItemsetK(vectorstring&item);五、实验截图1.程序运行界面2.输出文件截图13.输出文件截图1六、实验总结做完这个实验，有如下收获：1.同一数据集，最小支持度越小，那么产生的频繁项集维数越高，程序运行时间越长；2.更加深刻理解了：频繁子集的任何子集一定是频繁的，子集频繁父亲一定频繁；3.Apriori也存在缺点：第一在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素；第二,每次计算项集的支持度时，开销会随着数据的增多而成几何级增长。七、附1.程序源码main.cpp#includeiostream#includefstream#includestring#includevector#includemap#includealgorithm#includeiomanipusingnamespacestd;doubleminsup;//设置最小支持度mapstring,intitems_count;//统计各个项集的数目vectorvectorstringdatavec;//原始数据项集vectorvectorstringcandidatevec;//候选项集vectorvectorstringfrequentvec;//频繁项集ofstreamoutFile;intround=1;//生成项集轮次longtrancount=0;//原始事务总数//判断某个项目在某一个事务中是否存在，存在则值为1，反之为0vectormapstring,boolbitmap;//获取原始数据集，并统计事务个数voidgetOriData();//合并生成新的候选项集vectorstringmergeItem(vectorstringvect1,vectorstringvect2,intround);//判断项集item是否已经存在候选项集集合items中,存在则返回1intisExist(vectorstringitem,vectorvectorstringitems);//产生并输出候选1项集voidgenCanItemset1();//产生并输出频繁1项集voidgenFreItemset1();//产生并输出候选k-项集（k=2）voidgenCanItemsetK();//产生并输出频繁k-项集（k=2）voidgenFreItemsetK();//剪枝：剪去合并后项集中含有非频繁项集中的项voidcutNotCanItemsetK(vectorstring&item);intmain(){getOriData();//获取原始数据集，并统计事务个数cout请输入结果文件名：;//pausestringfName;cinfName;cout请输入最小支持度：;cinminsup;outFile.open(fName,ios::trunc);outFile最小支持度为minsup=minsupendl;genCanItemset1();genFreItemset1();if(!frequentvec.empty())//判断频繁1项集是否为空，为空则退出{do{genCanItemsetK();genFreItemsetK();}while(!frequentvec.empty());//频繁项集不为空,则循环继续}outFile.close();cout\n结果已保存到fName文件！\n;system(pause);return0;}//获取原始数据集，并统计事务个数voidgetOriData(){intflag;cout数据集文件：\n1.dataA.txt\n2.dataB.txt\n请输入（1选择dataA，其他选择2）\n;cinflag;stringfilename;if(flag==1)filename=dataA.txt;//打开数据文件elsefilename=dataB.txt;ifstreamfile(filename);if(!file)//检查文件是否打开成功{coutFailtoopendatafile!endl;system(pause);exit(0);}else{stringtemp;vectorstringitem;//项集的临时vectorcout原始数据集：endl;intbegin,end;while(getline(file,temp))//一行一行读入数据{trancount++;begin=0;temp.erase(0,temp.find_first_not_of(\r\t\n));//去除字符串首部的空格temp.erase(temp.find_last_not_of(\r\t\n)+1);//去除字符串尾部的空格while((end=temp.find('',begin))!=string::npos)//每一个事务中的项是以空格为分隔符的{item.push_back(temp.substr(begin,end-begin));//将每一个项插入item中begin=end+1;}item.push_back(temp.substr(begin));//一个事务中的最后一项datavec.push_back(item);//将一个事务中的所有项当成一个整体插入另一个大的vector中item.clear();//清空itemcouttempendl;}}file.close();}//产生并输出候选1项集voidgenCanItemset1(){mapstring,boolitem_map;for(intix=0;ix!=datavec.size();++ix){for(intiy=0;iy!=datavec[ix].size();++iy){items_count[datavec[ix].at(iy)]++;//该项集的计数加1item_map[datavec[ix].at(iy)]=true;//表示该项目在该事务中存在，值为1，否则默认为0}bitmap.push_back(item_map);item_map.clear();//这里一定要清空一下}mapstring,int::const_iteratormap_it=items_count.begin();outFile候选1项集:endl;while(map_it!=items_count.end())//输出候选1项集{outFile{map_it-first}endl;map_it++;}}//产生并输出频繁1项集voidgenFreItemset1(){mapstring,int::const_iteratormap_it=items_count.begin();outFile频繁1项集:endl;vectorstringitem;//项集的临时vectorwhile(map_it!=items_count.end())//频繁1项集{if(((float)map_it-second/(float)trancount)minsup||fabs(((float)map_it-second/(float)trancount)-minsup)1.0e-7)//支持度大于0.2{outFile.setf(ios::fixed);outFile{map_it-first}支持度:setprecision(2)(float)map_it-second/(float)trancountendl;item.push_back(map_it-first);frequentvec.push_back(item);//插入频繁1项集的vector中item.clear();}map_it++;}}//产生并输出候选k-项集（k=2）voidgenCanItemsetK(){/