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

1、matlab實現(xiàn)apriori算法源代碼、實驗?zāi)康耐ㄟ^實驗，加深數(shù)據(jù)挖掘中一個重要方法一一關(guān)聯(lián)分析的認(rèn)識，其經(jīng)典算法為apriori算法，了解影響apriori算法性能的因素，掌握基于apriori算法理論的關(guān)聯(lián)分析的原理和 方法。、實驗內(nèi)容對一數(shù)據(jù)集用apriori算法做關(guān)聯(lián)分析，用 matlab實現(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ù)軟件，那么將硬件擺放離軟件陳列近一點，可能有助于增加兩者的銷售。另一種策略是：將 硬件和軟件放在商店的兩端，可能誘發(fā)購買這些商品的顧客一路挑選其他商品。關(guān)聯(lián)規(guī)則是描述數(shù)據(jù)庫中數(shù)據(jù)項之間存在的潛在關(guān)系的規(guī)則，形式為A 4. AmBiB2 . Bn,其中 A(i 1,2.,m), Aj(j 1,2., n)是數(shù)據(jù)庫中的數(shù)據(jù)項數(shù)據(jù)項之間的關(guān)聯(lián)規(guī)則即根據(jù)一個事務(wù)中某些項的出現(xiàn)，可推導(dǎo)出另一些項在同一事務(wù)中

3、也出現(xiàn)。四、Apriori算法1 .算法描述Apriori算法的第一步是簡單統(tǒng)計所有含一個元素的項集出現(xiàn)的頻率，來決定最大的一維項目集。在第k步，分兩個階段，首先用一函數(shù)sc_candidate（候選），通過第（k-1）步中生成的最大項目集Lk-1來生成侯選項目集Q。然后搜索數(shù)據(jù)庫計算侯選項目集Q的支持度.為了更快速地計算G中項目的支持度，文中使用函數(shù)count_support計算支持度。Apriori算法描述如下：(1) C 1=candidate1-itemsets;(2) L 1=c C|c.count > minsupport;for(k=2,L mW，k+)/直到不能再生成最大

4、項目集為止(4) C k=sc_candidate(L k-1)；/ 生成含k個元素的侯選項目集 for all transactions tCD /辦理處理(6) Ct=count_support(C k,t);/ 包含在事務(wù)t中的侯選項目集 for all candidates c Ct(8) c.count=c.count+1;(9) next(10) L k=c C Ck|c.count > minsupport;(11) next(12) resultset=resultset U Lk其中，D表示數(shù)據(jù)庫；minsupport表示給定的最小支持度；resultset表示所有最大

5、項目集。Sc_candidate 函數(shù)該函數(shù)的參數(shù)為Lk-i,即：所有最大k-1維項目集，結(jié)果返回含有k個項目的侯選項目集 Q。事實上，Ck是k維最大項目集的超集，通過函數(shù)count_support計算項目的支持度，然后 生成Lk。該函數(shù)是如何完成這些功能的，詳細(xì)說明如下：首先，通過對Lk-i自連接操作生成Ck,稱join（連接）步，該步可表述為：insert into C kselect P.item 1,P.item 2,P.item k-1 ,Q.item k-1 from L k-1 P,Lk-1 Qwhere P.item 產(chǎn)Q.item 1,P.itemk-2=Q.item k-2

6、 ,P.item k-1 <Q.item k-1若用集合表示：Ck=XUX'|X,X'e Lk-1 ,|X nX'|=k-2然后，是prune（修剪）步，即對任意的c,c C Q,刪除G中所有那些（k-1）維子集不在Lk-1 中的項目集，得到侯選項目集Q。表述為： for all itemset c C Qfor all （k-1） 維子集 s of cif（s 不屬于 Lk-1） then delete c from C k;用集合表示：Ck=XCC<|X的所有k-1維子集在Lk-1中2.Apriori算法的舉例示例說明Apriori算法運作過程，有一數(shù)據(jù)

7、庫D,其中有四個事務(wù)記錄，分別表示為TIDItemsT1I1,I3,I4T2I2,I3,I5T3I1,I2,I3,I5T4I2,I5在Apriori算法中每一步創(chuàng)建該步的侯選集。統(tǒng)計每個侯選項目集的支持度，并和預(yù)定義的最小支持度比較，來確定該步的最大項目集。首先統(tǒng)計出一維項目集，即C.這里預(yù)定義最小支持度minsupport=2,侯選項目集中滿足最小支持度要求的項目集組合成最大的1-itemsets 。為生成最大的2-itemsets,使用了sc_candidate 函數(shù)中join 步，即：L1joinL 1,并通過prune步刪除那些 G的那些子集不在 L1中的項目集。生成了侯選項目集G。搜

8、索D中4個事務(wù)，統(tǒng)計C2中每個侯選項目集的支持度。然后和最小支持度比較，生成L2。侯選項目集 。是由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ù)記錄，生成

