高級人工智能第十二章

1、2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植1高級人工智能高級人工智能第十二章第十二章 史忠植史忠植 中國科學(xué)院計算技術(shù)研究所關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則 Association Rules Association Rules 2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植2內(nèi)容提要內(nèi)容提要 l引言引言lApriori 算法算法lFrequent-pattern tree 和和FP-growth 算法算法l多維關(guān)聯(lián)規(guī)則挖掘多維關(guān)聯(lián)規(guī)則挖掘l相關(guān)規(guī)則相關(guān)規(guī)則l關(guān)聯(lián)規(guī)則改進(jìn)關(guān)聯(lián)規(guī)則改進(jìn)l總結(jié)總結(jié)2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植3關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則 l關(guān)聯(lián)規(guī)則反映一個事物與其他事物之間的相互依存性和關(guān)聯(lián)

2、性。如果兩個或者多個事物之間存在一定的關(guān)聯(lián)關(guān)系，那么，其中一個事物就能夠通過其他事物預(yù)測到。關(guān)聯(lián)規(guī)則表示了項之間的關(guān)系。l示例:cereal, milk fruit“買谷類食品和牛奶的人也會買水果.”商店可以把牛奶和谷類食品作特價品以使人們買更多的水果.2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植4市場購物籃分析市場購物籃分析l分析事務(wù)數(shù)據(jù)庫表l我們是否可假定?lChips = Salsa Lettuce = SpinachPersonBasketAChips, Salsa, Cookies, Crackers, Coke, BeerBLettuce, Spinach, Oranges, Ce

3、lery, Apples, GrapesCChips, Salsa, Frozen Pizza, Frozen CakeDLettuce, Spinach, Milk, Butter2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植5基本概念l通常, 數(shù)據(jù)包含:TIDBasket事務(wù) ID項的子集2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植6 關(guān)聯(lián)規(guī)則挖掘l在事務(wù)數(shù)據(jù)庫,關(guān)系數(shù)據(jù)庫和其它信息庫中的項或?qū)ο蟮募现g,發(fā)現(xiàn)頻繁模式,關(guān)聯(lián),相關(guān),或因果關(guān)系的結(jié)構(gòu).l頻繁模式: 數(shù)據(jù)庫中出現(xiàn)頻繁的模式(項集,序列,等等)2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植7基本概念l項集項集l事務(wù)事務(wù)l關(guān)聯(lián)規(guī)則關(guān)

4、聯(lián)規(guī)則l - 事務(wù)數(shù)據(jù)集 (例如右圖例如右圖)l事務(wù)標(biāo)識事務(wù)標(biāo)識 TID 每一個事務(wù)關(guān)聯(lián)著一個標(biāo)識每一個事務(wù)關(guān)聯(lián)著一個標(biāo)識,稱作稱作TID.IT ,.,21miiiI BAIBIABA,DTransaction-idItems bought10A, B, C20A, C30A, D40B, E, F2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植8關(guān)聯(lián)規(guī)則的度量l支持度支持度s slD D中包含中包含A A和和 B B 的事務(wù)數(shù)與總的事務(wù)數(shù)的比值的事務(wù)數(shù)與總的事務(wù)數(shù)的比值規(guī)則規(guī)則 A AB B 在數(shù)據(jù)集在數(shù)據(jù)集D D中的支持度為中的支持度為s, s, 其中其中s s 表示表示D D中包含中包含A

