matlab實現(xiàn)apriori算法源代碼

matlab實現(xiàn)apriori算法源代碼

matlab實現(xiàn)apriori算法源代碼

一、實驗目的

通過實驗，加深數(shù)據(jù)挖掘中一個重要方法——關(guān)聯(lián)分析的認識，其經(jīng)典算法為apriori算法，了解影響apriori算法性能的因素，掌握基于apriori算法理論的關(guān)聯(lián)分析的原理和方法。

二、實驗C1={candidate1-itemsets};

(2)L1={c∈C1|c.count≥minsupport};

(3)for(k=2,Lk-1≠Φ,k++)//直到不能再生成最大項目集為止

(4)Ck=sc_candidate(Lk-1);//生成含k個元素的侯選項目集

(5)foralltransactionst∈D//辦理處理

(6)Ct=count_support(Ck,t);//包含在事務(wù)t中的侯選項目集

(7)forallcandidatesc∈Ct

(8)c.count=c.count+1;

(9)next

(10)Lk={c∈Ck|c.count≥minsupport};

(11)next

(12)resultset=resultset∪Lk

其中,D表示數(shù)據(jù)庫；minsupport表示給定的最小支持度；resultset表示所有最大項目集。

Sc_candidate函數(shù)

該函數(shù)的參數(shù)為Lk-1,即:所有最大k-1維項目集,結(jié)果返回含有k個項目的侯選項目集Ck。事實上,Ck是k維最大項目集的超集,通過函數(shù)count_support計算項目的支持度,然后生成Lk。

該函數(shù)是如何完成這些功能的,詳細說明如下:

首先,通過對Lk-1自連接操作生成Ck,稱join(連接)步,該步可表述為:

insertintoCk

selectP.item1,P.item2,...,P.itemk-1,Q.itemk-1fromLk-1P,Lk-1Q

whereP.item1=Q.item1,...,P.itemk-2=Q.itemk-2,P.itemk-1<Q.itemk-1

若用集合表示:Ck={X∪X’|X,X’∈Lk-1,|X∩X’|=k-2}

然后,是prune(修剪)步,即對任意的c,c∈Ck,刪除Ck中所有那些(k-1)維子集不在Lk-1中的項目集,得到侯選項目集Ck。表述為：

forallitemsetc∈Ck

forall(k-1)維子集sofc

if(s不屬于Lk-1)thendeletecfromCk;

用集合表示:Ck={X∈Ck|X的所有k-1維子集在Lk-1中}

2.Apriori算法的舉例

示例說明Apriori算法運作過程，有一數(shù)據(jù)庫D,其中有四個事務(wù)記錄,分別表示為

在Apriori,并和預定義的最小支持度比較,來確定該步的最大項目集。

首先統(tǒng)計出一維項目集,即C1.這里預定義最小支持度minsupport=2,侯選項目集中滿足最小支持度要求的項目集組合成最大的1-itemsets。為生成最大的2-itemsets,使用了sc_candidate函數(shù)中join步,即：L1joinL1，并通過prune步刪除那些C2的那些子集不在L1中的項目集。生成了侯選項目集C2。搜索D中4個事務(wù),統(tǒng)計C2中每個侯選項目集的支持度。然后和最小支持度比較,生成L2。侯選項目集C3是由L2生成.要求自連接的兩個最大2-itemsets中,第一個項目相同,在L2中滿足該條件的有{I2,I3},{I2,I5}.這兩個集合經(jīng)過join步后,產(chǎn)生集合{I2，I3，I5}.在prune步中,測試{I2，I3，I5}的子集{I3，I5},{I2，I3},{I2，I5}是否在L2中,由L2可以知道{I3,I5},{I2,I3},{I2,I5}本身就是最大2-itemsets.即{I2,I3,I5}的子集都是最大項目集.那么{I2,I3,I5}為侯選3-itemset.然后搜索數(shù)據(jù)庫中所有事務(wù)記錄,生成最大的3-tiemsetsL3。此時,從L3中不能再生成侯選4-itemset。Apriori算法結(jié)束.

算法的圖例說明

五、實驗結(jié)果

test.txt格式及內(nèi)容如下：

實驗結(jié)果如下：

六、實驗總結(jié)

Apriori算法可以很有效地找出數(shù)據(jù)集中存在的關(guān)聯(lián)規(guī)則且能找出最大項的關(guān)聯(lián)規(guī)則，但從以上的算法執(zhí)行過程可以看到Apriori算法的缺點:

