1、數(shù)據(jù)挖掘: 概念和技術(shù) Chapter 6 2022/9/141第6章：從大數(shù)據(jù)庫中挖掘關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則挖掘從交易數(shù)據(jù)庫中挖掘一維的布爾形關(guān)聯(lián)規(guī)則從交易數(shù)據(jù)庫中挖掘多層次關(guān)聯(lián)規(guī)則在交易數(shù)據(jù)庫和數(shù)據(jù)倉庫中挖掘多維關(guān)聯(lián)規(guī)則從關(guān)聯(lián)挖掘到相關(guān)性分析基于約束的關(guān)聯(lián)挖掘小結(jié)2022/9/142什么是關(guān)聯(lián)挖掘?關(guān)聯(lián)規(guī)則挖掘：在交易數(shù)據(jù)、關(guān)系數(shù)據(jù)或其他信息載體中，查找存在于項(xiàng)目集合或?qū)ο蠹现g的頻繁模式、關(guān)聯(lián)、相關(guān)性、或因果結(jié)構(gòu)。應(yīng)用：購物籃分析、交叉銷售、產(chǎn)品目錄設(shè)計(jì)、 loss-leader analysis、聚集、分類等。舉例： 規(guī)則形式： “Body Head support, confidence

2、”.buys(x, “diapers”) buys(x, “beers”) 0.5%, 60%major(x, “CS”) takes(x, “DB”) grade(x, “A”) 1%, 75%2022/9/143關(guān)聯(lián)規(guī)則：基本概念給定: (1)交易數(shù)據(jù)庫 (2)每筆交易是：一個(gè)項(xiàng)目列表 (消費(fèi)者一次購買活動中購買的商品)查找: 所有描述一個(gè)項(xiàng)目集合與其他項(xiàng)目集合相關(guān)性的規(guī)則E.g., 98% of people who purchase tires and auto accessories also get automotive services done應(yīng)用* 護(hù)理用品 (商店應(yīng)該怎樣提

3、高護(hù)理用品的銷售？)家用電器 * (其他商品的庫存有什么影響?)在產(chǎn)品直銷中使用附加郵寄Detecting “ping-pong”ing of patients, faulty “collisions”2022/9/144規(guī)則度量：支持度與可信度查找所有的規(guī)則 X & Y Z 具有最小支持度和可信度支持度, s, 一次交易中包含X 、 Y 、 Z的可能性可信度, c, 包含X 、 Y的交易中也包含Z的條件概率設(shè)最小支持度為50%, 最小可信度為 50%, 則可得到A C (50%, 66.6%)C A (50%, 100%)買尿布的客戶二者都買的客戶買啤酒的客戶2022/9/145關(guān)聯(lián)規(guī)則挖掘

4、：路線圖布爾 vs. 定量 關(guān)聯(lián) (基于 處理數(shù)據(jù)的類型)buys(x, “SQLServer”) buys(x, “DMBook”) buys(x, “DBMiner”) 0.2%, 60%age(x, “30.39”) income(x, “42.48K”) buys(x, “PC”) 1%, 75%單維 vs. 多維 關(guān)聯(lián) (例子同上)單層 vs. 多層 分析那個(gè)品種牌子的啤酒與那個(gè)牌子的尿布有關(guān)系?各種擴(kuò)展相關(guān)性、因果分析關(guān)聯(lián)并不一定意味著相關(guān)或因果最大模式和閉合相集添加約束如, 哪些“小東西”的銷售促發(fā)了“大家伙”的買賣？2022/9/146第6章：從大數(shù)據(jù)庫中挖掘關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則挖

5、掘從交易數(shù)據(jù)庫中挖掘一維的布爾形關(guān)聯(lián)規(guī)則從交易數(shù)據(jù)庫中挖掘多層次關(guān)聯(lián)規(guī)則在交易數(shù)據(jù)庫和數(shù)據(jù)倉庫中挖掘多維關(guān)聯(lián)規(guī)則從關(guān)聯(lián)挖掘到相關(guān)性分析基于約束的關(guān)聯(lián)挖掘小結(jié)2022/9/147關(guān)聯(lián)規(guī)則挖掘一個(gè)例子對于 A C：support = support(A 、C) = 50%confidence = support(A 、C)/support(A) = 66.6%Apriori的基本思想:頻繁項(xiàng)集的任何子集也一定是頻繁的最小值尺度 50%最小可信度 50%2022/9/148關(guān)鍵步驟：挖掘頻繁集頻繁集:是指滿足最小支持度的項(xiàng)目集合頻繁集的子集也一定是頻繁的如, 如果AB 是頻繁集，則 A B 也一定是

6、頻繁集從1到k（k-頻繁集）遞歸查找頻繁集用得到的頻繁集生成關(guān)聯(lián)規(guī)則2022/9/149Apriori算法連接: 用 Lk-1自連接得到Ck修剪: 一個(gè)k-項(xiàng)集，如果他的一個(gè)k-1項(xiàng)集（他的子集 ）不是頻繁的，那他本身也不可能是頻繁的。偽代碼:Ck: Candidate itemset of size kLk : frequent itemset of size kL1 = frequent items;for (k = 1; Lk !=; k+) do begin Ck+1 = candidates generated from Lk; for each transaction t in d

7、atabase do increment the count of all candidates in Ck+1 that are contained in t Lk+1 = candidates in Ck+1 with min_support endreturn k Lk;2022/9/1410Apriori算法 例子數(shù)據(jù)庫 D掃描 DC1L1L2C2C2掃描 DC3L3掃描 D2022/9/1411如何生成候選集假定 Lk-1 中的項(xiàng)按順序排列第一步: 自連接 Lk-1 insert into Ckselect p.item1, p.item2, , p.itemk-1, q.itemk