5、A B B ( (即同時包含即同時包含A A和和B)B)的事務(wù)的百分率的事務(wù)的百分率. .|)(DTBADTBAs2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植9關(guān)聯(lián)規(guī)則的度量l可信度可信度 c clD D中同時包含中同時包含A A和和B B的事務(wù)數(shù)與只包含的事務(wù)數(shù)與只包含A A的事務(wù)數(shù)的比值的事務(wù)數(shù)的比值|)(TADTTBADTBAc規(guī)則 AB 在數(shù)據(jù)集D中的可信度為c, 其中c表示D中包含A的事務(wù)中也包含B的百分率.即可用條件概率P(B|A)表示. confidence(A B )=P(B|A) 條件概率條件概率 P(B|A) P(B|A) 表示表示A A發(fā)生的條件下發(fā)生的條件下B B也發(fā)生

6、的概率也發(fā)生的概率. .2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植10關(guān)聯(lián)規(guī)則的度量l關(guān)聯(lián)規(guī)則根據(jù)以下兩個標(biāo)準(zhǔn)(包含或排除):l最小支持度 表示規(guī)則中的所有項在事務(wù)中出現(xiàn)的頻度l最小可信度 - 表示規(guī)則中左邊的項(集)的出現(xiàn)暗示著右邊的項(集)出現(xiàn)的頻度2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植11市場購物籃分析I是什么?事務(wù)ID B的T是什么?s(Chips=Salsa) 是什么?c(Chips=Salsa)是什么?事務(wù) ID購物籃AChips, Salsa, Cookies, Crackers, Coke, BeerBLettuce, Spinach, Oranges, Celery,

7、 Apples, GrapesCChips, Salsa, Frozen Pizza, Frozen CakeDLettuce, Spinach, Milk, Butter, Chips2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植12頻繁項集l項集 任意項的集合lk-項集 包含k個項的項集l頻繁 (或大)項集 滿足最小支持度的項集l若I包含m個項,那么可以產(chǎn)生多少個項集?2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植13強(qiáng)關(guān)聯(lián)規(guī)則l給定一個項集,容易生成關(guān)聯(lián)規(guī)則.l項集: Chips, Salsa, BeerlBeer, Chips = SalsalBeer, Salsa = ChipslChi

8、ps, Salsa = Beerl強(qiáng)規(guī)則是有趣的l強(qiáng)規(guī)則通常定義為那些滿足最小支持度和最小可信度的規(guī)則.2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植14關(guān)聯(lián)規(guī)則挖掘l兩個基本步驟l找出所有的頻繁項集l滿足最小支持度l找出所有的強(qiáng)關(guān)聯(lián)規(guī)則l由頻繁項集生成關(guān)聯(lián)規(guī)則l保留滿足最小可信度的規(guī)則2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植15內(nèi)容提要 l引言lApriori 算法lFrequent-pattern tree 和FP-growth 算法l多維關(guān)聯(lián)規(guī)則挖掘l相關(guān)規(guī)則l關(guān)聯(lián)規(guī)則改進(jìn)l總結(jié)2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植16AprioriApriori算法算法lIBM公司Almade

9、n研究中心的R.Agrawal 等人在1993年提出的AIS和SETM。l在1994年提出Apriori和AprioriTid。Apriori和AprioriTid算法利用前次過程中的數(shù)據(jù)項目集來生成新的候選數(shù)據(jù)項目集，減少了中間不必要的數(shù)據(jù)項目集的生成，提高了效率2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植17生成頻繁項集lNave algorithmn - |D|for each subset s of I do l - 0 for each transaction T in D do if s is a subset of T then l - l + 1 if minimum supp

10、ort = l/n then add s to frequent subsets2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植18生成頻繁項集lnave algorithm的分析lI 的子集: O(2m) l為每一個子集掃描n個事務(wù)l測試s為T的子集: O(2mn) l隨著項的個數(shù)呈指數(shù)級增長!l我們能否做的更好?2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植19Apriori 性質(zhì)l定理定理(Apriori 性質(zhì)性質(zhì)): 若A是一個頻繁項集,則A的每一個子集都是一個頻繁項集.l證明證明:設(shè)n為事務(wù)數(shù).假設(shè)A是l個事務(wù)的子集,若 A A , 則A 為l (l l )個事務(wù)的子集.因此, l/n s

11、(最小支持度), l/n s也成立.2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植20Apriori 算法lApriori算法是一種經(jīng)典的生成布爾型關(guān)聯(lián)規(guī)則的頻繁項集挖掘算法.算法名字是緣于算法使用了頻繁項集的性質(zhì)這一先驗知識.l思想: Apriori 使用了一種稱作level-wise搜索的迭代方法,其中k-項集被用作尋找(k+1)-項集.首先,找出頻繁1-項集,以L1表示.L1用來尋找L2,即頻繁2-項集的集合.L2用來尋找L3,以此類推,直至沒有新的頻繁k-項集被發(fā)現(xiàn).每個Lk都要求對數(shù)據(jù)庫作一次完全掃描.2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植21生成頻繁項集l中心思想: 由頻繁(k

12、-1)-項集構(gòu)建候選k-項集l方法l找到所有的頻繁1-項集l擴(kuò)展頻繁(k-1)-項集得到候選k-項集l剪除不滿足最小支持度的候選項集2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植22Apriori: 一種候選項集生成-測試方法lApriori 剪枝原理: 若任一項集是不頻繁的,則其超集不應(yīng)該被生成/測試!l方法: l由頻繁k-項集生成候選(k+1)-項集,并且l在DB中測試候選項集l性能研究顯示了Apriori算法是有效的和可伸縮(scalablility)的.2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植23The Apriori 算法算法一個示例一個示例Database TDB1st scan

13、C1L1L2C2C22nd scanC3L33rd scanTidItems10A, C, D20B, C, E30A, B, C, E40B, EItemsetsupA2B3C3D1E3ItemsetsupA2B3C3E3ItemsetA, BA, CA, EB, CB, EC, EItemsetsupA, B1A, C2A, E1B, C2B, E3C, E2ItemsetsupA, C2B, C2B, E3C, E2ItemsetB, C, EItemsetsupB, C, E22022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植24Apriori 算法算法Algorithm: Apriori輸

14、入輸入: Database, D, of transactions; minimum support threshold,min_sup.輸出輸出: L, freuqent itemsets in D.過程過程:Ck: Candidate itemset of size kLk : frequent itemset of size kL1 = find_frequent_1_itemsets(D);for (k = 2; Lk+1 !=; k+) do begin Ck = apriori_gen(Lk-1 ,min_sup); for each transaction t in databa

15、se D do/scan D for counts Ct =subset(Ck ,t);/ get the subsets of t that are candidates For each candidate c Ct c.count+; Lk = candidates in Ck with min_support endreturn L=k Lk;2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植25Apriori 算法算法Procedure apriori_gen(Lk-1: frequent (k-1)-itemsets; min_sup:minimum support threshold

16、)for each itemset l1 Lk-1 for each itemset l2Lk-1 if(l11=l21) (l12=l22) (l1k-1=l2k-1) Then c=join(l1,l2)/join step: generate candidates if has_infrequent_subset(c, Lk-1 ) then delete c;/prune step: remove unfruitful candidate else add c to Ckreturn Ck2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植26Apriori 算法算法Join is gener

17、ate candidates set of itemsets Ck from 2 itemsets in Lk-1Procedure join(p,q) insert into Ck select p.item1, p.item2,., p.itemk-1, q.itemk-1 from Lk-1 p, Lk-1 q where p.item1=q.item1, ., p.itemk-2=q.itemk-2, p.itemk-1 = q.itemk-12022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植27Apriori 算法算法 Procedure has_infrequent_subset(c:c

18、andidate k-itemset;Lk-1: frequent (k-1)-itemsets;)/use prior knowledge for each (k-1)-subset s of c if s Lk-1 then return TRUE;return FALSE.2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植28Apriori 算法算法l如何生成候選項集?l步驟 1: 自連接 Lkl步驟 2: 剪枝l如何計算候選項集的支持度?l候選項庥生成的示例lL3= abc, abd, acd, ace, bcd l自連接: L3*L3l由abcabc 和abdabd 連接得到abcdabc

19、d l由acdacd 和aceace 連接得到acdeacdel剪枝:l因為adeade 不在L L3 3中acdeacde 被剪除lC4=abcd2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植29如何生成候選項集如何生成候選項集? ?l假定Lk-1中的項以一定順序排列l(wèi)步驟 1: 自連接 Lk-1 insert into Ckselect p.item1, p.item2, , p.itemk-1, q.itemk-1from Lk-1 p, Lk-1 qwhere p.item1=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1 q.itemk-1l步驟 2

20、: 剪枝forall itemsets c in Ck doforall (k-1)-subsets s of c doif (s is not in Lk-1) then delete c from Ck2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植30如何計算候選項集的支持度如何計算候選項集的支持度? ?l為何候選項集的支持度的計算是一個問題?l候選項集的總數(shù)可能是巨大的l 一個事務(wù)可能包含多個候選項集l方法:l候選項集被存儲在一個哈希樹l哈希樹的葉子結(jié)點包含一個項集和計數(shù)的列表l內(nèi)部結(jié)點 包含一個哈希表l子集函數(shù): 找出包含在一個事務(wù)中的所有候選項集2022-2-23AA12 關(guān)聯(lián)規(guī)則 史

21、忠植31頻繁模式挖掘的挑戰(zhàn)l挑戰(zhàn)l多次掃描事務(wù)數(shù)據(jù)庫l巨大數(shù)量的候選項集l繁重的計算候選項集的支持度工作l改進(jìn) Apriori: 大體的思路l減少事務(wù)數(shù)據(jù)庫的掃描次數(shù)l縮減候選項集的數(shù)量l使候選項集的支持度計算更加方便2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植32AprioriTidAprioriTid算法算法lAprioriTid算法由Apriori算法改進(jìn)l優(yōu)點：只和數(shù)據(jù)庫做一次交互，無須頻繁訪問數(shù)據(jù)庫l將Apirori中的Ck 擴(kuò)展，內(nèi)容由c變?yōu)門ID，c，TID用于唯一標(biāo)識事務(wù)l引入Bk ，使得Bk 對于事務(wù)的項目組織集合，而不是被動的等待Ck 來匹配2022-2-23AA12 關(guān)聯(lián)

