matlab實(shí)現(xiàn)apriori算法關(guān)聯(lián)分析源代碼

1、matlab實(shí)現(xiàn)apriori算法源代碼一、實(shí)驗(yàn)?zāi)康耐ㄟ^實(shí)驗(yàn)，加深數(shù)據(jù)挖掘中一個重要方法關(guān)聯(lián)分析的認(rèn)識，其經(jīng)典算法為apriori算法，了解影響apriori算法性能的因素，掌握基于apriori算法理論的關(guān)聯(lián)分析的原理和方法。二、實(shí)驗(yàn)內(nèi)容對一數(shù)據(jù)集用apriori算法做關(guān)聯(lián)分析，用matlab實(shí)現(xiàn)。三、方法手段關(guān)聯(lián)規(guī)則挖掘的一個典型例子是購物籃分析。市場分析員要從大量的數(shù)據(jù)中發(fā)現(xiàn)顧客放入其購物籃中的不同商品之間的關(guān)系。如果顧客買牛奶，他也購買面包的可能性有多大？ 什么商品組或集合顧客多半會在一次購物時同時購買？例如，買牛奶的顧客有80%也同時買面包，或買鐵錘的顧客中有70%的人同時也買鐵釘，

2、這就是從購物籃數(shù)據(jù)中提取的關(guān)聯(lián)規(guī)則。分析結(jié)果可以幫助經(jīng)理設(shè)計不同的商店布局。一種策略是：經(jīng)常一塊購買的商品可以放近一些，以便進(jìn)一步刺激這些商品一起銷售，例如，如果顧客購買計算機(jī)又傾向于同時購買財務(wù)軟件，那么將硬件擺放離軟件陳列近一點(diǎn)，可能有助于增加兩者的銷售。另一種策略是：將硬件和軟件放在商店的兩端，可能誘發(fā)購買這些商品的顧客一路挑選其他商品。關(guān)聯(lián)規(guī)則是描述數(shù)據(jù)庫中數(shù)據(jù)項(xiàng)之間存在的潛在關(guān)系的規(guī)則,形式為,其中,是數(shù)據(jù)庫中的數(shù)據(jù)項(xiàng).數(shù)據(jù)項(xiàng)之間的關(guān)聯(lián)規(guī)則即根據(jù)一個事務(wù)中某些項(xiàng)的出現(xiàn),可推導(dǎo)出另一些項(xiàng)在同一事務(wù)中也出現(xiàn)。四、Apriori算法1.算法描述Apriori算法的第一步是簡單統(tǒng)計所有含一個

3、元素的項(xiàng)集出現(xiàn)的頻率,來決定最大的一維項(xiàng)目集。在第k步,分兩個階段,首先用一函數(shù)sc_candidate(候選),通過第(k-1)步中生成的最大項(xiàng)目集Lk-1來生成侯選項(xiàng)目集Ck。然后搜索數(shù)據(jù)庫計算侯選項(xiàng)目集Ck的支持度. 為了更快速地計算Ck中項(xiàng)目的支持度, 文中使用函數(shù)count_support計算支持度。Apriori算法描述如下：(1) C1=candidate1-itemsets;(2) L1=cC1|c.countminsupport;(3) for(k=2,Lk-1,k+) /直到不能再生成最大項(xiàng)目集為止(4) Ck=sc_candidate(Lk-1); /生成含k個元素的侯選

4、項(xiàng)目集(5) for all transactions tD /辦理處理(6) Ct=count_support(Ck,t); /包含在事務(wù)t中的侯選項(xiàng)目集(7) for all candidates cCt(8) c.count=c.count+1;(9) next(10) Lk=cCk|c.countminsupport;(11) next(12) resultset=resultsetLk其中, D表示數(shù)據(jù)庫；minsupport表示給定的最小支持度；resultset表示所有最大項(xiàng)目集。Sc_candidate函數(shù)該函數(shù)的參數(shù)為Lk-1,即: 所有最大k-1維項(xiàng)目集,結(jié)果返回含有k個項(xiàng)

5、目的侯選項(xiàng)目集Ck。事實(shí)上,Ck是k維最大項(xiàng)目集的超集,通過函數(shù)count_support計算項(xiàng)目的支持度,然后生成Lk。該函數(shù)是如何完成這些功能的, 詳細(xì)說明如下: 首先, 通過對Lk-1自連接操作生成Ck,稱join(連接)步,該步可表述為:insert into Ckselect P.item1,P.item2,.,P.itemk-1,Q.itemk-1 from Lk-1P,Lk-1Qwhere P.item1=Q.item1,.,P.itemk-2=Q.itemk-2,P.itemk-1<Q.itemk-1若用集合表示:Ck=XX'|X,X'Lk-1,|XX&#

6、39;|=k-2然后,是prune(修剪)步,即對任意的c,cCk, 刪除Ck中所有那些(k-1)維子集不在Lk-1中的項(xiàng)目集,得到侯選項(xiàng)目集Ck。表述為：for all itemsetcCkfor all (k-1)維子集s of cif(s不屬于Lk-1) then delete c from Ck;用集合表示:Ck=XCk|X的所有k-1維子集在Lk-1中2.Apriori算法的舉例示例說明Apriori算法運(yùn)作過程，有一數(shù)據(jù)庫D, 其中有四個事務(wù)記錄, 分別表示為TIDItemsT1I1,I3,I4T2I2,I3,I5T3I1,I2,I3,I5T4I2,I5在Apriori算法中每一步

