matlab实现apriori算法源代码

1、matlab 实现 apriori 算法源代码、实验目的通过实验，加深数据挖掘中一个重要方法一一关联分析的认识，其经典算法为 apriori算法，了解影响 apriori 算法性能的因素，掌握基于 apriori 算法理论的关联分析的原理和方法。、实验内容对一数据集用 apriori 算法做关联分析，用 matlab 实现。三、方法手段关联规则挖掘的一个典型例子是购物篮分析。市场分析员要从大量的数据中发现顾客放入其购物篮中的不同商品之间的关系。如果顾客买牛奶，他也购买面包的可能性有多大？什么商品组或集合顾客多半会在一次购物时同时购买？例如，买牛奶的顾客有 80 灿同时买面包，或买铁锤白顾客中有

2、 70%勺人同时也买铁钉，这就是从购物篮数据中提取的关联规则。分析结果可以帮助经理设计不同的商店布局。一种策略是：经常一块购买的商品可以放近一些，以便进一步刺激这些商品一起销售，例如，如果顾客购买计算机又倾向于同时购买财务软件，那么将硬件摆放离软件陈列近一点，可能有助于增加两者的销售。另一种策略是：将硬件和软件放在商店的两端，可能诱发购买这些商品的顾客一路挑选其他商品。关联规则是描述数据库中数据项之间存在的潜在关系的规则，形式为AAA2A.nAmnBABa八Bn,其中A(i=1,2.,m)Aj(j=1,2.,n)是数据库中的数据项数据项之间的关联规则即根据一个事务中某些项的出现，可推导出另一些

3、项在同一事务中也出现。四、Apriori算法1 .算法描述Apriori 算法的第一步是简单统计所有含一个元素的项集出现的频率，来决定最大的一维项目集。在第 k 步，分两个阶段，首先用一函数 sc_candidate（候选），通过第（k-1）步中生成的最大项目集 Lk-1来生成侯选项目集 Q。然后搜索数据库计算侯选项目集 Q 的支持度.为了更快速地计算 G 中项目的支持度，文中使用函数 count_support 计算支持度。Apriori 算法描述如下：(1) C1=candidate1-itemsets;(2) L1=cCC|c.countminsupport;for(k=2,Lk-1w，

4、k+)/直到不能再生成最大项目集为止(4)Ck=sc_candidate(Lk-1);/生成含 k 个元素的侯选项目集foralltransactionstCD/办理处理(6)Ct=count_support(Ck,t);/包含在事务 t 中的侯选项目集forallcandidatescCt(8) c.count=c.count+1;(9) next(10) Lk=cCCk|c.countminsupport;(11) next(12) resultset=resultsetULk其中，D 表示数据库；minsupport 表示给定的最小支持度；resultset 表示所有最大项目集。Sc_c

5、andidate 函数该函数的参数为 Lk-i,即： 所有最大 k-1 维项目集， 结果返回含有 k 个项目的侯选项目集 Q。 事实上，Ck是 k 维最大项目集的超集，通过函数 count_support 计算项目的支持度，然后生成 Lk。该函数是如何完成这些功能的，详细说明如下：首先，通过对 Lk-i自连接操作生成 Ck,称 join（连接）步，该步可表述为：insertintoCkselectP.item1,P.item2,P.itemk-1,Q.itemk-1fromLk-1P,Lk-1QwhereP.item 产 Q.item1,P.itemk-2=Q.itemk-2,P.itemk-

6、1Q.itemk-1若用集合表示：Ck=XUX|X,XeLk-1,|XnX|=k-2然后，是 prune（修剪）步，即对任意的 c,cCQ,删除 G 中所有那些（k-1）维子集不在 Lk-1中的项目集，得到侯选项目集 Q。表述为：forallitemsetcCQforall（k-1）维子集 sofcif（s 不属于 Lk-1）thendeletecfromCk;用集合表示：Ck=XCC|X 的所有 k-1 维子集在 Lk-1中2.Apriori 算法的举例示例说明 Apriori 算法运作过程，有一数据库 D,其中有四个事务记录，分别表示为TIDItemsT1I1,I3,I4丁2I2,I3,I

7、5T3I1,I2,I3,I5T4I2,I5在 Apriori 算法中每一步创建该步的侯选集。统计每个侯选项目集的支持度，并和预定义的最小支持度比较，来确定该步的最大项目集。首先统计出一维项目集，即 C.这里预定义最小支持度 minsupport=2,侯选项目集中满足最小支持度要求的项目集组合成最大的 1-itemsets。为生成最大的 2-itemsets,使用了sc_candidate 函数中 join 步，即：L1joinL1,并通过 prune 步删除那些 G 的那些子集不在 L1中的项目集。生成了侯选项目集 G。搜索 D 中 4 个事务，统计 C2中每个侯选项目集的支持度。然后和最小支

