【文章內(nèi)容簡(jiǎn)介】 s //支持度 ? //可信度 （ 置信度 ） 輸出 : R //滿足 s和 ?的關(guān)聯(lián)規(guī)則集合 ARGen算法： R = ?； for each l?L do for each x ? l such that x ? ? do if support(l)/support(x) ? ? then R = R ? {x ?(lx)}； 有關(guān)算法演示： 參考表 4 44 假定輸入的支持度和可信度分別為 s=30%和 ? =50%。 利用該 s值得到如下大項(xiàng)目集的集合： L={{啤酒 },{面包 },{牛奶 }， {花生醬 }, {面包 、 花生醬 }} 查看最后一個(gè)大項(xiàng)目集可以生成的關(guān)聯(lián)規(guī)則 ,其中： l = {面包、花生醬 } 有兩個(gè)非空子集： {面包 }和 {花生醬 } 對(duì)于第一個(gè)非空子集，可得： support({面包、花生醬 })/support({面包 }) = 60/80 = 意味著關(guān)聯(lián)規(guī)則： “ 面包 ?花生醬”的置信度為 75%，因?yàn)槠渲眯哦雀哂??， 所以是一條有效的關(guān)聯(lián)規(guī)則 。 演示關(guān)聯(lián)規(guī)則的樣本數(shù)據(jù) 事務(wù) 項(xiàng)目 t1 面包、果凍、花生醬 t2 面包、花生醬 t3 面包、牛奶、花生醬 t4 啤酒、面包 t5 啤酒、牛奶 表 43 找出的所有項(xiàng)目集合的支持度 集合 支持度 集合 支持度 啤酒 40 啤酒、面包、牛奶 0 面包 80 啤酒、面包、花生醬 0 果凍 20 啤酒、果凍、牛奶 0 牛奶 40 啤酒、果凍、花生醬 0 花生醬 60 啤酒、牛奶、花生醬 0 啤酒、面包 20 面包、果凍、牛奶 0 啤酒、果凍 0 面包、果凍、花生醬 20 啤酒、牛奶 20 面包、牛奶、花生醬 20 啤酒、花生醬 0 果凍、牛奶、花生醬 0 面包、果凍、 20 啤酒、面包、果凍、牛奶 0 面包、果凍 20 啤酒、面包、果凍、花生醬 0 面包、花生醬 60 啤酒、面包、牛奶、花生醬 0 果凍、牛奶 0 啤酒、果凍、牛奶、花生醬 0 果凍、花生醬 20 面包、果凍、牛奶、花生醬 0 牛奶、花生醬 20 啤酒、面包、果凍、牛奶、花生醬 0 啤酒、面包、果凍 0 項(xiàng)目的個(gè)數(shù)成指數(shù)增長(zhǎng)：從 5個(gè)項(xiàng)目的集合得到 31個(gè)項(xiàng)目集合（忽略空集） 表 44 對(duì)于 第二個(gè)非空子集，可得： support({面包、花生醬 })/support({花生醬 }) = 60/60 = 1 意味著關(guān)聯(lián)規(guī)則： “ 花生醬 ?面包”的置信度為 100%， 也是一條有效的關(guān)聯(lián)規(guī)則 。 找出大項(xiàng)目集的算法可以很簡(jiǎn)單 ， 但代價(jià)很高 。 簡(jiǎn)單的方法是：對(duì)出現(xiàn)在事務(wù)中的所有項(xiàng)目集進(jìn)行計(jì)數(shù) 。 給定一個(gè)大小為 m的項(xiàng)目集合 ， 共有 2m個(gè)子集 ， 去掉空集 ， 則潛在的大項(xiàng)目集數(shù)為 2m 1。 隨著項(xiàng)目數(shù)的增多 ，潛在的大項(xiàng)目集數(shù)成爆炸性增長(zhǎng) 。 （ 當(dāng) m=5， 為 31個(gè)；當(dāng)m=30， 變成 1073741823個(gè) ） 解決問(wèn)題的難點(diǎn)： 如何高效確定所有大項(xiàng)目集 。 大部分關(guān)聯(lián)規(guī)則算法都利用巧妙的方法來(lái)減少要計(jì)數(shù)的項(xiàng)目集。 關(guān)聯(lián)規(guī)則挖掘的 Apriori算法 Apriori算法的基本思想 Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則大 （頻繁 ） 項(xiàng)目集的算法 。 它使用一種稱作逐層搜索的迭代算法 ， 通過(guò) k項(xiàng)集用于探索 （ k+1） 項(xiàng)集 。 已經(jīng)為大部分商業(yè)產(chǎn)品所使用 。 Apriori算法的基本思想是： ? 首先 ， 通過(guò)掃描數(shù)據(jù)集 ， 產(chǎn)生一個(gè)大的候選數(shù)據(jù)項(xiàng)集 ,并計(jì)算每個(gè)候選數(shù)據(jù)項(xiàng)發(fā)生的次數(shù) ， 然后基于預(yù)先給定的最小支持度生成頻繁 1項(xiàng)集的集合 ， 該集合記作 ； ? 然后基于 和數(shù)據(jù)集中的數(shù)據(jù) ， 產(chǎn)生頻繁 2項(xiàng)集 ； ? 用同樣的方法 ， 直到生成頻繁 n項(xiàng)集 ， 其中已不再可能生成滿足最小支持度的 （ N+1） －項(xiàng)集 。 ? 最后 ， 從大數(shù)據(jù)項(xiàng)集中導(dǎo)出規(guī)則 。 1L1L2nL1L1L 2LnL在第一次迭代的第一步中，產(chǎn)生的候選集包含所有 1項(xiàng)集，實(shí)為數(shù)據(jù)庫(kù)中所有的項(xiàng)，再計(jì)算各自的支持度。 實(shí)例 Database TDB 1st scan C1 L1 L2 C2 C2 2nd scan C3 L3 3rd scan Tid Items 10 A, C, D 20 B, C, E 30 A, B, C, E 40 B, E Itemset sup {A} 2 {B} 3 {C} 3 {D} 1 {E} 3 Itemset sup {A} 2 {B} 3 {C} 3 {E} 3 Itemset {A, B} {A, C} {A, E} {B, C} {B, E} {C, E} Itemset sup {A, B} 1 {A, C} 2 {A, E} 1 {B, C} 2 {B, E} 3 {C, E} 2 Itemset sup {A, C} 2 {B, C} 2 {B, E} 3 {C, E} 2 Itemset {B, C, E} Itemset sup {B, C, E} 2 1. 大項(xiàng)目集的性質(zhì) ? 大項(xiàng)目集的任一子集也一定是大的 。 ? 大項(xiàng)目集也稱作是向下封閉的 ， 如果一個(gè)項(xiàng)目集滿足最小支持度的要求 ， 其所有的子集也滿足這一要求 。 ? 其逆命題：如果知道一個(gè)項(xiàng)目集是小的 ， 就不需要生成它的任何超集來(lái)作為它的候選集 ， 因?yàn)樗鼈円惨欢ㄊ切〉?。 ? Apriori性質(zhì)基于如下事實(shí) ：根據(jù)定義 ， 如果項(xiàng)集 I不滿足最小支持度閾值 min_sup， 則 I不是頻繁的 ， 即sup（ I） min_sup。 如果將項(xiàng) A添加到 I， 則結(jié)果項(xiàng)集 （ 即 I∪A ） 不可能比 I更頻繁出現(xiàn) 。 因此 ， I∪A 也不是頻繁的 ， 即 sup（ I∪A ） min_sup。 ? 頻繁項(xiàng)集的 Apriori性質(zhì)用于壓縮搜索空間 （ 剪枝 ） ，以提高逐層產(chǎn)生頻繁項(xiàng)集的效率 。 Apriori算法利用了大項(xiàng)目集的這些性質(zhì) 用圖表示上述性質(zhì) ， 例子中有四個(gè)項(xiàng)目 {A， B， C， D}，格中的線表示子集關(guān)系 ， 大項(xiàng)目集的性質(zhì)表明：如果原來(lái)的項(xiàng)目集是大的 ， 則在路徑中位于其上的任何集合也一定是大的 。 A B D C AB AC AD BC BD CD 216。 ABC ABD BCD ACD ABCD {A， B， C， D}項(xiàng)目集的格結(jié)構(gòu) 項(xiàng)目 {ACD}的非空子集是： {AC， AD， CD， A，C， D} 如果 {A， C， D}是大的 ， 則其每一個(gè)子集也是大的 ，如果其任何一個(gè)子集是小的 ， 則 {A， C， D}也是小的 。 216。 A B D C AB AC AD BC BD CD ABC ABD BCD ACD ABCD {A， C， D}的子集 項(xiàng)目 {ACD}的非空子集是： {AC， AD， CD， A，C， D} 按照 Apriori算法： ? 在第 i趟掃描的過(guò)程中 ， 對(duì) Ci進(jìn)行計(jì)數(shù) ， 只有那些大的候選集被用于生成下一趟掃描的候選集 ， 即用 Li生成Ci+1。 ? 只有一個(gè)項(xiàng)目集的所有子集都是大的 ， 它才被認(rèn)為是候選 。 ? 為了生成大小為 i+1的候選 ， 要對(duì)前一趟掃描發(fā)現(xiàn)的大項(xiàng)目集進(jìn)行連接運(yùn)算 。 ? 表示： Lk*Lk = {X?Y 其中 X， Y? Lk， |X?Y|=k – 1} 例：對(duì)表 43進(jìn)行演算 ， 其中 s=30%， ? =50% ? 假如有項(xiàng)目集合 I={1， 2， 3， 4， 5}，有事務(wù)集 T： ? 1,2,3 ? 1,2,4 ? 1,3,4 ? 1,2,3,5 ? 1,3,5 ? 2,4,5 ? 1,2,3,4 ? 設(shè)定 minsup=3/7， misconf=5/7。 首先：生成頻繁項(xiàng)目集： 1頻繁項(xiàng)目集： {1}， {2}， {3}， {4}， {5} 生成 2頻繁項(xiàng)目集： 根據(jù) 1頻繁項(xiàng)目集生成所有的包含 2個(gè)元素的項(xiàng)目集：任意取兩個(gè)只有最后一個(gè)元素不同的 1頻繁項(xiàng)目集，求其并集，由于每個(gè) 1頻繁項(xiàng)目集元素只有一個(gè)，所以生成的項(xiàng)目集如下： {1， 2}， {1， 3}， {1， 4}， {