Apriori算法例子

1、Apriori算法例子1Apriori介紹Apriori算法使用頻繁項集的先驗知識，使用一種稱作逐層搜索的迭代方法，k項集用于探索（k+1）項集。首先，通過掃描事務(wù)（交易）記錄，找出所有的頻繁1項集，該集合記做Li,然后利用Li找頻繁2項集的集合L2,L2找L3,如此下去，直到不能再找到任何頻繁k項集。最后再在所有的頻繁集中找出強規(guī)則，即產(chǎn)生用戶感興趣的關(guān)聯(lián)規(guī)則。其中，Apriori算法具有這樣一條性質(zhì)：任一頻繁項集的所有非空子集也必須是頻繁的。因為假如P（I）<最小支持度閾值，當(dāng)有元素A添加到I中時，結(jié)果項集（AAI）不可能比I出現(xiàn)次數(shù)更多。因此AAI也不是頻繁的。2連接步和剪枝步在上

2、述的關(guān)聯(lián)規(guī)則挖掘過程的兩個步驟中，第一步往往是總體性能的瓶頸。Apriori算法采用連接步和剪枝步兩種方式來找出所有的頻繁項集。1）連接步為找出Lk（所有的頻繁k項集的集合），通過將Lk-1（所有的頻繁k-1項集的集合）與自身連接產(chǎn)生候選k項集的集合。候選集合記作Q。設(shè)l1和12是Lk-1中的成員。記lij表示li中的第j項。假設(shè)Apriori算法對事務(wù)或項集中的項按字典次序排序，即對于（k-1）項集li,li1<li2<.<lik-1。將Lk-1與自身連接，如果（l11=l21）&&（l12=l22）&&.&&（l1k-2=l

3、2k-2）&&（l1k-1<l2k-1），那認(rèn)為11和l2是可連接。連接11和l2產(chǎn)生的結(jié)果是l11,l12,l1k-1,l2k-1。2）剪枝步a是Lk的超集，也就是說，a的成員可能是也可能不是頻繁的。通過掃描所有的事務(wù)（交易），確定Ck中每個候選的計數(shù)，判斷是否小于最小支持度計數(shù)，如果不是，則認(rèn)為該候選是頻繁的。為了壓縮Ck,可以利用Apriori性質(zhì)：任一頻繁項集的所有非空子集也必須是頻繁的，反之，如果某個候選的非空子集不是頻繁的，那么該候選肯定不是頻繁的，從而可以將其從Ck中刪除。（Tip：為什么要壓縮&呢？因為實際情況下事務(wù)記錄往往是保存在外存儲上，比如數(shù)

4、據(jù)庫或者其他格式的文件上，在每次計算候選計數(shù)時都需要將候選與所有事務(wù)進行比對，眾所周知，訪問外存的效率往往都比較低，因此Apriori加入了所謂的剪枝步，事先對候選集進行過濾，以減少訪問外存的次數(shù)。）3 Apriori算法實例交易ID商品ID列表T100I1,I2,I5T200I2,I4T300I2,I3T400I1,I2,I4T500I1,I3T600I2,I3T700I1,I3T800I1,I2,I3,I5T900I1,I2,I3上圖為某商場的交易記錄，共有9個事務(wù)，利用Apriori算法尋找所有的頻繁項集的過程如下：L1131Ml有的交號記錄_.理集支牌度訃莪阿&T（13；6網(wǎng)2

5、吟士比敢依羞支期SSHfc-石拿小支忤度慢潭理案支杵度計敲11£3317(B)6(B4)2明？由L1產(chǎn)生候gf由LZ產(chǎn)生鑲詹CJ-；口.喟QL用蝴<UK>但阿f瑞黨也即嘮夙*QL2居MW舊酬有的文品記錄.對等中3計散哽集支杵度計數(shù)L2。皿4I(11,134廈集變博度才翻:11,1411334ILK2斯叫；4uxnj4g23吩2支杵度計數(shù)f與敢小支"度性術(shù)m明2也閃442011410吩1口4吩01舊修胴育的對/1橫逸計被支南5計減立叫2阿的2L3支忤懂計救*與嵯小支持度慢窣詳細(xì)介紹下候選3項集的集合C3的產(chǎn)生過程：從連接步，首先C3=I1,I2,I3I1,I2,I

6、5,I1,I3,I5,I2,I3,I4,I2,I3,I5,I2,I4,I5(C3是由L2與自身連接產(chǎn)生）。根據(jù)Apriori性質(zhì)，頻繁項集的所有子集也必須頻繁的，可以確定有4個候選集I1,I3,I5,I2,I3,I4,I2,I3,I5,I2,I4,I5不可能時頻繁的，因為它們存在子集不屬于頻繁集，因此將它們從C3中刪除。注意，由于Apriori算法使用逐層搜索技術(shù)，給定候選k項集后，只需檢查它們的（k-1）個子集是否頻繁。3.Apriori偽代碼算法:輸入:AprioriD-事務(wù)數(shù)據(jù)庫；min_sup-最小支持度計數(shù)閾值輸出:L-D中的頻繁項集找出所有頻繁1項集并剪枝方法:Li=find_fr

7、equent_1-itemsets(D);/For(k=2;Lk-1!=null;k+)Ck=apriori_gen(Lk-1);產(chǎn)生候選,Foreach事務(wù)tinD/掃描D進行候選計數(shù)Ct=subset(Ck,t);/得到t的子集Foreach候選c屬于Ctc.count+;)Lk=c屬于Ck|c.count>=min_sup)ReturnL=所有的頻繁集；Procedureapriori_gen(Lk-1:frequent(k-1)-itemsets)Foreach項集11屬于Lk-1Foreach項集l2屬于Lk-1If(l11=l21)&&(l12=l22)&am

8、p;&&&(l1k-2=l2k-2)&&(l1k-1<l2k-1)thenc=l1連接l2/連接步：產(chǎn)生候選ifhas_infrequent_subset(c,Lk-1)thendeletec;/剪枝步：刪除非頻繁候選elseaddctoCk;ReturnCk;Procedurehas_infrequent_sub(c:candidatek-itemset;Lk-1:frequent(k-1)-itemsets)Foreach(k-1)-subsetsofcIfs不屬于Lk-1thenReturntrue;Returnfalse;4 .由頻繁項集產(chǎn)

9、生關(guān)聯(lián)規(guī)則Confidence(A->B)=P(B|A)=support_count(AB)/support_count(A)關(guān)聯(lián)規(guī)則產(chǎn)生步驟如下：1)對于每個頻繁項集l,產(chǎn)生其所有非空真子集；2)對于每個非空真子集s,如果support_count(l)/support_count(s)>=min_conf則輸出s->(l-s),其中，min_conf是最小置信度閾值。例如，在上述例子中，針對頻繁集I1,I2,I5?？梢援a(chǎn)生哪些關(guān)聯(lián)規(guī)則？該頻繁集的非空真子集有I1,I2,I1,I5,I2,I5,I1,I2和I5,對應(yīng)置信度如下：I1&&I2->I5confidence=2/4=50%I1&&I5->I2confidence=2/2=100%I2&&I5->I1confidence=2/2=100%I1->I2&&I5confidence=2/6=33%I2->I1&&am