數(shù)據(jù)挖掘?qū)嶒?yàn)三應(yīng)用-Apriori-算法挖掘頻繁項(xiàng)集

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實(shí)驗(yàn)三、應(yīng)用 Apriori 算法挖掘頻繁項(xiàng)集學(xué)院 計(jì)算機(jī)科學(xué)與軟件學(xué)院 實(shí)驗(yàn)?zāi)康模海?）熟悉 VC+編程工具和 Apriori 頻繁項(xiàng)集挖掘算法。（2）根據(jù)管理層的需求，確定數(shù)據(jù)挖掘的任務(wù)，明確數(shù)據(jù)挖掘的功能，也就是明確要挖掘什么。（3）由確定的數(shù)據(jù)挖掘任務(wù)，從實(shí)驗(yàn)一處理后的結(jié)果中，采用切塊或切片等聯(lián)機(jī)分析處理技術(shù)，選擇出挖掘任務(wù)相關(guān)數(shù)據(jù)。（4）用 VC+編程工具編寫 Apriori 算法的程序，對任務(wù)相關(guān)數(shù)據(jù)運(yùn)行 Apriori算法，挖掘出所有的頻繁項(xiàng)集。1. 寫出實(shí)驗(yàn)報告。 實(shí)驗(yàn)原理：1 、Apriori 算法 Apriori 使用一種稱作逐層搜索的迭代方法，k

2、 項(xiàng)集用于探索（k+1）項(xiàng)集。首先，通過掃描數(shù)據(jù)庫，累計(jì)每個項(xiàng)的計(jì)數(shù)，并收集滿足最小支持度的項(xiàng)，找出頻繁 1 項(xiàng)集的集合。該集合記作 L 1 。然后，L 1 用于找頻繁 2 項(xiàng)集的集合L 2 ，L 2 用于找 L 3 ，如此下去，直到不能再找到頻繁 k 項(xiàng)集。找每個 L k 需要一次數(shù)據(jù)庫全掃描。2、提高頻繁項(xiàng)集逐層產(chǎn)生的效率 Apriori 性質(zhì)：頻繁項(xiàng)集的所有非空子集也必須是頻繁的。 三、 實(shí)驗(yàn)內(nèi)容：1、實(shí)驗(yàn)內(nèi)容 在給定的數(shù)據(jù)中提取統(tǒng)一購物籃購買的商品信息，由這些數(shù)據(jù)構(gòu)成事務(wù)數(shù)據(jù)庫 D，挖掘其中的頻繁項(xiàng)集 L。挖掘頻繁項(xiàng)集的算法描述如下：Apriori 算法：使用逐層迭代找出頻繁項(xiàng)集輸入：

3、事務(wù)數(shù)據(jù)庫 D；最小支持度閾值。輸出：D 中的頻繁項(xiàng)集 L。（1） L 1 = find_frequent_1-itemsets(D); / 挖掘頻繁 1-項(xiàng)集，比較容易（2） for (k=2;L k-1 ;k+) （3） C k = apriori_gen(L k-1 ,min_sup); / 調(diào)用 apriori_gen 方法生成候選頻繁k-項(xiàng)集分為兩步：合并、減枝（4） for each transaction t D / 掃描事務(wù)數(shù)據(jù)庫 D（5） Ct = subset(C k ,t);（6） for each candidate c Ct（7） c.count+; / 統(tǒng)計(jì)候選頻繁

4、 k-項(xiàng)集的計(jì)數(shù)（8） （9） L k =c Ck|c.countmin_sup / 滿足最小支持度的 k-項(xiàng)集即為頻繁 k-項(xiàng)集（10） （11） return L= k L k ; / 合并頻繁 k-項(xiàng)集（k>0）算法在根據(jù)頻繁 k-1 項(xiàng)集生成頻繁 K 項(xiàng)集過程中要計(jì)算頻繁 K 項(xiàng)集中每個元素的支持度，并計(jì)算 K 項(xiàng)集中每個 k-1 項(xiàng)子集是否在 F k-1 中，上述兩條任何一條不滿足，則刪去這個 K 項(xiàng)集中的元素。2 、實(shí)驗(yàn)過程 1、打開試驗(yàn)用數(shù)據(jù)，讀取出同一流水號的商品 ID 并取前 5 位，生成以行為單位生成事務(wù)數(shù)據(jù)集 transitions; 2、ind_frequent_

