关联规则挖掘--AP算法.doc

模式识别与应用期中设计报告设计题目：关联规则挖掘实验班 级： 姓 名： 学 号： 指导教师： 1 实验目的（1）理解频繁模式挖掘的思想；（2）理解Apriori挖掘算法的原理；2 实验步骤2.1 算法原理Aprior使用一种称作逐层搜索的迭代方法，K项集用于搜索（K+1）项集。首先，通过扫描数据库，累积每个项的计数，并收集满足最小支持度的项，找出频繁1项集的集合。该集合记作L1。然后，L1用于寻找频繁2项集的集合L2，L2用于寻找L3，如此下去，直到不能再找到频繁K项集。为提高频繁项集逐层产生的效率，一种称作Apriori的重要性质用于压缩搜索空间。Apriori性质：频繁项集的所有非空子集也必须是频繁的。如何在算法中使用Apriori性质？主要有两步过程组成：连接步和剪枝步。(1) 连接步：为找L(k),通过将L(k-1)与自身连接产生候选K项集的集合。该候选项集合记作C(K)。设l1和l2是L(k-1)中的项集。记号l(i)j表示l(i)中的第j项。执行L(k-1)连接L(k-1)，如果它们的前（K-2）项相同的话，其中L(k-1)的元素是可连接的。(2) 剪枝步：为压缩C(K)，可以用Apriori的性质：任何非频繁的（K-1）项集都不是频繁K项集的子集。因此，如果候选K项集的（K-1）项子集不在L(k-1)中，则该候选也不可能是频繁的，从而可以从C(K)中删除。2.2 算法步骤算法第一步是简单统计所有含一个元素的项集出现的频率，来决定最大的一维项目集，在第k步，分两个阶段，首先用一函数sc_candidate,通过第（k-1）步中生成最大项目集来生成候选项目集，然后搜素数据库计算候选项目集的支持度。Apriori算法描述如下：（1） =candidate 1-itemset;（2） =c|c.countminsupport;（3） For (k=2,k+）（4） =sc_candidate();（5） for all transaction tD（6） =count_support(,t)（7） for all candidates c（8） c.count=c.count + 1;（9） next（10） =c|c.countminsupport;（11） Next（12） Resultset=resultset 其中，D表示数据库；minsupport表示给定的最小支持度；resultset表示所有最大项目 集。k-itemset表示k维项目集；：具有最小支持度的最大k-itemset；：候选的k- itemset(潜在最大项目集)2.3模型的建立和求解模型一：基于Apriori算法的关联规则挖掘模型1. 模型的准备 设: I= i1,i2.,im 是所有项目的集合. D是所有事务的集合(即数据库), 每个事务T是一些项目的集合, T包含在D中, 每个事务可以用唯一的标识符TID来标识.设X为某些项目的集合,如果X包含在T中,则称事务T包含X,关联规则则表示为如下形式(X包含在T)=(Y包含在T)的蕴涵式,这里X包含在I中, Y包含在I中,并且XY=.其意义在于一个事务中某些项的出现,可推导出另一些项在同一事务中也出现(为简单化,将(X包含在T)=(Y包含在T)表示为X=Y,这里,= 称为关联操作，X称为关联规则的先决条件,Y称为关联规则的结果). 事务数据库D中的规则X=Y是由支持度s（support）和置信度c(confidence)约束,置信度表示规则的强度, 支持度表示在规则中出现的频度。数据项集X的支持度s(X)是D中包含X的事务数量与D的总事务数量之比, 但为下文便于叙述, 数据项集X的支持度是用数据库D中包含X的数量来表示; 规则X=Y的支持度s定义为: 在D中包含XY的事务所占比例为s%, 表示同时包含X和Y的事务数量与D的总事务量之比。用该项集出现的次数除以TID总数即可得到，用如下公式表示：Support(X)=Count(X)/Count(TID) 规则X=Y的置信度c定义为: 在D中,c%的事务包含X的同时也包含Y, 表示D中包含X的事务中有多大可能性包含Y. 依据所求的频繁项集，及所求得的支持度，运用如下公式求解：Confidence(X=Y)=Support(XY)/Support(X) 最小支持度阈值minsupport表示数据项集在统计意义上的最低主要性. 最小置信度阈值mincontinence表示规则的最低可靠性. 如果数据项集X满足X.support=minsupport, 则X是大数据项集. 一般由用户给定最小置信度阈值和最小支持度阈值.置信度和支持度大于相应阈值的规则称为强关联规则, 反之称为弱关联规则. 发现关联规则的任务就是从数据库中发现那些置信度、支持度大小等于给定值的强壮规则. 基于上述概念，我们可以很容易得到一些基本结论: (1) K维数据项集XK是频繁项集的必要条件是它所有K-1维子项集也为频繁项集，记为XK-1（2） 如果K维数据项集XK的任意一个K-1维子集XK-1，不是频繁项集，则K维数据项集XK本身也不是最大数据项集。 (3) XK是K维频繁项集，如果所有K-1维频繁项集集合XK-1中包含XK的K-1维子项集的个数小于K，则XK不可能是K维最大频繁数据项集。 证明: 很明显，数据项集XK-1:的K-1维子项集的个数为K-1。如果高频繁数据项集XK-1，中包含XK的K-1.维子项集的个数小于K，则存在XK的K-1维子项集不是频繁数据项集，由结论(2)知K维数据项集本身也不是高频繁数据项集。2.3 程序流程图程序的主体部分首先接收用户输入的最小支持度，之后读取原始数据。产生频繁1项集的集合，之后用产生候选，以找出，其中k=2;如图1所示是Apriori算法的程序流程图。图1 Apriori算法流程图运行结果：程序代码：Apriori.m：function rules_left, rules_right = Apriori(dataset, min_sup, min_conf)%Apriori算法计算频繁项集以及关联规则%-变量-%literals = unique(dataset);%找出所有的项，包含0L1 = zeros(0,1);%1-频繁项集supports = zeros(0,1);%频繁项集对应的支持度L = zeros(0,size(literals,1);%频繁项集kborder = zeros(0,2);%记录k-频繁项集在L中的边界bordercount = 0;%辅助记录kborder%-生成L1-%for i = 1 : size(literals,1) if(literals(i) = 0)%对0项不做处理 continue; end index = find(dataset = literals(i);%找出包含项litertals(i)事务的下标 if(size(index,1) = min_sup)%若大等于最小支持度 itemtemp = literals(i),zeros(1, size(literals,1)-1); L = L; itemtemp;%所有项集 bordercount = bordercount + 1; L1 = L1; literals(i);%1-项集 supports = supports; size(index,1);%1-项集对应支持度 endend kborder(1,:) = 1,bordercount;%-迭代计算k-频繁项集-%k = 2;%首先利用L1计算L2while(1) KL = L(kborder(k-1,1):kborder(k-1,2),:);%取出Lk-1 kborder(k,1) = bordercount + 1; %记录下Lk在L中的起始下标 for i = 1 : size(KL,1) - 1%Lk-1连接运算 for j = i + 1: size(KL,1) if(isequal(KL(i,1:k-2),KL(j,1:k-2) = 1)%满足连接条件 itemtemp = sort(KL(i,1:k-2),KL(i,k-1),KL(j,k-1); if(all(ismember(combnk(itemtemp,k-1),KL(:,1:k-1),rows) = 1)%使用apriori性质剪枝-k-频繁项集的所有k-1-项子集都是频繁项集 suptemp = CheckSup(dataset,itemtemp);%计算该项集的支持度 if(suptemp = min_sup)%满足频繁条件 itemtemp = itemtemp,zeros(1,size(literals,1)-size(itemtemp,2);%末尾补0 L = L;itemtemp;%加入频繁项集 bordercount = bordercount + 1;%Lk的项集个数+1 supports = supports;suptemp; end end end end end kborder(k,2) = bordercount; if(kborder(k,1) kborder(k,2) %若Lk为空则终止计算 break; end k = k + 1;endPrintFrequentItemset(L,supports);%打印频繁项集及其对应支持度%-产生关联规则-%rules_left = zeros(0,size(literals,1) - 1);%产生式左部rules_right = zeros(0,size(literals,1) - 1);%产生式右部for i = kborder(2,1) : size(L,1)%对k=2-频繁项集的每个项集产生关联规则 l = nonzeros(L(i,:); sup_l = supports(i); for j = 1 : size(l,2) - 1%关联式左部项的个数由1到（项集项数-1） l_subset = combnk(l,j);%项集l的j项子集集合 for k = 1 : size(l_subset,1) s = l_subset(k,:);%左部项 sup_s = FindSup(s, L, supports);%找对应频繁项集的支持度 if(sup_l / sup_s = min_conf)%满足强关联条件 ltemp = s,zeros(1, size(literals,1)-1-size(s,2); rules_left = rules_left; ltemp; l_s = setdiff(l,s);%右部项，即项集-左部项剩余的项 rtemp = l_s,zeros(1, size(literals,1)-1-size(l_s,2); rules_right = rules_right; rtemp; end end endend Main.m：clear;clc; load testdata.mat%读入事务矩阵（每行代表一个事务，每列代表一个项）PrintTransactions(testdata);%打印出事务min_sup = 2;%初始化最小支持度min_conf = 0.7;%初始化最小置信度rules_left, rules_right = Apriori(testdata, min_sup, min_conf);%运算Apriori算法PrintRules(rules_left, rules_right);%打印强关联规则PrintTransactions.m：function PrintTransactions(dataset)%打印事务fprintf(-Transaction List-n);for i =1:size(dataset,1)%获取事务的个数（此处为矩阵的行数），第i个事务 fprintf(T%2d: ,i); items = nonzeros(dataset(i,:);%取事务中的项（即矩阵每行的非零元素） %输出事务列表 for j=1:size(items,1)%第j项 fprintf(%d, dataset(i, j); if(j = size(items,1) fprintf(n); else fprintf(, ); end end endfprintf(-nn);PrintRules.m：function PrintRules(rules_left, rules_right)%打印关联规则fprintf(-Rules-n);for i =1:size(rules_left,1) fprintf(R%2d: ,i); items = nonzeros(rules_left(i,:);%打印规则左部 for j=1:size(items,1) fprintf(%d, rules_left(i, j); if(j = size(items,1) fprintf( = ); else fprintf(, ); end end items = nonzeros(rules_right(i,:);%打印规则右部 for j=1:size(items,1) fprintf(%d, rules_right(i, j); if(j = size(items,1) fprintf(n); else fprintf(, ); end endendfprintf(-nn);PrintFrequentItemset.m：function PrintFr