数据挖掘上机报告 - 图文(3)

第二次上机训练内容

本次上机主要训练如何实现关联规则 Apriori 算法，训练前需掌握如何按算法流程对实 例进行手工计算，例如，之前布置的课后作业：

? 已知交易记录数据库 D 中有 9 条交易记录（事务）： ? T1：A，B，E T2：B，D T3：B，C T4：A，B，D ? T5：A，C T6：B，C T7：A，C T8：A，B，C，E ? T9：A，B，C

? 设定最小支持度为 20%，最小可信度为 60%，找出所有的强规则并计算其支持度和 可信度

在对以上类型的问题进行关联规则挖掘时，需要考虑以下算法实现的问题： （1）首先考虑如何用（-1/0/1）表示事务集、频繁集、关联规则； （2）其次考虑创建两个函数，分别计算项集的支持度和可信度； （3）然后考虑如何得到所有的频繁项集；

（4）最后考虑如何从所有频繁集中找出强关联规则。 提示 ：

1、此算法的接口可定义为：

[R,sup,conf]=Apriori(D,min_sup,min_conf)

其中输入变量分别为事务集、最小支持度和最小可信度，输出分别为强规则、支持度和 可信度。在作业中的例子中，事务集的可表示为： D(1:4, :)=[1,1,0,0,1; 0,1,0,1,0; 0,1,1,0,0; 1,1,0,1,0]; 输出的强规则由-1/0/1 组成，类似有如下形式： R=[-1, 1, 0, -1, 0]

此规则的含义是 A,D?B。

2、创建的计算支持度的函数有如下形式： sup=compute_sup(S, D)

其中 S 为要计算支持度的项集，由 0/1 组成，有类似于上一条中 R 的形式。

现在假设 S=[1, 0, 1, 0,0]，则其计算支持度时需要顺序与 D 中的每一行进行比较，比较 的公式如下：

判断：all(D(i, :)-S)==true，如成立则支持度计数增加1，否则不增加。 3、此问题的算法实现过程可能用到的 matlab 函数包含： eye, all, find, size, zeros, nchoosek 原理：

Apriori算法的基本过程是：

扫描一遍数据库，得到一阶频繁项；用一阶频繁项构造二阶候选项；扫描数据库对二阶候选项进行计数，删除其中的非频繁项，得到二阶频繁项；然后构造三阶候选项，以此类推，直到无法构造更高阶的候选项，或到达频繁项集的最大长度限制。Apriori算法的示意流程如下图所示：

如何从k阶的频繁项集生成k+1阶候选项集：自连接+裁剪（若k+1阶候选项的k阶子集中至少有一个不存在于k阶频繁项集中，则裁剪——Apriori裁剪规则，又称向下闭合特性）

表示事务集：

T1：A，B，E 1 1 0 0 1 T2：B，D 0 1 0 1 0 T3：B，C 0 1 1 0 0 T4：A，B，D 1 1 0 1 0 T5：A，C 1 0 1 0 0 T6：B，C 0 1 1 0 0 T7：A，C 1 0 1 0 0 T8：A，B，C，E 1 1 1 0 1 T9：A，B，C 1 1 1 0 0

计算项集的支持度： 代码：

function [sup] = compute_sup(S,D) [n,m]=size(D); sup=0;

for i=1:n

if all((D(i,:)-S)>=0)==true sup=sup+1; end end

sup = sup/n end

验证：

计算项集的置信度： 代码：

function [conf] = compute_conf(R,D)

conf=compute_sup(abs(R),D)/compute_sup((abs(R)-R)/2,D); end

Apriori.m 代码：

function [R,SupR,Conf]=Aprior(D,min_sup,min_conf) [m,n]=size(D); L=[]; C=[]; Lk=[]; Ck=[];

Sup=[];%频繁集L的支持度系数矩阵

for k=1:n, if (k==1)

Ck=eye(n); else

p=size(Lk,1);%1，获取矩阵的行数 Ck=[];

for i=1:p-1%find（）位置的判定：在矩阵中，第一列开始，自上而下，依次为1，2，3...,然后再从第二列，第三列依次往后数) for j=i+1:p

indi=find(Lk(i,:)==1); indj=find(Lk(j,:)==1);

if all(indi(1:end-1)==indj(1:end-1)) && (indi(end)~=indj(end)) Ck=[Ck;Lk(i,:) | Lk(j,:)]; end;

end; end end;

q=size(Ck,1);%获取矩阵的行数，即C1的项集 Supk=zeros([q,1]);%产生q×1的零矩阵 for i=1:q%CK的行数 for j=1:m%D的行数

if all(D(j,:)-Ck(i,:)>=0)%D的行-CK的行，若大于0则说明包含 Supk(i)=Supk(i)+1;%supk的第i行加1 end; end; end;

ind=find(Supk>=min_sup*m);

Sup=[Sup;Supk(ind,:)];%把支持度系数放到Sup矩阵中，第二个算法要用到 Lk=Ck(ind,:);

L=[L;Lk]; end;

[R,SupR,Conf]=find_rule(D,L,Sup,min_conf);

Find_rule.m

function [R,SupR,Conf]=find_rule(D,L,Sup,min_conf) R=[]; Conf=[]; SupR=[];

[m,n]=size(L); [g,h]=size(D);

for i=1:m%i是L的第i行，比如i=13,[1,1,0,0,1]

rowLi=sum(L(i,:)>0);%rowLi是L第i行含1的个数 rowLi=3 if(rowLi>1)

ind=find(L(i,:)==1);%ind是L第i行含1的下标矩阵 ind=[1,2,5] for j=1:rowLi-1 %j=1,j=2

nchoosei=nchoosek(ind,j);%[1,2,5][12,15,25] [a,b]=size(nchoosei);%a=3,b=1/a=3,b=2 for x=1:a

line_temp=zeros(1,n);%一个1×5的零矩阵， lineL=L(i,:);%L的第i行 for y=1:b

lineL(1,nchoosei(x,y))=-1;%每次循环将L的第i个集项的一个非空子集当成条件改成-1

line_temp(1,nchoosei(x,y))=1;%把零矩阵中条件项所在的位置改成1，用于接下来算该规则的置信度 end

for z=1:m