Apriori算法實驗報告

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

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