解释基于apriori算法的关联规则挖掘C语言版

#includefstream#includeiostream#includestdlib.husingnamespacestd;charshop[10];//用于存放每一种商品intsn;//商品信息（商品种类数）inttr[100][100],l[100],tn;//tr记录事务信息（数字化之后的事务信息），l记录每条事务包含的商品数，tn记录总共有多少条事务记录intmin_sup=2;//最小支持度计数floatmin_conf=0.7f;//最小置信度阈值typedefstruct{int**p;//记录i项集的所有内容（比如1项集的内容，2项集的内容，或者3项集的内容等等）int*num;//各个项集的支持计数（比如1项集中的每一条记录的支持度计数为多少，或者2项集中的每一条记录的支持度计数为多少等等）inti;//项集的项数（比如1项集，或者为2项集，或者为3项集）intn;//项集的数目（比如得到的1项集中有多少条记录，或者为2项集中有多少条记录，或者3项集中有多少条记录）}Large;voidInput(){ifstreamf1;f1.open(input.txt);inti,j,k,id;charc;f1sn;//用sn记录商品种类数for(i=1;i=sn;i++)//每一种商品名称放入shop数组{f1shop[i];}f1tn;//用tn记录总共有多少条事务记录for(i=1;i=tn;i++)//将每条事务中的每个商品对应在shop数组中的位序记录在数组tr中（相当于把商品的字符名称改为整形名称）{f1id;//id记录事务编号f1l[id];//记录编号为id的事务中总共有多少个商品for(j=1;j=l[id];j++){f1c;for(k=1;k=sn;k++){if(shop[k]==c){break;}}tr[id][j]=k;}}f1.close();}boolsubset(intt,intk)//判断名称为t的商品是否在事务k中{intmid,right,left;left=1;right=l[k];for(inti=left;i=right;i++){if(tr[k][i]==t){returntrue;}}/*while(left=right){mid=(left+right)/2;if(tr[k][mid]==t){returntrue;}if(tr[k][mid]t){right=mid-1;}else{left=mid+1;}}*/returnfalse;}Largefind_f1()//产生L1{LargeC1,L1;inti,k;C1.i=1;C1.n=0;for(i=1;i=sn;i++)//产生C1{if(C1.n==0)//初始化C1{C1.n=1;C1.p=(int**)malloc(C1.n*sizeof(int*));C1.num=(int*)malloc(C1.n*sizeof(int));*(C1.p+C1.n-1)=(int*)malloc(C1.i*sizeof(int));}else{C1.n++;C1.p=(int**)realloc(C1.p,C1.n*sizeof(int*));C1.num=(int*)realloc(C1.num,C1.n*sizeof(int));*(C1.p+C1.n-1)=(int*)malloc(C1.i*sizeof(int));}*(*(C1.p+C1.n-1)+0)=i;//将名称为i的商品放在数组C1.p中*(C1.num+C1.n-1)=0;//将名称为i的商品对应的数量放入数组C1.num中for(k=1;k=tn;k++){if(subset(i,k)){*(C1.num+C1.n-1)=*(C1.num+C1.n-1)+1;//如果名称为i的商品存在于事务K中，将数组C1.num中对应的数量加1}}}L1.i=1;L1.n=0;for(i=0;iC1.n;i++){if(*(C1.num+i)=min_sup)//求C1中的频繁项目集，过滤掉C1中非频繁项集{if(L1.n==0){L1.n=1;L1.p=(int**)malloc(L1.n*sizeof(int*));L1.num=(int*)malloc(L1.n*sizeof(int));*(L1.p+L1.n-1)=(int*)malloc(L1.i*sizeof(int));}else{L1.n++;L1.p=(int**)realloc(L1.p,L1.n*sizeof(int*));L1.num=(int*)realloc(L1.num,L1.n*sizeof(int));*(L1.p+L1.n-1)=(int*)malloc(L1.i*sizeof(int));}*(*(L1.p+L1.n-1)+0)=*(*(C1.p+i)+0);*(L1.num+L1.n-1)=*(C1.num+i);}}coutL1:endl;for(i=0;iL1.n;i++){coutshop[*(*(L1.p+i)+0)]''*(L1.num+i)endl;}returnL1;}boolIn_subset(LargeLp,int*c)//剪枝步运算（检查数组c的子集是否都在Lp中，如果都在，通过；如果有一个不再，不通过；）{inti,j,m,tag;int*temp=(int*)malloc(Lp.i*sizeof(int));for(i=0;iLp.i+1;i++){for(j=0;ji;j++)//生成子集{*(temp+j)=*(c+j);}for(j=i+1;jLp.i+1;j++){*(temp+j-1)=*(c+j);}tag=1;for(m=0;mLp.n;m++){for(j=0;jLp.i;j++){if(*(temp+j)!=*(*(Lp.p+m)+j)){break;}}if(j==Lp.i)//匹配成功，进行下个子集匹配{tag=0;break;}}if(tag==1){returnfalse;//匹配失败，终止}}returntrue;//全部子集匹配成功}Largeapriori_gen(LargeLp)//连接步运算{inti,j,k;int*c=(int*)malloc((Lp.i+1)*sizeof(int));//如果两个项目集可以连接，将这两个项目集连接后暂存在数组c中LargeCn;Cn.i=Lp.i+1;Cn.n=0;for(i=0;iLp.n;i++){for(j=i+1;jLp.n;j++){for(k=0;kLp.i-1;k++){if(*(*(Lp.p+i)+k)!=*(*(Lp.p+j)+k)){break;}else{*(c+k)=*(*(Lp.p+i)+k);}}if(k==Lp.i-1)//可以连接{if(*(*(Lp.p+i)+k)*(*(Lp.p+j)+k)){*(c+k)=*(*(Lp.p+j)+k);*(c+k+1)=*(*(Lp.p+i)+k);}else{*(c+k)=*(*(Lp.p+i)+k);*(c+k+1)=*(*(Lp.p+j)+k);}if(In_subset(Lp,c))//通过剪枝运算{if(Cn.n==0){Cn.n=1;Cn.p=(int**)malloc(Cn.n*sizeof(int*));Cn.num=(int*)malloc(Cn.n*sizeof(int));*(Cn.p+Cn.n-1)=(int*)malloc(Cn.i*sizeof(int));}else{Cn.n++;Cn.p=(int**)realloc(Cn.p,Cn.n*sizeof(int*));Cn.num=(int*)realloc(Cn.num,Cn.n*sizeof(int));*(Cn.p+Cn.n-1)=(int*)malloc(Cn.i*sizeof(int));}for(k=0;kCn.i;k++){*(*(Cn.p+Cn.n-1)+k)=*(c+k);}}}}}returnCn;}voidRules(Large*L,intlk)//产生关联规则{inti,j,k,h,m,n,t,count;int*temp1=(int*)malloc(lk*sizeof(int)),tp1;//申请一维整形数组temp1，存放关联规则前件；整形变量tp1记录关联规则前件包含的项数int*temp2=(int*)malloc(lk*sizeof(int)),tp2;//申请一维整形数组temp2，存放关联规则后件；整形变量tp2记录关联规则后件包含的项数for(i=1;i=lk;i++)//依次对每个频繁项目集推导关联规则{coutLi':'endl;for(j=0;j(*(L+i)).n;j++)//对当前频繁项目集的每一条记录进行推导{n=1;for(h=0;h(*(L+i)).i;h++){n*=2;//频繁项集子集总个数（实际总共有(2^i)-2个子集）}for(h=1;hn-1;h++)//对总数为(2^i)-2个子集进行操作{tp1=0;tp2=0;t=1;for(m=0;m(*(L+i)).i;m++){if((h/t)%2==1){temp1[tp1++]=*(*((*(L+i)).p+j)+m);}else{temp2[tp2++]=*(*((*(L+i)).p+j)+m);}t*=2;}count=0;//统计关联规则前件在数据库事务中出现的次数for(k=1;k=tn;k++){for(m=0;mtp1;m++){if(!subset(*(temp1+m),k)){break;}}if(m==tp1){count++;}}if((float)*((*(L+i)).num+j)/count=min_conf)//检查是否大于等于最小置信度阈值{for(k=0;ktp1;k++){coutshop[*(temp1+k)]'';}cout==;for(k=0;ktp2;k++){coutshop[*(temp2+k)]'';}cout\t置信度=(float)*((*(L+i)).num+j)/count*100%\t\t支持度=(float)*((*(L+i)).num+j)/tn*100%endl;}}}}}voidf(){inti,j,k,m,lk=1;Large*L=(Large*)malloc((lk+1)*sizeof(Large));Input();*(L+1)=find_f1();for(k=2;(*(L+k-1)).n!=0;k++){LargeCk=apriori_gen(*(L+k-1));//从k-1项集产生候选k项集Ckfor(i=0;iCk.n;i++)//对候选k项集的每一条记录进行统计计数{*(Ck.num+i)=0;//先设置第i条记录的对应的值为0for(m=1;m=tn;m++)//对于数据库中的每一个事务，查看该事务是否包k项集的当前记录{for(j=0;jCk.i;j++){if(!subset(*(*(Ck.p+i)+j),m)){break;}}if(j==Ck.i)//如果相等，说明数据库中的事务包含k项集的当前项{*(Ck.num+i)=*(Ck.num+i)+1;//使k项集的第i项加1}}}L=(Large*)realloc(L,(k+1)*sizeof(Large));//为存放k项频繁集申请空间(*(L+k)).n=0;//初始化k项频繁集包含的项数(*(L+k)).i=k;//初始化k项频繁集的标志“k”for(i=0;iCk.n;i++){if(*(Ck.num+i)=min_sup)//与