高級(jí)人工智能第十二章

1、2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植1高級(jí)人工智能 第十第十二二章章關(guān)聯(lián)規(guī)則 Association Rules2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植2內(nèi)容提要 n引言引言nApriori 算法算法nFrequent-pattern tree 和和FP-growth 算法算法n多維關(guān)聯(lián)規(guī)則挖掘多維關(guān)聯(lián)規(guī)則挖掘n相關(guān)規(guī)則相關(guān)規(guī)則n基于約束的關(guān)聯(lián)規(guī)則挖掘基于約束的關(guān)聯(lián)規(guī)則挖掘n總結(jié)總結(jié)2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植3關(guān)聯(lián)規(guī)則 n關(guān)聯(lián)規(guī)則表示了項(xiàng)之間的關(guān)系n示例:cereal, milk fruit“買谷類食品和牛奶的人也會(huì)買水果.”商店可以把牛奶和谷類食品作特價(jià)品以使人們買更

2、多的水果.2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植4市場(chǎng)購(gòu)物籃分析n分析事務(wù)數(shù)據(jù)庫(kù)表n我們是否可假定?nChips = Salsa Lettuce = SpinachPersonBasketAChips, Salsa, Cookies, Crackers, Coke, BeerBLettuce, Spinach, Oranges, Celery, Apples, GrapesCChips, Salsa, Frozen Pizza, Frozen CakeDLettuce, Spinach, Milk, Butter2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植5基本概念基本概念n通常, 數(shù)據(jù)包含

3、:TIDBasket事務(wù) ID項(xiàng)的子集2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植6 關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則挖掘n在事務(wù)數(shù)據(jù)庫(kù),關(guān)系數(shù)據(jù)庫(kù)和其它信息庫(kù)中的項(xiàng)或?qū)ο蟮募现g,發(fā)現(xiàn)頻繁模式,關(guān)聯(lián),相關(guān),或因果關(guān)系的結(jié)構(gòu).n頻繁模式: 數(shù)據(jù)庫(kù)中出現(xiàn)頻繁的模式(項(xiàng)集,序列,等等)2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植7基本概念基本概念n項(xiàng)集項(xiàng)集n事務(wù)事務(wù)n關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則n - 事務(wù)數(shù)據(jù)集 (例如右圖例如右圖)n事務(wù)標(biāo)識(shí)事務(wù)標(biāo)識(shí) TID 每一個(gè)事務(wù)關(guān)聯(lián)著一個(gè)標(biāo)識(shí)每一個(gè)事務(wù)關(guān)聯(lián)著一個(gè)標(biāo)識(shí),稱作稱作TID.IT ,.,21miiiI BAIBIABA,DTransaction-idItems bough