22、規(guī)則 史忠植33AprioriTidAprioriTid算法算法l舉例：minsupp = 2l數(shù)據(jù)庫：TID項目1001 3 42002 3 5300 1 2 3 54002 52022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植34AprioriTidAprioriTid算法算法示例示例TID項目集1001 3 42002 3 5300 1 2 3 54002 5項集支持度12233 3532022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植35ApioriTidApioriTid算法示例算法示例TID項目集1001 32002 3 2 5 3 5 300 1 2 1 3 1 5 2 3 2 5 3 54

23、002 5項集支持度1 322 322 5 33 522022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植36ApioriTidApioriTid算法示例算法示例TID項目集100 空2002 3 5300 2 3 5 400 空2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植37ApioriTidApioriTid算法算法l上面圖中分別為Bk 和Lk ，而Ck 和Apriori算法產(chǎn)生的一樣，因此沒有寫出來l可以看到Bk 由Bk-1 得到，無須由數(shù)據(jù)庫取數(shù)據(jù)l缺點：內(nèi)存要求很大，事務(wù)過多的時候資源難以滿足2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植38內(nèi)容提要 l引言lApriori 算法lFreque

24、nt-pattern tree 和FP-growth 算法l多維關(guān)聯(lián)規(guī)則挖掘l相關(guān)規(guī)則l關(guān)聯(lián)規(guī)則改進(jìn)l總結(jié)2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植39頻繁模式挖掘的瓶頸頻繁模式挖掘的瓶頸l多次掃描數(shù)據(jù)庫是高代價的l長模式的挖掘需要多次掃描數(shù)據(jù)庫以及生成許多的候選項集l找出頻繁項集 i1i2i100l掃描次數(shù): 100l候選項集的數(shù)量: (1001) + (1002) + + (110000) = 2100-1 = 1.27*1030 !l瓶頸:候選項集-生成-測試l我們能否避免生成候選項集?2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植40不生成候選項集的頻繁模式挖掘不生成候選項集的頻繁模式

