數(shù)據(jù)挖掘Apriori算法C++實現(xiàn)

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

2、ori_gen(Lk-1 ,min_sup); / 調(diào)用apriori_gen方法生成候選頻繁k-項集（4）for each transaction t D / 掃描事務(wù)數(shù)據(jù)庫D（5）Ct = subset(Ck,t);（6）for each candidate c Ct（7）c.count+; / 統(tǒng)計候選頻繁k-項集的計數(shù)（8）（9）Lk =c Ck|c.countmin_sup / 滿足最小支持度的k-項集即為頻繁k-項集（10） （11） return L= k Lk; / 合并頻繁k-項集（k0）2、算法流程 首先單趟掃描數(shù)據(jù)集，計算各個一項集的支持度，根據(jù)給定的最小支持度閔值，得到

3、一項頻繁集L1。 然后通過連接運算，得到二項候選集，對每個候選集再次掃描數(shù)據(jù)集，得出每個候選集的支持度，再與最小支持度比較。得到二項頻繁集L2。 如此進行下去，直到不能連接產(chǎn)生新的候選集為止。 對于找到的所有頻繁集，用規(guī)則提取算法進行關(guān)聯(lián)規(guī)則的提取。3、算法的不足：（ ）數(shù)據(jù)庫重復(fù)掃描的次數(shù)太多。在由 尋找 的過程中， 中的每一項都需要掃描事務(wù)數(shù)據(jù)庫進行驗證，以決定其是否加入 ，存在的頻繁 項集越大，重復(fù)掃描的次數(shù)就越多。這一過程耗時太大，增加了系統(tǒng) 開銷，處理效率低 ，不利于實際應(yīng)用。（ ）產(chǎn)生的候選集可能過于龐大。如果一個頻繁 項集包含個項，那么頻繁 項集就有 個，為找到元素個數(shù)為的頻繁項

4、集，如 ， ， ，那么就要掃描數(shù)據(jù)庫次，產(chǎn)生的候選項集總個數(shù)為：舉例：對于一個這樣龐大的項集，計算機難以存儲和計算，挖掘效率低下。二、算法的改進11、改進方法：性質(zhì)：頻繁項集的所有非空子集都必須是頻繁的。（ 性質(zhì)，記為性質(zhì) ）性質(zhì)：若頻繁 項集 中各個項可以做鏈接產(chǎn)生 ，則 中每個元素在 中出現(xiàn)的次數(shù)應(yīng)大于或等于 ，若小于 ，則刪除該項在 中所有的事務(wù)集 。（性質(zhì)的推論，記為性質(zhì) ）改進的方法：在連接之后得到的候選頻繁k項，直接進行最小支持度判斷，并進行剪枝，從而直接得到頻繁k項集，避免候選項集可能過大的問題；2、算法的流程 首先單趟掃描數(shù)據(jù)集，計算各個一項集的支持度，根據(jù)給定的最小支持度閾值

5、，得到一項頻繁集L1。 然后通過連接運算，對于每個連接的到項直接進行最小支持度判斷，如果大于最小支持度的加入頻繁二項集，如果小于則舍棄，循環(huán)直到連接完畢；得到二項頻繁集L2。 如此進行下去，直到不能連接產(chǎn)生新的頻繁項集為止。3、代碼實現(xiàn)的描述（詳細描述文末附上）：使用C+，構(gòu)造了一個Apriori類：class Aprioripublic:/初始化，輸入數(shù)據(jù)源，得到原始數(shù)據(jù)集、頻繁1項集void init(string fileName);/連接頻繁k項集、并且直接剪枝，得到頻繁k+1項集，加入到容器item_listvoid apri_gen();/連接頻繁k項集、并且直接剪枝，得到頻繁k+

6、1項集，加入到頻繁項集集合frequentvec中float calculateSup(vector judge_item); /求候選項的支持度vector mergeItem(vector vect1,vector vect2,int round); /判斷兩個項是否可以合并成一個新的項集做為新的候選項，能則合并，不能的返回空容器void showItem();/輸出頻繁項集private:vectorset datavec;/原始數(shù)據(jù)集int trancount;/原始數(shù)據(jù)項數(shù)量vectorvectorpairvector,float frequentvec; /頻繁項集的集合doubl