9、最大的3-tiemsets L3。此時，從L3中不能再生成侯選4-itemset 。Apriori算法結(jié)束.算法的圖例說明APR10R I 算法拈EC.悠個法祗計Z兌制，支濘數(shù)由l產(chǎn)生會越n支打K汁蚊111)2123口川3【JLI次計，»以小由h，尸土 M比率根型攵女撿&汁秋內(nèi)心小K持庶計程,乜”用武，此女為戊厘,以誦先Hl, INI 11 - UILjf少出小美計雙五、實驗結(jié)果test.txt格式及內(nèi)容如下:testbrt -記事*文悻因褊瑁但 唱式Q直惹M 超前世bread ffliIk beer bread diaper beer egg milk mills diap

10、er beer cook brtad milk diaper beer brtad milk diaper cook beer bread butter diaper milk coffee sveat cookie fish bread butter coftse diaper mi Ik bead butter fish chicken 弓弓 bx c4l bvttcxfish diaper milkbcreid tea sveat efgcoffee surest chicken eg bred di apex milk salt beer tea egs zookie diaper m

11、ilk實驗結(jié)果如下:Smgnd Windowbtrer飛©if"h rer"'di arper'"btor' mi 1Y"hnd"° diopgif，欣貝9 beerp' bEead'' ntlk*'bt eV六、實驗總結(jié)Apriori算法可以很有效地找出數(shù)據(jù)集中存在的關(guān)聯(lián)規(guī)則且能找出最大項的關(guān)聯(lián)規(guī)則，但從以上的算法執(zhí)行過程可以看到Apriori算法的缺點：第一，在每一步產(chǎn)生侯選項目集時循環(huán)產(chǎn)生的組合過多，沒有排除不應(yīng)該參與組合的元素；第二，每次計算項集的支持度時，都對

12、數(shù)據(jù)庫D中的全部記錄進(jìn)行了一遍掃描比較，如果是一個大型的數(shù)據(jù)庫的話，這種掃描比較會大大增加計算機(jī)系統(tǒng)的I/O開銷。而這種代價是隨著數(shù)據(jù)庫的記錄的增加呈現(xiàn)出幾何級數(shù)的增加。因此人們開始尋求一種能減少這種系統(tǒng)I/O開銷的更為快捷的算法。七、實驗程序function my_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

13、'J);m,n=size(file);for i=1:mwords=strread(filei,'%s','delimiter','');words=words'Xi二words;end%minsup=0.3; %預(yù)先定義支持度m,N=size(X); % 求 X 的維數(shù)temp=X1; %用已暫存變量存儲所有不同項集for i=2:Ntemp=union(temp,Xi); %找出所有不同項(種類)end%找出 k-頻繁項L=Sc_candidate(temp); % 找出 2-項候選項集sum=1;%統(tǒng)計滿足條件的最多項集wh

14、ile(isempty(L1) %循環(huán)終止條件為第k次頻繁項集為空sum=sum+1;C=count_support(L,X,minsup);%挑選出滿足最小支持度的k-頻繁項%sprintf('%s%d%s','滿足要求的,sum,'次頻繁項集依次為')%顯for i=1:size(C,1)%示disp(Ci,1);%部end% 分%L=gen_rule(C);%依次產(chǎn)生k-頻繁項(依據(jù)apriori算法規(guī)則)End%各個子程序如下function y=cell_union(X,Y)%實現(xiàn)兩cell元組合并功能，由k-1項集增加到k項集函數(shù)m,n=si

15、ze(X);if(iscellstr(X) % 判斷 X 是否元組L1=X;L1,2=Y;elseL=X;L1,n+1=Y;endy=L;%function y=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);for i=1:mfor j=1:Mif(ismember(Li,Xj)count(i)=count(i)+1;endendend%刪除數(shù)據(jù)表中不頻繁的項p=1;C=cell(1);for i=1:mif(co

16、unt(i)>minsup*M)%小于支持度的項為不頻繁數(shù)，將刪除，大于的保留Cp=Li;p=p+1;endendy=C'%function y=gen_rule(C) %apriori算法規(guī)則判斷是否產(chǎn)生k-候選項集if(isempty(C1) % 判斷 C 是否為空M,N=size(C);m,n=size(C1);temp1=C;L=cell(1);for i=1:Mtemp2i=temp1in;temp1in=;endp=1;for i=1:Mfor j=i+1:Mif(isequal(temp1i,temp1j) % 判斷前 k-1 項候選集是否相等Lp=cell_union(Ci,temp2j); % 若相等，貝 U 增加至k-項集p=p+1;endendendy=L'elsey=cell(1);%否則y返回空end%function y=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;for i=1:m-1% 注意for j=i+1:mLp=cell_union(Ci,Cj); %產(chǎn)生 2-項候選集p=p+1;endendy=L;function y=count_sup