数据挖掘Apriori算法报告

数据挖掘Apriori算法报告一．关联算法简介关联规则的目的在于在一个数据集中找出项之间的关系，也称之为购物蓝分析(marketbasketanalysis)。例如，购买鞋的顾客，有10%的可能也会买袜子，60%的买面包的顾客，也会买牛奶。这其中最有名的例子就是尿布和啤酒的故事了。关联规则的应用场合。在商业销售上，关联规则可用于交叉销售，以得到更大的收入；在保险业务方面，如果出现了不常见的索赔要求组合，则可能为欺诈，需要作进一步的调查。在医疗方面，可找出可能的治疗组合；在银行方面，对顾客进行分析，可以推荐感兴趣的服务等等。Apriorialgorithm是关联规则里一项基本算法。由RakeshAgrawal在1994年提出的，详细的介绍请猛击这里《FastAlgorithmsforMiningAssociationRules》。二.关联算法的基本原理该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法（1）L1=find_frequent_1-itemsets(D);//挖掘频繁1-项集，比较容易（2）for(k=2;Lk-1≠Φ;k++){（3）Ck=apriori_gen(Lk-1,min_sup);//调用apriori_gen方法生成候选频繁k-项集（4）foreachtransactiont∈D{//扫描事务数据库D（5）Ct=subset(Ck,t);（6）foreachcandidatec∈Ct（7）c.count++;//统计候选频繁k-项集的计数（8）}（9）Lk={c∈Ck|c.count≥min_sup}//满足最小支持度的k-项集即为频繁k-项集（10）}（11）returnL=∪kLk;//合并频繁k-项集（k0）三.关联算法的C++简单实现（1）算法数据：对给定数据集用Apriori算法进行挖掘，找出其中的频繁集并生成关联规则。对下面数据集进行挖掘：I1I2I5I1I2I2I4I1I2I4I1I3I1I2I3I5I1I2I3I2I5I2I3I4I3I4对于数据集，取最小支持度minsup=2，最小置信度minconf=0.8。（2）算法步骤：①首先单趟扫描数据集，计算各个一项集的支持度，根据给定的最小支持度闵值，得到一项频繁集L1。②然后通过连接运算，得到二项候选集，对每个候选集再次扫描数据集，得出每个候选集的支持度，再与最小支持度比较。得到二项频繁集L2。③如此进行下去，直到不能连接产生新的候选集为止。④对于找到的所有频繁集，用规则提取算法进行关联规则的提取。（3）C++算法的简单实现①首先要在工程名文件夹里自己定义date.txt文档存放数据，然后在main函数中用FILE*fp=fopen(date.txt,r);将数据导入算法。②定义intcountL1[10];找到各一维频繁子集出现的次数。定义charcurL1[20][2];实现出现的一维子集。由于给出的数据最多有4个数，所以同样的我们要定义到4维来放数据。intcountL2[10];//各二维频繁子集出现的次数charcurL2[20][3];//出现的二维子集intcountL3[10];//各三维频繁子集出现的次数charcurL3[20][4];//出现的三维子集charcur[50][4];③定义intSizeStr(char*m)得到字符串的长度。实现代码如下：intSizeStr(char*m){inti=0;while(*(m+i)!=0){i++;}returni;}④比较两个字符串，如果相等返回true,否则返回falseboolOpD(char*x,char*y){inti=0;if(SizeStr(x)==SizeStr(y)){while(*(x+i)==*(y+i)){i++;if(*(x+i)==0&&*(y+i)==0)returntrue;}}returnfalse;}⑤通过voidLoadItemL1(char**p)得到所有1元的字串和各自出现的次数voidLoadItemL1(char**p){inti,j,n=0,k=0;charch;char*s;intf;memset(cur,0,sizeof(cur));for(i=0;i20;i++){curL1[i][0]=0;curL1[i][1]=0;}for(j=0;j10;j++)countL1[j]=0;for(i=0;i10;i++)for(j=0;j4;j++){ch=*(*(p+i)+j);if(ch==0)break;cur[n][0]=ch;n++;}curL1[0][0]=cur[0][0];curL1[0][1]=cur[0][1];k=0;for(i=0;i50;i++){if(cur[i]==0)break;s=cur[i];f=1;for(j=0;j=k;j++){if(OpD(s,curL1[j])){f=0;break;}}if(f==1){++k;curL1[k][0]=cur[i][0];curL1[k][1]=cur[i][1];}}for(i=0;i20;i++)for(j=0;j50;j++){char*m;m=curL1[i];if(*m==0)break;if(OpD(m,cur[j]))countL1[i]++;}printf(L1:\n);printf(项集支持度计数\n);for(i=0;i10;i++){if(curL1[i]==0)break;if(countL1[i]=2)printf({I%s}:%d\n,curL1[i],countL1[i]);}}⑥通过voidSubItem2(char**p)得到所有的2元子串voidSubItem2(char**p){inti,j,k,n=0;char*s;memset(cur,0,sizeof(cur));for(i=0;i20;i++){curL2[i][0]=0;curL2[i][1]=0;curL2[i][2]=0;}for(i=0;i10;i++)countL2[i]=0;for(k=0;k10;k++){s=*(p+k);if(SizeStr(s)2)continue;for(i=0;iSizeStr(s);i++)for(j=i+1;jSizeStr(s);j++){if(*(s+j)==0)break;*(cur[n]+0)=*(s+i);*(cur[n]+1)=*(s+j);*(cur[n]+2)=0;*(cur[n]+3)=0;n++;}}}⑦通过voidLoadItemL2(char**p)得到各个2元频繁子串出现的次数voidLoadItemL2(char**p){intk,i,j;char*s;intf;SubItem2(p);curL2[0][0]=cur[0][0];curL2[0][1]=cur[0][1];curL2[0][2]=cur[0][2];k=0;for(i=0;i50;i++){if(cur[i]==0)break;s=cur[i];f=1;for(j=0;j=k;j++){if(OpD(s,curL2[j])){f=0;break;}}if(f==1){++k;curL2[k][0]=cur[i][0];curL2[k][1]=cur[i][1];curL2[k][2]=cur[i][2];}}for(i=0;i20;i++)for(j=0;j50;j++){s=curL2[i];if(*s==0)break;if(OpD(s,cur[j]))countL2[i]++;}printf(L2:\n);printf(项集支持度计数\n);for(i=0;i10;i++){if(curL2[i]==0)break;if(countL2[i]=2)printf({I%c,I%c}:%d\n,curL2[i][0],curL2[i][1],countL2[i]);}}⑧通过定义voidSubItem3(char**p)得到所有3元的子串voidSubItem3(char**p){char*s;inti,j,h,m;intn=0;memset(cur,0,sizeof(cur));for(j=0;j20;j++){curL3[j][0]=0;curL3[j][1]=0;curL3[j][2]=0;curL3[j][3]=0;}for(i=0;i10;i++)countL3[i]=0;for(m=0;m10;m++){s=*(p+m);if(SizeStr(s)3)continue;for(i=0;iSizeStr(s);i++)for(j=i+1;jSizeStr(s);j++){for(h=j+1;hSizeStr(s);h++){if(*(s+h)==0)break;*(cur[n]+0)=*(s+i);*(cur[n]+1)=*(s+j);*(cur[n]+2)=*(s+h);*(cur[n]+3)=0;n++;}}}}⑨同样我们要得到得到各个3元频繁子串出现的次数voidLoadItemL3(char**p){intk,i,j;char*s;intf;SubItem3(p);curL3[0][0]=cur[0][0];curL3[0][1]=cur[0][1];curL3[0][2]=cur[0][2];curL3[0][3]=cur[0][3];k=0;for(i=0;i50;i++){if(cur[i]==0)break;s=cur[i];f=1;for(j=0;j=k;j++){if(OpD(s,curL3[j])){f=0;break;}}if(f==1){++k;curL3[k][0]=cur[i][0];curL3[k][1]=cur[i][1];curL3[k][2]=cur[i][2];curL3[k][3]=cur[i][3];}}for(i=0;i20;i++)for(j=0;j50;j++){s=curL3[i];if(*s==0)break;if(OpD(s,cur[j]))countL3[i]++;}printf(L3:\n);printf(项集支持度计数\n);for(i=0;i10;i++){if(curL3[i]==0)break;if(countL3[i]=2)printf({I%c,I%c,I%c}:%d\n,curL3[i][0],curL3[i][1],curL3[i][2],countL3[i]);}}⑩定义voidLoadItemL4(char**p)得到各个3元子串出现的次数voidLoadItemL4(char**p){inti;char*s;intj=0;for(i=0;i10;i++){s=*(p+i);if(SizeStr(s)==4)j++;}printf(四维子集出现的次数:%d\n,j);printf(没有四维的频繁子集，算法结束!\n);}○11通过voidSupport(char*w,intg)得到关联规则，并输出结果voidSupport(char*w,intg){inti,j,k,n=0;char*s;floatc=0.8,d=0;memset(cur,0,sizeof(cur));s=w;for(i=0;iSizeStr(s);i++){*(cur[n]+0)=*(s+i);*(cur[n]+1)=0;*(cur[n]+2)=0;*(cur[n]+3)=0;n++;}for(i=0;iSizeStr(s);i+