7、創(chuàng)建該步的侯選集。統(tǒng)計每個侯選項(xiàng)目集的支持度,并和預(yù)定義的最小支持度比較,來確定該步的最大項(xiàng)目集。首先統(tǒng)計出一維項(xiàng)目集,即C1.這里預(yù)定義最小支持度minsupport=2,侯選項(xiàng)目集中滿足最小支持度要求的項(xiàng)目集組合成最大的1-itemsets。為生成最大的2-itemsets,使用了sc_candidate函數(shù)中join步,即：L1joinL1，并通過prune步刪除那些C2的那些子集不在L1中的項(xiàng)目集。生成了侯選項(xiàng)目集C2。搜索D中4個事務(wù),統(tǒng)計C2中每個侯選項(xiàng)目集的支持度。然后和最小支持度比較,生成L2。侯選項(xiàng)目集C3是由L2生成.要求自連接的兩個最大2-itemsets中,第一個項(xiàng)目相

8、同,在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的子集都是最大項(xiàng)目集.那么I2,I3,I5為侯選3-itemset.然后搜索數(shù)據(jù)庫中所有事務(wù)記錄,生成最大的3-tiemsets L3。此時, 從L3中不能再生成侯選4-itemset 。Apriori算法結(jié)束.算法的圖例說明五、實(shí)驗(yàn)結(jié)果test.txt格式及內(nèi)容如下： 實(shí)驗(yàn)結(jié)果如下：六、實(shí)驗(yàn)總結(jié)Ap

9、riori算法可以很有效地找出數(shù)據(jù)集中存在的關(guān)聯(lián)規(guī)則且能找出最大項(xiàng)的關(guān)聯(lián)規(guī)則，但從以上的算法執(zhí)行過程可以看到Apriori算法的缺點(diǎn):第一,在每一步產(chǎn)生侯選項(xiàng)目集時循環(huán)產(chǎn)生的組合過多，沒有排除不應(yīng)該參與組合的元素；第二,每次計算項(xiàng)集的支持度時，都對數(shù)據(jù)庫D中的全部記錄進(jìn)行了一遍掃描比較，如果是一個大型的數(shù)據(jù)庫的話，這種掃描比較會大大增加計算機(jī)系統(tǒng)的I/O開銷。而這種代價是隨著數(shù)據(jù)庫的記錄的增加呈現(xiàn)出幾何級數(shù)的增加。因此人們開始尋求一種能減少這種系統(tǒng)1/O開銷的更為快捷的算法。七、實(shí)驗(yàn)程序function my_apriori(X,minsup) clc;%主函數(shù)，輸入X數(shù)據(jù)集，判斷產(chǎn)生大于mi

10、nsup最小支持度的關(guān)聯(lián)規(guī)則%打開test.txt文件file = textread('test.txt','%s','delimiter','n','whitespace','');m,n=size(file);for i=1:m words=strread(filei,'%s','delimiter',' '); words=words' Xi=words;end%minsup=0.3; %預(yù)先定義支持度m,N=size(X); %求X的維

11、數(shù)temp=X1; %用已暫存變量存儲所有不同項(xiàng)集for i=2:N temp=union(temp,Xi); %找出所有不同項(xiàng)（種類）end %找出k-頻繁項(xiàng)L=Sc_candidate(temp); %找出2-項(xiàng)候選項(xiàng)集sum=1; %統(tǒng)計滿足條件的最多項(xiàng)集while(isempty(L1) %循環(huán)終止條件為第k次頻繁項(xiàng)集為空 sum=sum+1; C=count_support(L,X,minsup); %挑選出滿足最小支持度的k-頻繁項(xiàng) % sprintf('%s%d%s','滿足要求的',sum,'次頻繁項(xiàng)集依次為') %顯 for i

12、=1:size(C,1) %示 disp(Ci,1); %部 end %分 % L=gen_rule(C); %依次產(chǎn)生k-頻繁項(xiàng)(依據(jù)apriori算法規(guī)則）End%各個子程序如下function y=cell_union(X,Y) %實(shí)現(xiàn)兩cell元組合并功能,由k-1項(xiàng)集增加到k項(xiàng)集函數(shù)m,n=size(X);if(iscellstr(X) %判斷X是否元組 L1=X; L1,2=Y;else L=X; L1,n+1=Y;endy=L;%function y=count_support(L,X,minsup)%找出符合大于支持度sup的候選集,L為候選集，X為總數(shù)據(jù)集X=X'%轉(zhuǎn)

13、置%統(tǒng)計頻繁項(xiàng)m,n=size(L);M,N=size(X);count=zeros(m,1);for i=1:m for j=1:M if(ismember(Li,Xj) count(i)=count(i)+1; end endend%刪除數(shù)據(jù)表中不頻繁的項(xiàng)p=1;C=cell(1);for i=1:m if(count(i)>minsup*M) %小于支持度的項(xiàng)為不頻繁數(shù)，將刪除,大于的保留 Cp=Li; p=p+1; endendy=C'%function y=gen_rule(C) %apriori算法規(guī)則判斷是否產(chǎn)生k-候選項(xiàng)集if(isempty(C1) %判斷C是否

14、為空 M,N=size(C); m,n=size(C1); temp1=C; L=cell(1); for i=1:M temp2i=temp1in; temp1in=; end p=1; for i=1:M for j=i+1:M if(isequal(temp1i,temp1j) %判斷前k-1項(xiàng)候選集是否相等 Lp=cell_union(Ci,temp2j); %若相等，則增加至k-項(xiàng)集 p=p+1; end end end y=L'else y=cell(1);%否則y返回空end%function y=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;for i=1:m-1 %注意 for j=i+1:m Lp=cell_union(Ci,Cj); %產(chǎn)生2-項(xiàng)候選集 p=p+1; endendy=L;function y=count_support(L,X,minsup)%找出符合大于支持度sup的候選集,L為候選集，X為總數(shù)據(jù)集X=X'%