4、t10A, B, C20A, C30A, D40B, E, F2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植8度量有趣的關(guān)聯(lián)規(guī)則度量有趣的關(guān)聯(lián)規(guī)則n支持度snD中包含A和 B 的事務(wù)數(shù)與總的事務(wù)數(shù)的比值規(guī)則規(guī)則 A AB B 在數(shù)據(jù)集在數(shù)據(jù)集D D中的支持度為中的支持度為s, s, 其中其中s s 表示表示D D中包中包含含A A B B ( (即同時(shí)包含即同時(shí)包含A A和和B)B)的事務(wù)的百分率的事務(wù)的百分率. .|)(DTBADTBAs2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植9度量有趣的關(guān)聯(lián)規(guī)則度量有趣的關(guān)聯(lián)規(guī)則n可信度可信度 c cnD D中同時(shí)包含中同時(shí)包含A A和和B B的事務(wù)數(shù)與只包

5、含的事務(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ā)生的概率也發(fā)生的概率. .2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植10度量有趣的關(guān)聯(lián)規(guī)則度量有趣的關(guān)聯(lián)規(guī)則n關(guān)聯(lián)規(guī)則根據(jù)以下兩個(gè)標(biāo)準(zhǔn)(包含或排除):n最小支持度 表示規(guī)則中的所有項(xiàng)在事務(wù)中出現(xiàn)的頻度n最小可信度 - 表示規(guī)則中左邊的項(xiàng)(集)的出現(xiàn)暗示著右

6、邊的項(xiàng)(集)出現(xiàn)的頻度2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植11市場(chǎng)購(gòu)物籃分析市場(chǎng)購(gòu)物籃分析I是什么?事務(wù)ID B的T是什么?s(Chips=Salsa) 是什么?c(Chips=Salsa)是什么?事務(wù) ID購(gòu)物籃AChips, Salsa, Cookies, Crackers, Coke, BeerBLettuce, Spinach, Oranges, Celery, Apples, GrapesCChips, Salsa, Frozen Pizza, Frozen CakeDLettuce, Spinach, Milk, Butter, Chips2022-5-8AA12 關(guān)聯(lián)規(guī)則

7、史忠植12頻繁項(xiàng)集頻繁項(xiàng)集n項(xiàng)集 任意項(xiàng)的集合nk-項(xiàng)集 包含k個(gè)項(xiàng)的項(xiàng)集n頻繁 (或大)項(xiàng)集 滿足最小支持度的項(xiàng)集n若I包含m個(gè)項(xiàng),那么可以產(chǎn)生多少個(gè)項(xiàng)集?2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植13強(qiáng)關(guān)聯(lián)規(guī)則強(qiáng)關(guān)聯(lián)規(guī)則n給定一個(gè)項(xiàng)集,容易生成關(guān)聯(lián)規(guī)則.n項(xiàng)集: Chips, Salsa, BeernBeer, Chips = SalsanBeer, Salsa = ChipsnChips, Salsa = Beern強(qiáng)規(guī)則是有趣的n強(qiáng)規(guī)則通常定義為那些滿足最小支持度和最小可信度的規(guī)則.2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植14關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則挖掘n兩個(gè)基本步驟n找出所有的頻繁項(xiàng)集

8、n滿足最小支持度n找出所有的強(qiáng)關(guān)聯(lián)規(guī)則n由頻繁項(xiàng)集生成關(guān)聯(lián)規(guī)則n保留滿足最小可信度的規(guī)則2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植15內(nèi)容提要內(nèi)容提要 n引言nApriori 算法nFrequent-pattern tree 和FP-growth 算法n多維關(guān)聯(lián)規(guī)則挖掘n相關(guān)規(guī)則n基于約束的關(guān)聯(lián)規(guī)則挖掘n總結(jié)2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植16生成頻繁項(xiàng)集生成頻繁項(xiàng)集nNave 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 the

9、n l - l + 1 if minimum support = l/n then add s to frequent subsets2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植17生成頻繁項(xiàng)集生成頻繁項(xiàng)集nnave algorithm的分析nI 的子集: O(2m) n為每一個(gè)子集掃描n個(gè)事務(wù)n測(cè)試s為T的子集: O(2mn) n隨著項(xiàng)的個(gè)數(shù)呈指數(shù)級(jí)增長(zhǎng)!n我們能否做的更好?2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植18AprioriApriori 性質(zhì)性質(zhì)n定理定理(Apriori 性質(zhì)性質(zhì)): 若A是一個(gè)頻繁項(xiàng)集,則A的每一個(gè)子集都是一個(gè)頻繁項(xiàng)集.n證明證明:設(shè)n為事務(wù)數(shù).假設(shè)A是l個(gè)事務(wù)

10、的子集,若 A A , 則A 為l (l l )個(gè)事務(wù)的子集.因此, l/n s(最小支持度), l/n s也成立.2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植19AprioriApriori 算法算法nApriori算法是一種經(jīng)典的生成布爾型關(guān)聯(lián)規(guī)則的頻繁項(xiàng)集挖掘算法.算法名字是緣于算法使用了頻繁項(xiàng)集的性質(zhì)這一先驗(yàn)知識(shí).n思想: Apriori 使用了一種稱作level-wise搜索的迭代方法,其中k-項(xiàng)集被用作尋找(k+1)-項(xiàng)集.首先,找出頻繁1-項(xiàng)集,以L1表示.L1用來(lái)尋找L2,即頻繁2-項(xiàng)集的集合.L2用來(lái)尋找L3,以此類推,直至沒(méi)有新的頻繁k-項(xiàng)集被發(fā)現(xiàn).每個(gè)Lk都要求對(duì)數(shù)據(jù)庫(kù)作一

11、次完全掃描.2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植20生成頻繁項(xiàng)集生成頻繁項(xiàng)集n中心思想: 由頻繁(k-1)-項(xiàng)集構(gòu)建候選k-項(xiàng)集n方法n找到所有的頻繁1-項(xiàng)集n擴(kuò)展頻繁(k-1)-項(xiàng)集得到候選k-項(xiàng)集n剪除不滿足最小支持度的候選項(xiàng)集2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植21AprioriApriori: : 一種候選項(xiàng)集生成一種候選項(xiàng)集生成- -測(cè)試方法測(cè)試方法nApriori 剪枝原理: 若任一項(xiàng)集是不頻繁的,則其超集不應(yīng)該被生成/測(cè)試!n方法: n由頻繁k-項(xiàng)集生成候選(k+1)-項(xiàng)集,并且n在DB中測(cè)試候選項(xiàng)集n性能研究顯示了Apriori算法是有效的和可伸縮(scalabli

12、lity)的.2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植22The Apriori 算法一個(gè)示例Database TDB1st scanC1L1L2C2C22nd 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, EItems

13、etsupB, C, E22022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植23Apriori 算法Algorithm: Apriori輸入: Database, D, of transactions; minimum support threshold,min_sup.輸出: L, freuqent itemsets in D.過(guò)程: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 = a

14、priori_gen(Lk-1 ,min_sup); for each transaction t in database 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-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植24Apriori 算法Procedure apriori_gen(Lk-1: fre

15、quent (k-1)-itemsets; min_sup:minimum support threshold )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 Ckre

16、turn Ck2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植25Apriori 算法Join is generate 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-5-8AA12 關(guān)聯(lián)規(guī)則 史

17、忠植26Apriori 算法Procedure has_infrequent_subset(c:candidate 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-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植27Apriori算法的重要細(xì)節(jié)n如何生成候選項(xiàng)集?n步驟 1: 自連接 Lkn步驟 2: 剪枝n如何計(jì)算候選項(xiàng)集的支持度?n候選項(xiàng)庥生成的示例nL3= abc, abd, acd

18、, ace, bcd n自連接: L3*L3n由abc 和abd 連接得到abcd n由acd 和ace 連接得到acden剪枝:n因?yàn)閍de 不在L3中acde 被剪除nC4=abcd2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植28如何生成候選項(xiàng)集?n假定Lk-1中的項(xiàng)以一定順序排列n步驟 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.item

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

20、挖掘的挑戰(zhàn)頻繁模式挖掘的挑戰(zhàn)n挑戰(zhàn)n多次掃描事務(wù)數(shù)據(jù)庫(kù)n巨大數(shù)量的候選項(xiàng)集n繁重的計(jì)算候選項(xiàng)集的支持度工作n改進(jìn) Apriori: 大體的思路n減少事務(wù)數(shù)據(jù)庫(kù)的掃描次數(shù)n縮減候選項(xiàng)集的數(shù)量n使候選項(xiàng)集的支持度計(jì)算更加方便2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植31內(nèi)容提要內(nèi)容提要 n引言nApriori 算法nFrequent-pattern tree 和FP-growth 算法n多維關(guān)聯(lián)規(guī)則挖掘n相關(guān)規(guī)則n基于約束的關(guān)聯(lián)規(guī)則挖掘n總結(jié)2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植32頻繁模式挖掘的瓶頸n多次掃描數(shù)據(jù)庫(kù)是高代價(jià)的n長(zhǎng)模式的挖掘需要多次掃描數(shù)據(jù)庫(kù)以及生成許多的候選項(xiàng)集n找出頻繁項(xiàng)集

21、 i1i2i100n掃描次數(shù): 100n候選項(xiàng)集的數(shù)量: (1001) + (1002) + + (110000) = 2100-1 = 1.27*1030 !n瓶頸:候選項(xiàng)集-生成-測(cè)試n我們能否避免生成候選項(xiàng)集?2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植33不生成候選項(xiàng)集的頻繁模式挖掘n利用局部頻繁的項(xiàng)由短模式增長(zhǎng)為長(zhǎng)模式n“abc” 是一個(gè)頻繁模式n得到所有包含 “abc”的事務(wù): DB|abcn“d” 是 DB|abc 的一個(gè)局部頻繁的項(xiàng) abcd 是一個(gè)頻繁模式2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植34FP Growth算法 (Han, Pei, Yin 2000)nAprior

22、i算法的一個(gè)有問(wèn)題的方面是其候選項(xiàng)集的生成n指數(shù)級(jí)增長(zhǎng)的來(lái)源n另一種方法是使用分而治之的策略(divide and conquer)n思想思想: 將數(shù)據(jù)庫(kù)的信息壓縮成一個(gè)描述頻繁項(xiàng)相關(guān)信息的頻繁模式樹(shù)2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植35利用FP-樹(shù)進(jìn)行頻繁模式挖掘n思想: 頻繁模式增長(zhǎng)n遞歸地增長(zhǎng)頻繁模式借助模式和數(shù)據(jù)庫(kù)劃分n方法 n對(duì)每個(gè)頻繁項(xiàng),構(gòu)建它的條件模式基,然后構(gòu)建它的條件FP-樹(shù).n對(duì)每個(gè)新創(chuàng)建的條件FP-樹(shù)重復(fù)上述過(guò)程n直至結(jié)果FP-樹(shù)為空,或者它僅包含一個(gè)單一路徑.該路徑將生成其所有的子路徑的組合,每個(gè)組合都是一個(gè)頻繁模式.2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植3

23、6頻繁 1-項(xiàng)集n最小支持度為20% (計(jì)數(shù)為 2)TIDItems1I1,I2,I52I2,I43I2,I3,I64I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3ItemsetSupport countI16I27I36I42I52I61ItemsetSupport countI16I27I36I42I52 事務(wù)數(shù)據(jù)庫(kù) 支持度計(jì)數(shù) 頻繁1-項(xiàng)集2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植37FP-樹(shù) 構(gòu)建ItemsetSupport countI16I27I36I42I52ItemsetSupport countI27I16I36I42I52按支

24、持度降序排列2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植38FP-樹(shù) 構(gòu)建 創(chuàng)建根結(jié)點(diǎn)null 掃描數(shù)據(jù)庫(kù) 事務(wù)1: I1, I2, I5 排序: I2, I1, I5 處理事務(wù) 以項(xiàng)的順序增加結(jié)點(diǎn) 標(biāo)注項(xiàng)及其計(jì)數(shù)(I2,1)(I1,1)(I5,1)1I50I40I31I11I2 維護(hù)索引表2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植39FP-樹(shù) 構(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,I320

25、22-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植40FP-樹(shù) 構(gòu)建null(I2,7)(I1,4)(I5,1)2I52I46I36I17I2(I4,1)TIDItems1I1,I2,I52I2,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-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植41FP-樹(shù) 構(gòu)建n掃描事務(wù)數(shù)據(jù)庫(kù)D一次,得到頻繁項(xiàng)的集合F及它們的支持度.將F按支持度降序排列成L,L是頻繁項(xiàng)的列表.n創(chuàng)建FP-樹(shù)的根, 標(biāo)注其為NULL.對(duì)D中的每個(gè)事務(wù)進(jìn)行以下

26、操作:n根據(jù) L中的次序?qū)κ聞?wù)中的頻繁項(xiàng)進(jìn)行選擇和排序. 設(shè)事務(wù)中的已排序的頻繁項(xiàng)列表為p|P,其中p表示第一個(gè)元素,P表示剩余的列表.調(diào)用insert_Tree(p|P,T).2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植42FP-樹(shù) 構(gòu)建nInsert_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