25、挖掘l利用局部頻繁的項由短模式增長為長模式l“abc” 是一個頻繁模式l得到所有包含 “abc”的事務(wù): DB|abcl“d” 是 DB|abc 的一個局部頻繁的項 abcd 是一個頻繁模式2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植41FP Growth算法算法 (Han, Pei, Yin 2000)lApriori算法的一個有問題的方面是其候選項集的生成l指數(shù)級增長的來源l另一種方法是使用分而治之的策略(divide and conquer)l思想思想: 將數(shù)據(jù)庫的信息壓縮成一個描述頻繁項相關(guān)信息的頻繁模式樹2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植42利用利用FP-FP-樹進(jìn)行頻繁模

26、式挖掘樹進(jìn)行頻繁模式挖掘l思想: 頻繁模式增長l遞歸地增長頻繁模式借助模式和數(shù)據(jù)庫劃分l方法 l對每個頻繁項,構(gòu)建它的條件模式基,然后構(gòu)建它的條件FP-樹.l對每個新創(chuàng)建的條件FP-樹重復(fù)上述過程l直至結(jié)果FP-樹為空,或者它僅包含一個單一路徑.該路徑將生成其所有的子路徑的組合,每個組合都是一個頻繁模式.2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植43頻繁頻繁 1-1-項集項集l最小支持度為20% (計數(shù)為 2)TIDItems1I1,I2,I52I2,I43I2,I3,I64I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3ItemsetSuppo

27、rt countI16I27I36I42I52I61ItemsetSupport countI16I27I36I42I52 事務(wù)數(shù)據(jù)庫 支持度計數(shù) 頻繁1-項集2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植44FP-FP-樹樹 構(gòu)建構(gòu)建ItemsetSupport countI16I27I36I42I52ItemsetSupport countI27I16I36I42I52按支持度降序排列2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植45FP-FP-樹樹 構(gòu)建構(gòu)建 創(chuàng)建根結(jié)點null 掃描數(shù)據(jù)庫 事務(wù)1: I1, I2, I5 排序: I2, I1, I5 處理事務(wù) 以項的順序增加結(jié)點 標(biāo)注項及其

28、計數(shù)(I2,1)(I1,1)(I5,1)1I50I40I31I11I2 維護(hù)索引表2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植46FP-FP-樹樹 構(gòu)建構(gòu)建null(I2,2)(I1,1)(I5,1)0I51I40I30I12I2(I4,1)TIDItems1I1,I2,I52I2,I43I2,I3,I64I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I32022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植47FP-FP-樹樹 構(gòu)建構(gòu)建null(I2,7)(I1,4)(I5,1)2I52I46I36I17I2(I4,1)TIDItems1I1,I2,I52I

29、2,I43I2,I3,I64I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3(I3,2)(I3,2)(I1,2)(I3,2)(I4,1)(I5,1)2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植48FP-FP-樹樹 構(gòu)建構(gòu)建l掃描事務(wù)數(shù)據(jù)庫D一次,得到頻繁項的集合F及它們的支持度.將F按支持度降序排列成L,L是頻繁項的列表.l創(chuàng)建FP-樹的根, 標(biāo)注其為NULL.對D中的每個事務(wù)進(jìn)行以下操作:l根據(jù) L中的次序?qū)κ聞?wù)中的頻繁項進(jìn)行選擇和排序. 設(shè)事務(wù)中的已排序的頻繁項列表為p|P,其中p表示第一個元素,P表示剩余的列表.調(diào)用insert_Tree(p

30、|P,T).2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植49FP-FP-樹樹 構(gòu)建構(gòu)建lInsert_Tree(p|P,T) If T has a child N such that N.item-name= p.item-name, then increment Ns count by 1; else create a new node N, and let its count be 1, its parent link be linked to T, and its node- link to the nodes with the same item-name via the node-l

