《数据挖掘Apriori算法报告.doc》由会员分享，可在线阅读，更多相关《数据挖掘Apriori算法报告.doc（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 数据挖掘Apriori算法报告一关联算法简介关联规则的目的在于在一个数据集中找出项之间的关系，也称之为购物蓝分析 (market basketanalysis)。例如，购买鞋的顾客，有10%的可能也会买袜子，60%的买面包的顾客，也会买牛奶。这其中最有名的例子就是尿布和啤酒的故事了。关联规则的应用场合。在商业销售上，关联规则可用于交叉销售，以得到更大的收入；在保险业务方面，如果出现了不常见的索赔要求组合，则可能为欺诈，需要作进一步的调查。在医疗方面，可找出可能的治疗组合；在银行方面，对顾客进行分析，可以推荐感兴趣的服务等等。Apriori algorithm是关联规则里一项基本算法。由Rak
2、esh Agrawal 在 1994年提出的，详细的介绍请猛击这里Fast Algorithms for Mining Association Rules。二.关联算法的基本原理 该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法（1）L1 = find_fr
3、equent_1-itemsets(D); / 挖掘频繁1-项集，比较容易（2）for (k=2;Lk-1 ;k+) （3）Ck = 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.countmin_sup / 满足最小支持度的k-项集即为频繁k-项集（10） （11） retu
4、rn L= k Lk; / 合并频繁k-项集（k0）三.关联算法的C+简单实现（1）算法数据：对给定数据集用Apriori算法进行挖掘，找出其中的频繁集并生成关联规则。对下面数据集进行挖掘：I1 I2 I5I1 I2I2 I4I1 I2 I4I1 I3I1 I2 I3 I5I1 I2 I3I2 I5I2 I3 I4I3 I4对于数据集，取最小支持度minsup=2，最小置信度minconf=0.8。（2）算法步骤： 首先单趟扫描数据集，计算各个一项集的支持度，根据给定的最小支持度闵值，得到一项频繁集L1。 然后通过连接运算，得到二项候选集，对每个候选集再次扫描数据集，得出每个候选集的支持度，再
5、与最小支持度比较。得到二项频繁集L2。 如此进行下去，直到不能连接产生新的候选集为止。 对于找到的所有频繁集，用规则提取算法进行关联规则的提取。（3）C+算法的简单实现 首先要在工程名文件夹里自己定义date.txt文档存放数据，然后在main函数中用FILE* fp=fopen(date.txt,r);将数据导入算法。 定义int countL110;找到各一维频繁子集出现的次数。定义char curL1202;实现出现的一维子集。由于给出的数据最多有4个数，所以同样的我们要定义到4维来放数据。int countL210; /各二维频繁子集出现的次数char curL2203; /出现的二维
6、子集int countL310; /各三维频繁子集出现的次数char curL3204; /出现的三维子集char cur504; 定义int SizeStr(char* m) 得到字符串的长度。实现代码如下： int SizeStr(char* m)int i=0;while(*(m+i)!=0)i+;return i;比较两个字符串，如果相等返回true,否则返回false bool OpD(char* x,char* y)int i=0;if(SizeStr(x)=SizeStr(y)while(*(x+i)=*(y+i)i+;if(*(x+i)=0 & *(y+i)=0)return
7、true;return false;通过void LoadItemL1(char *p) 得到所有1元的字串和各自出现的次数 void LoadItemL1(char *p)int i,j,n=0,k=0;char ch;char* s;int f;memset(cur,0,sizeof(cur);for(i=0;i20;i+)curL1i0=0;curL1i1=0;for(j=0;j10;j+)countL1j=0;for(i=0;i10;i+)for(j=0;j4;j+)ch=*(*(p+i)+j);if(ch=0)break;curn0=ch;n+;curL100=cur00;curL1
8、01=cur01;k=0;for(i=0;i50;i+)if(curi=0)break;s=curi;f=1;for(j=0;j=k;j+)if(OpD(s,curL1j)f=0;break;if(f=1)+k;curL1k0=curi0;curL1k1=curi1;for(i=0;i20;i+)for(j=0;j50;j+)char* m;m=curL1i;if(*m=0)break;if(OpD(m,curj)countL1i+;printf(L1: n );printf(项集 支持度计数n);for(i=0;i=2)printf(I%s: %dn,curL1i,countL1i);通过v
9、oid SubItem2(char *p) 得到所有的2元子串 void SubItem2(char *p)int i,j,k,n=0;char* s;memset(cur,0,sizeof(cur);for(i=0;i20;i+)curL2i0=0;curL2i1=0;curL2i2=0;for(i=0;i10;i+)countL2i=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;*(curn+0)=*(s+
10、i);*(curn+1)=*(s+j);*(curn+2)=0;*(curn+3)=0;n+;通过void LoadItemL2(char *p) 得到各个2元频繁子串出现的次数 void LoadItemL2(char *p)int k,i,j;char* s;int f;SubItem2(p);curL200=cur00;curL201=cur01;curL202=cur02;k=0;for(i=0;i50;i+)if(curi=0)break;s=curi;f=1;for(j=0;j=k;j+)if(OpD(s,curL2j)f=0;break;if(f=1)+k;curL2k0=cur
11、i0;curL2k1=curi1;curL2k2=curi2;for(i=0;i20;i+)for(j=0;j50;j+)s=curL2i;if(*s=0)break;if(OpD(s,curj)countL2i+;printf(L2: n);printf(项集 支持度计数n);for(i=0;i=2)printf(I%c,I%c: %dn,curL2i0,curL2i1,countL2i);通过定义void SubItem3(char *p) 得到所有3元的子串 void SubItem3(char *p)char *s;int i,j,h,m;int n=0;memset(cur,0,si
12、zeof(cur);for(j=0;j20;j+)curL3j0=0;curL3j1=0;curL3j2=0;curL3j3=0;for(i=0;i10;i+)countL3i=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;*(curn+0)=*(s+i);*(curn+1)=*(s+j);*(curn+2)=*(s+h);*(curn+3)=0;n+;同样我们
13、要得到得到各个3元频繁子串出现的次数 void LoadItemL3(char* p)int k,i,j;char* s;int f;SubItem3(p);curL300=cur00;curL301=cur01;curL302=cur02;curL303=cur03;k=0;for(i=0;i50;i+)if(curi=0)break;s=curi;f=1;for(j=0;j=k;j+)if(OpD(s,curL3j)f=0;break;if(f=1)+k;curL3k0=curi0;curL3k1=curi1;curL3k2=curi2;curL3k3=curi3;for(i=0;i20;
14、i+)for(j=0;j50;j+)s=curL3i;if(*s=0)break;if(OpD(s,curj)countL3i+;printf(L3: n);printf(项集 支持度计数n);for(i=0;i=2)printf(I%c,I%c,I%c: %dn,curL3i0,curL3i1,curL3i2,countL3i);定义void LoadItemL4(char* p) 得到各个3元子串出现的次数 void LoadItemL4(char* p)int i;char* s;int j=0;for(i=0;i10;i+)s=*(p+i);if(SizeStr(s)=4)j+;pri
15、ntf(四维子集出现的次数: %dn,j);printf(没有四维的频繁子集，算法结束! n);通过void Support(char* w,int g) 得到关联规则，并输出结果 void Support(char* w,int g)int i,j,k,n=0;char* s;float c=0.8,d=0;memset(cur,0,sizeof(cur);s=w;for(i=0;iSizeStr(s);i+)*(curn+0)=*(s+i);*(curn+1)=0;*(curn+2)=0;*(curn+3)=0;n+;for(i=0;iSizeStr(s);i+)for(j=i+1;jSi
16、zeStr(s);j+)if(*(s+j)=0)break;*(curn+0)=*(s+i);*(curn+1)=*(s+j);*(curn+2)=0;*(curn+3)=0;n+;for(i=0;i10;i+)if(SizeStr(curi)=1)for(j=0;j=c)printf(I%s: %f,curL1i,d);break;if(SizeStr(curi)=2)for(j=0;j=c)printf(I%c,I%c: %f n,curL2j0,curL2j1,d);break;最后通过main函数完成整过程序 int main(int argc, char* argv)int i=0,
17、j=0,k;char buf106;char* p10;char ch;memset(buf,0,sizeof(buf);FILE* fp=fopen(date.txt,r);if(fp=NULL)return 0;ch=fgetc(fp);while(ch!=EOF)if(ch=0xa | ch=0xd)i+;ch=fgetc(fp);j=0;continue;bufij=ch;j+;ch=fgetc(fp);for(k=0;k10;k+)*(p+k)=bufk;LoadItemL1(p);LoadItemL2(p);LoadItemL3(p);LoadItemL4(p);printf(产生
18、关联规则: n);printf(非空子集: 置信度:n);for(i=0;i=2)Support(curL3i,i);return 0;（4）程序输出结果： 四.学习心得体会 关联算法基本原理学习思路简单，只需一步一步找出频集。再通过支持度算出可信度，如对于AC，support=support（A，C），confidence= support（A，C）/support（A）。其中频繁子集的任何子集一定是频繁的，子集频繁父亲一定频繁。相对较难的的部分在于C+代码的实现部分依次实现各个频繁子集，完成整个程序。这学期在商务智能课中学习了数据挖掘的10大算法，数据挖掘十分经典，掌握好一个简单的算法要下很功夫，在今后的工作中一定可以用到，我很庆幸这学期能选到这个课，在这之前听说过数据挖掘但一直没有机会接触，原理容易理解但没接触到以前就没有想过这样考虑问题，学习这个课程以后无论是知识面，智力上都是一个跳跃。还有也提醒我要多复习C+问题的思考，这学期一直忙于网页编程，忘记了上学期说要复习C+数据结构的学习。希望以后还有机会能选到老师的课。