Apriori算法實(shí)現(xiàn)實(shí)驗(yàn)報(bào)告材料

實(shí)用標(biāo)準(zhǔn)文案文檔大全題目Apriori算法實(shí)現(xiàn)學(xué)生姓名學(xué)生學(xué)號(hào)專業(yè)班級(jí)指導(dǎo)教師實(shí)驗(yàn)一Apriori算法實(shí)現(xiàn)實(shí)驗(yàn)?zāi)康募訌?qiáng)對(duì)Apriori算法的理解；鍛煉分析問題、解決問題并動(dòng)手實(shí)踐的能力。實(shí)驗(yàn)要求使用一種你熟悉的程序設(shè)計(jì)語言，如C++或Java，實(shí)現(xiàn)Apriori算法，至少在兩種不同的數(shù)據(jù)集上比較算法的性能。實(shí)驗(yàn)環(huán)境Win7旗艦版+VisualStudio2010語言：C++算法描述Apriori算法說明在Apriori算法中，尋找頻繁項(xiàng)集的基本思想是：簡單統(tǒng)計(jì)所有含一個(gè)元素項(xiàng)目集出現(xiàn)的頻率，找出不小于最小支持度的項(xiàng)目集,即頻繁項(xiàng)集；從第二步開始，循環(huán)處理直到再?zèng)]有最大項(xiàng)目集生成。循環(huán)過程是:第k步中,根據(jù)第k-1步生成的頻繁(k-1)項(xiàng)集產(chǎn)生侯選k項(xiàng)集。根據(jù)候選k項(xiàng)集，算出候選k項(xiàng)集支持度，并與最小支持度比較,找到頻繁k項(xiàng)集。下文中遇到的以下符號(hào),分別代表相應(yīng)的內(nèi)容k-itemsetk項(xiàng)集 Lk頻繁k項(xiàng)集Ck侯選k項(xiàng)集Apriori算法描述數(shù)據(jù)結(jié)構(gòu)說明doubleminsup;//設(shè)置最小支持度map<string,int>items_count;//統(tǒng)計(jì)各個(gè)項(xiàng)集的數(shù)目vector<vector<string>>datavec;//原始數(shù)據(jù)項(xiàng)集vector<vector<string>>candidatevec;//候選項(xiàng)集vector<vector<string>>frequentvec;//頻繁項(xiàng)集ofstreamoutFile;intround=1;//生成項(xiàng)集輪次longtrancount=0;//原始事務(wù)總數(shù)//判斷某個(gè)項(xiàng)目在某一個(gè)事務(wù)中是否存在，存在則值為1，反之為0vector<map<string,bool>>bitmap;Apriori算法的第一步是簡單統(tǒng)計(jì)所有含一個(gè)元素的項(xiàng)集出現(xiàn)的頻率，來決定頻繁1項(xiàng)集。在第k步,分兩個(gè)階段：1，用函數(shù)genCanItemsetK，通過第(k-1)步中生成的頻繁(k-1)項(xiàng)集來生成侯選k項(xiàng)集；2.計(jì)算侯選k項(xiàng)集的支持度，并找出頻繁k項(xiàng)集。Apriori算法描述如下getOriData(); //獲取原始數(shù)據(jù)集，并統(tǒng)計(jì)事務(wù)個(gè)數(shù)genCanItemset1();//產(chǎn)生輸出候選1項(xiàng)集genFreItemset1();//產(chǎn)生頻繁項(xiàng)集 if(!frequentvec.empty())//根據(jù)頻繁1項(xiàng)集，執(zhí)行程序 { do { genCanItemsetK(); //生成并輸出候選k項(xiàng)集 genFreItemsetK(); //計(jì)算并輸出頻繁k項(xiàng)集 }while(!frequentvec.empty());//頻繁項(xiàng)集不為空,則循環(huán)繼續(xù) }其中，產(chǎn)生候選k項(xiàng)集函數(shù)genCanItemsetK中涉及兩個(gè)重要函數(shù)，項(xiàng)集合并函數(shù)mergeItem和剪枝函數(shù)cutNotCanItemsetK。函數(shù)方法說明//獲取原始數(shù)據(jù)集，并統(tǒng)計(jì)事務(wù)個(gè)數(shù)voidgetOriData();//合并生成新的候選項(xiàng)集vector<string>mergeItem(vector<string>vect1,vector<string>vect2,intround);//判斷項(xiàng)集item是否已經(jīng)存在候選項(xiàng)集集合items中,存在則返回1intisExist(vector<string>item,vector<vector<string>>items);//產(chǎn)生并輸出候選1項(xiàng)集voidgenCanItemset1();//產(chǎn)生并輸出頻繁1項(xiàng)集voidgenFreItemset1();//產(chǎn)生并輸出候選k-項(xiàng)集（k>=2）voidgenCanItemsetK();//產(chǎn)生并輸出頻繁k-項(xiàng)集（k>=2）voidgenFreItemsetK();//剪枝：剪去合并后項(xiàng)集中含有非頻繁項(xiàng)集中的項(xiàng)voidcutNotCanItemsetK(vector<string>&item);實(shí)驗(yàn)截圖

