高級人工智能大綱日歷及教案10關(guān)聯(lián)規(guī)則

1、2022/7/141高級人工智能 第十二章關(guān)聯(lián)規(guī)則 Association Rules2022/7/142內(nèi)容提要 引言Apriori 算法Frequent-pattern tree 和FP-growth 算法多維關(guān)聯(lián)規(guī)則挖掘相關(guān)規(guī)則基于約束的關(guān)聯(lián)規(guī)則挖掘總結(jié)2022/7/143關(guān)聯(lián)規(guī)則 關(guān)聯(lián)規(guī)則表示了項之間的關(guān)系示例:cereal, milk fruit“買谷類食品和牛奶的人也會買水果.”商店可以把牛奶和谷類食品作特價品以使人們買更多的水果.2022/7/144市場購物籃分析分析事務(wù)數(shù)據(jù)庫表我們是否可假定?Chips = Salsa Lettuce = SpinachPersonBasket

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

3、等)2022/7/147基本概念項集事務(wù)關(guān)聯(lián)規(guī)則 - 事務(wù)數(shù)據(jù)集 (例如右圖)事務(wù)標(biāo)識 TID 每一個事務(wù)關(guān)聯(lián)著一個標(biāo)識,稱作TID.Transaction-idItems bought10A, B, C20A, C30A, D40B, E, F2022/7/148度量有趣的關(guān)聯(lián)規(guī)則支持度sD中包含A和 B 的事務(wù)數(shù)與總的事務(wù)數(shù)的比值規(guī)則 AB 在數(shù)據(jù)集D中的支持度為s, 其中s 表示D中包含AB (即同時包含A和B)的事務(wù)的百分率.2022/7/149度量有趣的關(guān)聯(lián)規(guī)則可信度 cD中同時包含A和B的事務(wù)數(shù)與只包含A的事務(wù)數(shù)的比值規(guī)則 AB 在數(shù)據(jù)集D中的可信度為c, 其中c表示D中包含A的事

4、務(wù)中也包含B的百分率.即可用條件概率P(B|A)表示. confidence(A B )=P(B|A) 條件概率 P(B|A) 表示A發(fā)生的條件下B也發(fā)生的概率.2022/7/1410度量有趣的關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則根據(jù)以下兩個標(biāo)準(zhǔn)(包含或排除):最小支持度 表示規(guī)則中的所有項在事務(wù)中出現(xiàn)的頻度最小可信度 - 表示規(guī)則中左邊的項(集)的出現(xiàn)暗示著右邊的項(集)出現(xiàn)的頻度2022/7/1411市場購物籃分析I是什么?事務(wù)ID B的T是什么?s(Chips=Salsa) 是什么?c(Chips=Salsa)是什么?事務(wù) ID購物籃AChips, Salsa, Cookies, Crackers, Cok

5、e, BeerBLettuce, Spinach, Oranges, Celery, Apples, GrapesCChips, Salsa, Frozen Pizza, Frozen CakeDLettuce, Spinach, Milk, Butter, Chips2022/7/1412頻繁項集項集 任意項的集合k-項集 包含k個項的項集頻繁 (或大)項集 滿足最小支持度的項集若I包含m個項,那么可以產(chǎn)生多少個項集?2022/7/1413強關(guān)聯(lián)規(guī)則給定一個項集,容易生成關(guān)聯(lián)規(guī)則.項集: Chips, Salsa, BeerBeer, Chips = SalsaBeer, Salsa = C

6、hipsChips, Salsa = Beer強規(guī)則是有趣的強規(guī)則通常定義為那些滿足最小支持度和最小可信度的規(guī)則.2022/7/1414關(guān)聯(lián)規(guī)則挖掘兩個基本步驟找出所有的頻繁項集滿足最小支持度找出所有的強關(guān)聯(lián)規(guī)則由頻繁項集生成關(guān)聯(lián)規(guī)則保留滿足最小可信度的規(guī)則2022/7/1415內(nèi)容提要 引言Apriori 算法Frequent-pattern tree 和FP-growth 算法多維關(guān)聯(lián)規(guī)則挖掘相關(guān)規(guī)則基于約束的關(guān)聯(lián)規(guī)則挖掘總結(jié)2022/7/1416生成頻繁項集Nave algorithmn - |D|（給n賦值）for each subset s of I do l - 0 for eac