31、ink structure. If P is nonempty, call insert_tree(P,N) recursively. 2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植50挖掘挖掘 FP-treeFP-treel從索引表中的最后一個項開始l找到所有包含該項的路徑l沿著結(jié)點-鏈接(node-links)l確定條件模式l路徑中符合頻度要求的模式l構(gòu)建 FP-tree Cl添加項至C中所有路徑,生成頻繁模式l遞歸地挖掘C (添加項)l從索引表和樹中移除項2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植51挖掘挖掘 FP-TreeFP-Treenull(I2,7)(I1,4)(I5,1)2I5

32、2I46I36I17I2(I4,1)(I3,2)(I3,2)(I4,1)(I5,1)(I1,2)(I3,2) 前綴路徑(I2 I1,1)(I2 I1 I3, 1)條件路徑(I2 I1, 2) 條件 FP-tree (I2 I1 I5, 2), (I2 I5, 2), (I1 I5, 2)null(I2,2)(I1,2)2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植52挖掘挖掘 FP-Tree項條件模式基條件FP-tree生成的頻繁模式I5(I2 I1:1),(I2 I1 I3:1)I2 I5:2,I1 I5:2,I2 I1 I5:2I4(I2 I1:1),(I2:1)I2 I4:2I3(I2 I

33、1:2,(I2:2),(I1:2),I2 I3:4,I1 I3:2,I2 I1 I3:2I1(I2:4)I2 I1:42022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植53挖掘挖掘 FP-TreeProcedure FP_growth(Tree, )(1)If Tree contains a single path P then (2) for each combination (denote as ) of the nodes in the path P(3) generate pattern with support = minisup of nodes in ;(4)Else for each

34、 ai in the header of Tree (5) generate pattern =ai with support =ai.support;(6) construct , s conditional pattern base and then conditional FP_tree Tree;(7) IF Tree then(8) call FP_growth(Tree, ); 2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植54由事務(wù)數(shù)據(jù)庫構(gòu)建由事務(wù)數(shù)據(jù)庫構(gòu)建FP-FP-樹樹f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem frequ

35、ency head f4c4a3b3m3p3min_support = 3TIDItems bought (ordered) frequent items100f, a, c, d, g, i, m, pf, c, a, m, p200a, b, c, f, l, m, of, c, a, b, m300 b, f, h, j, o, wf, b400 b, c, k, s, pc, b, p500 a, f, c, e, l, p, m, nf, c, a, m, p1. 掃描DB一次,找到頻繁1項 (單一項模式)2. 按支持度降序?qū)︻l繁項排序為 F-list3. 再次掃描DB,構(gòu)建FP-t

36、reeF-list=f-c-a-b-m-p2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植55劃分模式和數(shù)據(jù)庫劃分模式和數(shù)據(jù)庫l頻繁模式根據(jù)F-list可以被劃分為若干子集lF-list=f-c-a-b-m-pl包含 p的模式l包含 m 但包含 p的模式ll包含 c 但不包含 a ,b, m, p的模式l模式 fl完整性 和 非冗余性2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植56從從P P的條件數(shù)據(jù)庫找出包含的條件數(shù)據(jù)庫找出包含P P的模式的模式l從 FP-tree的索引表的頻繁項開始l沿著每個頻繁項p的鏈接遍歷 FP-treel累積項p的所有轉(zhuǎn)換前綴路徑來形成的p的條件模式基條件模式基條件模式

37、基項項 條件模式基條件模式基cf:3afc:3bfca:1, f:1, c:1mfca:2, fcab:1pfcam:2, cb:1f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem frequency head f4c4a3b3m3p32022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植57遞歸遞歸: : 挖掘每個條件挖掘每個條件FP-treeFP-treef:3c:3a:3m-條件條件 FP-tree“am”的條件模式基: (fc:3)f:3c:3am-條件條件 FP-tree“cm”的條件模式基: (f:3)f:3cm-條件條件 FP-tree“c

