Apriori算法实验报告材料
word题 目Apriori算法实现学生某某学生学号专业班级指导教师2014-12-27实验一 Apriori算法实现一、 实验目的1. 加强对Apriori算法的理解；2. 锻炼分析问题、解决问题并动手实践的能力。二、 实验要求使用一种你熟悉的程序设计语言，如C+或Java，实现Apriori算法，至少在两种不同的数据集上比拟算法的性能。三、 实验环境Win7 旗舰版 + Visual Studio 2010语言：C+四、 算法描述1、 Apriori算法说明在Apriori算法中，寻找频繁项集的根本思想是：A. 简单统计所有含一个元素项目集出现的频率，找出不小于最小支持度的项目集, 即频繁项集；B. 从第二步开始，循环处理直到再没有最大项目集生成。循环过程是: 第k步中, 根据第k-1步生成的频繁(k-1)项集产生侯选k项集。根据候选k项集，算出候选k项集支持度，并与最小支持度比拟, 找到频繁k项集。下文中遇到的以下符号,分别代表相应的内容k-itemsetk项集Lk频繁k项集Ck侯选k项集2、 Apriori算法描述数据结构说明double minsup; /设置最小支持度map<string,int> items_count; /统计各个项集的数目vector<vector<string>> datavec; /原始数据项集vector<vector<string>> candidatevec; /候选项集vector<vector<string>> frequentvec; /频繁项集ofstream outFile;int round=1; /生成项集轮次long trancount=0; /原始事务总数/判断某个项目在某一个事务中是否存在，存在如此值为1，反之为0vector<map<string,bool> > bitmap;Apriori算法的第一步是简单统计所有含一个元素的项集出现的频率，来决定频繁1项集。在第k步,分两个阶段：1，用函数genCanItemsetK，通过第(k-1)步中生成的频繁(k-1)项集来生成侯选k项集；2.计算侯选k项集的支持度，并找出频繁k项集。Apriori算法描述如下getOriData();/获取原始数据集，并统计事务个数genCanItemset1(); /产生输出候选1项集genFreItemset1(); /产生频繁项集if(!frequentvec.empty() /根据频繁1项集，执行程序dogenCanItemsetK();/生成并输出候选k项集genFreItemsetK();/计算并输出频繁k项集while(!frequentvec.empty(); /频繁项集不为空,如此循环继续其中，产生候选k项集函数genCanItemsetK中涉与两个重要函数，项集合并函数mergeItem和剪枝函数cutNotCanItemsetK。3、 函数方法说明/获取原始数据集，并统计事务个数void getOriData();/合并生成新的候选项集vector<string> mergeItem(vector<string> vect1,vector<string> vect2,int round);/判断项集item是否已经存在候选项集集合items中,存在如此返回1int isExist(vector<string> item,vector<vector<string> >items);/产生并输出候选1项集void genCanItemset1();/产生并输出频繁1项集void genFreItemset1();/产生并输出候选k-项集k>=2void genCanItemsetK();/产生并输出频繁k-项集k>=2void genFreItemsetK();/剪枝：剪去合并后项集中含有非频繁项集中的项void cutNotCanItemsetK(vector<string> & item);五、 实验截图1. 程序运行界面2. 输出文件截图13. 输出文件截图1六、 实验总结做完这个实验，有如下收获：1. 同一数据集，最小支持度越小，那么产生的频繁项集维数越高，程序运行时间越长；2. 更加深刻理解了：频繁子集的任何子集一定是频繁的，子集频繁父亲一定频繁；3. Apriori也存在缺点：第一在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素；第二,每次计算项集的支持度时，开销会随着数据的增多而成几何级增长。七、 附1.#include <iostream>#include <fstream>#include <string>#include <vector>#include <map>#include <algorithm>#include <iomanip>using namespace std;double minsup; /设置最小支持度map<string,int> items_count; /统计各个项集的数目vector<vector<string>> datavec; /原始数据项集vector<vector<string>> candidatevec; /候选项集vector<vector<string>> frequentvec; /频繁项集ofstream outFile;int round=1; /生成项集轮次long trancount=0; /原始事务总数/判断某个项目在某一个事务中是否存在，存在如此值为1，反之为0vector<map<string,bool> > bitmap;/获取原始数据集，并统计事务个数void getOriData();/合并生成新的候选项集vector<string> mergeItem(vector<string> vect1,vector<string> vect2,int round);/判断项集item是否已经存在候选项集集合items中,存在如此返回1int isExist(vector<string> item,vector<vector<string> >items);/产生并输出候选1项集void genCanItemset1();/产生并输出频繁1项集void genFreItemset1();/产生并输出候选k-项集k>=2void genCanItemsetK();/产生并输出频繁k-项集k>=2void genFreItemsetK();/剪枝：剪去合并后项集中含有非频繁项集中的项void cutNotCanItemsetK(vector<string> & item);int main()getOriData();/获取原始数据集，并统计事务个数cout << "请输入结果文件名：" /pausestring fName;cin >> fName;cout << "请输入最小支持度："cin >> minsup;outFile.open(fName,ios:trunc);outFile << "最小支持度为minsup = " << minsup << endl;genCanItemset1();genFreItemset1();if(!frequentvec.empty() /判断频繁1项集是否为空，为空如此退出dogenCanItemsetK();genFreItemsetK();while(!frequentvec.empty(); /频繁项集不为空,如此循环继续outFile.close();cout << "n结果已保存到" << fName << "文件！n"system("pause");return 0;/获取原始数据集，并统计事务个数void getOriData()int flag;cout << "数据集文件：n1.dataA.txtn2.dataB.txtn请输入1选择dataA，其他选择2n"cin >> flag;string filename;if(flag = 1)filename = "dataA.txt" /打开数据文件elsefilename = "dataB.txt"ifstream file(filename);if(!file) /检查文件是否打开成功cout<<"Fail to open data file!"<<endl;system("pause");exit(0);elsestring temp;vector<string> item; /项集的临时vector cout<<"原始数据集："<<endl;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) /每一个事务中的项是以空格为分隔符的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(); /清空itemcout <<temp<<endl;file.close();/产生并输出候选1项集void genCanItemset1()map<string,bool> item_map;for(int ix=0;ix!=datavec.size();+ix)for(int iy=0;iy!=datavecix.size();+iy)items_countdatavecix.at(iy)+; /该项集的计数加1item_mapdatavecix.at(iy)=true; /表示该项目在该事务中存在，值为1，否如此默认为0bitmap.push_back(item_map);item_map.clear(); /这里一定要清空一下
