matlab实现apriori算法源代码

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

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

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

4、port;for(k=2,L k-1 工 ,k+)/直到不能再生成最大项目集为止(4) C k=sc_candidate(Lk-1 );/生成含 k 个兀素的侯选项目集(5) for all transactions t?D/ 办理处理(6) Ct=count_support(Ck,t);/包含在事务t 中的侯选项目集(7) for all candidates c? Ct(8) c.count=c.count+1;(9) next(10) L k=c ? Ck|c.count> min support;(11) next(12) resultset=resultsetU Lk其中 ，D

5、 表示数据库； min support 表示给定的最小支持度；resultset表示所有最大项目集。Sc_candidate函数该函数的参数为Lk-i ,即 ：所有最大 k-1 维项目集 , 结果返回含有k 个项目的侯选项目集G。事实上 ,Ck 是 k 维最大项目集的超集, 通过函数 count_support 计算项目的支持度 , 然后 生成 Lk。该函数是如何完成这些功能的，详细说明如下 ：首先 ，通过对 Lk-i 自连接操作生成G,称 join （连接）步 ,该步可表述为 ：insert into Ckselect P.item1,P.item2,.,P.itemk-1 ,Q.itemk

6、-1 from Lk-1 P,Lk-1 Qwhere P.item1=Q.item1,.,P.itemk-2=Q.itemk-2 ,P.itemk-1 <Q.itemk-1若用集合表示 ：Ck=X U X'|X,X'?Lk-1 ,|X n X'|=k-2然后 ,是 prune （修剪 ）步，即对任意的 c,c ?G, 删除 G 中所有那些 （k-1 ）维子集不在Lk-1 中的项目集 ，得到侯选项目集G。表述为：for all itemsetc?Gfor all （k-1 ） 维子集s of cif（s 不属于Lk-1 ） then delete c from Ck

7、；用集合表示 :C k=X ?G|X 的所有 k-1 维子集在 Lk-1 中 2.Apriori 算法的举例示例说明 Apriori 算法运作过程，有一数据库D,其中有四个事务记录，分别表示为TIDItemsT1T2T3I1,I3,I4I2,I3,I5I1,I2,I3,I5T4I2,I5在 Apriori 算法中每一步创建该步的侯选集。统计每个侯选项目集的支持度，并和预定义的最小支持度比较，来确定该步的最大项目集。首先统计出一维项目集，即 C.这里预定义最小支持度minsupport=2, 侯选项目集中满足最小支持度要求的项目集组合成最大的1-itemsets。为生成最大的2-itemsets

8、, 使用了sc_candidate函数中 join 步，即： L1joinL 1 , 并通过 prune 步删除那些G 的那些子集不在L1 中的项目集。生成了侯选项目集C2。搜索 D 中 4 个事务 ，统计 C2 中每个侯选项目集的支持度。然后和最小支持度比较，生成 L2。侯选项目集C3 是由 L2 生成 .要求自连接的两个最大2-itemsets 中,第一个项目相同 ，在 L2 中满足该条件的有12,13,12,15.这两个集合经过join 步后 ，产生集合 I2 ,I3 ,I5. 在 prune 步中 ，测试 I2 ,I3 ,I5 的子集 I3 ,15,12,13,12, 15 是否在L2

9、 中，由 L2 可以知道 13,15,12,13,12,15本身就是最大2-itemsets.即12,13,15的子集都是最大项目集.那么 12,13,15 为侯选 3-itemset. 然后搜索数据库中所有事务记录 ，生成最大的3-tiemsets L3。此时 ，从 L3 中不能再生成侯选4-itemset 。Apriori算法结束 .算法的图例说明APRIOR I 算法Pi hlI :'TinII 九 144/T/ 订-数T1212UH12.13.15313g11 J2.IJJ53T4i<3JI2J51(I4J1 呷3EL t 严生法超。比羊 M祕迅支対反计员豎持魁订数妙無m

10、 uiEH - 121)；11. 13J411 TJ2l2 r 13：4tri .附I!A2 罚212. 口2“3* 15JI2 + 15|J13. I5f2占 H关噫文超该计举乩JK 小夬箱灰汁致f/ ?<% fJ T K2五、实验结果test.txt格式及内容如下 :test.bct -记事本文件 （B 稠稻式回童看世 J 穂助 （tbread fflilk beer bread diaper beer nilk mills diaper beer cookbrtad milk diaper beer brtad milk diaper cook beer bread butter