27、to T, and its node- link to the nodes with the same item-name via the node-link structure. If P is nonempty, call insert_tree(P,N) recursively. 2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植43挖掘 FP-treen從索引表中的最后一個(gè)項(xiàng)開(kāi)始n找到所有包含該項(xiàng)的路徑n沿著結(jié)點(diǎn)-鏈接(node-links)n確定條件模式n路徑中符合頻度要求的模式n構(gòu)建 FP-tree Cn添加項(xiàng)至C中所有路徑,生成頻繁模式n遞歸地挖掘C (添加項(xiàng))n從索引表和樹(shù)中移除項(xiàng)20

28、22-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植44挖掘 FP-Treenull(I2,7)(I1,4)(I5,1)2I52I46I36I17I2(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-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植45挖掘 FP-Tree項(xiàng)條件模式基條件FP-tree生成的頻繁模式I5(I2 I1:1),(I2 I1 I3:1) I2 I

29、5:2,I1 I5:2,I2 I1 I5:2I4(I2 I1:1),(I2:1)I2 I4:2I3(I2 I1:2,(I2:2),(I1:2) ,I2 I3:4,I1 I3:2,I2 I1 I3:2I1(I2:4)I2 I1:42022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植46挖掘 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

30、with support = minisup of nodes in ;(4)Else for each 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-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植47由事務(wù)數(shù)據(jù)庫(kù)構(gòu)建FP-樹(shù)f:4c:1b:1p:1b:1c

31、:3a:3b:1m:2p:2m:1Header TableItem frequency 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項(xiàng) (單一項(xiàng)模式)

32、2. 按支持度降序?qū)︻l繁項(xiàng)排序?yàn)?F-list3. 再次掃描DB,構(gòu)建FP-treeF-list=f-c-a-b-m-p2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植48劃分模式和數(shù)據(jù)庫(kù)n頻繁模式根據(jù)F-list可以被劃分為若干子集nF-list=f-c-a-b-m-pn包含 p的模式n包含 m 但包含 p的模式nn包含 c 但不包含 a ,b, m, p的模式n模式 fn完整性 和 非冗余性2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植49從P的條件數(shù)據(jù)庫(kù)找出包含P的模式n從 FP-tree的索引表的頻繁項(xiàng)開(kāi)始n沿著每個(gè)頻繁項(xiàng)p的鏈接遍歷 FP-treen累積項(xiàng)p的所有轉(zhuǎn)換前綴路徑來(lái)形成的p的條件模