8、持度比较，生成匕。侯选项目集。是由 L2生成.要求自连接的两个最大2-itemsets 中，第一个项目相同，在 L2中满足该条件的有I2,I3,I2,I5.这两个集合经过join 步后，产生集合I2,I3,I5.在 prune 步中，测试I2,I3,I5的子集I3,I5,I2,I3,I2,I5是否在 L2中，由 L2可以知道I3,I5,I2,I3,I2,I5本身就是最大 2-itemsets.即I2,I3,I5的子集都是最大项目集.那么I2,I3,I5为侯选 3-itemset.然后搜索数据库中所有事务记录，生成最大的 3-tiemsetsL3。此时，从 L3中不能再生成侯选 4-itemse

9、t。Apriori 算法结束.算法的图例说明APRIORI算法五、实验结果test.txt 格式及内容如下:test.txt-记事本文件（B 领格式查看 M 帮助（LbreadmilkbeerbreaddiaperbeereggmilkmilkdiaperbeexcookbreadmilkdiaperbeerbxsadmilkdiapercookbeerbreadbuttexcoffeesveatbxeadbutterbreadbuttererFnllEbreaddiaperrbread.diaper1,jiilkp满足要求的 3次盛繁项箪依次为beer1breadriiilkbeer,dia

10、peritilkbreaddiaperrTiilkr六、实验总结Apriori 算法可以很有效地找出数据集中存在的关联规则且能找出最大项的关联规则，但从以上的算法执行过程可以看到 Apriori 算法的缺点：第一，在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素；第二，每次计算项集的支持度时，都对数据库 D 中的全部记录进行了一遍扫描比较，如果是一个大型的数据库的话，这种扫描比较会大大增加计算机系统的 I/O 开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此人们开始寻求一种能减少这种系统I/O 开销的更为快捷的算法。七、实验程序functionmy_a

11、priori(X,minsup)clc;%主函数，输入 X 数据集，判断产生大于 minsup 最小支持度的关联规则%打开 test.txt 文件file=textread(test.txt,%s,delimiter,n,WhitespaceJ);m,n=size(file);fori=1:mwords=strread(filei,%s,delimiter,);words=words;Xi二 words;end%minsup=0.3;%预先定义支持度m,N=size(X);%求 X 的维数temp=X1;%用已暂存变量存储所有不同项集fori=2:Ntemp=union(temp,Xi);%找

12、出所有不同项(种类)end%找出 k-频繁项L=Sc_candidate(temp);%找出 2-项候选项集sum=1;%统计满足条件的最多项集while(isempty(L1)%循环终止条件为第 k 次频繁项集为空sum=sum+1;C=count_support(L,X,minsup);%挑选出满足最小支持度的 k-频繁项%sprintf(%s%d%s,满足要求的,sum,次频繁项集依次为)%显fori=1:size(C,1)%示disp(Ci,1);%部end%分%L=gen_rule(C);%依次产生 k-频繁项(依据 apriori 算法规则)End%各个子程序如下functiony

13、=cell_union(X,Y)%实现两 cell 元组合并功能，由 k-1 项集增加到 k 项集函数m,n=size(X);if(iscellstr(X)%判断 X 是否元组L1=X;L1,2=Y;elseL=X;L1,n+1=Y;endy=L;%functiony=count_support(L,X,minsup)%找出符合大于支持度 sup 的候选集,L 为候选集，X 为总数据集X=X;%转置%统计频繁项m,n=size(L);M,N=size(X);count=zeros(m,1);fori=1:mforj=1:Mif(ismember(Li,Xj)count(i)=count(i)+

14、1;endendend%删除数据表中不频繁的项p=1;C=cell(1);fori=1:mif(count(i)minsup*M)%小于支持度的项为不频繁数，将删除，大于的保留Cp=Li;p=p+1;endendy=C;%functiony=gen_rule(C)%apriori 算法规则判断是否产生 k-候选项集if(isempty(C1)%判断 C 是否为空M,N=size(C);m,n=size(C1);temp1=C;L=cell(1);fori=1:Mtemp2i=temp1in;temp1in=;endp=1;fori=1:Mforj=i+1:Mif(isequal(temp1i,

15、temp1j)%判断前 k-1 项候选集是否相等Lp=cell_union(Ci,temp2j);%若相等，贝 U 增加至 k-项集p=p+1;endendendy=L;elsey=cell(1);%否则 y 返回空end%functiony=Sc_candidate(C)%产生 2-项候选集函数C=C;%转置m,n=size(C);bcount=zeros(m*(m-1)/2,1);L=cell(m*(m-1)/2,1);p=1;fori=1:m-1%注意forj=i+1:mLp=cell_union(Ci,Cj);%产生 2-项候选集p=p+1;endendy=L;functiony=count_support(L,X,minsup)%