數據挖掘Apriori算法C實現

1、一、原 Apriori 算法1、算法原理：該算法的基本思想是：首先找出所有的頻集，這些項集出現的頻繁性至少和預定義的最小支持度一樣。然后由頻集產生強關聯(lián)規(guī)則，這些規(guī)則必須滿足最小支持度和最小可信度。然后使用第 1 步找到的頻集產生期望的規(guī)則，產生 只包含集合的項的所有規(guī)則， 其中每一條規(guī)則的右部只有一項， 這里采用的是中規(guī)則的定義。 一旦這些規(guī)則被生成， 那么只有那些大于用戶給定的最小可信度的規(guī)則才被留下來。為了生成所有頻集，使用了遞推的方法1) L1 = find_frequent_1-itemsets(D);/ 挖掘頻繁 1- 項集，比較容易(2) for (k=2;Lk- 1 工；k+)

2、 3) Ck = apriori_gen(Lk-1 ,min_sup);/ 調用 apriori_gen 方法生成候選頻繁 k- 項集4) for each transaction t5) Ct = subset(Ck,t);6) for each candidate c7) c.count+; D /掃描事務數據庫D Ct/ 統(tǒng)計候選頻繁 k- 項集的計數8) (9) Lk =c Ck|c.count > min_sup/滿足最小支持度的k-項集即為頻繁 k-項集10) (11) return L= U k Lk;/ 合并頻繁 k- 項集( k>0 )2、算法流程 首先單趟掃描數

3、據集，計算各個一項集的支持度，根據給定的最小支持度閔值，得到一項頻繁集L1。 然后通過連接運算，得到二項候選集，對每個候選集再次掃描數據集，得出每個候選集的支持度，再與最小 支持度比較。得到二項頻繁集L2。 如此進行下去，直到不能連接產生新的候選集為止。 對于找到的所有頻繁集，用規(guī)則提取算法進行關聯(lián)規(guī)則的提取。3、算法的不足：(1 )數據庫重復掃描的次數太多。在由C K尋找L K的過程中，C K中的每一項都需要掃描事務數據庫進行驗證，以決定其是否加入 L k，存在的頻繁 K 大，增加了系統(tǒng) 1 / 0開銷，處理效率低 10 (2 )產生的候選集可能過于龐大。如果一個頻繁1-10 0個，為找到元

4、素個數為10 0的頻繁項集，如b 庫100次，產生的候選項集總個數為：- 項集越大，重復掃描的次數就越多。這一過程耗時太 ，不利于實際應用。項集包含100個項，那么頻繁2 - 項集就有 C21, b 2,，b 10 0,那么就要掃描數據舉例：對于一個這樣龐大的項集，計算機難以存儲和計算，挖掘效率低下。二、算法的改進 11 、改進方法：性質1：頻繁項集的所有非空子集都必須是頻繁的。(Apri ori性質，記為性質1性質2:若頻繁K -項集L k中各個項可以做鏈接產生 ，則L k中每個元素在 L k中出現的次數應大于或等于L k 1K，若小于K，則刪除該項在 L k中所有的事務集11。(Aprio

5、ri性質的推論，記為性質2)改進的方法：在連接之后得到的候選頻繁 k項，直接進行最小支持度判斷，并進行剪枝，從而直接得到頻繁 k項集,避免候選項集可能過大的問題；2、算法的流程 首先單趟掃描數據集，計算各個一項集的支持度，根據給定的最小支持度閾值，得到一項頻繁集L1。 然后通過連接運算，對于每個連接的到項直接進行最小支持度判斷，如果大于最小支持度的加入頻繁二項集， 如果小于則舍棄，循環(huán)直到連接完畢；得到二項頻繁集 L2。 如此進行下去，直到不能連接產生新的頻繁項集為止。3、代碼實現的描述(詳細描述文末附上)：使用C+,構造了一個Apriori類：class Aprioripublic:/ 初始

6、化,輸入數據源,得到原始數據集、頻繁1項集void init(string fileName); /連接頻繁k項集、并且直接剪枝，得到頻繁k+1項集，加入到容器item_listvoid即ri_gen();連接頻繁k項集、并且直接剪枝，得到頻繁k+1項集，加入到頻繁項集集合frequentvec中float calculateSup(vector<string> judge_item); /求候選項的支持度vector<string> mergeItem(vector<string> vect1,vector<string> vect2,int

7、round); /判斷兩個項是否可以合并成一個新的項集做為新的候選項,能則合并,不能的返回空容器void showItem();/ 輸出頻繁項集private:vector<set<string>> datavec;/ 原始數據集int trancount;/ 原始數據項數量vector<vector<pair<vector<string>,float>>> frequentvec; /頻繁項集的集合double minsup; / 設置最小支持度和最小置信度double minconf; / 設置最小支持度和最小置信度;

8、運行結果： 效果對比： 數據集大?。?9835 數據元素多少： 170 置信度： 0.05 原始：頻繁 1 項集 28候選2項集2A28頻繁 2項集 3 改進后：頻繁 1 項集 28 頻繁 2項集 3算法的改進 2 第一次掃描數據庫時,對于數據庫中的數據,利用各項元素的數字編號來替換各數據元素的名稱；即將數據元素的 名稱字符傳用數字來替換,從而減少在求各候選項的支持度時的資源消耗；代碼中的改進之處,string 類型的元素轉為對應的 int 代號：儲存頻繁項集的容器由 vector<vector<pair<vector<string>,float>>&

9、gt;變?yōu)?vector<vector<pair<vector<int>,float>>>；然后對代碼進行相應的調整,使得代碼正常運行；代碼的描述：class Aprioripublic:void init(string fileName); /初始化,輸入數據源,得到原始數據集、頻繁 1項集void apri_gen();連接頻繁k項集、并且直接剪枝，得到頻繁k+1項集，加入到頻繁項集集合frequentvec中float calculateSup(vector<int> judge_item); /求候選項的支持度vector&l