33、式基條件模式基條件模式基項(xiàng)項(xiàng) 條件模式基條件模式基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-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植50遞歸: 挖掘每個(gè)條件FP-treef:3c:3a:3m-條件條件 FP-tree“am”的條件模式基: (fc:3)f:3c:3am-條件條件 FP-tree“cm”的條件模式基: (f:3)f:3cm-條件條件 FP-tree“cam”的條件模

34、式基: (f:3)f:3cam-條件條件 FP-tree2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植51一個(gè)特例: FP-tree中的單一前綴路徑n假定 (條件的) FP-tree T 有一個(gè)共享的單一前綴路徑 Pn挖掘可以分為兩部分n將單一前綴路徑約簡(jiǎn)為一個(gè)結(jié)點(diǎn)n將兩部分的挖掘結(jié)果串聯(lián)a2:n2a3:n3a1:n1b1:m1C1:k1C2:k2C3:k3b1:m1C1:k1C2:k2C3:k3r1+a2:n2a3:n3a1:n1r1=2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植52通過(guò) DB 投影(Projection)使FP-growth可伸縮nFP-tree 不能全放入內(nèi)存?DB 投影n首先

35、將一個(gè)數(shù)據(jù)庫(kù)劃分成一個(gè)由若干投影(Projected)數(shù)據(jù)庫(kù)組成的集合n然后對(duì)每個(gè)投影數(shù)據(jù)庫(kù)構(gòu)建和挖掘 FP-treenParallel projection vs. Partition projection 技術(shù)nParallel projection is space costly2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植53Partition-based ProjectionnParallel projection 需要很多磁盤空間nPartition projection 節(jié)省磁盤空間Tran. DB fcampfcabmfbcbpfcampp-proj DB fcamcbfcamm-