5、1-itemsets 生成頻繁一項(xiàng)集for（each transaction in transitions）for(each item in transaction）oneItemSet；oneItemSet.count+；/對 1 項(xiàng)集進(jìn)行計(jì)數(shù) 3、apriori-gen (L k-1 ) 候選集產(chǎn)生算法For all itemset pLk-1 doFor all itemset qLk-1 doIf p.item1=q.item1, p.item2=q.item2, ,p.itemk-2=q.itemk-2,p.item k-1 !=q.item k-1thenbegin c=pq/p、

6、q 合并后任意的 L k-1 子集if has_infrequent_subset(c, L k-1 )then delete c /存在 c 不屬于 L k-1 剪枝else add c to CkEndReturn Ck 4、has_infrequent_subset(c, L k-1 ）判斷候選集的元素For all (k-1)-subsets of c doIf Not(SLk-1) THEN return TRUE;Return FALSE;1. 流程圖4、主要程序代碼1、/產(chǎn)生事務(wù)數(shù)據(jù)庫代碼（加注釋）#include<iostream>#include<strin

7、g>#include<fstream>#include<algorithm>using namespace std;class Sales_npublic:string serial;int market;char date10;int sn; int id;float num;float price;int main() /打開并創(chuàng)建txt文件/char name150,name250; ifstream infile;cout<<"選擇要打開的文件：1019n.txt 1020n.txt 1021n.txt"<<en

8、dl; cin>>name1; infile.open(name1,ios:in); /*string contents;*/if(infile.fail()cout << "error open!" << endl;cout<<"要保存的文件名："<<endl; cin>>name2; ofstream outfile(name2,ios:out); if(!outfile) cout<<"open eror!"<<endl; exit(

9、1); /訪問預(yù)處理文件/Sales_n sal10000;int sal_size=0;int ser_size=0;int m = 0,n = 1; int new1340020=0; /暫時儲存商品IDwhile(!infile.eof()infile >> salsal_size.serial >> salsal_size.market >> salsal_size.date>> salsal_size.sn>> salsal_size.id>> salsal_size.num>> salsal_siz

10、e.price;sal_size+;/取統(tǒng)一流水的商品ID前三位按升序無重復(fù)的保存起來/new100=sal0.id/10000;for (int i =1;i<sal_size;i+) if (sali.serial=sali-1.serial) new1mn=sali.id/10000; /流水號相同n+;/outfile<<sali.id/100<<'t'else /排序/for(int k = 0;k<n;k+)for(int j = 0;j < n-k-1;j+) if(new1mj > new1mj+1) int t

11、= new1mj; new1mj = new1mj+1; new1mj+1 = t; for(int l= 0;l< n;l+)if(new1ml-1!=new1ml) outfile<<new1ml<<'t'outfile<<endl;m+;n = 0;new1mn=sali.id/10000;n+; infile.close();/關(guān)閉文件 outfile.close();/關(guān)閉文件system( "PAUSE ");2、/Apriori算法挖掘頻繁項(xiàng)集support = 2（加注釋）#include <i

12、ostream>#include <fstream>#include <string>#include <vector>#include <map>#include <cmath>#include <bitset>#include <algorithm>#include <iomanip>using namespace std;const int minsup=2; /設(shè)置最小支持度map<string,int> items_count; /統(tǒng)計(jì)各個項(xiàng)集的數(shù)目vector<s

13、tring> mergeItem(vector<string> vect1,vector<string> vect2,int round); /合并生成新的候選項(xiàng)集int isExist(vector<string> item,vector<vector<string> >items); /判斷項(xiàng)集item是否已經(jīng)存在候選項(xiàng)集集合items中,存在則返回vector<string> mergeItem(vector<string> vect1,vector<string> vect2,int

14、round) /判斷兩個項(xiàng)集是否可以合并(要求只有一項(xiàng)不同)成一個新的項(xiàng)集（做為候選集） /剪枝工作/ int count=0; /統(tǒng)計(jì)兩個vector中相同的項(xiàng)的數(shù)目 vector<string> vect; map<string,int> tempMap; /輔助判斷兩個vector中重復(fù)的項(xiàng) for(vector<string>:size_type st=0;st<vect1.size();st+) tempMapvect1st+; vect.push_back(vect1st); for(int st=0;st<vect2.size();

15、st+) tempMapvect2st+; if(tempMapvect2st=2) /表示這兩項(xiàng)相同 count+; else vect.push_back(vect2st); if(count+1)!=round) /要求兩個項(xiàng)目集只有一個項(xiàng)目不相同，其他都相同 vect.clear(); return vect;int isExist(vector<string> item,vector<vector<string> >items) /判斷項(xiàng)集item是否已經(jīng)存在候選項(xiàng)集集合items中,存在則返回 int count; /統(tǒng)計(jì)相同的項(xiàng)的數(shù)目 if(!

16、items.empty() for(vector<vector<string> >:size_type ix=0;ix!=items.size();ix+) count=0; for(vector<string>:size_type iy=0;iy!=itemsix.size();iy+) for(vector<string>:size_type iz=0;iz!=item.size();iz+) if(itemiz=itemsix.at(iy) count+; if(count=item.size() /表示存在 return 1; retur

17、n 0;int main() vector<vector<string> > datavec; /原始數(shù)據(jù)項(xiàng)集 vector<vector<string> > candidatevec; /候選項(xiàng)集 vector<vector<string> > frequentvec; /頻繁項(xiàng)集 vector<map<string,int> > bitmap; /判斷某個項(xiàng)目在某一個事務(wù)中是否存在，存在則值為1，反之為0 long trancount=0; /原始事務(wù)總數(shù) char name150; ifstr

18、eam file; cout<<"選擇要打開的文件：new1.txt new2.txt new3.txt"<<endl; cin>>name1; file.open(name1,ios:in); /打開數(shù)據(jù)文件 if(!file) /檢查文件是否打開成功 cout<<"Fail to open data file!"<<endl; return 1; else string temp; vector<string> item; /項(xiàng)集的臨時vector int begin,end;

19、while(getline(file,temp) /一行一行讀入數(shù)據(jù) 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('t',begin)!=string:npos) /每一個事務(wù)中的項(xiàng)是以't'為分隔符的 item.push_back(temp.substr(begin,end-begin

20、); /將每一個項(xiàng)插入item中 begin=end+1; item.push_back(temp.substr(begin); /一個事務(wù)中的最后一項(xiàng) datavec.push_back(item); /將一個事務(wù)中的所有項(xiàng)當(dāng)成一個整體插入另一個大的vector中 item.clear(); /清空item cout<<"Press Enter to continue the processing" /pause getchar(); map<string,int> item_map; for(vector<vector<string&

21、gt; >:size_type ix=0;ix!=datavec.size();+ix) for(vector<string>:size_type iy=0;iy!=datavecix.size();+iy) items_countdatavecix.at(iy)+; /該項(xiàng)集的計(jì)數(shù)加 item_mapdatavecix.at(iy)=1; /表示該項(xiàng)目在該事務(wù)中存在，值為1，否則默認(rèn)為0 bitmap.push_back(item_map); item_map.clear(); /這里一定要清空一下 map<string,int>:const_iterator

22、map_it=items_count.begin(); cout<<"候選項(xiàng)集1:"<<endl; while(map_it!=items_count.end() /輸出候選1項(xiàng)集 cout<<""<<map_it->first<<""<<endl; map_it+; cout<<"Press Enter to continue the processing" /pause getchar(); map_it=items_co

23、unt.begin(); cout<<"頻繁1項(xiàng)集(minsup=2):"<<endl; while(map_it!=items_count.end() /頻繁1項(xiàng)集 if(map_it->second>minsup) /支持度大于2 cout.setf(ios:fixed); cout<<""<<map_it->first<<""<<" 支持度:"<<setprecision(6)<<map_it-&

24、gt;second<<endl; item.push_back(map_it->first); frequentvec.push_back(item); /插入候選項(xiàng)集的vector中 item.clear(); map_it+; if(!frequentvec.empty() /判斷頻繁項(xiàng)集是否為空，為空則退出 cout<<"Press Enter to continue the processing" /pause getchar(); int round=1; /生成候選項(xiàng)集輪次 int found; /是否包含有非頻繁的子集,為表示含有

25、，有的話進(jìn)行剪枝 string tempstr; vector<string> tempvec; do /生成下一輪的候選項(xiàng)集 vector<vector<string> >:size_type st=frequentvec.size(); candidatevec.clear(); /清除上一輪的候選項(xiàng)集 for(vector<vector<string> >:size_type st1=0;st1<st;st1+) for(vector<vector<string> >:size_type st2=s

26、t1+1;st2<st;st2+) found=0; item=mergeItem(frequentvecst1,frequentvecst2,round); /調(diào)用函數(shù)合并生成下一輪的候選項(xiàng)集 if(!item.empty()&&!isExist(item,candidatevec) /若經(jīng)過判斷處理后返回的vector不為空且還不存在該項(xiàng)集，則作為候選項(xiàng)集加入候選vector中 /實(shí)現(xiàn)剪枝/ string teststr; int testint; tempvec=item; sort(tempvec.begin(),tempvec.end(); while(next

27、_permutation(tempvec.begin(),tempvec.end() /遍歷所有的組合 for(vector<string>:size_type tempst=0;tempst!=tempvec.size();tempst+) /拼接出該字符串組合 tempstr+=tempvectempst; for(map<string,int>:const_iterator tempit=items_count.begin();tempit!=items_count.end();tempit+) if(tempit->second<minsup) /非

28、頻繁項(xiàng)集 if(tempstr.find(tempit->first)!=string:npos) /表示包含有非頻繁子項(xiàng)集 found=1; teststr=tempit->first; testint=tempit->second; break; tempstr.erase(); if(found) /包含非頻繁子項(xiàng)集 break; if(!found) /只有不包含有非頻繁子項(xiàng)集才加入候選項(xiàng)集中，否則剪枝掉 candidatevec.push_back(item); found=0; /重置 frequentvec.clear(); /清除上一輪的頻繁項(xiàng)集 round+

29、; cout<<"候選"<<round<<"項(xiàng)集:"<<endl; for(vector<vector<string> >:size_type ix=0;ix!=candidatevec.size();+ix) /輸出候選項(xiàng)集 cout<<"" for(vector<string>:size_type iy=0;iy!=candidatevecix.size();+iy) cout<<candidatevecix.at(iy)&

30、lt;<' ' cout<<""<<endl; if(candidatevec.empty() /候選項(xiàng)集為空 cout<<"候選"<<round<<"項(xiàng)集為空!"<<endl; int flag; /標(biāo)記某個項(xiàng)集在某條事務(wù)中是否出現(xiàn)，出現(xiàn)為1，不出現(xiàn)為0 int count; /統(tǒng)計(jì)某個想集在整個交易的事務(wù)集中出現(xiàn)的次數(shù) string tempstr; /臨時string，用于串接各個項(xiàng)成一個字符串 int mark; /為避免執(zhí)行多余的字

31、符串串接工作 for(vector<vector<string> >:size_type sx=0;sx!=candidatevec.size();+sx) /構(gòu)造下一輪的頻繁項(xiàng)集 mark=1; count=0; for(vector<map<string,int> >:size_type sy=0;sy!=bitmap.size();+sy) flag=1; /初始化為1，表出現(xiàn) for(vector<string>:size_type sz=0;sz!=candidatevecsx.size();+sz) if(bitmapsy

32、candidatevecsx.at(sz)=0) /存在某一個子項(xiàng)不存在，則沒出現(xiàn)項(xiàng)集 flag=0; if(mark=1) /只串接一次 tempstr+=candidatevecsx.at(sz); /串接字符串 if(flag) /flag仍然為，表示該項(xiàng)集在該條事務(wù)中出現(xiàn)了，計(jì)數(shù)加 count+; mark+; if(count>minsup) /支持度大于2 frequentvec.push_back(candidatevecsx); /插入頻繁項(xiàng)集 items_counttempstr=count; /對應(yīng)該項(xiàng)集的計(jì)數(shù)值 sort(candidatevecsx.begin(),candidatevecsx.end(); /排序 string tempstr2; while(next_permutation(candidatevecsx.