Apriori算法實現(xiàn)實驗報告材料

實用標準文案實用標準文案文檔大全文檔大全實用標準文案實用標準文案文檔大全文檔大全題 目學(xué)生姓名Apriori算法實現(xiàn)學(xué)生學(xué)號專業(yè)班級指導(dǎo)教師實驗一Apriori算法實現(xiàn)一、 實驗?zāi)康募訌妼priori算法的理解；鍛煉分析問題、解決問題并動手實踐的能力。二、 實驗要求使用一種你熟悉的程序設(shè)計語言，如C++或Java，實現(xiàn)Apriori算法，至少在兩種不同的數(shù)據(jù)集上比較算法的性能。三、 實驗環(huán)境Win7旗艦版+VisualStudio2010語言：C++四、 算法描述1、Apriori算法說明在Apriori算法中，尋找頻繁項集的基本思想是：簡單統(tǒng)計所有含一個元素項目集出現(xiàn)的頻率，找出不小于最小支持度的項目集，即頻繁項集；從第二步開始，循環(huán)處理直到再沒有最大項目集生成。循環(huán)過程是：第k步中，根據(jù)第k-1步生成的頻繁（k-1）項集產(chǎn)生侯選k項集。根據(jù)候選k項集，算出候選k項集支持度，并與最小支持度比較，找到頻繁k項集。下文中遇到的以下符號，分別代表相應(yīng)的內(nèi)容k-itemsetk項集Lk 頻繁k項集Ck 侯選k項集2、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步,分兩個階段：用函數(shù)genCanltemsetK，通過第(k-1)步中生成的頻繁(k-1)項集來生成侯選k項集；2?計算侯選k項集的支持度，并找出頻繁k項集。Apriori算法描述如下getOriData();//獲取原始數(shù)據(jù)集，并統(tǒng)計事務(wù)個數(shù)genCanItemset1();//產(chǎn)生輸出候選1項集genFreltemset1();//產(chǎn)生頻繁項集if(!frequentvec.empty())//根據(jù)頻繁1項集，執(zhí)行程序{do{genCanltemsetK();//生成并輸出候選k項集genFreItemsetK();//計算并輸出頻繁k項集}while(!frequentvec.empty()); //頻繁項集不為空 ，則循環(huán)繼續(xù)}其中，產(chǎn)生候選k項集函數(shù)genCanltemsetK中涉及兩個重要函數(shù)，項集合并函數(shù)mergeItem和剪枝函數(shù)cutNotCanltemsetK。3、函數(shù)方法說明//獲取原始數(shù)據(jù)集，并統(tǒng)計事務(wù)個數(shù)voidgetOriData();〃合并生成新的候選項集vector<string> mergeltem(vector<string>vect1,vector<string>vect2,intround);〃判斷項集item是否已經(jīng)存在候選項集集合 items中，存在則返回1int isExist(vector<string>item,vector<vector<string>>items);〃產(chǎn)生并輸出候選1項集voidgenCanltemset1();〃產(chǎn)生并輸出頻繁1項集voidgenFreltemset1();//產(chǎn)生并輸出候選k-項集(k>=2)voidgenCanltemsetK();//產(chǎn)生并輸出頻繁k-項集(k>=2)voidgenFreItemsetK();//剪枝：剪去合并后項集中含有非頻繁項集中的項voidcutNotCanltemsetK(vector<string>&item);五、實驗截圖1.程序運行界面數(shù)押集文件：.dateiA.txt.tldldlB.LXL￡諭入（丄遠擇ditafi.其他選擇⑺AEEARrnRBCEABCBL>I-r杵■EO.咬--:1X--名廈_t—ft文w笛取囉AA己隹VI果勒亡^*^誓請2.輸出文件截圖1lA.Lit-記宰0刃it：F看帰日標W】直宵朗WSbtHl40.oooO6E54O.O.O.OB嵐5:1:“吏更豆支21-----"^^1俑支頂頊談23S3DJD1第旳選曹——川——3.輸出文件截圖1=0.2小選o6:OB嗽支支支支iM1/10=0,101/10=0-101/10^0,101/100,10u/lcto.DO:AD:EC:AD:EC