11、diaper milk coffee sveat cookie fish bx&d butter coftse diaper milk egg bi&d but ter fish chickenegg bxbvttcxfish diaper milkbcred tea sveat efg coffee surest chicken egbred di apex milk salt beer tea egs zookie diaper aiilk实验结果如下 :Smnund Windowr" h rar""di apei j ，'bror&#

12、39;? ni Uf' iitQP日F5 MWFITFdiap? if'P KLlkrXis'石諒裏熨工 拄師蜀殛 SE 铁 : 乂為'HE 対' beead'"h f? breid'?wir六、实验总结Apriori 算法可以很有效地找出数据集中存在的关联规则且能找出最大项的关联规则，但从以上的算法执行过程可以看到Apriori 算法的缺点 ：第一 ,在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素；第二 ，每次计算项集的支持度时，都对数据库D 中的全部记录进行了一遍扫描比较，如果是一个大型的数据库的话

13、，这种扫描比较会大大增加计算机系统的I/O 开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。I/O 开销的更为快捷的算法。七、实验程序fun cti on my_apriori(X,m in sup)clc;% 主函数，输入X 数据集，判断产生大于min sup 最小支持度的关联规则%打开test.txt 文件n','whitespace',；”)m, n=size(file);for i=1:mwords 二 strread(filei,'%s','delimiter','');words 二 words&

14、#39;Xi 二 words;end%minsup=0.3; %预先定义支持度因此人们开始寻求一种能减少这种系统%找岀k-频繁项L=Sc_candidate(temp);% 找岀2- 项候选项集sum=1;% 统计满足条件的最多项集while( ? isempty(L1) %循环终止条件为第k 次频繁项集为空sum=sum+1;C=cou nt_support(L,X,mi nsup);% 挑选岀满足最小支持度的k-频繁项%sprintf('%s%d%s','满足要求的 ',sum,' 次频繁项集依次为')% 显for i=1:size(C,1)

15、% 示disp(Ci,1);% 部end% 分%L=gen_rule(C);%依次产生k-频繁项 ( 依据 apriori 算法规则 )m,N=size(X); %求 X 的维数temp=X1; % 用已暂存变量存储所有不同项集for i=2:Ntemp 二 u nion (temp,Xi); %找岀所有不同项( 种类 )endEnd%各个子程序如下function y=cell_union(X,Y)% 实现两 cell 元组合并功能 ， 由 k-1 项集增加到 k 项集函数m,n=size(X);if(? iscellstr(X) % 判断 X 是否元组L1=X;L1,2=Y;elseL=X

16、;L1, n+1=Y;endy=L;%fun cti on y二 co un t_support(L,X,m in sup)% 找出符合大于支持度sup 的候选集丄为候选集， X 为总数据集X=X'% 转置%统计频繁项m,n=size(L);M,N=size(X);coun t=zeros(m,1);for i=1:mfor j=1:Mif(ismember(Li,Xj)coun t(i)=co un t(i)+1;endendend%删除数据表中不频繁的项p=1;C=cell(1);for i=1:mif(cou nt(i)>mi nsup*M)% 小于支持度的项为不频繁数，将

17、删除 ， 大于的保留Cp=Li;p=p+1;endendy=c'fun ction y=gen_rule(C) %apriori算法规则判断是否产生k- 候选项集if(isempty(C1) %判断C 是否为空%M,N=size(C);m,n=size(C1);temp1=C;L=cell(1);for i=1:Mtemp2i=temp1i n;temp1in=;endp=1;for i=1:Mfor j=i+1:Mif(isequal(temp1i,temp1j)% 判断前k-1 项候选集是否相等Lp=cell_u nion (Ci,temp2j);% 若相等，则增加至 k-项集p=p+1;endendendy=L'elsey=cell(1);% 否则 y 返回空end%function y=Sc_candidate(C)% 产生2- 项候选集函数C=C' % 转置m, n=size(C);bcou nt=zeros(m*(m-1)/2,1);L=cell(m*(m-1)/2,1);p=1;for i=1:m-1% 注意for j=i+1:mLp=cell_union(Ci,Cj); %产生2- 项候选集p=p+1;endendy=L;fun cti on y=co un t_support(L,X,