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

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

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

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

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

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

6、_gen();/連接頻繁 k項(xiàng)集、并且直接剪枝，得到頻繁k+1項(xiàng)集，加入到頻繁項(xiàng)集集合frequentvecfloat calculateSup(vector<string> judge_item); /求候選項(xiàng)的支持度vector<string> mergeItem(vector<string> vect1,vector<string> vect2,int round); /判斷兩個(gè)項(xiàng)是否中可以合并成一個(gè)新的項(xiàng)集做為新的候選項(xiàng)，能則合并，不能的返回空容器void showItem();/輸出頻繁項(xiàng)集private:vector<set&l

7、t;string>> datavec; int trancount;/ 原始數(shù)據(jù)集/ 原始數(shù)據(jù)項(xiàng)數(shù)量vector<vector<pair<vector<string>,float>>> frequentvec;/頻繁項(xiàng)集的集合double minsup; double minconf;/設(shè)置最小支持度和最小置信度設(shè)置最小支持度和最小置信度;運(yùn)行結(jié)果：效果對(duì)比：數(shù)據(jù)集大?。?9835數(shù)據(jù)元素多少：170置信度： 0.05原始：頻繁 1項(xiàng)集 28候選 2項(xiàng)集 228頻繁 2項(xiàng)集 3改進(jìn)后：頻繁 1項(xiàng)集 28頻繁 2項(xiàng)集 3算法的改進(jìn) 2第

8、一次掃描數(shù)據(jù)庫(kù)時(shí)，對(duì)于數(shù)據(jù)庫(kù)中的數(shù)據(jù)，利用各項(xiàng)元素的數(shù)字編號(hào)來(lái)替換各數(shù)據(jù)元素的名稱(chēng)；即將數(shù)據(jù)元素的名稱(chēng)字符傳用數(shù)字來(lái)替換，從而減少在求各候選項(xiàng)的支持度時(shí)的資源消耗；代碼中的改進(jìn)之處，string類(lèi)型的元素轉(zhuǎn)為對(duì)應(yīng)的int 代號(hào)：儲(chǔ)存頻繁項(xiàng)集的容器由vector<vector<pair<vector<string>,float>>>為 vector<vector<pair<vector<int>,float>>>；然后對(duì)代碼進(jìn)行相應(yīng)的調(diào)整，使得代碼正常運(yùn)行；變代碼的描述：class Aprioripu

9、blic:void init(string fileName); /初始化，輸入數(shù)據(jù)源，得到原始數(shù)據(jù)集、頻繁1項(xiàng)集void apri_gen();/連接頻繁 k項(xiàng)集、并且直接剪枝，得到頻繁k+1項(xiàng)集，加入到頻繁項(xiàng)集集合float calculateSup(vector<int> judge_item); /求候選項(xiàng)的支持度f(wàn)requentvec中vector<int> mergeItem(vector<int> vect1,vector<int> vect2,int round); /判斷兩個(gè)項(xiàng)是否可以合并成一個(gè)新的項(xiàng)集做為新的候選項(xiàng)，能則合并，

10、不能的返回空容器void showItem();/輸出頻繁項(xiàng)集private:vector<set<int>> dataNumVec;/ map<string,int> reflection; /原始數(shù)據(jù)集轉(zhuǎn)換出來(lái)的、數(shù)據(jù)項(xiàng)用代號(hào)來(lái)表示的數(shù)據(jù)原始數(shù)據(jù)中各個(gè)不同的元素的代號(hào)映射, 數(shù)據(jù)元素從1開(kāi)始編號(hào)int trancount;/ 原始數(shù)據(jù)項(xiàng)數(shù)量vector<vector<pair<vector<int>,float>>> frequentvec;/頻繁項(xiàng)集集合，儲(chǔ)存各項(xiàng)以及其支持度double minsup;

11、/設(shè)置最小支持度和最小置信度;運(yùn)行結(jié)果：效果對(duì)比：改進(jìn)后 14.496 ； 14.549 ； 14.577改進(jìn)前 20.165 ； 20.463 ； 20.383效率提升 28.1%附：改進(jìn) 1的代碼（改進(jìn) 2與改進(jìn) 1代碼幾乎相同，不同之處在于儲(chǔ)存頻繁項(xiàng)的數(shù)據(jù)類(lèi)型，代碼略）#include <iostream>#include <fstream>#include <string>#include <vector>#include <map>#include <cmath>#include <algorithm>

