matlab实现apriori算法源代码

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

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

3、项之间的关联规那么即根据一个事务中某些项的出现, 可推导出另一些项在同一事务中也出现。四、Apriori 算法Apriori 算法的第一步是简单统计所有含一个元素的项集出现的频率 , 来决定最大的一 维工程集。在第 k 步,分两个阶段 ,首先用一函数 sc_candidate( 候选), 通过第 (k-1) 步中生 成的最大工程集Lk-i来生成侯选工程集G。然后搜索数据库计算侯选工程集G的支持度.为了更快速地计算 G中工程的支持度,文中使用函数count_support计算支持度。Apriori 算法描述如下：(1) C 1=candidate1-itemsets;(2) L i=c C &g

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

5、k其中，D表示数据库；min support表示给定的最小支持度；resultset表示所有最大工程集。Sc_candidate 函数该函数的参数为Lk-i,即：所有最大k-1维工程集,结果返回含有k个工程的侯选工程集G。事实上,Ck是k维最大工程集的超集,通过函数count_support计算工程的支持度,然后 生成Lk。该函数是如何完成这些功能的，详细说明如下：首先，通过对Lk-i自连接操作生成 G,称join连接步,该步可表述为：insert into C kselect12,. k-1k-1 from L k-1 P,Lk-1 Qwhere 11,. k-2k-2k-1k-1假设用集合

6、表示：Ck=XU 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 cifs 不属于 Lk-1 then delete c from Ck；用集合表示:Ck=X G|X的所有k-1维子集在Lk-1中例如说明Apriori算法运作过程，有一数据库D,其中有四个事务记录，分别表示为TIDItemsT1I1,I3,I4T2I2,I3,I5T3I1,I2,I3,I5T4I

7、2,I5在Apriori算法中每一步创立该步的侯选集。统计每个侯选工程集的支持度，并和预定义的最小支持度比拟，来确定该步的最大工程集。首先统计出一维工程集，即C.这里预定义最小支持度minsupport=2,侯选工程集中满足最小支持度要求的工程集组合成最大的1-itemsets。为生成最大的2-itemsets,使用了sc_candidate函数中join 步，即：L1joinL 1,并通过prune步删除那些 G的那些子集不在L1中的工程集。生成了侯选工程集C2。搜索D中4个事务，统计C2中每个侯选工程集的支持度。然后和最小支持度比拟，生成L2。侯选工程集C3是由L2生成.要求自连接的两个最

8、大2-itemsets 中,第一个工程相同，在L2中满足该条件的有12,13,12,15.这两个集合经过join 步后，产生集合I2 , I3 ,15.在 prune 步中，测试I2 , I3 , I5的子集I3 , 15,12,13,12,15是否在 L2中，由 L2可以知道13,15,12,13,12,15本身就是最大 2-itemsets.即12,13,15的子集都是最大工程集.那么12,13,15 为侯选3-itemset.然后搜索数据库中所有事务记录，生成最大的3-tiemsets L3。此时，从L3中不能再生成侯选4-itemset 。Apriori算法结束.算法的图例说明/XPR

9、IORI 算江rmTI11 J3J41212.I3J513II 1 I2J3J5T412.15Di SI M'fl ?.耳如、垃雀亠 介醉龙at 纤芒电Anij2H3I5wi3tM1l<5|3m/gfP.时松于茯扯叶g之曲rV-fft(IHJ(12)3:】用3“再3曲対"*0承小上£1厚丈次血t Jt持反计小</v ir持反计直盘玄持度il St；11. 13412> 13(412. 15!13. I5JE/ J Z空订我(112. 13. 15)17777五、实验结果test.txt格式及内容如下:test tirt -记事本文件桎聒式W幣助!b

10、read milk beeTbread diaper beer egg itilk mili diaper beer cook bTead milk diapeT beer bzead. milk diapex cook beei bread butter diaper inilk coffee sveat cookie fish br&ad butier coffee diaper milk egg bread butter fish chickenugg bxcd Luttexfisrh diaper milkbxoad! oa owGiii： og思 coffee svat ch

11、icken ;g briaid di apT nilk 書毎 1 十 bT t阳 egg cookie diaper milk实验结果如下:gtnnund WindowMB s两足妾T旳F店姣餐崇帀*为'beer''di"ni IF"eiapsrFIT'iKLlk'EH0 馬号丑班fr 3戏旳蚩畫苗味玄为't ser"'匕E：日f"diaper1wir六、实验总结Apriori算法可以很有效地找出数据集中存在的关联规那么且能找出最大项的关联规那么， 但从以上的算法执行过程可以看到Apriori算法的

12、缺点：第一,在每一步产生侯选工程集时循环产生的组合过多，没有排除不应该参与组合的元 素；第二，每次计算项集的支持度时，都对数据库D中的全部记录进行了一遍扫描比拟，如果是一个大型的数据库的话，这种扫描比拟会大大增加电脑系统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此人们开始寻求一种能减少这种系统 I/O开销的更为快捷的算法。七、实验程序fun cti on my_apriori(X,m in sup)clc;%主函数，输入 X数据集，判断产生大于min sup最小支持度的关联规那么%翻开文件file = textread('test.txt',

13、9;%s','delimiter','n','whitespace',)；m, n=size(file);for i=1:mwords二strread(filei,'%s','delimiter','');words二words'Xi二words;end%minsup=0.3; %预先定义支持度m,N=size(X); % 求 X 的维数temp=X1; %用已暂存变量存储所有不同项集for i=2:Ntemp二u nion (temp,Xi); % 找岀所有不同项种类end% 找岀

14、 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)%示disp(Ci,1);%部end% 分%L=gen_rule(C);%依次产生k-频繁项(依据apriori算法规那么%各个子程

15、序如下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;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)co

16、un t(i)=co un t(i)+1;endendend%删除数据表中不频繁的项p=1;C=cell(1);for i=1:mif(cou nt(i)>mi nsup*M)%小于支持度的项为不频繁数，将删除，大于的保存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;f

17、or 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,m