数据挖掘Apriori算法C实现

1、一、原 Apriori 算法1、算法原理：该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1 步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法（ 1）L1 = find_frequent_1-itemsets(D);/挖掘频繁1- 项集，比较容易（ 2）for (k=2;Lk- 1 ;k+) （ 3）Ck

2、= apriori_gen(Lk-1 ,min_sup);/调用 apriori_gen 方法生成候选频繁k- 项集（ 4） for each transaction t D /扫描事务数据库D（ 5）Ct = subset(Ck,t);（ 6） for each candidate c Ct（ 7）c.count+;/统计候选频繁k- 项集的计数（ 8）（ 9） Lk =c Ck|c.count min_sup/满足最小支持度的k- 项集即为频繁k- 项集（10） （ 11） return L= k Lk;/合并频繁k- 项集（ k>0 ）2、算法流程 首先单趟扫描数据集，计算各个一项

3、集的支持度，根据给定的最小支持度闵值，得到一项频繁集L1。 然后通过连接运算，得到二项候选集，对每个候选集再次扫描数据集，得出每个候选集的支持度，再与最小支持度比较。得到二项频繁集L2。 如此进行下去，直到不能连接产生新的候选集为止。 对于找到的所有频繁集，用规则提取算法进行关联规则的提取。3、算法的不足：（ ）数据库重复扫描的次数太多。在由 寻找 的过程中， 中的每一项都需要扫描事务数据库进行验证，以决定其是否加入 ，存在的频繁 项集越大，重复扫描的次数就越多。这一过程耗时太大，增加了系统 开销，处理效率低 ，不利于实际应用。（ ）产生的候选集可能过于庞大。如果一个频繁 项集包含个项，那么频

4、繁 项集就有 个，为找到元素个数为的频繁项集，如 ， ， ， ，那么就要扫描数据库次，产生的候选项集总个数为：举例：对于一个这样庞大的项集，计算机难以存储和计算，挖掘效率低下。二、算法的改进11、改进方法：性质：频繁项集的所有非空子集都必须是频繁的。（ 性质，记为性质）性质：若频繁 项集 中各个项可以做链接产生 ，则 中每个元素在 中出现的次数应大于或等于 ，若小于 ，则删除该项在务集 。（性质的推论，记为性质） 中所有的事改进的方法： 在连接之后得到的候选频繁k 项，直接进行最小支持度判断，并进行剪枝， 从而直接得到频繁k 项集，避免候选项集可能过大的问题；2、算法的流程 首先单趟扫描数据集

5、，计算各个一项集的支持度，根据给定的最小支持度阈值，得到一项频繁集L1。 然后通过连接运算，对于每个连接的到项直接进行最小支持度判断，如果大于最小支持度的加入频繁二项集，如果小于则舍弃，循环直到连接完毕；得到二项频繁集L2。 如此进行下去，直到不能连接产生新的频繁项集为止。3、代码实现的描述（详细描述文末附上）：使用 C+，构造了一个 Apriori类：class Aprioripublic:/ 初始化，输入数据源，得到原始数据集、频繁1项集void init(string fileName); /连接频繁 k项集、并且直接剪枝，得到频繁k+1项集，加入到容器item_listvoidapri

6、_gen();/连接频繁 k项集、并且直接剪枝，得到频繁k+1项集，加入到频繁项集集合frequentvecfloat calculateSup(vector<string> judge_item); /求候选项的支持度vector<string> mergeItem(vector<string> vect1,vector<string> vect2,int round); /判断两个项是否中可以合并成一个新的项集做为新的候选项，能则合并，不能的返回空容器void showItem();/输出频繁项集private:vector<set&l

7、t;string>> datavec; int trancount;/ 原始数据集/ 原始数据项数量vector<vector<pair<vector<string>,float>>> frequentvec;/频繁项集的集合double minsup; double minconf;/设置最小支持度和最小置信度设置最小支持度和最小置信度;运行结果：效果对比：数据集大小： 9835数据元素多少：170置信度： 0.05原始：频繁 1项集 28候选 2项集 228频繁 2项集 3改进后：频繁 1项集 28频繁 2项集 3算法的改进 2第

