数据挖掘Apriori算法C++实现

1、一、原Apriori算法1、算法原理：该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法（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); / 调用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.countmin_sup / 满足最小支持度的k-项集即为频繁k-项集（10） （11） return L= k Lk; / 合并频繁k-项集（k0）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_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;/原始数据集int trancount;/原始数据项数量vectorvectorpairvector,float frequentvec; /频繁项集的集合doubl

7、e minsup; /设置最小支持度和最小置信度double minconf; /设置最小支持度和最小置信度;运行结果：效果对比：数据集大小：9835数据元素多少：170置信度：0.05原始：频繁1项集28候选2项集228频繁2项集3改进后：频繁1项集28频繁2项集3算法的改进2第一次扫描数据库时，对于数据库中的数据，利用各项元素的数字编号来替换各数据元素的名称；即将数据元素的名称字符传用数字来替换，从而减少在求各候选项的支持度时的资源消耗；代码中的改进之处，string类型的元素转为对应的int代号：储存频繁项集的容器由vectorvectorpairvector,float变为vector

8、vectorpairvector,float；然后对代码进行相应的调整，使得代码正常运行；代码的描述：class Aprioripublic:void init(string fileName); /初始化，输入数据源，得到原始数据集、频繁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;/原始数据集转换出来的、数据项用代号来表示的数据map reflection;/原始数据中各个不同的元素的代号映射,数据元素从1开始编号int trancount;/原始数据项数量vectorvectorpairvector,float frequentvec; /频繁项集集合，储存各项以及其支持度double minsup; /设置最小支持度和最小置信度;运行结果：效果对比：改进后14.496；14.549；14.577改进前20

10、.165；20.463；20.383效率提升28.1%附：改进1的代码（改进2与改进1代码几乎相同，不同之处在于储存频繁项的数据类型，代码略）#include #include #include #include #include #include #include #include #include #include #include using namespace std;/*最大数据集数量，置信度阈值，*/class Aprioripublic:/初始化，输入数据源，得到原始数据集、频繁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;/原始数据集int trancount;/原始数据项数量vectorvectorpairvector,float frequentvec; /频繁项集de集合d

12、ouble minsup; /设置最小支持度和最小置信度double minconf; /设置最小支持度和最小置信度;void Apriori:init(string fileName)/std:cout调用initendl;minsup = 0.05;minconf = 0.5; trancount=0;ifstream file(fileName); /打开数据文件if(!file) /检查文件是否打开成功std:coutFail to open data file!endl;elsestring temp;set item; /项集的临时set int begin,end;while(g

13、etline(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=temp.find(,begin)!=string:npos) /每一个事务中的项是以空格为分隔符的item.insert(temp.substr(begin,end-begin); /将每一个项插入item中begin=end+1;item.insert(temp.sub

14、str(begin); /一个事务中的最后一项datavec.push_back(item); /将一个事务中的所有项当成一个整体插入另一个大的vector中item.clear(); /清空item/couttempendl;map items_count;/统计各个项集的数目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+; /该项集的计数加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调用mergeItemendl;/剪枝工作

17、/int count=0; /统计两个vector中相同的项的数目vector vect;map tempMap; /辅助判断两个vector中重复的项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调用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调用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() /循环在达到频繁项集集合的末尾结束int i=0;if (frequentvecround-1.size() 2)/当前轮次的频繁round项集中想的个数小于2时，算法结束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、*最大数据集数量，置信度阈值，*/class Aprioripublic:/初始化，输入数据源，得到原始数据集、频繁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;/原始数据集转换出来的、数据项用代号来表示的数据map reflection;/原始数据中各个不同的元素的代号映射,数据元素从1开始编号int trancount;/原始数据项数量vectorvectorpairvector,float frequentvec; /频繁项集de集合double minsup; /设置最小支持度和最小置信度double minconf; /设置最小支持度和最小置信度;void Apriori:init(string fileName)/std:cout调用initendl;minsup = 0.05

27、;minconf = 0.5; trancount=0;int elemNumber = 1;/用于元素代号的设定ifstream file(fileName); /打开数据文件if(!file) /检查文件是否打开成功std:coutFail to open data file!endl;elsestring temp;string temp2;set numItem;/项目集的临时代号setint begin,end;while(getline(file,temp) /一行一行读入数据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) /每一个事务中的项是以逗号为分隔符的temp2 =temp.substr(begin,end-begin);if (reflection.find(temp2) = reflection.end()/如果这个元素是第一次出现，则加入到映射map中去reflectiontemp2 = elemNumber+;numItem.insert(reflectiontemp2)

29、;begin=end+1;temp2 = temp.substr(begin);if (reflection.find(temp2) = reflection.end()/如果这个元素是第一次出现，则加入到映射map中去reflectiontemp2 = elemNumber+;numItem.insert(reflectiontemp2);dataNumVec.push_back(numItem);/将一个事务中的所有项当成一个整体插入另一个大的vector中numItem.clear();/清空numItem/couttempendl;map items_count;/统计各个项集的数目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+; /该项集的计数加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调用mergeItemendl;/剪枝工作/int count=0; /统计两个vector中相同的项的数目vector vect;map tempMap; /辅助判断两个vector中重复的项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调用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调用apri_genendl;int round = 1;vectorvectorpairvector,float:size_type st = 0;vectorpairvector,float tempVec;vector tempItem;float fre = 0.0;while (st != frequentvec.size() /循环在达到频繁项集集合的末尾结束int i=0;if (frequentvecround-1.size() 2)/当前轮次的频繁round项集中想的个数小于2时，算法结束ret