频繁模式挖掘算法(Apriori)

数据挖掘实验报告1实验一频繁模式挖掘算法（Apriori）一、实验目的1、理解频繁模式和关联规则2、掌握频繁模式挖掘算法Apriori3、为改进Apriori打下基础二、实验内容1、选定一个数据集（可以参考教学中使用的数据集）2、选择合适的实现环境和工具实现算法，本次试验采用的是C++3、根据设置的最小支持度和置信度，给出数据集的频繁模式集三、实验原理该算法的基本思想是：Apriori使用一种称作逐层搜索的迭代方法，k项集用于探索（k+1）项集。首先，通过扫描数据库，累积每个项的计数，并收集满足最小支持度的项，找出频繁1项集的集合。该集合记作L1.然后，L1用于找频繁2项集的集合L2，L2用于找L3，如此迭代，直到不能再找到频繁k项集。找每个Lk需要一次数据库全扫描。Apriori性质：频繁项集的所有非空子集也必是频繁的。Apriori算法主要包括连接步和剪枝步两步组成。在连接步和剪枝步中采用Apriori性质可以提高算法的效率。Apriori伪代码算法：Apriori输入：D-事务数据库；min_sup-最小支持度计数阈值输出：L-D中的频繁项集方法：L1=find_frequent_1-itemsets(D);//找出所有频繁1项集For(k=2;Lk-1!=null;k++){Ck=apriori_gen(Lk-1);//产生候选，并剪枝Foreach事务tinD{//扫描D进行候选计数Ct=subset(Ck,t);//得到t的子集Foreach候选c属于Ctc.count++;}Lk={c属于Ck|c.count=min_sup}}ReturnL=所有的频繁集；Procedureapriori_gen(Lk-1:frequent(k-1)-itemsets)Foreach项集l1属于Lk-1Foreach项集l2属于Lk-1If((l1[1]=l2[1])&&(l1[2]=l2[2])&&……..&&(l1[k-2]=l2[k-2])&&(l1[k-1]l2[k-1]))then{数据挖掘实验报告2c=l1连接l2//连接步：产生候选ifhas_infrequent_subset(c,Lk-1)thendeletec;//剪枝步：删除非频繁候选elseaddctoCk;}ReturnCk;Procedurehas_infrequent_sub(c:candidatek-itemset;Lk-1:frequent(k-1)-itemsets)Foreach(k-1)-subsetsofcIfs不属于Lk-1thenReturntrue;Returnfalse;四、实验要求1、数据集具有一定的代表性，可以使用数据库技术管理2、最小支持度和置信度可以设置3、实现界面友好4、提交实验报告：实验题目、目的、数据集描述、实验环境、过程、结果和分析等。五、实验步骤1、所采用的数据集I1I2I5I1I2I2I4I1I2I4I1I3I1I2I3I5I1I2I3I2I5I2I3I4I3I4对于数据集，取最小支持度min_sup=2，最小置信度min_conf=0.8。2、算法步骤①首先单趟扫描数据集，计算各个一项集的支持度，根据给定的最小支持度闵值，得到一项频繁集L1。②然后通过连接运算，得到二项候选集，对每个候选集再次扫描数据集，得出每个候选集的支持度，再与最小支持度比较。得到二项频繁集L2。③如此进行下去，直到不能连接产生新的候选集为止。④由频繁项集产生关联规则，关联规则产生步骤如下：1）对于每个频繁项集l，产生其所有非空真子集；2）对于每个非空真子集s,如果support_count(l)/support_count(s)=min_conf，则输出s-(l-s)，其中，min_conf是最小置信度阈值。3、程序实现数据挖掘实验报告31)首先要在工程名文件夹里自己定义date.txt文档存放数据，然后在main函数中用FILE*fp=fopen(date.txt,r);将数据导入算法。2)定义intcountL1[10];找到各一维频繁子集出现的次数。定义charcurL1[20][2];实现出现的一维子集。由于给出的数据最多有4个数，所以同样的我们要定义到4维来放数据。intcountL2[10];//各二维频繁子集出现的次数charcurL2[20][3];//出现的二维子集intcountL3[10];//各三维频繁子集出现的次数charcurL3[20][4];//出现的三维子集charcur[50][4];3)定义intSizeStr(char*m)得到字符串的长度。实现代码如下：intSizeStr(char*m){inti=0;while(*(m+i)!=0){i++;}returni;}4)比较两个字符串，如果相等返回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;}5)通过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++)数据挖掘实验报告4{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];数据挖掘实验报告5if(*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]);}}6)通过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++;数据挖掘实验报告6}}}7)通过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]))数据挖掘实验报告7countL2[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]);}}8)通过定义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;数据挖掘实验报告8n++;}}}}9)同样我们要得到得到各个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++){数据挖掘实验报告9s=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]);}}10)定义voidLoadIt