36、proj DB fcabfcafcab-proj DB fcba-proj DBfcc-proj DBff-proj DB am-proj DB fcfcfccm-proj DB fff2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植54改進(jìn)途徑n使用哈希表存儲(chǔ)候選k-項(xiàng)集的支持度計(jì)數(shù)n移除不包含頻繁項(xiàng)集的事務(wù)n對(duì)數(shù)據(jù)采樣n劃分?jǐn)?shù)據(jù)n若一個(gè)項(xiàng)集是頻繁的,則它必定在某個(gè)數(shù)據(jù)分區(qū)中是頻繁的.2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植55FP-tree 結(jié)構(gòu)的優(yōu)點(diǎn)n完整性 n保持了頻繁項(xiàng)集挖掘的完整信息n沒(méi)有打斷任何事務(wù)的長(zhǎng)模式n緊密性n減少不相關(guān)的信息不頻繁的項(xiàng)沒(méi)有了n項(xiàng)按支持度降序排列: 越頻繁出現(xiàn),

37、越可能被共享n決不會(huì)比原數(shù)據(jù)庫(kù)更大 (不計(jì)結(jié)點(diǎn)鏈接和計(jì)數(shù)域)n對(duì) Connect-4 數(shù)據(jù)庫(kù), 壓縮比率可以超過(guò)1002022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植56FP-Growth vs. Apriori: 支持度的可伸縮性010203040506070809010000.511.522.53Support threshold(%)Run time(sec.)D1 FP-grow th runtimeD1 Apriori runtimeData set T25I20D10K2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植57FP-Growth vs. Tree-Projection:支持度的可伸縮

38、性02040608010012014000.511.52Support threshold (%)Runtime (sec.)D2 FP-growthD2 TreeProjectionData set T25I20D100K2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植58關(guān)聯(lián)規(guī)則可視化: 方格圖(Pane Graph)2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植59關(guān)聯(lián)規(guī)則可視化: 規(guī)則圖(Rule Graph)2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植60內(nèi)容提要內(nèi)容提要 n引言nApriori 算法nFrequent-pattern tree 和FP-growth 算法n多維關(guān)聯(lián)規(guī)則挖掘n相關(guān)