12、;#include <iomanip>#include <set>#include <utility>#include <time.h>using namespace std;/* 最大數(shù)據(jù)集數(shù)量，置信度閾值，*/class Aprioripublic:/ 初始化，輸入數(shù)據(jù)源，得到原始數(shù)據(jù)集、頻繁1項(xiàng)集void init(string fileName);/ 連接頻繁 k項(xiàng)集、并且直接剪枝，得到頻繁 k+1項(xiàng)集，加入到容器 item_listvoid apri_gen();/ 判斷候選項(xiàng)，是否為頻繁項(xiàng)float calculateSup(vect

13、or<string> judge_item);vector<string> mergeItem(vector<string> vect1,vector<string> vect2,int round);/判斷兩個(gè)項(xiàng)集是否可以合并( 要求只有一項(xiàng)不同) 成一個(gè)新的項(xiàng)集（做為候選集）void showItem();private:vector<set<string>> datavec;/ 原始數(shù)據(jù)集int trancount;/ 原始數(shù)據(jù)項(xiàng)數(shù)量vector<vector<pair<vector<stri

14、ng>,float>>> frequentvec;/頻繁項(xiàng)集de集合double minsup; / double minconf; /設(shè)置最小支持度和最小置信度設(shè)置最小支持度和最小置信度;void Apriori:init(string fileName)/std:cout<<"調(diào)用 init"<<endl;minsup = 0.05;minconf = 0.5;trancount=0;ifstream file(fileName);/打開(kāi)數(shù)據(jù)文件if(!file)/檢查文件是否打開(kāi)成功std:cout<<&qu

15、ot;Fail to open data file!"<<endl;elsestring temp;set<string> item;/項(xiàng)集的臨時(shí)setint begin,end;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=