38、am”的條件模式基: (f:3)f:3cam-條件條件 FP-tree2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植58一個特例一個特例: FP-tree: FP-tree中的單一前綴路徑中的單一前綴路徑l假定 (條件的) FP-tree T 有一個共享的單一前綴路徑 Pl挖掘可以分為兩部分l將單一前綴路徑約簡為一個結(jié)點l將兩部分的挖掘結(jié)果串聯(lián)a2:n2a3:n3a1:n1b1:m1C1:k1C2:k2C3:k3b1:m1C1:k1C2:k2C3:k3r1+a2:n2a3:n3a1:n1r1=2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植59通過通過 DB DB 投影投影(Projection)(

39、Projection)使使FP-growthFP-growth可可伸縮伸縮lFP-tree 不能全放入內(nèi)存?DB 投影l(fā)首先將一個數(shù)據(jù)庫劃分成一個由若干投影(Projected)數(shù)據(jù)庫組成的集合l然后對每個投影數(shù)據(jù)庫構(gòu)建和挖掘 FP-treelParallel projection vs. Partition projection 技術(shù)lParallel projection is space costly2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植60Partition-based ProjectionlParallel projection 需要很多磁盤空間lPartition proje

40、ction 節(jié)省磁盤空間Tran. DB fcampfcabmfbcbpfcampp-proj DB fcamcbfcamm-proj DB fcabfcafcab-proj DB fcba-proj DBfcc-proj DBff-proj DB am-proj DB fcfcfccm-proj DB fff2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植61改進(jìn)途徑改進(jìn)途徑l使用哈希表存儲候選k-項集的支持度計數(shù)l移除不包含頻繁項集的事務(wù)l對數(shù)據(jù)采樣l劃分?jǐn)?shù)據(jù)l若一個項集是頻繁的,則它必定在某個數(shù)據(jù)分區(qū)中是頻繁的.2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植62FP-tree FP-tree

41、結(jié)構(gòu)的優(yōu)點結(jié)構(gòu)的優(yōu)點l完整性 l保持了頻繁項集挖掘的完整信息l沒有打斷任何事務(wù)的長模式l緊密性l減少不相關(guān)的信息不頻繁的項沒有了l項按支持度降序排列: 越頻繁出現(xiàn),越可能被共享l決不會比原數(shù)據(jù)庫更大 (不計結(jié)點鏈接和計數(shù)域)l對 Connect-4 數(shù)據(jù)庫, 壓縮比率可以超過1002022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植63關(guān)聯(lián)規(guī)則可視化關(guān)聯(lián)規(guī)則可視化: 方格圖方格圖(Pane Graph)2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植64關(guān)聯(lián)規(guī)則可視化關(guān)聯(lián)規(guī)則可視化: : 規(guī)則圖規(guī)則圖(Rule Graph)(Rule Graph)2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植65內(nèi)容提要

42、l引言lApriori 算法lFrequent-pattern tree 和FP-growth 算法l多維關(guān)聯(lián)規(guī)則挖掘l相關(guān)規(guī)則l關(guān)聯(lián)規(guī)則改進(jìn)l總結(jié)2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植66挖掘多種規(guī)則或規(guī)律挖掘多種規(guī)則或規(guī)律l多層(Multi-level),量化(quantitative)關(guān)聯(lián)規(guī)則, 相關(guān)(correlation)和因果(causality), 比率(ratio)規(guī)則, 序列 (sequential) 模式,浮現(xiàn)(emerging)模式, temporal associations, 局部周期(partial periodicity)l分類(classification

43、),聚類(clustering),冰山立方體( iceberg cubes), 等等.2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植67多層關(guān)聯(lián)規(guī)則多層關(guān)聯(lián)規(guī)則l項常常構(gòu)成層次l可伸縮的(flexible)支持度設(shè)置: 在較低層的項預(yù)期有較低的支持度.l事務(wù)數(shù)據(jù)庫可以基于維度和層次編碼l探尋共享多層挖掘統(tǒng)一支持度Milksupport = 10%2% Milk support = 6%Skim Milk support = 4%Level 1min_sup = 5%Level 2min_sup = 5%Level 1min_sup = 5%Level 2min_sup = 3%減少的支持度202

44、2-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植68可伸縮的支持度約束的多層可伸縮的支持度約束的多層/ /多維多維(ML/MD)(ML/MD)關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則l為什么設(shè)置可伸縮的支持度?l實際生活中項的出現(xiàn)頻率變化巨大l在一個商店購物籃中的鉆石,手表,鋼筆l統(tǒng)一的支持度未必是一個有趣的模型l一個可伸縮模型l較低層的,較多維的組合以及長模式通常具有較小的支持度l總體規(guī)則應(yīng)該要容易說明和理解l特殊的項和特殊的項的組合可以特別設(shè)定(最小支持度)以及擁有更高的優(yōu)先級2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植69多維關(guān)聯(lián)規(guī)則多維關(guān)聯(lián)規(guī)則l單維規(guī)則:buys(X, “milk”) buys(X, “bread”)