7、h transaction T in D do if s is a subset of T then l - l + 1 if minimum support = l/n then add s to frequent subsets2022/7/1417生成頻繁項集nave algorithm的分析I 的子集: O(2m) 為每一個子集掃描n個事務(wù)測試s為T的子集: O(2mn) 隨著項的個數(shù)呈指數(shù)級增長!我們能否做的更好?2022/7/1418Apriori 性質(zhì)定理(Apriori 性質(zhì)): 若A是一個頻繁項集,則A的每一個子集都是一個頻繁項集.證明:設(shè)n為事務(wù)數(shù).假設(shè)A是l個事務(wù)的子集,

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

9、: 由頻繁(k-1)-項集構(gòu)建候選k-項集方法找到所有的頻繁1-項集擴展頻繁(k-1)-項集得到候選k-項集剪除不滿足最小支持度的候選項集2022/7/1421Apriori: 一種候選項集生成-測試方法Apriori 剪枝原理: 若任一項集是不頻繁的,則其超集不應(yīng)該被生成/測試!方法: 由頻繁k-項集生成候選(k+1)-項集,并且在DB中測試候選項集性能研究顯示了Apriori算法是有效的和可伸縮(scalablility)的.2022/7/1422The Apriori 算法一個示例Database TDB1st scanC1L1L2C2C22nd scanC3L33rd scanTidI

10、tems10A, 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/7/1423Apriori 算法Algorithm: Apriori輸入: Database, D, of transactions; minimum support

11、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 database D do/scan D for counts Ct =subset(Ck ,t);/ get the s

