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

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

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

一、實(shí)驗(yàn)?zāi)康?/p>

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

二、實(shí)驗(yàn)C1={candidate1-itemsets};

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

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

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

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

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

(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ù)庫(kù)；minsupport表示給定的最小支持度；resultset表示所有最大項(xiàng)目集。

Sc_candidate函數(shù)

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

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

首先,通過(guò)對(duì)Lk-1自連接操作生成Ck,稱(chēng)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(修剪)步,即對(duì)任意的c,c∈Ck,刪除Ck中所有那些(k-1)維子集不在Lk-1中的項(xiàng)目集,得到侯選項(xiàng)目集Ck。表述為：

forallitemsetc∈Ck

forall(k-1)維子集sofc

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

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

2.Apriori算法的舉例

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

在Apriori,并和預(yù)定義的最小支持度比較,來(lái)確定該步的最大項(xiàng)目集。

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

算法的圖例說(shuō)明

五、實(shí)驗(yàn)結(jié)果

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

實(shí)驗(yàn)結(jié)果如下：

六、實(shí)驗(yàn)總結(jié)

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

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

七、實(shí)驗(yàn)程序

functionmy_apriori(X,minsup)clc;

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

%%%%%%%%%%%%%%%%%%%%%%%%%%打開(kāi)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;%預(yù)先定義支持度

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

temp=X{1};%用已暫存變量存儲(chǔ)所有不同項(xiàng)集fori=2:N

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

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

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

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

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

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

End

%%%%%%%%%%%%%%%%%%%%%%%%各個(gè)子程序如下functiony=cell_union(X,Y)%實(shí)現(xiàn)兩cell元組合并功能,由k-1項(xiàng)集增加到k項(xiàng)集函數(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)計(jì)頻繁項(xià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ù)表中不頻繁的項(xiàng)p=1;C=cell(1);fori=1:m

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%functiony=gen_rule(C)%apriori算法規(guī)則判斷是否產(chǎn)生k-候選項(xiàng)集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項(xiàng)候選集是否相等

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

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

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%functiony=Sc_candidate(C)%產(chǎn)生2-項(xiàng)候選集函數(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-項(xiàng)候選集p=p+1;endendy=L;

functiony=count_support(L,X,minsup)

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

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

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

if(ismem