45、l多維規(guī)則: 2 個維度或謂詞( predicates)l跨維度(Inter-dimension)關(guān)聯(lián)規(guī)則 (無重復(fù)謂詞)age(X,”19-25”) occupation(X,“student”) buys(X,“coke”)l混合維度(hybrid-dimension)關(guān)聯(lián)規(guī)則 (重復(fù)謂詞)age(X,”19-25”) buys(X, “popcorn”) buys(X, “coke”)l分類(Categorical)屬性l有限的幾個可能值,值之間不可排序l數(shù)量(Quantitative)屬性l數(shù)值的,值之間有固有的排序2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植70多層關(guān)聯(lián)規(guī)則多層關(guān)聯(lián)規(guī)

46、則: :冗余濾除冗余濾除l根據(jù)項之間的”先輩” (ancestor)關(guān)系,一些規(guī)則可能是冗余的. l示例lmilk wheat bread support = 8%, confidence = 70%l2% milk wheat bread support = 2%, confidence = 72%l我們說第1個規(guī)則是第2個規(guī)則的先輩.l一個規(guī)則是冗余的,當(dāng)其支持度接近基于先輩規(guī)則的”預(yù)期”(expected)值.2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植71多層關(guān)聯(lián)規(guī)則多層關(guān)聯(lián)規(guī)則: :逐步深化逐步深化(Progressive Deepening)(Progressive Deepeni

47、ng)l一個自上而下的,逐步深化的方法:l 首先挖掘高層的頻繁項: milk (15%), bread (10%)l 然后挖掘它們的較低層”較弱” (weaker)頻繁項: 2% milk (5%), wheat bread (4%)l多層之間不同的最小支持度閾值導(dǎo)致了不同的算法:l如果在多個層次間采用了相同的最小支持度,若t的任何一個先輩都是非頻繁的則扔棄(toss)t.l如果在較低層采用了減少的最小支持度，則只檢驗?zāi)切┫容叺闹С侄仁穷l繁的不可忽略的派生（descendents）即可2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植72多維關(guān)聯(lián)規(guī)則挖掘的技術(shù)多維關(guān)聯(lián)規(guī)則挖掘的技術(shù)l搜索頻繁 k-謂

48、詞集(predicate set):l示例: age, occupation, buys是一個 3-謂詞集以age處理的方式,技術(shù)可以如下分類1. 利用數(shù)量屬性的統(tǒng)計離散(static discretization)方法 利用預(yù)先確定的概念層次對數(shù)量屬性進(jìn)行統(tǒng)計離散化2. 量化關(guān)聯(lián)規(guī)則l基于數(shù)據(jù)的分布,數(shù)量屬性被動態(tài)地離散化到不同的容器空間(bins)3. 基于距離(Distance-based)的關(guān)聯(lián)規(guī)則l這是一個動態(tài)離散化的過程,該過程考慮數(shù)據(jù)點之間的距離2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植73數(shù)量屬性的統(tǒng)計離散化數(shù)量屬性的統(tǒng)計離散化l挖掘之前利用概念層次離散化l數(shù)值被范圍(ran

49、ges)替代.l關(guān)系數(shù)據(jù)庫中,找出所有的頻繁k-謂詞(predicate)集要求 k 或 k+1次表掃描.l數(shù)據(jù)立方體(data cube)非常適合數(shù)據(jù)挖掘.lN-維立方體的 cells 與謂詞集( predicate sets)相對應(yīng).l通過數(shù)據(jù)立方體挖掘會非?？焖?(income)(age)()(buys)(age, income)(age,buys) (income,buys)(age,income,buys)2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植74量化關(guān)聯(lián)規(guī)則量化關(guān)聯(lián)規(guī)則age(X,”30-34”) income(X,”24K - 48K”) buys(X,”high reso

50、lution TV”)l數(shù)值屬性動態(tài)離散化l這樣挖掘的規(guī)則的可信度或緊密度最大化l2-維 量化關(guān)聯(lián)規(guī)則: Aquan1 Aquan2 Acatl示例2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植75Mining Distance-based Association RuleslBinning methods do not capture the semantics of interval datalDistance-based partitioning, more meaningful discretization considering:ldensity/number of points in

51、 an intervall“closeness” of points in an intervalPrice($)Equi-width(width $10)Equi-depth(depth 2)Distance-based70,107,207,72011,2022,5020,222221,3051,5350,535031,405141,505351,602022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植76Interestingness Measure: Correlations (Lift)lplay basketball eat cereal 40%, 66.7% is misleadinglT

52、he overall percentage of students eating cereal is 75% which is higher than 66.7%.lplay basketball not eat cereal 20%, 33.3% is more accurate, although with lower support and confidencelMeasure of dependent/correlated events: liftBasketballNot basketballSum (row)Cereal200017503750Not cereal100025012