16、temp.find(',',begin)!=string:npos)/每一個(gè)事務(wù)中的項(xiàng)是以空格為分隔符的item.insert(temp.substr(begin,end-begin);/將每一個(gè)項(xiàng)插入item中begin=end+1;item.insert(temp.substr(begin);/一個(gè)事務(wù)中的最后一項(xiàng)datavec.push_back(item);/將一個(gè)事務(wù)中的所有項(xiàng)當(dāng)成一個(gè)整體插入另一個(gè)大的vector 中item.clear(); / /cout<<temp<<endl;清空 itemmap<string,int> i

17、tems_count;/ 統(tǒng)計(jì)各個(gè)項(xiàng)集的數(shù)目for(vector<set<string> >:size_type ix= 0 ;ix !=datavec.size(); +ix)for(set<string>:iterator iy=datavecix.begin();iy!=datavecix.end();+iy)if (items_count.find(*iy) = items_count.end()items_count*iy=1;elseitems_count*iy+;/該項(xiàng)集的計(jì)數(shù)加1vector <string> elem;vecto

18、r<pair<vector<string>,float>> candidatevec;/候選項(xiàng)集for (map<string,int>:iterator ix = items_count.begin(); ix != items_count.end(); ix+ )if ( (float(ix->second)/trancount >= minsup)/ 判斷候選頻繁 1項(xiàng)集中的各項(xiàng)， 是否大于最小頻繁度，如果是，則為頻繁項(xiàng)集；elem.push_back(ix->first);candidatevec.push_back(m

19、ake_pair(elem,(float(ix->second)/trancount);elem.clear();/ 一定要清空if (!candidatevec.empty()frequentvec.push_back(candidatevec);candidatevec.clear();/ 一定要清空/ 將得到的頻繁1項(xiàng)集加入頻繁項(xiàng)集集合中/ 判斷兩個(gè)項(xiàng)集是否可以合并 ( 要求只有一項(xiàng)不同 ) 成一個(gè)新的項(xiàng)集（做為候選集）vector<string> Apriori:mergeItem(vector<string> vect1,vector<string

20、> vect2,int round)/cout<<"調(diào)用 mergeItem"<<endl;/剪枝工作 /int count=0;/統(tǒng)計(jì)兩個(gè) vector 中相同的項(xiàng)的數(shù)目vector<string> vect;map<string,int> tempMap;/輔助判斷兩個(gè)vector 中重復(fù)的項(xiàng)for(vector<string>:size_type st=0;st<vect1.size();st+)tempMapvect1st+;vect.push_back(vect1st);for(vector&

21、lt;string>:size_type st=0;st<vect2.size();st+)tempMapvect2st+;if(tempMapvect2st=2) /表示這兩項(xiàng)相同count+;elsevect.push_back(vect2st);if(count+1)!=round)/要求兩個(gè)項(xiàng)目集只有一個(gè)項(xiàng)目不相同，其他都相同vect.clear();sort(vect.begin(),vect.end();return vect;/ 判斷一個(gè)項(xiàng)，是否為頻繁項(xiàng)float Apriori:calculateSup(vector<string> judgeVect)

22、/cout<<"調(diào)用 judge"<<endl;int count = 0;vector<string>:iterator iter;vector<string>:iterator iterBegin = judgeVect.begin();vector<string>:iterator iterEnd = judgeVect.end();for (vector<set<string>>:size_type st=0; st != datavec.size(); st+ )iter = it

23、erBegin;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_gen"<<endl;int round = 1;vector<vector<vector<string>

24、>>:size_type st = 0;vector<pair<vector<string>,float>> tempVec;vector<string> tempItem;float fre = 0.0;while (st != frequentvec.size() /循環(huán)在達(dá)到頻繁項(xiàng)集集合的末尾結(jié)束int i=0;if (frequentvecround-1.size() <2) /當(dāng)前輪次的頻繁round 項(xiàng)集中想的個(gè)數(shù)小于2時(shí)，算法結(jié)束return;vector<vector<string>>:s

25、ize_type ix , iy;for (ix = 0; ix != frequentvecround-1.size(); ix+)for (iy = ix + 1; 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_bac

26、k(make_pair(tempItem,fre);if (!tempVec.empty()/ 如果生成的頻繁round+1 項(xiàng)集frequentvec.push_back(tempVec);tempItem.clear();tempVec.clear();round+;st+;elsereturn;void Apriori:showItem()std:cout << "支持度 "<< minsup << "置信度 " << minconf << endl;for (vector<vect

27、or<pair<vector<string>,float>>>:size_type st1 = 0; st1 != frequentvec.size();st1+)std:cout << " 頻繁 " << st1+1 << " 項(xiàng)集： " << endl; for (vector<pair<vector<string>,float>>:size_typest2=0; st2!= frequentvecst1.size();st2

28、+)for (vector<string>: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()

29、;string infilename = "D:test.txt"Apriori calculation;calculation.init(infilename);calculation.apri_gen();calculation.showItem();endTime=clock();cout << "程序用時(shí) " << (double)(endTime - startTime)/CLOCKS_PER_SEC << "s" <<endl;system("pause"

30、);return 0;附：改進(jìn) 2代碼#include <iostream>#include <fstream>#include <string>#include <vector>#include <map>#include <cmath>#include <bitset>#include <algorithm>#include <iomanip>#include <set>#include <utility>#include <time.h>usin

31、g namespace std;/* 最大數(shù)據(jù)集數(shù)量，置信度閾值，*/class Aprioripublic:/ 初始化，輸入數(shù)據(jù)源，得到原始數(shù)據(jù)集、頻繁1項(xiàng)集void init(string fileName);/ 連接頻繁 k項(xiàng)集、并且直接剪枝，得到頻繁 k+1項(xiàng)集，加入到容器 item_listvoid apri_gen();/ 判斷候選項(xiàng)，是否為頻繁項(xiàng)float calculateSup(vector<int> judge_item);vector<int>mergeItem(vector<int>vect1,vector<int>vec

32、t2,intround);/判斷兩個(gè)項(xiàng)集是否可以合并( 要求只有一項(xiàng)不同) 成一個(gè)新的項(xiàng)集（做為候選集）void showItem();private:vector<set<int>> dataNumVec;/ 原始數(shù)據(jù)集轉(zhuǎn)換出來(lái)的、數(shù)據(jù)項(xiàng)用代號(hào)來(lái)表示的數(shù)據(jù)map<string,int> reflection;/ 原始數(shù)據(jù)中各個(gè)不同的元素的代號(hào)映射, 數(shù)據(jù)元素從 1開(kāi)始編號(hào)int trancount;/ 原始數(shù)據(jù)項(xiàng)數(shù)量vector<vector<pair<vector<int>,float>>> frequen

33、tvec;/頻繁項(xiàng)集 de集合double minsup; /設(shè)置最小支持度和最小置信度double minconf; /設(shè)置最小支持度和最小置信度;void Apriori:init(string fileName)/std:cout<<"調(diào)用 init"<<endl;minsup = 0.05;minconf = 0.5;trancount=0;int elemNumber = 1; /用于元素代號(hào)的設(shè)定ifstream file(fileName);/打開(kāi)數(shù)據(jù)文件if(!file)/檢查文件是否打開(kāi)成功std:cout<<"

34、;Fail to open data file!"<<endl;elsestring temp;string temp2;set<int> numItem;/ 項(xiàng)目集的臨時(shí)代號(hào)setint begin,end;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);/去除字符串首部的空格去除字符串尾部

35、的空格while(end=temp.find(',',begin)!=string:npos)/每一個(gè)事務(wù)中的項(xiàng)是以逗號(hào)為分隔符的temp2 =temp.substr(begin,end-begin);if (reflection.find(temp2) = reflection.end()/ 如果這個(gè)元素是第一次出現(xiàn)，則加入到映射map中去reflectiontemp2 = elemNumber+;numItem.insert(reflectiontemp2);begin=end+1;temp2 = temp.substr(begin);if (reflection.find

36、(temp2) = reflection.end()/ 如果這個(gè)元素是第一次出現(xiàn)，則加入到映射map中去reflectiontemp2 = elemNumber+;numItem.insert(reflectiontemp2);dataNumVec.push_back(numItem);/ 將一個(gè)事務(wù)中的所有項(xiàng)當(dāng)成一個(gè)整體插入另一個(gè)大的 vector 中numItem.clear();/ 清空 numItem/cout<<temp<<endl;map<int,int> items_count;/ 統(tǒng)計(jì)各個(gè)項(xiàng)集的數(shù)目for(vector<set<i

37、nt> >:size_type ix= 0 ;ix !=dataNumVec.size(); +ix)for(set<int>:iteratoriy=dataNumVecix.begin();iy!=dataNumVecix.end();+iy)if (items_count.find(*iy) = items_count.end()items_count*iy=1;elseitems_count*iy+;/該項(xiàng)集的計(jì)數(shù)加1vector <int> elem;vector<pair<vector<int>,float>>

38、candidatevec;/候選項(xiàng)集for (map<int,int>:iterator ix = items_count.begin(); ix != items_count.end();ix+ )if ( (float(ix->second)/trancount >= minsup)/ 判斷候選頻繁 1項(xiàng)集中的各項(xiàng)，是否大于最小頻繁度，如果是，則為頻繁項(xiàng)集；elem.push_back(ix->first);candidatevec.push_back(make_pair(elem,(float(ix->second)/trancount);elem.c

39、lear();/ 一定要清空if (!candidatevec.empty()frequentvec.push_back(candidatevec);/ 將得到的頻繁1項(xiàng)集加入頻繁項(xiàng)集集合中candidatevec.clear();/ 一定要清空/ 判斷兩個(gè)項(xiàng)集是否可以合并 ( 要求只有一項(xiàng)不同 ) 成一個(gè)新的項(xiàng)集（做為候選集）vector<int> Apriori:mergeItem(vector<int> vect1,vector<int> vect2,int round)/cout<<"調(diào)用 mergeItem"<

40、<endl;/剪枝工作 /int count=0;/統(tǒng)計(jì)兩個(gè) vector 中相同的項(xiàng)的數(shù)目vector<int> vect;map<int,int> tempMap;/輔助判斷兩個(gè) vector 中重復(fù)的項(xiàng)for(vector<int>:size_type st=0;st<vect1.size();st+)tempMapvect1st+;vect.push_back(vect1st);for(vector<int>:size_type st=0;st<vect2.size();st+)tempMapvect2st+;if(te

41、mpMapvect2st=2) /表示這兩項(xiàng)相同count+;elsevect.push_back(vect2st);if(count+1)!=round)/要求兩個(gè)項(xiàng)目集只有一個(gè)項(xiàng)目不相同，其他都相同vect.clear();sort(vect.begin(),vect.end();return vect;/ 判斷一個(gè)項(xiàng)，是否為頻繁項(xiàng)float Apriori:calculateSup(vector<int> judgeVect)/cout<<"調(diào)用 judge"<<endl;int count = 0;vector<int>

42、;:iterator iter;vector<int>:iterator iterBegin = judgeVect.begin();vector<int>:iterator iterEnd = judgeVect.end();for (vector<set<int>>:size_type st=0; st != dataNumVec.size(); st+ )iter = iterBegin;for (; iter != iterEnd; iter +)if (dataNumVecst.find(*iter) = dataNumVecst.en

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