39、規(guī)則n基于約束的關(guān)聯(lián)規(guī)則挖掘n總結(jié)2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植61挖掘多種規(guī)則或規(guī)律n多層(Multi-level),量化(quantitative)關(guān)聯(lián)規(guī)則, 相關(guān)(correlation)和因果(causality), 比率(ratio)規(guī)則, 序列 (sequential) 模式,浮現(xiàn)(emerging)模式, temporal associations, 局部周期(partial periodicity)n分類(classification),聚類(clustering),冰山立方體( iceberg cubes), 等等.2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植62多

40、層關(guān)聯(lián)規(guī)則n項(xiàng)常常構(gòu)成層次n可伸縮的(flexible)支持度設(shè)置: 在較低層的項(xiàng)預(yù)期有較低的支持度.n事務(wù)數(shù)據(jù)庫(kù)可以基于維度和層次編碼n探尋共享多層挖掘統(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%減少的支持度2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植63可伸縮的支持度約束的多層/多維(ML/MD)關(guān)聯(lián)規(guī)則n為什么設(shè)置可伸縮的支持度?n實(shí)際生活中項(xiàng)的出現(xiàn)頻率變化

41、巨大n在一個(gè)商店購(gòu)物籃中的鉆石,手表,鋼筆n統(tǒng)一的支持度未必是一個(gè)有趣的模型n一個(gè)可伸縮模型n較低層的,較多維的組合以及長(zhǎng)模式通常具有較小的支持度n總體規(guī)則應(yīng)該要容易說(shuō)明和理解n特殊的項(xiàng)和特殊的項(xiàng)的組合可以特別設(shè)定(最小支持度)以及擁有更高的優(yōu)先級(jí)2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植64多維關(guān)聯(lián)規(guī)則n單維規(guī)則:buys(X, “milk”) buys(X, “bread”)n多維規(guī)則: 2 個(gè)維度或謂詞( predicates)n跨維度(Inter-dimension)關(guān)聯(lián)規(guī)則 (無(wú)重復(fù)謂詞)age(X,”19-25”) occupation(X,“student”) buys(X,“c

42、oke”)n混合維度(hybrid-dimension)關(guān)聯(lián)規(guī)則 (重復(fù)謂詞)age(X,”19-25”) buys(X, “popcorn”) buys(X, “coke”)n分類(Categorical)屬性n有限的幾個(gè)可能值,值之間不可排序n數(shù)量(Quantitative)屬性n數(shù)值的,值之間有固有的排序2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植65多層關(guān)聯(lián)規(guī)則:冗余濾除n根據(jù)項(xiàng)之間的”先輩” (ancestor)關(guān)系,一些規(guī)則可能是冗余的. n示例nmilk wheat bread support = 8%, confidence = 70%n2% milk wheat bread s

43、upport = 2%, confidence = 72%n我們說(shuō)第1個(gè)規(guī)則是第2個(gè)規(guī)則的先輩.n一個(gè)規(guī)則是冗余的,當(dāng)其支持度接近基于先輩規(guī)則的”預(yù)期”(expected)值.2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植66多層關(guān)聯(lián)規(guī)則:逐步深化(Progressive Deepening)n一個(gè)自上而下的,逐步深化的方法:n 首先挖掘高層的頻繁項(xiàng): milk (15%), bread (10%)n 然后挖掘它們的較低層”較弱” (weaker)頻繁項(xiàng): 2% milk (5%), wheat bread (4%)n多層之間不同的最小支持度閾值導(dǎo)致了不同的算法:n如果在多個(gè)層次間采用了相同的最小

44、支持度,若t的任何一個(gè)先輩都是非頻繁的則扔棄(toss)t.n如果在較低層采用了減少的最小支持度，則只檢驗(yàn)?zāi)切┫容叺闹С侄仁穷l繁的不可忽略的派生（descendents）即可2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植67多維關(guān)聯(lián)規(guī)則挖掘的技術(shù)n搜索頻繁 k-謂詞集(predicate set):n示例: age, occupation, buys是一個(gè) 3-謂詞集n以age處理的方式,技術(shù)可以如下分類1. 利用數(shù)量屬性的統(tǒng)計(jì)離散(static discretization)方法 利用預(yù)先確定的概念層次對(duì)數(shù)量屬性進(jìn)行統(tǒng)計(jì)離散化2. 量化關(guān)聯(lián)規(guī)則n基于數(shù)據(jù)的分布,數(shù)量屬性被動(dòng)態(tài)地離散化到不同的容器