程序運(yùn)行界面輸出文件截圖1輸出文件截圖1實(shí)驗(yàn)總結(jié)做完這個(gè)實(shí)驗(yàn)，有如下收獲：同一數(shù)據(jù)集，最小支持度越小，那么產(chǎn)生的頻繁項(xiàng)集維數(shù)越高，程序運(yùn)行時(shí)間越長；更加深刻理解了：頻繁子集的任何子集一定是頻繁的，子集頻繁父親一定頻繁；Apriori也存在缺點(diǎn)：第一在每一步產(chǎn)生侯選項(xiàng)目集時(shí)循環(huán)產(chǎn)生的組合過多，沒有排除不應(yīng)該參與組合的元素；第二,每次計(jì)算項(xiàng)集的支持度時(shí)，開銷會(huì)隨著數(shù)據(jù)的增多而成幾何級(jí)增長。附程序源碼main.cpp#include<iostream>#include<fstream>#include<string>#include<vector>#include<map>#include<algorithm>#include<iomanip>usingnamespacestd;doubleminsup;//設(shè)置最小支持度map<string,int>items_count;//統(tǒng)計(jì)各個(gè)項(xiàng)集的數(shù)目vector<vector<string>>datavec;//原始數(shù)據(jù)項(xiàng)集vector<vector<string>>candidatevec;//候選項(xiàng)集vector<vector<string>>frequentvec;//頻繁項(xiàng)集ofstreamoutFile;intround=1;//生成項(xiàng)集輪次longtrancount=0;//原始事務(wù)總數(shù)//判斷某個(gè)項(xiàng)目在某一個(gè)事務(wù)中是否存在，存在則值為1，反之為0vector<map<string,bool>>bitmap;//獲取原始數(shù)據(jù)集，并統(tǒng)計(jì)事務(wù)個(gè)數(shù)voidgetOriData();//合并生成新的候選項(xiàng)集vector<string>mergeItem(vector<string>vect1,vector<string>vect2,intround);//判斷項(xiàng)集item是否已經(jīng)存在候選項(xiàng)集集合items中,存在則返回1intisExist(vector<string>item,vector<vector<string>>items);//產(chǎn)生并輸出候選1項(xiàng)集voidgenCanItemset1();//產(chǎn)生并輸出頻繁1項(xiàng)集voidgenFreItemset1();//產(chǎn)生并輸出候選k-項(xiàng)集（k>=2）voidgenCanItemsetK();//產(chǎn)生并輸出頻繁k-項(xiàng)集（k>=2）voidgenFreItemsetK();//剪枝：剪去合并后項(xiàng)集中含有非頻繁項(xiàng)集中的項(xiàng)voidcutNotCanItemsetK(vector<string>&item);intmain(){ getOriData(); //獲取原始數(shù)據(jù)集，并統(tǒng)計(jì)事務(wù)個(gè)數(shù) cout<<"請(qǐng)輸入結(jié)果文件名：";//pause stringfName; cin>>fName; cout<<"請(qǐng)輸入最小支持度："; cin>>minsup; outFile.open(fName,ios::trunc); outFile<<"最小支持度為minsup="<<minsup<<endl; genCanItemset1(); genFreItemset1(); if(!frequentvec.empty())//判斷頻繁1項(xiàng)集是否為空，為空則退出 { do { genCanItemsetK(); genFreItemsetK(); }while(!frequentvec.empty());//頻繁項(xiàng)集不為空,則循環(huán)繼續(xù) } outFile.close(); cout<<"\n結(jié)果已保存到"<<fName<<"文件！\n"; system("pause"); return0;}//獲取原始數(shù)據(jù)集，并統(tǒng)計(jì)事務(wù)個(gè)數(shù)voidgetOriData(){ intflag; cout<<"數(shù)據(jù)集文件：\n1.dataA.txt\n2.dataB.txt\n請(qǐng)輸入（1選擇dataA，其他選擇2）\n"; cin>>flag; stringfilename; if(flag==1) filename="dataA.txt";//打開數(shù)據(jù)文件 else filename="dataB.txt"; ifstreamfile(filename); if(!file)//檢查文件是否打開成功 { cout<<"Failtoopendatafile!"<<endl; system("pause"); exit(0); } else { stringtemp; vector<string>item;//項(xiàng)集的臨時(shí)vector cout<<"原始數(shù)據(jù)集："<<endl; intbegin,end; while(getline(file,temp))//一行一行讀入數(shù)據(jù) { 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)//每一個(gè)事務(wù)中的項(xiàng)是以空格為分隔符的 { item.push_back(temp.substr(begin,end-begin));//將每一個(gè)項(xiàng)插入item中 begin=end+1; } item.push_back(temp.substr(begin));//一個(gè)事務(wù)中的最后一項(xiàng) datavec.push_back(item);//將一個(gè)事務(wù)中的所有項(xiàng)當(dāng)成一個(gè)整體插入另一個(gè)大的vector中 item.clear();//清空item cout<<temp<<endl; } } file.close();}//產(chǎn)生并輸出候選1項(xiàng)集voidgenCanItemset1(){ map<string,bool>item_map; for(intix=0;ix!=datavec.size();++ix) { for(intiy=0;iy!=datavec[ix].size();++iy) { items_count[datavec[ix].at(iy)]++;//該項(xiàng)集的計(jì)數(shù)加1 item_map[datavec[ix].at(iy)]=true;//表示該項(xiàng)目在該事務(wù)中存在，值為1，否則默認(rèn)為0 } bitmap.push_back(item_map); item_map.clear();//這里一定要清空一下 } map<string,int>::const_iteratormap_it=items_count.begin(); outFile<<"候選1項(xiàng)集:"<<endl; while(map_it!=items_count.end())//輸出候選1項(xiàng)集 { outFile<<"{"<<map_it->first<<"}"<<endl; map_it++; }}//產(chǎn)生并輸出頻繁1項(xiàng)集voidgenFreItemset1(){ map<string,int>::const_iteratormap_it=items_count.begin(); outFile<<"頻繁1項(xiàng)集:"<<endl; vector<string>item;//項(xiàng)集的臨時(shí)vector while(map_it!=items_count.end())//頻繁1項(xiàng)集 { 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)trancount<<endl; item.push_back(map_it->first); frequentvec.push_back(item);//插入頻繁1項(xiàng)集的vector中 item.clear(); } map_it++; }}//產(chǎn)生并輸出候選k-項(xiàng)集（k>=2）voidgenCanItemsetK(){ //生成下一輪的候選項(xiàng)集 vector<string>item;//項(xiàng)集的臨時(shí)vector intst=frequentvec.size(); candidatevec.clear();//清除上一輪的候選項(xiàng)集 for(intst1=0;st1<st;st1++) { for(intst2=st1+1;st2<st;st2++) { item=mergeItem(frequentvec[st1],frequentvec[st2],round);//調(diào)用函數(shù)合并生成下一輪的候選項(xiàng)集 if(!item.empty()&&!isExist(item,candidatevec))//若經(jīng)過判斷處理后返回的vector不為空且還不存在該項(xiàng)集，則作為候選項(xiàng)集加入候選vector中 { cutNotCanItemsetK(item); } } } round++; outFile<<"候選"<<round<<"項(xiàng)集:"<<endl; for(intix=0;ix!=candidatevec.size();++ix)//輸出候選項(xiàng)集 { outFile<<"{"; for(intiy=0;iy!=candidatevec[ix].size();++iy) { outFile<<candidatevec[ix].at(iy); } outFile<<"}"<<endl; } if(candidatevec.empty())//候選項(xiàng)集為空 { outFile<<"候選"<<round<<"項(xiàng)集為空!"<<endl; }}//產(chǎn)生并輸出頻繁k-項(xiàng)集(k>=2)voidgenFreItemsetK(){ intflag;//標(biāo)記某個(gè)項(xiàng)集在某條事務(wù)中是否出現(xiàn)，出現(xiàn)為1，不出現(xiàn)為0，如：{I1I2} intcount;//統(tǒng)計(jì)某個(gè)想集在整個(gè)交易的事務(wù)集中出現(xiàn)的次數(shù) stringtempstr;//臨時(shí)string，用于串接各個(gè)項(xiàng)成一個(gè)字符串：如:I1I2I3串接為"I1I2I3" intmark;//為避免執(zhí)行多余的字符串串接工作 frequentvec.clear();//清除上一輪的頻繁項(xiàng)集 for(intsx=0;sx!=candidatevec.size();++sx)//構(gòu)造下一輪的頻繁項(xiàng)集 { mark=1; count=0; for(intsy=0;sy!=bitmap.size();++sy) { flag=1;//初始化為1，表出現(xiàn) for(intsz=0;sz!=candidatevec[sx].size();++sz) { if(bitmap[sy][candidatevec[sx].at(sz)]==false)//存在某一個(gè)子項(xiàng)不存在，則沒出現(xiàn)項(xiàng)集 { flag=0; } if(mark==1)//只串接一次，如I1I2否則為10個(gè)I1I2的串接 { tempstr+=candidatevec[sx].at(sz);//串接字符串 } } if(flag)//flag仍然為1，表示該項(xiàng)集在該條事務(wù)中出現(xiàn)了，計(jì)數(shù)加1 { count++; } mark++; } if(((float)count/(float)trancount)>minsup||fabs(((float)count/(float)trancount)-minsup)<1.0e-7)//支持度大于0.2 { frequentvec.push_back(candidatevec[sx]);//插入頻繁項(xiàng)集 } items_count[tempstr]=count;//對(duì)應(yīng)該項(xiàng)集的計(jì)數(shù)值 /////////假設(shè)此時(shí)生成的tempstr為I1I2I3,為便于后面的求置信度的計(jì)算，這里需要產(chǎn)生I2I1I3,I1I3I2等組合，并 //在items_count中給它們賦予和I1I2I3相同的值 sort(candidatevec[sx].begin(),candidatevec[sx].end());//排序 stringtempstr2; while(next_permutation(candidatevec[sx].begin(),candidatevec[sx].end()))//取下一排列組合 { for(inttempst=0;tempst!=candidatevec[sx].size();tempst++)//拼接出該字符串組合 { tempstr2+=candidatevec[sx][tempst]; } items_count[tempstr2]=count;//對(duì)應(yīng)該項(xiàng)集的計(jì)數(shù)值 tempstr2.erase(); } tempstr.erase(); } if(!frequentvec.empty())//頻繁項(xiàng)集不為空 { outFile<<"頻繁"<<round<<"項(xiàng)集:"<<endl; for(intsx=0;sx!=frequentvec.size();++sx)//輸出頻繁項(xiàng)集 { outFile.setf(ios::fixed); outFile<<"{"; for(intsz=0;sz!=frequentvec[sx].size();++sz) { outFile<<frequentvec[sx].at(sz); tempstr+=frequentvec[sx].at(sz);//串接字符串 } outFile<<"}"; outFile<<"支持度:"<<setprecision(2)<<(float)items_count[tempstr]/(float)trancount<<endl; tempstr.erase(); } } else { outFile<<"沒有"<<round<<"-頻繁項(xiàng)集,Apriori算法結(jié)束!"<<endl; }}//兩個(gè)項(xiàng)集合并(要求只有一項(xiàng)不同)成一個(gè)新的項(xiàng)集（做為候選集）vector<string>mergeItem(vector<string>vect1,vector<string>vect2,intround){ intcount=0;//統(tǒng)計(jì)兩個(gè)vector中相同的項(xiàng)的數(shù)目 vector<string>vect; map<string,int>tempMap;//輔助判斷兩個(gè)vector中重復(fù)的項(xiàng) for(unsignedintst=0;st<vect1.size();st++) { tempMap[vect1[st]]++; vect.push_back(vect1[st]); } for(unsignedintst=0;st<vect2.size();st++) { tempMap[vect2[st]]++; if(tempMap[vect2[st]]==2)//表示這兩項(xiàng)相同 { count++; } else { vect.push_back(vect2[st]); } } if((count+1)!=round)//要求兩個(gè)項(xiàng)目集只有一個(gè)項(xiàng)目不相同，其他都相同,如:I1I2I4和I1I2I3 { vect.clear(); } returnvect;}//剪枝：剪去合并后項(xiàng)集中含有非頻繁項(xiàng)集中的項(xiàng)voidcutNotCanItemsetK(vector<string>&item){ ////////實(shí)現(xiàn)剪枝////////////////////////// stringtempstr; vector<string>tempvec; boolfound=false;//是否包含有非頻繁的子集,為1表示含有，有的話進(jìn)行剪枝，如假設(shè)I1I4為非頻繁項(xiàng)集，則I1I2I4要剪枝掉 stringteststr; inttestint; tempvec=item; sort(tempvec.begin(),tempvec.end()); while(next_permutation(tempvec.begin(),tempvec.end()))//遍歷所有的組合I1I2I4,要變成I1I4I2或其他如I2I1I4才能判斷它包含I1I4這個(gè)非頻繁項(xiàng)集 { for(inttempst=0;tempst!=tempvec.size();tempst++)//拼接出該字符串組合 { tempstr+=tempvec[tempst]; } for(map<string,int>::const_iteratortempit=items_count.begin();tempit!=items_count.end();tempit++) { if(((floa