8、一次扫描数据库时，对于数据库中的数据，利用各项元素的数字编号来替换各数据元素的名称；即将数据元素的名称字符传用数字来替换，从而减少在求各候选项的支持度时的资源消耗；代码中的改进之处，string类型的元素转为对应的int 代号：储存频繁项集的容器由vector<vector<pair<vector<string>,float>>>为 vector<vector<pair<vector<int>,float>>>；然后对代码进行相应的调整，使得代码正常运行；变代码的描述：class Aprioripu

9、blic:void init(string fileName); /初始化，输入数据源，得到原始数据集、频繁1项集void apri_gen();/连接频繁 k项集、并且直接剪枝，得到频繁k+1项集，加入到频繁项集集合float calculateSup(vector<int> judge_item); /求候选项的支持度frequentvec中vector<int> mergeItem(vector<int> vect1,vector<int> vect2,int round); /判断两个项是否可以合并成一个新的项集做为新的候选项，能则合并，

10、不能的返回空容器void showItem();/输出频繁项集private:vector<set<int>> dataNumVec;/ map<string,int> reflection; /原始数据集转换出来的、数据项用代号来表示的数据原始数据中各个不同的元素的代号映射, 数据元素从1开始编号int trancount;/ 原始数据项数量vector<vector<pair<vector<int>,float>>> frequentvec;/频繁项集集合，储存各项以及其支持度double minsup;

11、/设置最小支持度和最小置信度;运行结果：效果对比：改进后 14.496 ； 14.549 ； 14.577改进前 20.165 ； 20.463 ； 20.383效率提升 28.1%附：改进 1的代码（改进 2与改进 1代码几乎相同，不同之处在于储存频繁项的数据类型，代码略）#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;/* 最大数据集数量，置信度阈值，*/class Aprioripublic:/ 初始化，输入数据源，得到原始数据集、频繁1项集void init(string fileName);/ 连接频繁 k项集、并且直接剪枝，得到频繁 k+1项集，加入到容器 item_listvoid apri_gen();/ 判断候选项，是否为频繁项float calculateSup(vect

13、or<string> judge_item);vector<string> mergeItem(vector<string> vect1,vector<string> vect2,int round);/判断两个项集是否可以合并( 要求只有一项不同) 成一个新的项集（做为候选集）void showItem();private:vector<set<string>> datavec;/ 原始数据集int trancount;/ 原始数据项数量vector<vector<pair<vector<stri

14、ng>,float>>> frequentvec;/频繁项集de集合double minsup; / double minconf; /设置最小支持度和最小置信度设置最小支持度和最小置信度;void Apriori:init(string fileName)/std:cout<<"调用 init"<<endl;minsup = 0.05;minconf = 0.5;trancount=0;ifstream file(fileName);/打开数据文件if(!file)/检查文件是否打开成功std:cout<<&qu

15、ot;Fail to open data file!"<<endl;elsestring temp;set<string> item;/项集的临时setint begin,end;while(getline(file,temp)/一行一行读入数据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)/每一个事务中的项是以空格为分隔符的item.insert(temp.substr(begin,end-begin);/将每一个项插入item中begin=end+1;item.insert(temp.substr(begin);/一个事务中的最后一项datavec.push_back(item);/将一个事务中的所有项当成一个整体插入另一个大的vector 中item.clear(); / /cout<<temp<<endl;清空 itemmap<string,int> i

17、tems_count;/ 统计各个项集的数目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+;/该项集的计数加1vector <string> elem;vecto