45、空間(bins)3. 基于距離(Distance-based)的關(guān)聯(lián)規(guī)則n這是一個(gè)動(dòng)態(tài)離散化的過(guò)程,該過(guò)程考慮數(shù)據(jù)點(diǎn)之間的距離2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植68數(shù)量屬性的統(tǒng)計(jì)離散化n挖掘之前利用概念層次離散化n數(shù)值被范圍(ranges)替代.n關(guān)系數(shù)據(jù)庫(kù)中,找出所有的頻繁k-謂詞(predicate)集要求 k 或 k+1次表掃描.n數(shù)據(jù)立方體(data cube)非常適合數(shù)據(jù)挖掘.nN-維立方體的 cells 與謂詞集( predicate sets)相對(duì)應(yīng).n通過(guò)數(shù)據(jù)立方體挖掘會(huì)非?？焖?(income)(age)()(buys)(age, income)(age,buys)

46、(income,buys)(age,income,buys)2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植69量化關(guān)聯(lián)規(guī)則age(X,”30-34”) income(X,”24K - 48K”) buys(X,”high resolution TV”)n數(shù)值屬性動(dòng)態(tài)離散化n這樣挖掘的規(guī)則的可信度或緊密度最大化n2-維 量化關(guān)聯(lián)規(guī)則: Aquan1 Aquan2 Acatn示例2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植70量化關(guān)聯(lián)規(guī)則nARCS: Association Rule Clustering System (關(guān)聯(lián)規(guī)則聚類系統(tǒng)) 借鑒了圖像處理中的思想. 本質(zhì)上, 這種方法映射一對(duì)數(shù)量屬性到

47、滿足給定的分類屬性條件的2-維元組格. 然后對(duì)柵格搜索找到聚類點(diǎn),由其生成關(guān)聯(lián)規(guī)則. nARCS 步驟: 裝箱(Binning)找出頻繁謂詞集(predicate sets) 聚類關(guān)聯(lián)規(guī)則 2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植71量化關(guān)聯(lián)規(guī)則n裝箱(Binning): 劃分 過(guò)程被認(rèn)為是裝箱,即稱作間隔為箱柜(bins). 三種常用裝箱策略是: Equiwidth binning, where the intervalsize of each bin is the same Equidepth: where each bin has approximately the same numb

48、er of tuples assigned to it Homogeneity-based binning, where bin size is determined so that the tuples in each bin are uniformly distributed.2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植72量化關(guān)聯(lián)規(guī)則n找出頻繁謂詞集: Once the 2-D array containing the count distribution for each category is set up, this can be scanned in order to find t

49、he frequent predicate sets that also satisfy minimum confidence.n聚類關(guān)聯(lián)規(guī)則: age(X,”34-35”) income(X,”31K - 50K”) buys(X,”high resolution TV”)2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植73ARCS (Association Rules Clustering System)ARCS 1. Binning2. Frequent Items Set3. Clustering4. Optimization2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植74nARCS: n成功

50、的應(yīng)用聚類的概念到分類中. n但僅限于基于2-維規(guī)則的分類,如A B Classi 的格式所示n利用裝箱(Binning)方法將數(shù)據(jù)屬性值離散化,因此ACRS的準(zhǔn)確度與使用的離散化程度強(qiáng)烈相關(guān). 2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植75基于關(guān)聯(lián)規(guī)則的分類(Classification Based on Association rules, CBA)n分類規(guī)則挖掘與關(guān)聯(lián)規(guī)則挖掘n目標(biāo)n一個(gè)小的規(guī)則集作為分類器n所有規(guī)則依照最小支持度與最小可信度n語(yǔ)法(Syntax)nX ynX Y2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植76為何及如何結(jié)合n分類規(guī)則挖掘與關(guān)聯(lián)規(guī)則挖掘都是實(shí)際應(yīng)用中必需的.

51、 n結(jié)合著眼于關(guān)聯(lián)規(guī)則的一個(gè)特定子集,其右件限制為分類的類屬性. nCARs: Class Association Rules2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植77CBA: 三個(gè)步驟n若有連續(xù)值,則離散化.n生成所有的 class association rules (CARs)n構(gòu)建一個(gè)若干生成的CARs的分類器.2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植78CAR集n生成完整的CARs的集合,其滿足用戶指定的最小支持度與最小可信度約束.n由 CARs構(gòu)建一個(gè)分類器.2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植79規(guī)則生成:基本概念n規(guī)則項(xiàng)(Ruleitem) :條件集 condset