:HJ頊頂頊費子.cir^^J^I-■-----------ooooooo532一飛t山nzlllooooooo—:gACIECIbf隼持持桁芍仔檸持=rmc}d}e}d)+mhh"i<h4j"六、實驗總結(jié)做完這個實驗，有如下收獲：同一數(shù)據(jù)集，最小支持度越小，那么產(chǎn)生的頻繁項集維數(shù)越高，程序運行時間越長；更加深刻理解了：頻繁子集的任何子集一定是頻繁的，子集頻繁父親一定頻繁；Apriori也存在缺點：第一在每一步產(chǎn)生侯選項目集時循環(huán)產(chǎn)生的組合過多，沒有排除不應(yīng)該參與組合的元素；第二，每次計算項集的支持度時，開銷會隨著數(shù)據(jù)的增多而成幾何級增長。七、附1.程序源碼 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ù)voidgetOriData();〃合并生成新的候選項集vector<string> mergeItem(vector<string>vect1,vector<string>vect2,intround);〃判斷項集item是否已經(jīng)存在候選項集集合 items中，存在則返回1int isExist(vector<string>item,vector<vector<string>>items);〃產(chǎn)生并輸出候選1項集voidgenCanltemset1();〃產(chǎn)生并輸出頻繁1項集voidgenFreltemset1();//產(chǎn)生并輸出候選k-項集(k>=2)voidgenCanltemsetK();//產(chǎn)生并輸出頻繁k-項集(k>=2)voidgenFreItemsetK();//剪枝：剪去合并后項集中含有非頻繁項集中的項voidcutNotCanltemsetK(vector<string>&item);intmain(){getOriData(); //獲取原始數(shù)據(jù)集，并統(tǒng)計事務(wù)個數(shù)cout<<"請輸入結(jié)果文件名：";//pausestringfName;cin>>fName;cout<<"請輸入最小支持度：";cin>>minsup;outFile.open(fName,ios::trunc);outFile<<"最小支持度為minsup="<<minsup<<endl;genCanltemset1();genFreltemset1();if(!frequentvec.empty()) //判斷頻繁1項集是否為空，為空則退出{do{genCanltemsetK();genFreltemsetK();}while(!frequentvec.empty()); //頻繁項集不為空 ，則循環(huán)繼續(xù)實用標準文案實用標準文案{文檔大全{文檔大全實用標準文案實用標準文案{文檔大全{文檔大全outFile.close();cout<<"\n結(jié)果已保存到”<<fName<<"文件！\n";system("pause");return0;}//獲取原始數(shù)據(jù)集，并統(tǒng)計事務(wù)個數(shù)voidgetOriData(){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ù)文件elsefilename="dataB.txt";ifstreamfile(filename);if(!file) 〃檢查文件是否打開成功cout<<"Failtoopendatafile!"<<endl;實用標準文案實用標準文案{文檔大全{文檔大全實用標準文案實用標準文案{文檔大全{文檔大全實用標準文案實用標準文案文檔大全文檔大全system("pause");exit(O);}else{stringtemp;vector<string>item; //項集的臨時vectorcoutvv"原始數(shù)據(jù)集："vvendl;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中item.clear();//清空itemcoutvvtempvvendl;}}file.close();}〃產(chǎn)生并輸出候選1項集voidgenCanItemset1(){map<string,bool>item_map;for(intix=O;ix!=datavec.size();++ix){for(intiy=O;iy!=datavec[ix].size();++iy)實用標準文案實用標準文案文檔大全文檔大全實用標準文案實用標準文案文檔大全文檔大全實用標準文案實用標準文案{文檔大全{文檔大全items_count[datavec[ix].at(iy)]++; //該項集的計數(shù)加1item_map[datavec[ix].at(iy)]=true; //表示該項目在該事務(wù)中存在，值為 1,否則默認為0}bitmap.push_back(item_map);item_map.clear(); //這里一定要清空一下}map<string,int>::const_iteratormap_it=items_count.begin();outFile<<"候選1項集:"<<endl;while(map_it!=items_count.end()) //輸出候選1項集{outFilevv"{"vvmap_it->first<v"}"vvendl;map」t++;}}〃產(chǎn)生并輸出頻繁1項集voidgenFreItemset1()mapvstring,int>::const_iteratormap_it=items_count.begin();outFilevv"頻繁1項集:"vvendl;vector<string>item;//項集的臨時vectorwhile(map」t!=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 <<"{"vvmap_it->first<v"}"v<" 支持度："vvsetprecision(2)vv(float)map_it->second/(float)trancountvvendl;item.push_back(map」t->first);frequentvec.push_back(item); //插入頻繁1項集的vector中item.clear();}map」t++;}//產(chǎn)生并輸出候選k-項集(k>=2)voidgenCanltemsetK(){//生成下一輪的候選項集vector<string>item; //項集的臨時vectorintst=frequentvec.size();candidatevec.clear(); //清除上一輪的候選項集for(intst1=O;st1<st;st1++){for(intst2=st1+1;st2<st;st2++){item=mergeltem(frequentvec[st1],frequentvec[st2],round);//調(diào)用函數(shù)合并生成下一輪的候選項集if(!item.empty()&&!isExist(item,candidatevec))//若經(jīng)過判斷處理后返回的 vector不為空且還不存在該項集，則作為候選項集加入候選 vector中{cutNotCanltemsetK(item);}}round++;outFilevv"候選"vvroundvv"項集:"vvendl;for(intix=O;ix!=candidatevec.size();++ix) //輸出候選項集{outFile<<"{";for(intiy=O;iy!=candidatevec[ix].size();++iy){outFile<vcandidatevec[ix].at(iy);}outFilevv"}"vvendl;}if(candidatevec.empty()) //候選項集為空{(diào)outFilevv"候選"vvroundvv"項集為空!"vvendl;}}//產(chǎn)生并輸出頻繁k-項集(k>=2)voidgenFreltemsetK()intflag; 〃標記某個項集在某條事務(wù)中是否出現(xiàn)，出現(xiàn)為1,不出現(xiàn)為0,如：{1112}intcount; //統(tǒng)計某個想集在整個交易的事務(wù)集中出現(xiàn)的次數(shù)stringtempstr;//臨時string，用于串接各個項成一個字符串： 如：11I213串接為"111213"intmark; 〃為避免執(zhí)行多余的字符串串接工作frequentvec.clear(); //清除上一輪的頻繁項集for(intsx=0;sx!=candidatevec.size();++sx) //構(gòu)造下一輪的頻繁項集{mark=1;count=0;for(intsy=0;sy!=bitmap.size();++sy){flag=1; II初始化為1,表出現(xiàn)for(intsz=0;sz!=candidatevec[sx].size();++sz){if(bitmap[sy][candidatevec[sx].at(sz)]==false)II存在某一個子項不存在，則沒出現(xiàn)項集flag=O;}if(mark==1) 〃只串接一次，如 1112否則為10個1112的串接{tempstr+=candidatevec[sx].at(sz);//串接字符串}}if(flag)//flag仍然為1，表示該項集在該條事務(wù)中出現(xiàn)了，計數(shù)加1{count++;}mark++;}if(((float)count/(float)trancount)>minsup||fabs(((float)count/(float)trancount)-minsup)<1.0e-7) //支持度大于0.2frequentvec.push_back(candidatevec[sx]);//插入頻繁項集}items_count[tempstr]=count; //對應(yīng)該項集的計數(shù)值/////////假設(shè)此時生成的tempstr為111213,為便于后面的求置信度的計算，這里需要產(chǎn)生121113,111312等組合，并〃在items_count中給它們賦予和I1I2I3相同的值sort(candidatevec[sx].begin(),candidatevec[sx].end());//排序stringtempstr2;while(next_permutation(candidatevec[sx].begin(),candidatevec[sx].end()))//取下一排列組合{for(inttempst=O;tempst!=candidatevec[sx].size();tempst++)//拼接出該字符串組合{tempstr2+=candidatevec[sx][tempst];items_count[tempstr2]=count; //對應(yīng)該項集的計數(shù)值tempstr2.erase();}tempstr.erase();}if(!frequentvec.empty()) //頻繁項集不為空{(diào)outFilevv"頻繁"vvroundvv"項集:"vvendl;for(intsx=O;sx!=frequentvec.size();++sx) //輸出頻繁項集{outFile.setf(ios::fixed);outFilevv"{";for(intsz=O;sz!=frequentvec[sx].size();++sz){outFilevvfrequentvec[sx].at(sz);tempstr+=frequentvec[sx].at(sz);//串接字符串}outFilevv"}";outFilevv"度:"vvsetprecision(2)vv(float)items_count[tempstr]/(float)trancountvvendl;tempstr.erase();}}else{outFilevv"沒有"vvroundvv"-頻繁項集,Apriori算法結(jié)束!"vvendl;}}〃兩個項集合并(要求只有一項不同)成一個新的項集(做為候選集)vectorvstring> mergeItem(vectorvstring>vect1,vectorvstring>vect2,intround){intcount=0; //統(tǒng)計兩個vector中相同的項的數(shù)目vectorvstring>vect;mapvstring,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) //要求兩個項目集只有一個項目不相同，其他都相同，如：I1I214和11I213vect.clear();實用標準文案實用標準文案文檔大全文檔大全實用標準文案實用標準文案}文檔大全}文檔大全}returnvect;}//剪枝：剪去合并后項集中含有非頻繁項集中的項voidcutNotCanltemsetK(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=O;tempst!=tempvec.size();tempst++)//拼接出該字符串組合{tempstr+=tempvec[tempst];}for(map<string,int>::const_iteratortempit=items_count.begin();tempit!=items_count.end();tempit++){if(((float)(tempit->se