12、ubsets of t that are candidates For each candidate c Ct c.count+; Lk = candidates in Ck with min_support endreturn L=k Lk;2022/7/1424Apriori 算法Procedure apriori_gen(Lk-1: frequent (k-1)-itemsets; min_sup:minimum support threshold )for each itemset l1 Lk-1 for each itemset l2Lk-1 if(l11=l21) (l12=l22

13、) (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/7/1425Apriori 算法Join is generate candidates set of itemsets Ck from 2 itemsets in Lk-1Procedure join(p,q) insert i

14、nto 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/7/1426Apriori 算法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 i

15、f s Lk-1 then return TRUE;return FALSE.2022/7/1427Apriori算法的重要細節(jié)如何生成候選項集?步驟 1: 自連接 Lk步驟 2: 剪枝如何計算候選項集的支持度?候選項庥生成的示例L3= abc, abd, acd, ace, bcd 自連接: L3*L3由abc 和abd 連接得到abcd 由acd 和ace 連接得到acde剪枝:因為ade 不在L3中acde 被剪除C4=abcd2022/7/1428如何生成候選項集?假定Lk-1中的項以一定順序排列步驟 1: 自連接 Lk-1 insert into Ckselect p.item1,

16、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-1步驟 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/7/1429如何計算候選項集的支持度?為何候選項集的支持度的計算是一個問題?候選項集的總數(shù)可能是巨大的 一個事務(wù)可能包含多個候選項集方法:候選項集

17、被存儲在一個哈希樹哈希樹的葉子結(jié)點包含一個項集和計數(shù)的列表內(nèi)部結(jié)點 包含一個哈希表子集函數(shù): 找出包含在一個事務(wù)中的所有候選項集2022/7/1430頻繁模式挖掘的挑戰(zhàn)挑戰(zhàn)多次掃描事務(wù)數(shù)據(jù)庫巨大數(shù)量的候選項集繁重的計算候選項集的支持度工作改進 Apriori: 大體的思路減少事務(wù)數(shù)據(jù)庫的掃描次數(shù)縮減候選項集的數(shù)量使候選項集的支持度計算更加方便2022/7/1431內(nèi)容提要 引言Apriori 算法Frequent-pattern tree 和FP-growth 算法多維關(guān)聯(lián)規(guī)則挖掘相關(guān)規(guī)則基于約束的關(guān)聯(lián)規(guī)則挖掘總結(jié)2022/7/1432頻繁模式挖掘的瓶頸多次掃描數(shù)據(jù)庫是高代價的長模式的挖掘需要

18、多次掃描數(shù)據(jù)庫以及生成許多的候選項集找出頻繁項集 i1i2i100掃描次數(shù): 100候選項集的數(shù)量: (1001) + (1002) + + (110000) = 2100-1 = 1.27*1030 !瓶頸:候選項集-生成-測試我們能否避免生成候選項集?2022/7/1433不生成候選項集的頻繁模式挖掘利用局部頻繁的項由短模式增長為長模式“abc” 是一個頻繁模式得到所有包含 “abc”的事務(wù): DB|abc“d” 是 DB|abc 的一個局部頻繁的項 abcd 是一個頻繁模式2022/7/1434FP Growth算法 (Han, Pei, Yin 2000)Apriori算法的一個有問題

19、的方面是其候選項集的生成指數(shù)級增長的來源另一種方法是使用分而治之的策略(divide and conquer)思想: 將數(shù)據(jù)庫的信息壓縮成一個描述頻繁項相關(guān)信息的頻繁模式樹2022/7/1435利用FP-樹進行頻繁模式挖掘思想: 頻繁模式增長遞歸地增長頻繁模式借助模式和數(shù)據(jù)庫劃分方法 對每個頻繁項,構(gòu)建它的條件模式基,然后構(gòu)建它的條件FP-樹.對每個新創(chuàng)建的條件FP-樹重復(fù)上述過程直至結(jié)果FP-樹為空,或者它僅包含一個單一路徑.該路徑將生成其所有的子路徑的組合,每個組合都是一個頻繁模式.2022/7/1436頻繁 1-項集最小支持度為20% (計數(shù)為 2)TIDItems1I1,I2,I52I

20、2,I43I2,I3,I64I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3ItemsetSupport countI16I27I36I42I52I61ItemsetSupport countI16I27I36I42I52 事務(wù)數(shù)據(jù)庫 支持度計數(shù) 頻繁1-項集2022/7/1437FP-樹 構(gòu)建ItemsetSupport countI16I27I36I42I52ItemsetSupport countI27I16I36I42I52按支持度降序排列2022/7/1438FP-樹 構(gòu)建 創(chuàng)建根結(jié)點null 掃描數(shù)據(jù)庫 事務(wù)1: I1, I2, I5

21、排序: I2, I1, I5 處理事務(wù) 以項的順序增加結(jié)點 標(biāo)注項及其計數(shù)(I2,1)(I1,1)(I5,1)1I50I40I31I11I2 維護索引表2022/7/1439FP-樹 構(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/7/1440FP-樹 構(gòu)建null(I2,7)(I1,4)(I5,1)2I52I46I36I17I2(I4,1)TIDItems1I1,I2,I52I2,I

22、43I2,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/7/1441FP-樹 構(gòu)建掃描事務(wù)數(shù)據(jù)庫D一次,得到頻繁項的集合F及它們的支持度.將F按支持度降序排列成L,L是頻繁項的列表.創(chuàng)建FP-樹的根, 標(biāo)注其為NULL.對D中的每個事務(wù)進行以下操作:根據(jù) L中的次序?qū)κ聞?wù)中的頻繁項進行選擇和排序. 設(shè)事務(wù)中的已排序的頻繁項列表為p|P,其中p表示第一個元素,P表示剩余的列表.調(diào)用insert_Tree(p|P,T).2022/7/1442FP-樹 構(gòu)建I

23、nsert_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-link structure. If P is nonempty, call insert_

24、tree(P,N) recursively. 2022/7/1443挖掘 FP-tree從索引表中的最后一個項開始找到所有包含該項的路徑沿著結(jié)點-鏈接(node-links)確定條件模式路徑中符合頻度要求的模式構(gòu)建 FP-tree C添加項至C中所有路徑,生成頻繁模式遞歸地挖掘C (添加項)從索引表和樹中移除項2022/7/1444挖掘 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) 條件

25、 FP-tree (I2 I1 I5, 2), (I2 I5, 2), (I1 I5, 2)null(I2,2)(I1,2)2022/7/1445挖掘 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 I1:2,(I2:2),(I1:2),I2 I3:4,I1 I3:2,I2 I1 I3:2I1(I2:4)I2 I1:42022/7/1446挖掘 FP-TreeProcedure FP_growth(Tree,)If Tree

26、 contains a single path P then for each combination (denote as ) of the nodes in the path P generate pattern with support = minisup of nodes in ;Else for each ai in the header of Tree generate pattern =ai with support =ai.support; construct , s conditional pattern base and then conditional FP_tree T

27、ree; IF Tree then call FP_growth(Tree, ); 2022/7/1447由事務(wù)數(shù)據(jù)庫構(gòu)建FP-樹f:4c:1b:1p:1b:1c: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,