8、-1from Lk-1 p, Lk-1 qwhere p.item1=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1 Z 的支持度和置信度都占優(yōu)勢我們需要一個(gè)方法來度量事件的依靠性和相關(guān)性P(B|A)/P(B) 使館聯(lián)規(guī)則 A = B的提升2022/9/1454其他的興趣度衡量方法: InterestInterest (correlation, lift)同時(shí)考慮 P(A) and P(B)如果 A 和 B 是獨(dú)立事件的畫，P(AB)=P(B)*P(A)如果值小于1，則A 和 B 是負(fù)相關(guān)，否則是正相關(guān)的2022/9/1455第六章：挖掘大型數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)

9、則關(guān)聯(lián)規(guī)則挖掘由事務(wù)數(shù)據(jù)庫挖掘單維布爾關(guān)聯(lián)規(guī)則由事務(wù)數(shù)據(jù)庫挖掘多層關(guān)聯(lián)規(guī)則由關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫挖掘多維關(guān)聯(lián)規(guī)則由關(guān)聯(lián)挖掘到相關(guān)分析基于約束的關(guān)聯(lián)挖掘2022/9/1456基于約束的挖掘交互式的，探索挖掘giga-bytes 的數(shù)據(jù)可能嗎? 好好利用約束在數(shù)據(jù)挖掘中，約束的分類：知識類型約束: 指定要挖掘的知識類型.數(shù)據(jù)約束: 指定任務(wù)相關(guān)的數(shù)據(jù)集找到在1998年12月在倫敦所賣的產(chǎn)品對維/層約束:相關(guān)與地區(qū)，價(jià)格，品牌，顧客等類規(guī)則約束小買賣 (price $200).興趣度約束:強(qiáng)規(guī)則 (min_support 3%, min_confidence 60%).2022/9/1457關(guān)聯(lián)挖掘

10、中的規(guī)則約束兩種規(guī)則約束: 規(guī)則形成約束: 元規(guī)則制導(dǎo)挖掘 P(x, y) Q(x, w) takes(x, “database systems”). 內(nèi)容形成約束: 約束基于查詢的優(yōu)化 (Ng, et al., SIGMOD98).sum(LHS) 20 count(LHS) 3 sum(RHS) 10001-變量 vs. 2-變量的約束 (Lakshmanan, et al. SIGMOD99): 1-變量: 一個(gè)約束限制規(guī)則的一個(gè)方面2-變量: 一個(gè)約束限制規(guī)則的兩個(gè)方面sum(LHS) min(RHS) max(RHS) = 500”是簡潔性約束2022/9/1460可轉(zhuǎn)化的約束假如在

11、模式中的所有項(xiàng)都按順序R排列一個(gè)約束 C 是 可轉(zhuǎn)變的反單調(diào)的，如果一個(gè)模式滿足約束表明 S 的每一個(gè)后綴也滿足，那么 R 也滿足 C一個(gè)約束 C 是 可轉(zhuǎn)變的約束， 如果一個(gè)模式滿足約束表明S的每的一個(gè)模式是后綴，R 也滿足約束 C2022/9/1461約束的各種分類之間的聯(lián)系簡潔性約束反單調(diào)的約束單調(diào)的約束可以轉(zhuǎn)化的約束不能轉(zhuǎn)化的約束2022/9/1462約束的性質(zhì)：反單調(diào)反單調(diào): 如果集合 S 違反這個(gè)約束，它的任何子集也違反這個(gè)約束例子: sum(S.Price) v 是反單調(diào)的sum(S.Price) v 不是反單調(diào)的sum(S.Price) = v 是partly部風(fēng)反單調(diào)應(yīng)用:

12、“sum(S.price) 1000”2022/9/1463反單調(diào)約束的描述S v, , , v SS VS VS Vmin(S) vmin(S) vmin(S) vmax(S) vmax(S) vmax(S) vcount(S) vcount(S) vcount(S) vsum(S) vsum(S) vsum(S) vavg(S) v, , , (frequent constraint)yesnonoyespartlynoyespartlyyesnopartlyyesnopartlyyesnopartlyconvertible(yes)2022/9/1464可轉(zhuǎn)變的約束的例子: Avg(S)

13、 V讓 R 是按降冪排列的項(xiàng)集的值E.g. I=9, 8, 6, 4, 3, 1Avg(S) v 是可轉(zhuǎn)變?yōu)閱握{(diào)的 w.r.t. R如果 S 是 S1的后綴，則 avg(S1) avg(S)8, 4, 3 是 9, 8, 4, 3的后綴avg(9, 8, 4, 3)=6 avg(8, 4, 3)=5如果S 滿足 avg(S) v ，那么同樣滿足 S18, 4, 3 滿足約束 avg(S) 4， 9, 8, 4, 3也滿足這個(gè)約束2022/9/1465約束的性質(zhì): 簡潔性簡潔性:對任何數(shù)據(jù)集 S1 和 S2 都滿足 C, S1 S2 也滿足 C給定 A1 是大小為1的數(shù)據(jù)集，滿足 C, 那么任何集 S 滿足 C 都是基于 A1 的。 例如：它包含一個(gè)子集也屬于 A1 , 例子 : sum(S.Price ) v 不是簡潔的min(S.Price ) v 是簡潔的2022/9/1466簡潔性約束的描述S v, , , v SS VS VS Vm