10、t;int> mergeItem(vector<int> vect1,vector<int> vect2,int round); /判斷兩個項是否可以合并成一個新的項集做為新的候選項，能則合并，不能的返回空容器void showItem();/輸出頻繁項集private: vector<set<int>> dataNumVec;/ 原始數據集轉換出來的、數據項用代號來表示的數據 map<string,int> reflection; /原始數據中各個不同的元素的代號映射 , 數據元素從 1開始編號int trancount; /

11、 原始數據項數量 vector<vector<pair<vector<int>,float>>> frequentvec; /頻繁項集集合，儲存各項以及其支持度double minsup; / 設置最小支持度和最小置信度 ;運行結果：效果對比：改進后 14.496 ；14.549 ； 14.577改進前 20.165 ；20.463 ； 20.383 效率提升 28.1%附：改進1的代碼(改進2與改進1代碼幾乎相同，不同之處在于儲存頻繁項的數據類型，代碼略)#in elude <iostream>#in elude <fstre

12、am>#in elude <stri ng>#in elude <veetor>#in elude <map>#in elude <emath>#i nclude <algorithm>#i nclude <ioma nip>#in elude <set>#in elude <utility>#in elude <time.h>using n amespaee std;/*最大數據集數量，置信度閾值，*/elass Aprioripublie:/初始化，輸入數據源，得到原始數據集、

13、頻繁1項集void init(string fileName);/連接頻繁k項集、并且直接剪枝，得到頻繁k+1項集，加入到容器item_listvoid apri_ge n();/判斷候選項，是否為頻繁項float ealeulateSup(veetor<stri ng> judge_item);veetor<stri ng> mergeItem(veetor<stri ng> vect1,vector<stri ng> vect2,i nt roun d);/判斷兩個項集是否可以合并(要求只有一項不同)成一個新的項集(做為候選集)void sh

14、owltem();private:veetor<set<string>> datavee;/ 原始數據集int trancount;/原始數據項數量veetor<veetor<pair<veetor<string>,float>>> frequentvec; /頻繁項集 de集合double min sup; /設置最小支持度和最小置信度double minconf; /設置最小支持度和最小置信度;void Apriori:init(string fileName)std:cout<<"調用 init