28、 c, k, s, pc, b, p500 a, f, c, e, l, p, m, nf, c, a, m, p掃描DB一次,找到頻繁1項 (單一項模式)按支持度降序?qū)︻l繁項排序為 F-list再次掃描DB,構(gòu)建FP-treeF-list=f-c-a-b-m-p2022/7/1448劃分模式和數(shù)據(jù)庫頻繁模式根據(jù)F-list可以被劃分為若干子集F-list=f-c-a-b-m-p包含 p的模式包含 m 但包含 p的模式包含 c 但不包含 a ,b, m, p的模式模式 f完整性 和 非冗余性2022/7/1449從P的條件數(shù)據(jù)庫找出包含P的模式從 FP-tree的索引表的頻繁項開始沿著每個頻繁

29、項p的鏈接遍歷 FP-tree累積項p的所有轉(zhuǎn)換前綴路徑來形成的p的條件模式基條件模式基項 條件模式基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/7/1450遞歸: 挖掘每個條件FP-treef:3c:3a:3m-條件 FP-tree“am”的條件模式基: (fc:3)f:3c:3am-條件 FP-tree“cm”的條件模式基: (f:3)f:3cm-條件 FP-tree“

30、cam”的條件模式基: (f:3)f:3cam-條件 FP-tree2022/7/1451一個特例: FP-tree中的單一前綴路徑假定 (條件的) FP-tree T 有一個共享的單一前綴路徑 P挖掘可以分為兩部分將單一前綴路徑約簡為一個結(jié)點將兩部分的挖掘結(jié)果串聯(lián)a2:n2a3:n3a1:n1b1:m1C1:k1C2:k2C3:k3b1:m1C1:k1C2:k2C3:k3r1+a2:n2a3:n3a1:n1r1=2022/7/1452通過 DB 投影(Projection)使FP-growth可伸縮FP-tree 不能全放入內(nèi)存?DB 投影首先將一個數(shù)據(jù)庫劃分成一個由若干投影(Project

31、ed)數(shù)據(jù)庫組成的集合然后對每個投影數(shù)據(jù)庫構(gòu)建和挖掘 FP-treeParallel projection vs. Partition projection 技術(shù)Parallel projection is space costly2022/7/1453Partition-based ProjectionParallel projection 需要很多磁盤空間Partition projection 節(jié)省磁盤空間Tran. DB fcampfcabmfbcbpfcampp-proj DB fcamcbfcamm-proj DB fcabfcafcab-proj DB fcba-proj DBf

32、cc-proj DBff-proj DB am-proj DB fcfcfccm-proj DB fff2022/7/1454改進途徑使用哈希表存儲候選k-項集的支持度計數(shù)移除不包含頻繁項集的事務(wù)對數(shù)據(jù)采樣劃分數(shù)據(jù)若一個項集是頻繁的,則它必定在某個數(shù)據(jù)分區(qū)中是頻繁的.2022/7/1455FP-tree 結(jié)構(gòu)的優(yōu)點完整性 保持了頻繁項集挖掘的完整信息沒有打斷任何事務(wù)的長模式緊密性減少不相關(guān)的信息不頻繁的項沒有了項按支持度降序排列: 越頻繁出現(xiàn),越可能被共享決不會比原數(shù)據(jù)庫更大 (不計結(jié)點鏈接和計數(shù)域)對 Connect-4 數(shù)據(jù)庫, 壓縮比率可以超過1002022/7/1456FP-Growt

33、h vs. Apriori: 支持度的可伸縮性Data set T25I20D10K2022/7/1457FP-Growth vs. Tree-Projection:支持度的可伸縮性Data set T25I20D100K2022/7/1458關(guān)聯(lián)規(guī)則可視化: 方格圖(Pane Graph)2022/7/1459關(guān)聯(lián)規(guī)則可視化: 規(guī)則圖(Rule Graph)2022/7/1460內(nèi)容提要 引言Apriori 算法Frequent-pattern tree 和FP-growth 算法多維關(guān)聯(lián)規(guī)則挖掘相關(guān)規(guī)則基于約束的關(guān)聯(lián)規(guī)則挖掘總結(jié)2022/7/1461挖掘多種規(guī)則或規(guī)律多層(Multi-le

34、vel),量化(quantitative)關(guān)聯(lián)規(guī)則, 相關(guān)(correlation)和因果(causality), 比率(ratio)規(guī)則, 序列 (sequential) 模式,浮現(xiàn)(emerging)模式, temporal associations, 局部周期(partial periodicity)分類(classification),聚類(clustering),冰山立方體( iceberg cubes), 等等.2022/7/1462多層關(guān)聯(lián)規(guī)則項常常構(gòu)成層次可伸縮的(flexible)支持度設(shè)置: 在較低層的項預(yù)期有較低的支持度.事務(wù)數(shù)據(jù)庫可以基于維度和層次編碼探尋共享多層挖掘統(tǒng)

