Matlab關(guān)于Apriori算法設(shè)計

1、Apriori算法實(shí)現(xiàn)步驟：

Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法Apriori使用一種稱作逐層搜索的迭代方法，“K-1項集”用于搜索“K項集”。

首先，找出頻繁“1項集”的集合，該集合記作L1。L1用于找頻繁“2項集”的集合L2，而L2用于找L3。如此下去，直到不能找到“K項集”。找每個Lk都需要一次數(shù)據(jù)庫掃描。

核心思想是：連接步和剪枝步。連接步是自連接，原則是保證前k-2項相同，并按照字典順序連接。剪枝步，是使任一頻繁項集的所有非空子集也必須是頻繁的。反之，如果某

個候選的非空子集不是頻繁的，那么該候選肯定不是頻繁的，從而可以將其從CK中刪除。

簡單的講，1、發(fā)現(xiàn)頻繁項集，過程為（1）掃描（2）計數(shù)（3）比較（4）產(chǎn)生頻繁項集（5）連接、剪枝，產(chǎn)生候選項集 重復(fù)步驟（1）~（5）直到不能發(fā)現(xiàn)更大的頻集

2、產(chǎn)生關(guān)聯(lián)規(guī)則，過程為：根據(jù)前面提到的置信度的定義，關(guān)聯(lián)規(guī)則的產(chǎn)生如下：

（1）對于每個頻繁項集L，產(chǎn)生L的所有非空子集；

（2）對于L的每個非空子集S，如果

P（L）/P（S）≧min_conf

則輸出規(guī)則“SàL-S”

注：L-S表示在項集L中除去S子集的項集

例子：

代碼實(shí)現(xiàn)：

在講究代碼之前，我先跟大家講清楚我代碼里面說需要的關(guān)鍵點(diǎn)。我的算法全部加起來最多一百多行代碼，同時我包裝在三個函數(shù)中：compute_sup.m（算支持度）、compute_conf.m（算可信度）、Apriori.m（主函數(shù)）。

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

function sup=compute_sup（S， D）

%------------S指傳入的一個行向量--------

%------------D指整個數(shù)據(jù)集------------

sup=0;

［m，n］=size（D）;

for i=1:1：m

%對應(yīng)取出D的第i行與S對比，若D（i）-S所有的都>=0則支持度+1

if all（（D（i，：）-S）>=0）

sup=sup+1;

end

end

-----------------------------測試------------------------------

已知（自己構(gòu)造）

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指傳入的一條關(guān)聯(lián)規(guī)則，如：［-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指生成的強(qiáng)關(guān)聯(lián)規(guī)則----------------------

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

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

［n，m］=size（D）;

min_sup=min_sup*n;

L=［］;

%產(chǎn)生頻繁集

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

%-------產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則-----------------

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

%---------------生成規(guī)則---------------

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

---------------------------------------------------結(jié)果測試---------------------------------------------------------------------

已知

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 =

-1.0000? ? ? ? ? ? ? ?1.0000? ? ? ? ?0? ? ? ? ?0? ? ? ?0? ? ? ? ?4.0000? ? ? ? ? 0.6667? ? ? ? %A->B

-1.0000? ? ? ? ? ? ? ? ? ? ? ? 0? ? ? ?1.0000? ?0? ? ? 0? ? ? ? ?4.0000? ? ? ? ? 0.6667

1.0000? ? ? ? ? ? ? ? ? ? ? ? ?0? ? ? -1.0000? ? 0? ? ?0? ? ? ? ? 4.0000? ? ? ? ? ?0.6667

1.0000? ? ? ? ? ? ? ? ? ? ? ? ?0? ? ? ? ?0? ? ? ? ? 0? ? ? ? -1.0000 2.0000? ? ? ? 1.0000

0? ? ? ? ? ? ? ? ? ? ? ? ? 1.0000 -1.0000 0 0 4.0000? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0.6667

0? ? ? ? ? ? ? ? ? ? ? ? ?1.0000 0 -1.0000 0 2.0000? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?1.0000

0 1.0000? ? ? ? ? ? ? ? ? ? 0? ? ? ? ? ?0? ? ? -1.0000? ? ? ? ? ? ? ? 2.0000? ? ? ? ?1.0000

1.0000? ? ? ? ? ? ? ?1.0000? ? ? 0? ? ? ? ? ?0? ? ? ? ? ?-1.0000? ? ? ? ? ?2.0000? ? ? ? 1.0000

-1.0000? ? ? ? ? ? ?1.0000? ? ? ?0? ? ? ? ? ? 0? ? ? ? -1.0000 2.0000? ? ? ? ? ? ? ? ? ?1.0000

1.0000? ? ? ? ? ? ? -1.0000? ? ? ?0? ? ? ? ? ? 0? ? ? ? ?-1.0000 2.0000? ? ? ? ? ? ? ?1.0000

由于最小可信度是double型，所以弄得整個矩陣都是double行，有點(diǎn)失策。。。