53、50Sum(col.)300020005000)()()(,BPAPBAPcorrBA2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植77內(nèi)容提要 l引言lApriori 算法lFrequent-pattern tree 和FP-growth 算法l多維關(guān)聯(lián)規(guī)則挖掘l相關(guān)規(guī)則l關(guān)聯(lián)規(guī)則改進(jìn)l總結(jié)2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植78相關(guān)規(guī)則相關(guān)規(guī)則(Correlation Rules)(Correlation Rules)l“Beyond Market Baskets,” Brin et al.l假設(shè)執(zhí)行關(guān)聯(lián)規(guī)則挖掘ccrowt20525t70575col9010100tea = cof

54、fee20% support80% confidencebut 90% of the people buy coffee anyway!2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植79相關(guān)規(guī)則相關(guān)規(guī)則l一種度量是計算相關(guān)性l若兩個隨機(jī)變量 A 和 B 是統(tǒng)計獨(dú)立的l對tea 和 coffee:1)()()(BPAPBAP89.0)()()(cPtPctP2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植80相關(guān)規(guī)則相關(guān)規(guī)則l利用 2 統(tǒng)計檢驗來測試獨(dú)立性l設(shè)n為購物籃的總數(shù)l設(shè)k為考慮的項的總數(shù)l設(shè) r 為一個包含項 (ij, ij)的規(guī)則l設(shè)O(r) 表示包含規(guī)則r的購物籃的數(shù)量 (即頻率)l對單

55、個項ij,設(shè) Eij = O(ij) (反過來即為 n - Eij)lEr = n * Er1/n * * Erk / n2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植81相關(guān)規(guī)則相關(guān)規(guī)則l2 統(tǒng)計量定義為lLook up for significance value in a statistical textbooklThere are k-1 degrees of freedomlIf test fails cannot reject independence, otherwise contigency table represents dependence.RrrErErO)(222022

56、-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植82示例示例lBack to tea and coffeelEt = 25, Et=75, Ec=90, Ec=10lEtc=100 * 25/100 * 90 /100=22.5lO(tc) = 20lContrib. to 2 = (20 - 22.5)2 / 22.5 = 0.278lCalculate for the rest to get 2=2.204lNot significant at 95% level (3.84 for k=2)lCannot reject independence assumptionccrowt20525t 7057

57、5col90101002022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植83興趣度（興趣度（InterestInterest）lIf 2 test shows significance, then want to find most interesting cell(s) in tablelI(r) = O(r)/ErlLook for values far away from 1lI(tc) = 20/22.5 = 0.89lI(tc) = 5/2.5 = 2lI(tc) = 70/67.5 = 1.04lI(tc) = 5/7.5 = 0.662022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植842

58、統(tǒng)計量的性質(zhì)l上封閉性(Upward closed)l若一個k-項集是相關(guān)的,則其所有的超集也是相關(guān)的.l尋找最小的相關(guān)的項集l沒有子集是相關(guān)的l能否將a-priori and 2 統(tǒng)計量有效地結(jié)合lNo generate and prune as in support-confidence2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植85其它度量其它度量(Measures)(Measures)l(A B) P(A,B)P(A)P(B)TIDItems1I1,I2,I52I2,I43I2,I3,I64I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3l

59、作用度(Lift)l度量項之間的相關(guān)性,但沒有檢驗2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植86其它度量其它度量(Measures)(Measures)l可信度(Conviction)l度量一個規(guī)則的強(qiáng)度A B (AB)c(A B) P(A)P(B)P(A,B)TIDItems1I1,I2,I52I2,I43I2,I3,I64I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I32022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植87內(nèi)容提要 l引言lApriori 算法lFrequent-pattern tree 和FP-growth 算法l多維關(guān)聯(lián)規(guī)則挖掘

60、l相關(guān)規(guī)則l關(guān)聯(lián)規(guī)則改進(jìn)l總結(jié)2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植88關(guān)聯(lián)規(guī)則改進(jìn)關(guān)聯(lián)規(guī)則改進(jìn)lLin等人提出解決規(guī)則挖掘算法中的數(shù)據(jù)傾斜問題，從而使算法具有較好的均衡性。Park等人提出把哈希表結(jié)構(gòu)用于關(guān)聯(lián)規(guī)則挖掘。lAgrawal首先提出事務(wù)縮減技術(shù)，Han和Park等人也分別在減小數(shù)據(jù)規(guī)模上做了一些工作。 l抽樣的方法是由Toivonen提出的。 lBrin等人采用動態(tài)項集計數(shù)方法求解頻繁項集。 lAggarwal提出用圖論和格的理論求解頻繁項集的方法。Prutax算法就是用格遍歷的辦法求解頻繁項集。 2022-2-23AA12 關(guān)聯(lián)規(guī)則 史忠植89關(guān)聯(lián)規(guī)則改進(jìn)關(guān)聯(lián)規(guī)則改進(jìn)l關(guān)聯(lián)