7、e minsup; /設(shè)置最小支持度和最小置信度double minconf; /設(shè)置最小支持度和最小置信度;運行結(jié)果：效果對比：數(shù)據(jù)集大?。?835數(shù)據(jù)元素多少：170置信度：0.05原始：頻繁1項集28候選2項集228頻繁2項集3改進后：頻繁1項集28頻繁2項集3算法的改進2第一次掃描數(shù)據(jù)庫時，對于數(shù)據(jù)庫中的數(shù)據(jù)，利用各項元素的數(shù)字編號來替換各數(shù)據(jù)元素的名稱；即將數(shù)據(jù)元素的名稱字符傳用數(shù)字來替換，從而減少在求各候選項的支持度時的資源消耗；代碼中的改進之處，string類型的元素轉(zhuǎn)為對應(yīng)的int代號：儲存頻繁項集的容器由vectorvectorpairvector,float變?yōu)関ector

8、vectorpairvector,float；然后對代碼進行相應(yīng)的調(diào)整，使得代碼正常運行；代碼的描述：class Aprioripublic:void init(string fileName); /初始化，輸入數(shù)據(jù)源，得到原始數(shù)據(jù)集、頻繁1項集void apri_gen();/連接頻繁k項集、并且直接剪枝，得到頻繁k+1項集，加入到頻繁項集集合frequentvec中float calculateSup(vector judge_item); /求候選項的支持度vector mergeItem(vector vect1,vector vect2,int round); /判斷兩個項是否可以合

9、并成一個新的項集做為新的候選項，能則合并，不能的返回空容器 void showItem();/輸出頻繁項集private:vectorset dataNumVec;/原始數(shù)據(jù)集轉(zhuǎn)換出來的、數(shù)據(jù)項用代號來表示的數(shù)據(jù)map reflection;/原始數(shù)據(jù)中各個不同的元素的代號映射,數(shù)據(jù)元素從1開始編號int trancount;/原始數(shù)據(jù)項數(shù)量vectorvectorpairvector,float frequentvec; /頻繁項集集合，儲存各項以及其支持度double minsup; /設(shè)置最小支持度和最小置信度;運行結(jié)果：效果對比：改進后14.496；14.549；14.577改進前20

10、.165；20.463；20.383效率提升28.1%附：改進1的代碼（改進2與改進1代碼幾乎相同，不同之處在于儲存頻繁項的數(shù)據(jù)類型，代碼略）#include #include #include #include #include #include #include #include #include #include #include using namespace std;/*最大數(shù)據(jù)集數(shù)量，置信度閾值，*/class Aprioripublic:/初始化，輸入數(shù)據(jù)源，得到原始數(shù)據(jù)集、頻繁1項集void init(string fileName);/連接頻繁k項集、并且直接剪枝，得到頻繁k

11、+1項集，加入到容器item_listvoid apri_gen();/判斷候選項，是否為頻繁項float calculateSup(vector judge_item);vector mergeItem(vector vect1,vector vect2,int round); /判斷兩個項集是否可以合并(要求只有一項不同)成一個新的項集（做為候選集）void showItem();private:vectorset datavec;/原始數(shù)據(jù)集int trancount;/原始數(shù)據(jù)項數(shù)量vectorvectorpairvector,float frequentvec; /頻繁項集de集合d