35、一支持度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/7/1463可伸縮的支持度約束的多層/多維(ML/MD)關(guān)聯(lián)規(guī)則為什么設(shè)置可伸縮的支持度?實際生活中項的出現(xiàn)頻率變化巨大在一個商店購物籃中的鉆石,手表,鋼筆統(tǒng)一的支持度未必是一個有趣的模型一個可伸縮模型較低層的,較多維的組合以及長模式通常具有較小的支持度總體規(guī)則應(yīng)該要容易說明和理解特殊的項和特殊的項

36、的組合可以特別設(shè)定(最小支持度)以及擁有更高的優(yōu)先級2022/7/1464多維關(guān)聯(lián)規(guī)則單維規(guī)則:buys(X, “milk”) buys(X, “bread”)多維規(guī)則: 2 個維度或謂詞( predicates)跨維度(Inter-dimension)關(guān)聯(lián)規(guī)則 (無重復(fù)謂詞)age(X,”19-25”) occupation(X,“student”) buys(X,“coke”)混合維度(hybrid-dimension)關(guān)聯(lián)規(guī)則 (重復(fù)謂詞)age(X,”19-25”) buys(X, “popcorn”) buys(X, “coke”)分類(Categorical)屬性有限的幾個可能值,

37、值之間不可排序數(shù)量(Quantitative)屬性數(shù)值的,值之間有固有的排序2022/7/1465多層關(guān)聯(lián)規(guī)則:冗余濾除根據(jù)項之間的”先輩” (ancestor)關(guān)系,一些規(guī)則可能是冗余的. 示例milk wheat bread support = 8%, confidence = 70%2% milk wheat bread support = 2%, confidence = 72%我們說第1個規(guī)則是第2個規(guī)則的先輩.一個規(guī)則是冗余的,當(dāng)其支持度接近基于先輩規(guī)則的”預(yù)期”(expected)值.2022/7/1466多層關(guān)聯(lián)規(guī)則:逐步深化(Progressive Deepening)一個自

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

39、, buys是一個 3-謂詞集以age處理的方式,技術(shù)可以如下分類1. 利用數(shù)量屬性的統(tǒng)計離散(static discretization)方法 利用預(yù)先確定的概念層次對數(shù)量屬性進行統(tǒng)計離散化2. 量化關(guān)聯(lián)規(guī)則基于數(shù)據(jù)的分布,數(shù)量屬性被動態(tài)地離散化到不同的容器空間(bins)3. 基于距離(Distance-based)的關(guān)聯(lián)規(guī)則這是一個動態(tài)離散化的過程,該過程考慮數(shù)據(jù)點之間的距離2022/7/1468數(shù)量屬性的統(tǒng)計離散化挖掘之前利用概念層次離散化數(shù)值被范圍(ranges)替代.關(guān)系數(shù)據(jù)庫中,找出所有的頻繁k-謂詞(predicate)集要求 k 或 k+1次表掃描.數(shù)據(jù)立方體(data cu

40、be)非常適合數(shù)據(jù)挖掘.N-維立方體的 cells 與謂詞集( predicate sets)相對應(yīng).通過數(shù)據(jù)立方體挖掘會非?？焖?( e)(age)()(buys)(age, e)(age,buys)( e,buys)( e,buys)2022/7/1469量化關(guān)聯(lián)規(guī)則age(X,”30-34”) e(X,”24K - 48K”) buys(X,”high resolution TV”)數(shù)值屬性動態(tài)離散化這樣挖掘的規(guī)則的可信度或緊密度最大化2-維 量化關(guān)聯(lián)規(guī)則: Aquan1 Aquan2 Acat示例2022/7/1470量化關(guān)聯(lián)規(guī)則ARCS: Association Rule Clust