52、 是一個(gè)項(xiàng)集, y 是一個(gè)類標(biāo)簽(class label) 每個(gè)規(guī)則項(xiàng)表示一個(gè)規(guī)則: condset-yn條件集支持度(condsupCount)nD中包含condset的事例(case)數(shù)n規(guī)則支持度(rulesupCount)nD中包含condset 及標(biāo)注類別 y的事例(case)數(shù)n支持度Support=(rulesupCount/|D|)*100%n可信度Confidence=(rulesupCount/condsupCount)*100%2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植80規(guī)則生成:基本概念(Cont.)n頻繁規(guī)則項(xiàng)(frequent ruleitems)n一個(gè)規(guī)則項(xiàng)是頻

53、繁的,當(dāng)其支持度不小于最小支持度 minsup.n精確規(guī)則(Accurate rule)n一個(gè)規(guī)則是精確的 ,當(dāng)其可信度不小于最小可信度 minconf .n潛在規(guī)則(Possible rule)n對(duì)所有包含同樣條件集condset的規(guī)則項(xiàng), 可信度最大的規(guī)則項(xiàng)為這一規(guī)則項(xiàng)集合的潛在規(guī)則.n類別關(guān)聯(lián)規(guī)則 class association rules (CARs) 包含所有的潛在規(guī)則possible rules (PRs) ,其即是頻繁的又是精確的.2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植81規(guī)則生成: 一個(gè)示例n一個(gè)規(guī)則項(xiàng): n假定n條件集 condset (condsupCount) 的

54、支持度計(jì)數(shù)為 3, n規(guī)則項(xiàng)ruleitem (rulesupCount) 的支持度計(jì)數(shù)為2,n|D|=10 n則 (A,1),(B,1) - (class,1)nsupt=20% (rulesupCount/|D|)*100%nconfd=66.7% (rulesupCount/condsupCount)*100% 2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植82RG: 算法1 F 1 = large 1-ruleitems; 2 CAR 1 = genRules (F 1 ); 3 prCAR 1 = pruneRules (CAR 1 ); /count the item and clas

55、s occurrences to determine the frequent 1-ruleitems and prune it4 for (k = 2; F k-1 ; k+) do5C k = candidateGen (F k-1 ); /generate the candidate ruleitems Ck using the frequent ruleitems Fk-16 for each data case d D do /scan the database7C d = ruleSubset (C k , d); /find all the ruleitems in Ck who

56、se condsets are supported by d8 for each candidate c C d do9 c.condsupCount+;10 if d.class = c.class then c.rulesupCount+; /update various support counts of the candidates in Ck11 end12 end2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植83RG: 算法(cont.)13 F k = c C k | c.rulesupCount minsup; /select those new frequent ruleitem

57、s to form Fk14 CAR k = genRules(F k ); /select the ruleitems both accurate and frequent15 prCAR k = pruneRules(CAR k ); 16 end17 CARs = k CAR k ; 18 prCARs = k prCAR k ;2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植84分類構(gòu)建器 M1: 基本概念n給定兩個(gè)規(guī)則 ri and rj,定義: ri rj 當(dāng)nri的可信度大于 rj的, 或者n它們的可信度相同,但ri的支持度大于rj的, 或者n它們的可信度與支持度都相同, 但 ri 比

58、rj生成的早.n我們的分類器如下面格式所示:n, nwhere ri R, ra rb if ba2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植85M1: 三個(gè)步驟 基本思想是選擇R中一個(gè)優(yōu)先規(guī)則(high precedence)的集合來(lái)覆蓋 D.n對(duì)生成的規(guī)則集R排序.n根據(jù)已排好的序列從R中選擇為分類所用的規(guī)則并放入Cn每個(gè)選擇的規(guī)則必須正確分類至少一個(gè)增加的事例(case).n并選擇默認(rèn)的屬性和計(jì)算誤差.n拋棄C中的不能改進(jìn)分類器的準(zhǔn)備度的規(guī)則.n保留那些最小誤差的規(guī)則的位置,拋棄序列中的其余規(guī)則.2022-5-8AA12 關(guān)聯(lián)規(guī)則 史忠植86M1: Algorithmn1 R = sort

59、(R); /Step1:sort R according to the relation “”n2 for each rule r R in sequence don3 temp = ;n4 for each case d D do /go through D to find those cases covered by each rule rn5 if d satisfies the conditions of r thenn6 store d.id in temp and mark r if it correctly classifies d;n7 if r is marked thenn

60、8 insert r at the end of C; /r will be a potential rule because it can correctly classify at least one case dn9 delete all the cases with the ids in temp from D;n10 selecting a default class for the current C; /the majority class in the remaining datan11 compute the total number of errors of C;n12 e