15、"<<endl;min sup = 0.05;minconf = 0.5;trancoun t=0;ifstream file(fileName); /打開數據文件if(!file) /檢查文件是否打開成功std:cout<<"Fail to ope n data file!"<<e ndl;elsestri ng temp;set<string> item; /項集的臨時 setint beg in,end;while(getli ne(file,temp) /一行一行讀入數據trancoun t+;begi n=

16、0;temp.erase(O,temp.fi nd_first_ no t_of("rtn "); / temp.erase(temp.fi nd_last_ no t_of("rt n")+1);/去除字符串首部的空格去除字符串尾部的空格while(e nd=temp.fi nd(',',begi n)!=stri ng: npos) /符的每一個事務中的項是以空格為分隔item.i nsert(temp.substr(begi n,en d-begi n); /將每一個項插入item中beg in=en d+1; item.i nse

17、rt(temp.substr(begi n);/datavec.push_back(item); /vector 中一個事務中的最后一項將一個事務中的所有項當成一個整體插入另一個大的item.clear(); /清空 itemcout<<temp<<e ndl;/統(tǒng)計各個項集的數目mapvstri ng,i nt> items_co unt;for(vector<set<stri ng> >:size_type ix= 0 ;ix !=datavec.size(); +ix)for(set<stri ng>:iterator i

18、y=datavecix.begi n( );iy!=datavecix.e nd();+iy) if (items_co un t.fi nd(*iy) = items_co un t.e nd()items_cou nt*iy=1; elseitems_cou nt*iy+; /該項集的計數加 1vector <stri ng> elem;vector<pair<vector<stri ng>,float>> can didatevec; /候選項集for (mapvstring,int>:iterator ix = items_coun

19、t.begin(); ix != items_count.end(); ix+ ) if ( (float(ix->sec on d)/tra ncount >= min sup)/判斷候選頻繁1項集中的各項，是否大于最小頻繁度，如果是，則為頻繁項集；elem.push_back(ix->first);can didatevec.push_back(make_pair(elem,(float(ix->sec on d)/tra ncoun t); elem.clear();/ 一定要清空if (!ca ndidatevec.empty()frequentvec.push

20、_back(candidatevec);/將得到的頻繁1項集加入頻繁項集集合中candidatevec.clear();/ 一定要清空/判斷兩個項集是否可以合并(要求只有一項不同)成一個新的項集(做為候選集)vector<stri ng> Apriori:mergeltem(vector<stri ng> vect1,vector<stri ng> vect2,i nt round)cout<<"調用 mergeItem"<<endl;/剪枝工作 /int count=O;/統(tǒng)計兩個vector中相同的項的數目ve

21、ctor<stri ng> vect;mapvstring,int> tempMap; / 輔助判斷兩個 vector中重復的項for(vector<stri ng>:size_type st=0;st<vect1.size();st+)tempMapvect1st+; vect.push_back(vect1st);for(vector<stri ng>:size_type st=0;st<vect2.size();st+)tempMapvect2st+;if(tempMapvect2st=2) /表示這兩項相同coun t+;elsev

22、ect.push_back(vect2st);if(cou nt+1)!=rou nd)/要求兩個項目集只有一個項目不相同，其他都相同vect.clear();sort(vect.beg in(), vect.e nd();return vect;/判斷一個項，是否為頻繁項float Apriori:calculateSup(vector<stri ng> judgeVect)cout<<"調用 judge"<<e ndl;int count = 0;vector<string>:iterator iter;vector<

23、;stri ng>:iterator iterBegi n = judgeVect.begi n();vector<stri ng>:iterator iterE nd = judgeVect.e nd();for (vector<set<stri ng»:size_type st=0; st != datavec.size(); st+ )iter = iterBegi n;for (; iter != iterE nd; iter +)if (datavecst.fi nd(*iter) = datavecst.e nd()break;if (ite

24、r = iterE nd)coun t+;float freque nt = (float)co unt/trancount;retur n freque nt;void Apriori:apri_ge n()/std:cout<<" 調用 apri_gen"<<endl;int round = 1;vector<vector<vector<stri ng>»:size_type st = 0;vector<pair<vector<stri ng>,float>> tempVec;

25、vector<stri ng> tempitem;float fre = 0.0;while (st != freque ntvec.size() /循環(huán)在達到頻繁項集集合的末尾結束int i=0;if (frequentvecround-1.size() <2) /當前輪次的頻繁round項集中想的個數小于 2時，算法結束return;vector<vector<stri ng»:size_type ix , iy;for (ix = 0; ix != freque ntvecro un d-1.size(); ix+)for (iy = ix + 1

26、; iy != freque ntvecr oun d-1.size(); iy+)tempitem =mergeitem(freque ntvecr oun d-1.at(ix).first,freque ntvecr oun d-1.at(iy).first,ro un d);if (!tempitem.empty()fre = calculateSup(tempitem);if (fre >= min sup)tempVec.push back(make pair(templtem,fre);if (!tempVec.empty()/ 如果生成的頻繁 round+1 項集frequ

27、e ntvec.push_back(tempVec);templtem.clear();tempVec.clear();roun d+;st+;elsereturn;void Apriori:showltem()std:cout << " 支持度"<< min sup << " 置信度"<< minconf << en dl;for (vector<vector<pair<vector<stri ng>,float>»:size_type st1 =

28、 0; st1 != freque ntvec.size();st1+)std:cout << " 頻繁"<< st1+1 << " 項集："<< endl;for (vector<pair<vector<string>,float»:size_typest2 =0; st2 != frequentvecst1.size();st2+)for (vector<string>:size_type st3 = 0; st3 != frequentvecst1.at(

29、st2).first.size();st3+)std:cout << freque ntvecst1.at(st2).firstst3<<":"<<freque ntvecst1.at(st2).seco nd<<","std:cout << en dl;int mai n()time_t startTime,e ndTime;startTime= clock();stri ng in file name = "D:test.txt"Apriori calculati on;

30、calculati on .i nit(i nfile name);calculati on .apri_ge n();calculati on. showItem();en dTime=clock();cout << " 程序用時"<< (double)(endTime - startTime)/CLOCKS_PER_SEC << "s" <<endl; system("pause");return 0;附：改進2代碼#in elude <iostream> #in elu

31、de <fstream> #in elude <stri ng> #in elude <veetor> #in elude <map>#in elude <emath>#in elude <bitset>#i nclude <algorithm> #i nclude <ioma nip> #in elude <set> #in elude <utility> #in elude <time.h> using n amespaee std;/*最大數據集數量，置信度

32、閾值，*/ elass Aprioripublie:/初始化，輸入數據源，得到原始數據集、頻繁1項集void init(string fileName);/連接頻繁k項集、并且直接剪枝，得到頻繁 k+1項集，加入到容器item_list void apri_ge n();/判斷候選項，是否為頻繁項float calculateSup(vector <int> judge_item);vector<int>mergeltem(vect or<int>veet1,veetor <int>veet2,i ntroun d);/void showltem

33、();private:veetor<set< in t>> dataNumVee; 據map<stri ng,i nt> reflect ion;從1開始編號int trancount;判斷兩個項集是否可以合并(要求只有一項不同)成一個新的項集(做為候選集)/原始數據集轉換出來的、數據項用代號來表示的數/原始數據中各個不同的元素的代號映射，數據元素頻繁項集de集合/原始數據項數量veetor<veetor<pair<veet or<in t>,float>>> freque ntvec; / double mi

34、n sup; /設置最小支持度和最小置信度double minconf; /設置最小支持度和最小置信度;void Apriori:init(string fileName)std:cout<<"調用 init"<<endl;min sup = 0.05;minconf = 0.5;trancoun t=0;int elemNumber = 1; /用于元素代號的設定ifstream file(fileName); /打開數據文件if(!file) /檢查文件是否打開成功std:cout<<"Fail to ope n data

35、file!"<<e ndl;elsestri ng temp;string temp2;set<int> numItem;/項目集的臨時代號setint beg in,end;while(getli ne(file,temp) /一行一行讀入數據trancoun t+;去除字符串首部的空格 去除字符串尾部的每一個事務中的項是以/如begi n=0;temp.erase(0,temp.fi nd_first_ no t_of("rtn "); / temp.erase(temp.fi nd_last_ no t_of("rt n&q

36、uot;)+1);/空格while(e nd=temp.fi nd(',',begi n)!=stri ng: npos) /逗號為分隔符的temp2 =temp.substr(beg in,en d-begi n);if (reflectio n.fin d(temp2) = reflectio n.e nd() 果這個元素是第一次出現，則加入到映射map中去reflection temp2 = elemNumber+;nu mltem.i nsert(reflectio ntemp2);beg in=en d+1; temp2 = temp.substr(begi n);i

37、f (reflection.find(temp2) = reflection.end()/ 女口果這個元素是第一次出現，則加入到映射map中去reflect ion temp2 = elemNumber+;nu mltem.i nsert(reflectio ntemp2);dataNumVec.push_back(numltem);/將一個事務中的所有項當成一個整體插入另一個大的 vector中numltem.clear();/ 清空 numltemcout<<temp<<e ndl;map<int,int> items_count;/統(tǒng)計各個項集的數目f

38、or(vector<set< int> >:size_type ix= 0 ;ix !=dataNumVec.size(); +ix) for(set<i nt>:iteratoriy=dataNumVecix.begi n( );iy!=dataNumVecix.e nd();+iy)if (items_co un t.fi nd(*iy) = items_co un t.e nd()items_co un t*iy=1;elseitems_cou nt*iy+; /該項集的計數加 1vector <int> elem; vector<p

39、air<vect or<in t>,float>> can didatevec; /候選項集for (map<int,int>:iterator ix = items_count.begin(); ix != items_count.end();ix+ )if ( (float(ix->seco nd)/tra ncou nt >= min sup)/ 判斷候選頻繁 1 項集中的各項，是否大于最小頻繁度，如果是，則為頻繁項集；elem.push_back(ix->first);can didatevec.push_back(make_

40、pair(elem,(float(ix->sec on d)/tra ncoun t); elem.clear();/ 一定要清空if (!ca ndidatevec.empty()frequentvec.push_back(candidatevec);/將得到的頻繁1項集加入頻繁項集集合中candidatevec.clear();/ 一定要清空/判斷兩個項集是否可以合并(要求只有一項不同)成一個新的項集(做為候選集)vector <int> Apriori:mergeltem(vect or<int> vect1,vect or<int> vect2

41、,i nt round)/cout<<"調用 mergeItem"<<endl;/剪枝工作 /int count=O;/統(tǒng)計兩個vector中相同的項的數目vector<i nt> vect;map<int,int> tempMap; / 輔助判斷兩個vector中重復的項 for(vector<in t>:size_type st=0;st<vect1.size();st+)tempMapvect1st+; vect.push_back(vect1st);for(vector<in t>:siz

42、e_type st=0;st<vect2.size();st+)tempMapvect2st+;if(tempMapvect2st=2) /表示這兩項相同coun t+;elsevect.push_back(vect2st);if(cou nt+1)!=rou nd)/要求兩個項目集只有一個項目不相同，其他都相同vect.clear();sort(vect.beg in(), vect.e nd();return vect;/判斷一個項，是否為頻繁項float Apriori:calculateSup(vect or<int> judgeVect)cout<<&q

43、uot;調用 judge"<<e ndl;int count = 0;vector<in t>:iterator iter;vector<in t>:iterator iterBegi n = judgeVect.beg in();vector<in t>:iterator iterE nd = judgeVect.e nd();for (vector<set< in t>>:size_type st=0; st != dataNumVec.size(); st+ )iter = iterBegi n;for (

44、; iter != iterE nd; iter +)if (dataNumVecst.fi nd(*iter) = dataNumVecst.e nd()break;if (iter = iterE nd)coun t+;float freque nt = (float)co unt/trancount;retur n freque nt;void Apriori:apri_ge n()std:cout<<"調用 apri gen"<<endl;int round = 1;vector<vector<pair<vect or<

45、;in t>,float>»:size_type st = 0;vector<pair<vect or<in t>,float>> tempVec;vector<int> tempItem;float fre = 0.0;while (st != freque ntvec.size() /循環(huán)在達到頻繁項集集合的末尾結束int i=0;if (frequentvecround-1.size() <2) /當前輪次的頻繁round項集中想的個數小于 2時，算法結束return;vector<pair<vect or<in t>,float>>:size_type ix , iy;for (ix =