知识挖掘实验报告

实验一、Apriori算法发现频繁项集一、实验目的：1)进一步熟悉Matlab编程算法；2)掌握使用Apriori算法从事物数据库中挖掘频繁项集的方法。二、实验原理：1、Apriori算法Apriori使用一种称作逐层搜索的迭代方法，k项集用于探索（k+1）项集。首先，通过扫描数据库，累计每个项的计数，并收集满足最小支持度的项，找出频繁1项集的集合。该集合记作L1。然后，L1用于找频繁2项集的集合L2，L2用于找L3，如此下去，直到不能再找到频繁k项集。找每个Lk需要一次数据库全扫描。2、提高频繁项集逐层产生的效率Apriori性质：频繁项集的所有非空子集也必须是频繁的。三、实验内容：1、程序框图2、实验内容1)使用Apriori算法编程实现对实验数据中提供的AllElectronics某分店的事物数据库挖掘频繁项集，并在实验报告中写出程序框图；2)产生全部频繁模式，保留其中的闭频繁项集。3)在实验报告中写明各主要程序片段的功能和作用。3、实验步骤1)算法第一次迭代，每项都是候选1项集的集合C1的成员，简单的扫描所有的事物，对每项的出现次数计数；2)按先验的最小支持度计数阈值min_sup=2，确定频繁1项集的集合L1，令i=1，Ni是Li中项的数量；3)调用子函数Join_Prune(Li,min_sup)，存储频繁项集Li；子函数Join_Prune(Li,min_sup)：a)对频繁i项集Li执行连接步，产生候选i+1项集Ci+1；b)对候选i+1项集Ci+1执行剪枝步，产生频繁i+1项集Li+1；c)返回频繁i+1项集Li+1。4)如果Ni+10，则令i=i+1，转到步骤3)；否则，算法结束。4、实验数据AllElectronics某分店的事物数据TID商品ID的列表T100I1,I2,I5T200I2,I4T300I2,I3T400I1,I2,I4T500I1,I3T600I2,I3T700I1,I3T800I1,I2,I3,I5T900I1,I2,I35、实验代码：function[C]=ExamDM1(AllETrans)[M,N]=size(AllETrans);Ni=5;fori=1:NiCC{i,1}=zeros(1,2);endfork=1:N[Mk,Nk]=size(AllETrans{k});fori=1:NkCC{AllETrans{k}(i),1}(1,1)=AllETrans{k}(i);CC{AllETrans{k}(i),1}(1,2)=CC{AllETrans{k}(i),1}(1,2)+1;endendC{1,1}=CC;NC=1;[MC2,NC2]=size(C{1,1});min_sup=2;whileNC=NiNCifMC2=2[C1NC,MC2]=Link(C{1,NC},Ni);%Linkstep.[CC1NC]=ScanCount(C1NC,AllETrans,N,Ni);%Scanningthetransactiondatabasetocountthesupportnumber.[MC3,NC3]=size(CC1NC);NC=NC+1;kk=0;fork=1:MC3%Pronestep.[MC4,NC4]=size(C1NC{k,1});ifCC1NC{k,1}(1,NC4)=min_supkk=kk+1;C{1,NC}{kk,1}=CC1NC{k,1};endendelseNC=Ni+10;endend%Thefollowingislinkfunction.function[C1NC,MC2]=Link(C1,Ni)[MC1,NC1]=size(C1);%C1NC{1,1}=zeros(1,NC1+1);MC2=0;fori=1:MC1-1i[MC1i,NC1i]=size(C1{i,1});Ii=zeros(1,Ni);forii=1:NC1i-1Ii(C1{i,1}(ii))=1;2endforj=i+1:MC1j[MC1j,NC1j]=size(C1{j,1});Ij=zeros(1,Ni);forjj=1:NC1j-1Ij(C1{j,1}(jj))=1;endI=Ii+Ij;N12=zeros(1,2);NC2=0;C12=zeros(1,1);fork=1:NiifI(k)=1N12(1)=N12(1)+1;NC2=NC2+1;C12(1,NC2)=k;endifI(k)=2N12(2)=N12(2)+1;endendC12(1,NC2+1)=0;ifN12(1)-N12(2)==2MC2=MC2+1;C1N{MC2,1}=C12(1,:);endendendC1NC{1,1}=C1N{1,1};MC1NC=1;ifMC2=2fori=2:MC2KM=1;forj=1:MC1NCKM=KM*sum(abs(C1N{i,1}-C1NC{j,1}));endifKM~=0MC1NC=MC1NC+1;C1NC{MC1NC,1}=C1N{i,1}endendend%------------------------------------------------------------------------function[CC1NC]=ScanCount(C1NC,AllETrans,N,Ni)[MC,NC]=size(C1NC);fork=1:N[Mk,Nk]=size(AllETrans{k});IScCo=zeros(1,Ni);forkk=1:NkIScCo(AllETrans{k}(kk))=1;endforkk=1:MC[MCi,NCi]=size(C1NC{kk});C1NCkk1NCi=IScCo(C1NC{kk}(1));ifNCi2fori=2:NCi-1C1NCkk1NCi=C1NCkk1NCi*IScCo(C1NC{kk}(i));endC1NC{kk}(1,NCi)=C1NC{kk}(1,NCi)+C1NCkk1NCi;endendendCC1NC=C1NC;四、实验结果：实验二使用FP增长算法挖掘频繁项集一、实验目的1)进一步熟悉Matlab编程环境；2)掌握使用频繁模式（FP）增长算法从事物数据库中挖掘频繁项集的方法。二、实验原理1、建立频繁模式（FP）树先对事物数据集扫描，得到频繁1项集的集合和支持度计数，并按支持度计数递减对频繁1项集中的各项排序；按每条事物再次扫描事物数据集，依照上次扫描的支持度计数递减排序，从根节点对每个事物创建一条分支（尽量共享已存在的前缀，共享一次节点计数加1），得到频繁模式（FP）树。2、频繁模式树的挖掘过程由每个长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基（一个“子数据库”，由FP树中与后缀模式一起出现的前缀路径集组成），然后，构造它的条件FP树，并递归地进行数据挖掘。模式增长通过后缀模式与条件FP树产生的频繁模式连接实现。三、实验内容：1、程序框图取头指针表中的每个频繁元素在树的各个路径中获得此元素的条件模式基根据这些条件模式基创建FP树树中只有一个节点2、实验内容1)使用Apriori算法编程实现对实验数据中提供的AllElectronics某分店的事物数据库挖掘频繁项集，并在实验报告中写出程序框图；2)产生全部频繁模式，保留其中的闭频繁项集。3)在实验报告中写明各主要程序片段的功能和作用。3、实验步骤1)算法第一次迭代，每项都是候选1项集的集合C1的成员，简单的扫描所有的事物，对每项的出现次数计数；2)按先验的最小支持度计数阈值min_sup=2，确定频繁1项集的集合L1，令i=1，Ni是Li中项的数量；3)调用子函数Join_Prune(Li,min_sup)，存储频繁项集Li；子函数Join_Prune(Li,min_sup)：a)对频繁i项集Li执行连接步，产生候选i+1项集Ci+1；b)对候选i+1项集Ci+1执行剪枝步，产生频繁i+1项集Li+1；c)返回频繁i+1项集Li+1。4)如果Ni+10，则令i=i+1，转到步骤3)；否则，算法结束。4、实验数据AllElectronics某分店的事物数据TID商品ID的列表T100I1,I2,I5T200I2,I4T300I2,I3各条递归路径中头指针表所取频繁元素组成频繁项集，每一层递归的头指针的每个频繁元素都生成一个集合频繁项集挖掘完毕T400I1,I2,I4T500I1,I3T600I2,I3T700I1,I3T800I1,I2,I3,I5T900I1,I2,I35、实验代码：function[C,AllE,FPtree]=ExamDM2(AllETrans)[M,N]=size(AllETrans);Ni=5;CC=zeros(Ni,2);fork=1:N[Mk,Nk]=size(AllETrans{k});%Countingthefrequenceoftheitems.fori=1:NkCC(AllETrans{k}(i),1)=AllETrans{k}(i);CC(AllETrans{k}(i),2)=CC(AllETrans{k}(i),2)+1;endendC=zeros(Ni,3);fori=1:Ni%Arrangetheitemsaccordingtofrequencesequencedegression.[A,P]=max(CC(:,2));C(P,1)=i;C(i,2:3)=CC(P,:);CC(P,2)=-2*i;endfork=1:N%Arangetheitemsofeachtransactionaccordingtofrequencesequencedegression.CR=zeros(1,Ni);[Mk,Nk]=size(AllETrans{k});fori=1:NkCR(C(AllETrans{k}(i),1))=AllETrans{k}(i);endj=0;fori=1:NiifCR(i)0.5j=j+1;AllE{k}(j)=CR(i);endendendR=0;FPtree{1,1}=zeros(1,5);fork=1:N%Createfrequentpatterntree[Mk,Nk]=size(AllE{k});J=ones(1,Nk);kifFPtree{1,1}(1,2)1%FPtreeisacellmatricsforexpressingFPtree.FPtree{1,1}=[01111];%ThefirstelementofeachcellinFPtreeisthenameofitem.R=R+1;%ThesecondelementofeachcellinFPtreeisthefrequentnumberoftheitem.fori=1:NkFPtree{1,i+1}=[AllE{k}(i)1RiR];endFPtree{1,i+1}(5)=0;%ThethirdelementofeachcellinFPtreeistherowpositionofformercell.else%TheforthelementofeachcellinFPtreeisthecolumnpositionofformercell.FPtree{1,1}(1,2)=FPtree{1,1}(1,2)+1;fori=1:Nk%ThefifthelementofeachcellandthefollowersinFPtreeisthecolumnpositionofthefollowercell.[Mfp,Nfp]=size(FPtree{J(i),i});ifFPtree{J(i),i}(Nfp)==0FPtree{R,i+1}=[AllE{k}(i)1J(i)i0];FPtree{J(i),i}(Nfp)=R;J(i+1)=R;elsej=5;iwhilej=NfpifFPtree{FPtree{J(i),i}(j),i+1}(1)==AllE{k}(i)FPtre