12、ouble minsup; /設(shè)置最小支持度和最小置信度double minconf; /設(shè)置最小支持度和最小置信度;void Apriori:init(string fileName)/std:cout調(diào)用initendl;minsup = 0.05;minconf = 0.5; trancount=0;ifstream file(fileName); /打開數(shù)據(jù)文件if(!file) /檢查文件是否打開成功std:coutFail to open data file!endl;elsestring temp;set item; /項集的臨時set int begin,end;while(g

13、etline(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(,begin)!=string:npos) /每一個事務(wù)中的項是以空格為分隔符的item.insert(temp.substr(begin,end-begin); /將每一個項插入item中begin=end+1;item.insert(temp.sub

14、str(begin); /一個事務(wù)中的最后一項datavec.push_back(item); /將一個事務(wù)中的所有項當(dāng)成一個整體插入另一個大的vector中item.clear(); /清空item/couttempendl;map items_count;/統(tǒng)計各個項集的數(shù)目for(vectorset :size_type ix= 0 ;ix !=datavec.size(); +ix)for(set:iterator iy=datavecix.begin();iy!=datavecix.end();+iy)if (items_count.find(*iy) = items_count.e

15、nd()items_count*iy=1;elseitems_count*iy+; /該項集的計數(shù)加1vector elem;vectorpairvector,float candidatevec; /候選項集for (map:iterator ix = items_count.begin(); ix != items_count.end(); ix+ )if ( (float(ix-second)/trancount = minsup)/判斷候選頻繁1項集中的各項，是否大于最小頻繁度，如果是，則為頻繁項集；elem.push_back(ix-first);candidatevec.push_

16、back(make_pair(elem,(float(ix-second)/trancount);elem.clear();/一定要清空if (!candidatevec.empty()frequentvec.push_back(candidatevec);/將得到的頻繁1項集加入頻繁項集集合中candidatevec.clear();/一定要清空/判斷兩個項集是否可以合并(要求只有一項不同)成一個新的項集（做為候選集）vector Apriori:mergeItem(vector vect1,vector vect2,int round) /cout調(diào)用mergeItemendl;/剪枝工作

17、/int count=0; /統(tǒng)計兩個vector中相同的項的數(shù)目vector vect;map tempMap; /輔助判斷兩個vector中重復(fù)的項for(vector:size_type st=0;stvect1.size();st+)tempMapvect1st+;vect.push_back(vect1st);for(vector:size_type st=0;stvect2.size();st+)tempMapvect2st+;if(tempMapvect2st=2) /表示這兩項相同count+;elsevect.push_back(vect2st);if(count+1)!=r

18、ound) /要求兩個項目集只有一個項目不相同，其他都相同vect.clear();sort(vect.begin(),vect.end();return vect;/判斷一個項，是否為頻繁項float Apriori:calculateSup(vector judgeVect)/cout調(diào)用judgeendl;int count = 0;vector:iterator iter;vector:iterator iterBegin = judgeVect.begin();vector:iterator iterEnd = judgeVect.end();for (vectorset:size_

19、type st=0; st != datavec.size(); st+ )iter = iterBegin;for (; iter != iterEnd; iter +)if (datavecst.find(*iter) = datavecst.end()break;if (iter = iterEnd)count+;float frequent = (float)count/trancount;return frequent;void Apriori:apri_gen()/std:cout調(diào)用apri_genendl;int round = 1;vectorvectorvector:siz

20、e_type st = 0;vectorpairvector,float tempVec;vector tempItem;float fre = 0.0;while (st != frequentvec.size() /循環(huán)在達到頻繁項集集合的末尾結(jié)束int i=0;if (frequentvecround-1.size() 2)/當(dāng)前輪次的頻繁round項集中想的個數(shù)小于2時，算法結(jié)束return;vectorvector:size_type ix , iy;for (ix = 0; ix != frequentvecround-1.size(); ix+)for (iy = ix + 1;

21、 iy != frequentvecround-1.size(); iy+)tempItem = mergeItem(frequentvecround-1.at(ix).first,frequentvecround-1.at(iy).first,round);if (!tempItem.empty()fre = calculateSup(tempItem);if (fre = minsup)tempVec.push_back(make_pair(tempItem,fre);if (!tempVec.empty()/如果生成的頻繁round+1項集frequentvec.push_back(te

22、mpVec);tempItem.clear();tempVec.clear();round+;st+;elsereturn;void Apriori:showItem()std:cout 支持度 minsup 置信度 minconf endl;for (vectorvectorpairvector,float:size_type st1 = 0; st1 != frequentvec.size(); st1+)std:cout 頻繁 st1+1 項集： endl;for (vectorpairvector,float:size_type st2 =0; st2 != frequentvecst

23、1.size(); st2+)for (vector:size_type st3 = 0; st3 != frequentvecst1.at(st2).first.size(); st3+)std:cout frequentvecst1.at(st2).firstst3: frequentvecst1.at(st2).second, ;std:cout endl;int main()time_t startTime,endTime;startTime= clock();string infilename = D:test.txt;Apriori calculation;calculation.

24、init(infilename);calculation.apri_gen();calculation.showItem();endTime=clock();cout 程序用時 (double)(endTime - startTime)/CLOCKS_PER_SEC s endl;system(pause);return 0;附：改進2代碼#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;/

25、*最大數(shù)據(jù)集數(shù)量，置信度閾值，*/class Aprioripublic:/初始化，輸入數(shù)據(jù)源，得到原始數(shù)據(jù)集、頻繁1項集void init(string fileName);/連接頻繁k項集、并且直接剪枝，得到頻繁k+1項集，加入到容器item_listvoid apri_gen();/判斷候選項，是否為頻繁項float calculateSup(vector judge_item);vector mergeItem(vector vect1,vector vect2,int round); /判斷兩個項集是否可以合并(要求只有一項不同)成一個新的項集（做為候選集）void showItem

26、();private:vectorset dataNumVec;/原始數(shù)據(jù)集轉(zhuǎn)換出來的、數(shù)據(jù)項用代號來表示的數(shù)據(jù)map reflection;/原始數(shù)據(jù)中各個不同的元素的代號映射,數(shù)據(jù)元素從1開始編號int trancount;/原始數(shù)據(jù)項數(shù)量vectorvectorpairvector,float frequentvec; /頻繁項集de集合double minsup; /設(shè)置最小支持度和最小置信度double minconf; /設(shè)置最小支持度和最小置信度;void Apriori:init(string fileName)/std:cout調(diào)用initendl;minsup = 0.05

27、;minconf = 0.5; trancount=0;int elemNumber = 1;/用于元素代號的設(shè)定ifstream file(fileName); /打開數(shù)據(jù)文件if(!file) /檢查文件是否打開成功std:coutFail to open data file!endl;elsestring temp;string temp2;set numItem;/項目集的臨時代號setint begin,end;while(getline(file,temp) /一行一行讀入數(shù)據(jù)trancount+;begin=0;temp.erase(0,temp.find_first_not_o

28、f(rtn ); /去除字符串首部的空格temp.erase(temp.find_last_not_of(rtn)+1); /去除字符串尾部的空格while(end=temp.find(,begin)!=string:npos) /每一個事務(wù)中的項是以逗號為分隔符的temp2 =temp.substr(begin,end-begin);if (reflection.find(temp2) = reflection.end()/如果這個元素是第一次出現(xiàn)，則加入到映射map中去reflectiontemp2 = elemNumber+;numItem.insert(reflectiontemp2)

29、;begin=end+1;temp2 = temp.substr(begin);if (reflection.find(temp2) = reflection.end()/如果這個元素是第一次出現(xiàn)，則加入到映射map中去reflectiontemp2 = elemNumber+;numItem.insert(reflectiontemp2);dataNumVec.push_back(numItem);/將一個事務(wù)中的所有項當(dāng)成一個整體插入另一個大的vector中numItem.clear();/清空numItem/couttempendl;map items_count;/統(tǒng)計各個項集的數(shù)目f

30、or(vectorset :size_type ix= 0 ;ix !=dataNumVec.size(); +ix)for(set:iterator iy=dataNumVecix.begin();iy!=dataNumVecix.end();+iy)if (items_count.find(*iy) = items_count.end()items_count*iy=1;elseitems_count*iy+; /該項集的計數(shù)加1vector elem;vectorpairvector,float candidatevec; /候選項集for (map:iterator ix = item

31、s_count.begin(); ix != items_count.end(); ix+ )if ( (float(ix-second)/trancount = minsup)/判斷候選頻繁1項集中的各項，是否大于最小頻繁度，如果是，則為頻繁項集；elem.push_back(ix-first);candidatevec.push_back(make_pair(elem,(float(ix-second)/trancount);elem.clear();/一定要清空if (!candidatevec.empty()frequentvec.push_back(candidatevec);/將得

32、到的頻繁1項集加入頻繁項集集合中candidatevec.clear();/一定要清空/判斷兩個項集是否可以合并(要求只有一項不同)成一個新的項集（做為候選集）vector Apriori:mergeItem(vector vect1,vector vect2,int round) /cout調(diào)用mergeItemendl;/剪枝工作/int count=0; /統(tǒng)計兩個vector中相同的項的數(shù)目vector vect;map tempMap; /輔助判斷兩個vector中重復(fù)的項for(vector:size_type st=0;stvect1.size();st+)tempMapvect

33、1st+;vect.push_back(vect1st);for(vector:size_type st=0;stvect2.size();st+)tempMapvect2st+;if(tempMapvect2st=2) /表示這兩項相同count+;elsevect.push_back(vect2st);if(count+1)!=round) /要求兩個項目集只有一個項目不相同，其他都相同vect.clear();sort(vect.begin(),vect.end();return vect;/判斷一個項，是否為頻繁項float Apriori:calculateSup(vector ju

34、dgeVect)/cout調(diào)用judgeendl;int count = 0;vector:iterator iter;vector:iterator iterBegin = judgeVect.begin();vector:iterator iterEnd = judgeVect.end();for (vectorset:size_type st=0; st != dataNumVec.size(); st+ )iter = iterBegin;for (; iter != iterEnd; iter +)if (dataNumVecst.find(*iter) = dataNumVecst

35、.end()break;if (iter = iterEnd)count+;float frequent = (float)count/trancount;return frequent;void Apriori:apri_gen()/std:cout調(diào)用apri_genendl;int round = 1;vectorvectorpairvector,float:size_type st = 0;vectorpairvector,float tempVec;vector tempItem;float fre = 0.0;while (st != frequentvec.size() /循環(huán)在達到頻繁項集集合的末尾結(jié)束int i=0;if (frequentvecround-1.size() 2)/當(dāng)前輪次的頻繁round項集中想的個數(shù)小于2時，算法結(jié)束return;vectorpairvector,fl