41、ering System (關(guān)聯(lián)規(guī)則聚類系統(tǒng)) 借鑒了圖像處理中的思想. 本質(zhì)上, 這種方法映射一對數(shù)量屬性到滿足給定的分類屬性條件的2-維元組格. 然后對柵格搜索找到聚類點,由其生成關(guān)聯(lián)規(guī)則. ARCS 步驟: 裝箱(Binning)找出頻繁謂詞集(predicate sets) 聚類關(guān)聯(lián)規(guī)則 2022/7/1471量化關(guān)聯(lián)規(guī)則裝箱(Binning): 劃分 過程被認為是裝箱,即稱作間隔為箱柜(bins). 三種常用裝箱策略是: Equiwidth binning, where the intervalsize of each bin is the same Equidepth: where

42、 each bin has approximately the same number of tuples assigned to it Homogeneity-based binning, where bin size is determined so that the tuples in each bin are uniformly distributed.2022/7/1472量化關(guān)聯(lián)規(guī)則找出頻繁謂詞集: Once the 2-D array containing the count distribution for each category is set up, this can b

43、e scanned in order to find the frequent predicate sets that also satisfy minimum confidence.聚類關(guān)聯(lián)規(guī)則: age(X,”34-35”) e(X,”31K - 50K”) buys(X,”high resolution TV”)2022/7/1473ARCS (Association Rules Clustering System)ARCS 1. Binning2. Frequent Items Set3. Clustering4. Optimization2022/7/1474ARCS: 成功的應(yīng)用聚

44、類的概念到分類中. 但僅限于基于2-維規(guī)則的分類,如A B Classi 的格式所示利用裝箱(Binning)方法將數(shù)據(jù)屬性值離散化,因此ACRS的準(zhǔn)確度與使用的離散化程度強烈相關(guān). ARCS 的特點2022/7/1475基于關(guān)聯(lián)規(guī)則的分類(Classification Based on Association rules, CBA)分類規(guī)則挖掘與關(guān)聯(lián)規(guī)則挖掘目標(biāo)一個小的規(guī)則集作為分類器所有規(guī)則依照最小支持度與最小可信度語法(Syntax)X yX Y2022/7/1476為何及如何結(jié)合分類規(guī)則挖掘與關(guān)聯(lián)規(guī)則挖掘都是實際應(yīng)用中必需的. 結(jié)合著眼于關(guān)聯(lián)規(guī)則的一個特定子集,其右件限制為分類的類屬性

45、. CARs: Class Association Rules2022/7/1477CBA: 三個步驟若有連續(xù)值,則離散化.生成所有的 class association rules (CARs)構(gòu)建一個若干生成的CARs的分類器.2022/7/1478CAR集生成完整的CARs的集合,其滿足用戶指定的最小支持度與最小可信度約束.由 CARs構(gòu)建一個分類器.2022/7/1479規(guī)則生成:基本概念規(guī)則項(Ruleitem) :條件集 condset 是一個項集, y 是一個類標(biāo)簽(class label) 每個規(guī)則項表示一個規(guī)則: condset-y條件集支持度(condsupCount)D中

46、包含condset的事例(case)數(shù)規(guī)則支持度(rulesupCount)D中包含condset 及標(biāo)注類別 y的事例(case)數(shù)支持度Support=(rulesupCount/|D|)*100%可信度Confidence=(rulesupCount/condsupCount)*100%2022/7/1480規(guī)則生成:基本概念(Cont.)頻繁規(guī)則項(frequent ruleitems)一個規(guī)則項是頻繁的,當(dāng)其支持度不小于最小支持度 minsup.精確規(guī)則(Accurate rule)一個規(guī)則是精確的 ,當(dāng)其可信度不小于最小可信度 minconf .潛在規(guī)則(Possible rule

47、)對所有包含同樣條件集condset的規(guī)則項, 可信度最大的規(guī)則項為這一規(guī)則項集合的潛在規(guī)則.類別關(guān)聯(lián)規(guī)則 class association rules (CARs) 包含所有的潛在規(guī)則possible rules (PRs) ,其即是頻繁的又是精確的.2022/7/1481規(guī)則生成: 一個示例一個規(guī)則項: 假定條件集 condset (condsupCount) 的支持度計數(shù)為 3, 規(guī)則項ruleitem (rulesupCount) 的支持度計數(shù)為2,|D|=10 則 (A,1),(B,1) - (class,1)supt=20% (rulesupCount/|D|)*100%conf