第一,在每一步產(chǎn)生侯選項目集時循環(huán)產(chǎn)生的組合過多，沒有排除不應該參與組合的元素；第二,每次計算項集的支持度時，都對數(shù)據(jù)庫D中的全部記錄進行了一遍掃描比較，如果是一個大型的數(shù)據(jù)庫的話，這種掃描比較會大大增加計算機系統(tǒng)的I/O開銷。而這種代價是隨著數(shù)據(jù)庫的記錄的增加呈現(xiàn)出幾何級數(shù)的增加。因此人們開始尋求一種能減少這種系統(tǒng)1/O開銷的更為快捷的算法。

七、實驗程序

functionmy_apriori(X,minsup)clc;

%%%%主函數(shù)，輸入X數(shù)據(jù)集，判斷產(chǎn)生大于minsup最小支持度的關(guān)聯(lián)規(guī)則

%%%%%%%%%%%%%%%%%%%%%%%%%%打開test.txt文件file=textread(‘test.txt’,’%s’,’delimiter’,’\n’,’whitespace’,’’);[m,n]=size(file);fori=1:m

words=strread(file{i},’%s’,’delimiter’,’‘);words=words’;X{i}=words;end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%minsup=0.3;%預先定義支持度

[m,N]=size(X);%求X的維數(shù)

temp=X{1};%用已暫存變量存儲所有不同項集fori=2:N

temp=union(temp,X{i});%找出所有不同項（種類）end

%%%%%%%%%%%%%%%%%%%%找出k-頻繁項L=Sc_candidate(temp);%找出2-項候選項集sum=1;%統(tǒng)計滿足條件的最多項集

while(~isempty(L{1}))%循環(huán)終止條件為第k次頻繁項集為空sum=sum+1;

C=count_support(L,X,minsup);%挑選出滿足最小支持度的k-頻繁項

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

sprintf(‘%s%d%s’,’滿足要求的’,sum,’次頻繁項集依次為’)%顯fori=1:size(C,1)%示disp(C{i,1});%部end%分%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%L=gen_rule(C);%依次產(chǎn)生k-頻繁項(依據(jù)apriori算法規(guī)則）

End

%%%%%%%%%%%%%%%%%%%%%%%%各個子程序如下functiony=cell_union(X,Y)%實現(xiàn)兩cell元組合并功能,由k-1項集增加到k項集函數(shù)[m,n]=size(X);

if(~iscellstr(X))%判斷X是否元組L{1}=X;L{1,2}=Y;elseL=X;L{1,n+1}=Y;endy=L;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%functiony=count_support(L,X,minsup)

%找出符合大于支持度sup的候選集,L為候選集，X為總數(shù)據(jù)集X=X’;%轉(zhuǎn)置

%%%%%%%%%%%%%%%%%統(tǒng)計頻繁項[m,n]=size(L);[M,N]=size(X);count=zeros(m,1);fori=1:mforj=1:M

if(ismember(L{i},X{j}))count(i)=count(i)+1;endendend

%%%%%%%%%%%刪除數(shù)據(jù)表中不頻繁的項p=1;C=cell(1);fori=1:m

if(count(i)>minsup*M)%小于支持度的項為不頻繁數(shù)，將刪除,大于的保留C{p}=L{i};p=p+1;endendy=C’;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%functiony=gen_rule(C)%apriori算法規(guī)則判斷是否產(chǎn)生k-候選項集if(~isempty(C{1}))%判斷C是否為空[M,N]=size(C);[m,n]=size(C{1});temp1=C;L=cell(1);fori=1:M

temp2{i}=temp1{i}{n};temp1{i}{n}=[];endp=1;fori=1:Mforj=i+1:M

if(isequal(temp1{i},temp1{j}))%判斷前k-1項候選集是否相等

L{p}=cell_union(C{i},temp2{j});%若相等，則增加至k-項集

p=p+1;endendendy=L’;else

y=cell(1);%否則y返回空end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%functiony=Sc_candidate(C)%產(chǎn)生2-項候選集函數(shù)C=C’;%轉(zhuǎn)置[m,n]=size(C);

bcount=zeros(m*(m-1)/2,1);L=cell(m*(m-1)/2,1);p=1;

fori=1:m-1%注意forj=i+1:m

L{p}=cell_union(C{i},C{j});%產(chǎn)生2-項候選集p=p+1;endendy=L;

functiony=count_support(L,X,minsup)

%找出符合大于支持度sup的候選集,L為候選集，X為總數(shù)據(jù)集

X=X’;%轉(zhuǎn)置

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%統(tǒng)計頻繁項[m,n]=size(L);[M,N]=size(X);count=zeros(m,1);fori=1:mforj=1:M

if(ismem