18、r<pair<vector<string>,float>> candidatevec;/候选项集for (map<string,int>:iterator ix = items_count.begin(); ix != items_count.end(); ix+ )if ( (float(ix->second)/trancount >= minsup)/ 判断候选频繁 1项集中的各项， 是否大于最小频繁度，如果是，则为频繁项集；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项集加入频繁项集集合中/ 判断两个项集是否可以合并 ( 要求只有一项不同 ) 成一个新的项集（做为候选集）vector<string> Apriori:mergeItem(vector<string> vect1,vector<string

20、> vect2,int round)/cout<<"调用 mergeItem"<<endl;/剪枝工作 /int count=0;/统计两个 vector 中相同的项的数目vector<string> vect;map<string,int> tempMap;/辅助判断两个vector 中重复的项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) /表示这两项相同count+;elsevect.push_back(vect2st);if(count+1)!=round)/要求两个项目集只有一个项目不相同，其他都相同vect.clear();sort(vect.begin(),vect.end();return vect;/ 判断一个项，是否为频繁项float Apriori:calculateSup(vector<string> judgeVect)

22、/cout<<"调用 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<<"调用 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() /循环在达到频繁项集集合的末尾结束int i=0;if (frequentvecround-1.size() <2) /当前轮次的频繁round 项集中想的个数小于2时，算法结束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 项集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 << " 项集： " << 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 << "程序用时 " << (double)(endTime - startTime)/CLOCKS_PER_SEC << "s" <<endl;system("pause"

30、);return 0;附：改进 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;/* 最大数据集数量，置信度阈值，*/class Aprioripublic:/ 初始化，输入数据源，得到原始数据集、频繁1项集void init(string fileName);/ 连接频繁 k项集、并且直接剪枝，得到频繁 k+1项集，加入到容器 item_listvoid apri_gen();/ 判断候选项，是否为频繁项float calculateSup(vector<int> judge_item);vector<int>mergeItem(vector<int>vect1,vector<int>vec

32、t2,intround);/判断两个项集是否可以合并( 要求只有一项不同) 成一个新的项集（做为候选集）void showItem();private:vector<set<int>> dataNumVec;/ 原始数据集转换出来的、数据项用代号来表示的数据map<string,int> reflection;/ 原始数据中各个不同的元素的代号映射, 数据元素从 1开始编号int trancount;/ 原始数据项数量vector<vector<pair<vector<int>,float>>> frequen

33、tvec;/频繁项集 de集合double minsup; /设置最小支持度和最小置信度double minconf; /设置最小支持度和最小置信度;void Apriori:init(string fileName)/std:cout<<"调用 init"<<endl;minsup = 0.05;minconf = 0.5;trancount=0;int elemNumber = 1; /用于元素代号的设定ifstream file(fileName);/打开数据文件if(!file)/检查文件是否打开成功std:cout<<"

34、;Fail to open data file!"<<endl;elsestring temp;string temp2;set<int> numItem;/ 项目集的临时代号setint begin,end;while(getline(file,temp)/一行一行读入数据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)/每一个事务中的项是以逗号为分隔符的temp2 =temp.substr(begin,end-begin);if (reflection.find(temp2) = reflection.end()/ 如果这个元素是第一次出现，则加入到映射map中去reflectiontemp2 = elemNumber+;numItem.insert(reflectiontemp2);begin=end+1;temp2 = temp.substr(begin);if (reflection.find

36、(temp2) = reflection.end()/ 如果这个元素是第一次出现，则加入到映射map中去reflectiontemp2 = elemNumber+;numItem.insert(reflectiontemp2);dataNumVec.push_back(numItem);/ 将一个事务中的所有项当成一个整体插入另一个大的 vector 中numItem.clear();/ 清空 numItem/cout<<temp<<endl;map<int,int> items_count;/ 统计各个项集的数目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+;/该项集的计数加1vector <int> elem;vector<pair<vector<int>,float>>

38、candidatevec;/候选项集for (map<int,int>:iterator ix = items_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.c

39、lear();/ 一定要清空if (!candidatevec.empty()frequentvec.push_back(candidatevec);/ 将得到的频繁1项集加入频繁项集集合中candidatevec.clear();/ 一定要清空/ 判断两个项集是否可以合并 ( 要求只有一项不同 ) 成一个新的项集（做为候选集）vector<int> Apriori:mergeItem(vector<int> vect1,vector<int> vect2,int round)/cout<<"调用 mergeItem"<

40、<endl;/剪枝工作 /int count=0;/统计两个 vector 中相同的项的数目vector<int> vect;map<int,int> tempMap;/辅助判断两个 vector 中重复的项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) /表示这两项相同count+;elsevect.push_back(vect2st);if(count+1)!=round)/要求两个项目集只有一个项目不相同，其他都相同vect.clear();sort(vect.begin(),vect.end();return vect;/ 判断一个项，是否为频繁项float Apriori:calculateSup(vector<int> judgeVect)/cout<<"调用 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<<"调用 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() / 循环在达到频繁项集集合的末尾结束int i=0;if (frequentvecround-1.size() <2) /当前轮次的频繁round 项集中想的个数小于2时，算法结束return;vector<pair<vector<int>,float>>:size_type ix , iy;for (ix = 0; ix != fre