48、d=66.7% (rulesupCount/condsupCount)*100% 2022/7/1482RG: 算法1 F 1 = large 1-ruleitems; 2 CAR 1 = genRules (F 1 ); 3 prCAR 1 = pruneRules (CAR 1 ); /count the item and class occurrences to determine the frequent 1-ruleitems and prune it4 for (k = 2; F k-1 ; k+) doC k = candidateGen (F k-1 ); /generate

49、the candidate ruleitems Ck using the frequent ruleitems Fk-16 for each data case d D do /scan the databaseC d = ruleSubset (C k , d); /find all the ruleitems in Ck whose condsets are supported by d8 for each candidate c C d do9 c.condsupCount+;10 if d.class = c.class then c.rulesupCount+; /update va

50、rious support counts of the candidates in Ck11 end12 end2022/7/1483RG: 算法(cont.)13 F k = c C k | c.rulesupCount minsup; /select those new frequent ruleitems 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 ;

51、 18 prCARs = k prCAR k ;2022/7/1484分類構(gòu)建器 M1: 基本概念給定兩個規(guī)則 ri and rj,定義: ri rj 當(dāng)ri的可信度大于 rj的, 或者它們的可信度相同,但ri的支持度大于rj的, 或者它們的可信度與支持度都相同, 但 ri 比rj生成的早.我們的分類器如下面格式所示:, where ri R, ra rb if ba2022/7/1485M1: 三個步驟 基本思想是選擇R中一個優(yōu)先規(guī)則(high precedence)的集合來覆蓋 D.對生成的規(guī)則集R排序.根據(jù)已排好的序列從R中選擇為分類所用的規(guī)則并放入C每個選擇的規(guī)則必須正確分類至少一個增

52、加的事例(case).并選擇默認的屬性和計算誤差.拋棄C中的不能改進分類器的準(zhǔn)備度的規(guī)則.保留那些最小誤差的規(guī)則的位置,拋棄序列中的其余規(guī)則.2022/7/1486M1: Algorithm1 R = sort(R); /Step1:sort R according to the relation “”2 for each rule r R in sequence do3 temp = ;4 for each case d D do /go through D to find those cases covered by each rule r5 if d satisfies the cond

53、itions of r then6 store d.id in temp and mark r if it correctly classifies d;7 if r is marked then8 insert r at the end of C; /r will be a potential rule because it can correctly classify at least one case d9 delete all the cases with the ids in temp from D;10 selecting a default class for the curre

54、nt C; /the majority class in the remaining data11 compute the total number of errors of C;12 end13 end / Step 214 Find the first rule p in C with the lowest total number of errors and drop all the rules after p in C;15 Add the default class associated with p to end of C, and return C (our classifier

55、). /Step 32022/7/1487M1: 滿足的兩個條件Each training case is covered by the rule with the highest precedence among the rules that can cover the case.Every rule in C correctly classifies at least one remaining training case when it is chosen.2022/7/1488 MOUCLASAssumption: MOUCLAS algorithm assumes that the

56、initial association rules can be agglomerated into clustering regionsThe implication of the form of the Mouclas Pattern (so called MP) :Cluster(D)t y where Cluster(D)t is a cluster of D, t = 1 to m, and y is a class label. 2022/7/1489MOUCLASDefinitions: Frequency of Mouclas Patterns Accuracy of Mouc

57、las Patterns Reliability of Mouclas PatternsTask of Mouclas:To discover MPs that have support and confidence greater than the user-specified minimum support threshold (called minsup), and minimum confidence threshold (called minconf) and minimum reliability threshold (called minR) respectively, and

58、to construct a classifier based upon MPs. 2022/7/1490The MOUCLAS algorithm Two steps: Step 1. Discovery of the frequent and accurate and reliable MPs. Step 2. Construction of a classifier, called De-MP, based on MPs.2022/7/1491The MOUCLAS algorithmThe core of the first step in the Mouclas algorithm

59、is to find all cluster_rules that satisfy minsup and minconf and minR. Let C denote the dataset D after dimensionality reduction processing. A cluster_rule represents a MP, namely a rule: cluset y,where cluset is a set of itemsets from a cluster Cluster(C)t, y is a class label, y Y. 2022/7/1492The M

60、OUCLAS algorithmAlgorithm of the first step: Mouclas Mining frequent and accurate and reliable Mouclas patterns (MPs)Input: A training transaction database, D; minimum support threshold (minsup); minimum confidence threshold (minconf) ; minimum reliability threshold (minR) Output: A set of frequent