行业新闻
Group news
江苏宏丰木业有限公司    您的位置: 首页  >  行业新闻  >  正文

Matlab关于Apriori算法设计

2019年11月07日 文章来源:网络整理 热度:84℃ 作者:刘英

1、Apriori算法实现步骤:

Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法Apriori使用一种称作逐层搜索的迭代方法,“K-1项集”用于搜索“K项集”。

首先,找出频繁“1项集”的集合,该集合记作L1。L1用于找频繁“2项集”的集合L2,而L2用于找L3。如此下去,直到不能找到“K项集”。找每个Lk都需要一次数据库扫描。

核心思想是:连接步和剪枝步。连接步是自连接,原则是保证前k-2项相同,并按照字典顺序连接。剪枝步,是使任一频繁项集的所有非空子集也必须是频繁的。反之,如果某

个候选的非空子集不是频繁的,那么该候选肯定不是频繁的,从而可以将其从CK中删除。

简单的讲,1、发现频繁项集,过程为(1)扫描(2)计数(3)比较(4)产生频繁项集(5)连接、剪枝,产生候选项集 重复步骤(1)~(5)直到不能发现更大的频集

2、产生关联规则,过程为:根据前面提到的置信度的定义,关联规则的产生如下:

(1)对于每个频繁项集L,产生L的所有非空子集;

(2)对于L的每个非空子集S,如果

P(L)/P(S)≧min_conf

则输出规则“SàL-S”

注:L-S表示在项集L中除去S子集的项集

例子:

Matlab关于Apriori算法设计

代码实现:

在讲究代码之前,我先跟大家讲清楚我代码里面说需要的关键点。我的算法全部加起来最多一百多行代码,同时我包装在三个函数中:compute_sup.m(算支持度)、compute_conf.m(算可信度)、Apriori.m(主函数)。

-----------------------compute_sup.m-------------------------------------------------------------------------

funcTIon sup=compute_sup(S, D)

%------------S指传入的一个行向量--------

%------------D指整个数据集------------

sup=0;

[m,n]=size(D);

for i=1:1:m

%对应取出D的第i行与S对比,若D(i)-S所有的都>=0则支持度+1

if all((D(i,:)-S)>=0)

sup=sup+1;

end

end

-----------------------------测试------------------------------

已知(自己构造)

D =

1 1 0 0 1

0 1 0 1 0

0 1 1 0 0

1 1 0 1 0

1 0 1 0 0

0 1 1 0 0

1 0 1 0 0

1 1 1 0 1

1 1 1 0 0

输入:sup=compute_sup([1,1,0,0,0], D)

输出:sup = 4

--------------------------------------compute_conf.m-----------------------------------------------

funcTIon conf=compute_conf(Q,D)

%Q指传入的一条关联规则,如:[-1,0,0,1,0]指A->D=P(AD)/P(A)

s=abs(Q);

d=(abs(Q)-Q)/2;

conf=compute_sup(s,D)/compute_sup(d,D); %P(AD)/P(A)

------------------------------------------测试-----------------------------------------------------------------------------------

已知D

输入:conf=compute_conf([-1,0,0,1,0],D)

输出:conf = 0.1667 %置信度为0.1667

----------------------------------------------Apriori.m(算法的核心)---------------------------------

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

%--------------R指生成的强关联规则----------------------

%--------------输出sup指支持度、min_sup-最小支持度-------------------------

%--------------

[n,m]=size(D);

min_sup=min_sup*n;

L=[];

%产生频繁集

C1=eye(m);

Ck=C1;

for k=1:m

Lk=[];

q=size(Ck,1);

for i=1:q

%-----------------剪枝-------------------------

sup= compute_sup(Ck(i,:),D);

if sup>=(min_sup)

Lk=[Lk;Ck(i,:)];

end

end

Ck=[];

q=size(Lk,1);

for i=1:q

for j=i+1:q

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

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

ind=indi-indj;

%从候选集中选出频繁集,相邻两个行对比,前k-1个相同,第k个不同,然后加入Ck。

if(all(ind(1:k-1)==0)&& ind(k)~=0)

Ck=[Ck;Lk(i,:)|Lk(j,:)];

end

end

end

L=[L;Lk];

end

%-------产生强关联规则-----------------

q=size(L,1);

R=[];

H=[];

M=[];

for i=1:q

ind =find(L(i,:)==1);

if length(ind)==1 conTInue;end

for j=1:length(ind)-1

SubSet= nchoosek(ind,j);

n=size(SubSet,1);

for m=1:n

L(i,SubSet(m,:))=-1;

H=[H;L(i,:)];

L=abs(L);

end

end

end

%---------------生成规则---------------

m=size(H,1);

M=abs(H);

T=[];

for n=1:m

sup=compute_sup(M(n,:),D);

conf=compute_conf(H(n,:),D);

if conf>=min_conf

T=[T;H(n,:),sup,conf];

end

end

R=[R;T];

end

---------------------------------------------------结果测试---------------------------------------------------------------------

已知

D =

1 1 0 0 1

0 1 0 1 0

0 1 1 0 0

1 1 0 1 0

1 0 1 0 0

0 1 1 0 0

1 0 1 0 0

1 1 1 0 1

1 1 1 0 0

min_conf = 0.6000

min_sup=0.2000

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

输出:

R =

上一篇:浅谈rtimer定时器原理和rtimer移植


下一篇:印制电路板设计前需要做的步骤解析

友情链接
Links
鸿运国际官网_鸿运国际备用网址