數(shù)據(jù)挖掘6章關(guān)聯(lián)1ppt課件

1、第第6章：發(fā)掘大型數(shù)據(jù)庫中的關(guān)章：發(fā)掘大型數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)那么聯(lián)規(guī)那么n6.1 關(guān)聯(lián)規(guī)那么發(fā)掘關(guān)聯(lián)規(guī)那么發(fā)掘n6.2由事務(wù)數(shù)據(jù)庫發(fā)掘單維布爾關(guān)聯(lián)規(guī)那么由事務(wù)數(shù)據(jù)庫發(fā)掘單維布爾關(guān)聯(lián)規(guī)那么n6.3由事務(wù)數(shù)據(jù)庫發(fā)掘多層關(guān)聯(lián)規(guī)那么由事務(wù)數(shù)據(jù)庫發(fā)掘多層關(guān)聯(lián)規(guī)那么n6.4由關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫發(fā)掘多維關(guān)聯(lián)規(guī)那由關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫發(fā)掘多維關(guān)聯(lián)規(guī)那么么n6.5由關(guān)聯(lián)發(fā)掘到相關(guān)性分析由關(guān)聯(lián)發(fā)掘到相關(guān)性分析n6.6基于約束的關(guān)聯(lián)發(fā)掘基于約束的關(guān)聯(lián)發(fā)掘n6.7小結(jié)小結(jié)什么是關(guān)聯(lián)發(fā)掘什么是關(guān)聯(lián)發(fā)掘?n關(guān)聯(lián)規(guī)那么發(fā)掘：關(guān)聯(lián)規(guī)那么發(fā)掘：n在買賣數(shù)據(jù)、關(guān)系數(shù)據(jù)或其他信息載體中，查找存在于工在買賣數(shù)據(jù)、關(guān)系數(shù)據(jù)或其他信息載

2、體中，查找存在于工程集合或?qū)ο蠹现g的頻繁方式、關(guān)聯(lián)、相關(guān)性、或因程集合或?qū)ο蠹现g的頻繁方式、關(guān)聯(lián)、相關(guān)性、或因果構(gòu)造。果構(gòu)造。n運(yùn)用：運(yùn)用：n購物籃分析、交叉銷售、產(chǎn)品目錄設(shè)計(jì)、購物籃分析、交叉銷售、產(chǎn)品目錄設(shè)計(jì)、 loss-leader analysis、聚集、分類等。、聚集、分類等。n舉例：舉例： n規(guī)那么方式：規(guī)那么方式： “Body Head support, confidence.nbuys(x, “diapers) buys(x, “beers) 0.5%, 60%nmajor(x, “CS) takes(x, “DB) grade(x, “A) 1%, 75%關(guān)聯(lián)規(guī)那么：

3、根本概念關(guān)聯(lián)規(guī)那么：根本概念n給定給定: (1)買賣數(shù)據(jù)庫買賣數(shù)據(jù)庫 (2)每筆買賣是：一個(gè)工程列表每筆買賣是：一個(gè)工程列表 (消費(fèi)消費(fèi)者一次購買活動中購買的商品者一次購買活動中購買的商品)n查找查找: 一切描畫一個(gè)工程集合與其他工程集合相關(guān)性的規(guī)那一切描畫一個(gè)工程集合與其他工程集合相關(guān)性的規(guī)那么么nE.g., 98% of people who purchase tires and auto accessories also get automotive services donen運(yùn)用運(yùn)用n* 護(hù)理用品護(hù)理用品 (商店應(yīng)該怎樣提高護(hù)理用品的銷售？商店應(yīng)該怎樣提高護(hù)理用品的銷售？)n家用電器

4、家用電器 * (其他商品的庫存有什么影響其他商品的庫存有什么影響?)n在產(chǎn)品直銷中運(yùn)用附加郵寄在產(chǎn)品直銷中運(yùn)用附加郵寄規(guī)那么度量：支持度與可信度規(guī)那么度量：支持度與可信度n查找一切的規(guī)那么查找一切的規(guī)那么 X & Y Z 具有最小支持度和可信度具有最小支持度和可信度n支持度支持度, s, 一次買賣中包含一次買賣中包含X 、 Y 、 Z的能夠性的能夠性n置信度置信度, c, 包含包含X 、 Y的買的買賣中也包含賣中也包含Z的條件概率的條件概率交易ID購買的商品2000A,B,C1000A,C4000A,D5000B,E,F設(shè)最小支持度為設(shè)最小支持度為50%, 最小可信最小可信度為度為 5

5、0%, 那么可得到那么可得到A C (50%, 66.6%)C A (50%, 100%)買尿布的客買尿布的客戶戶二者都買二者都買的客戶的客戶買啤酒的客戶買啤酒的客戶關(guān)聯(lián)規(guī)那么發(fā)掘：道路圖關(guān)聯(lián)規(guī)那么發(fā)掘：道路圖n布爾布爾 vs. 定量定量 關(guān)聯(lián)關(guān)聯(lián) (基于規(guī)那么中所處置數(shù)據(jù)的值類型基于規(guī)那么中所處置數(shù)據(jù)的值類型)nbuys(x, “SQLServer) buys(x, “DMBook) buys(x, “DBMiner) 0.2%, 60%nage(x, “30.39) income(x, “42.48K) buys(x, “PC) 1%, 75%n單維單維 vs. 多維多維 關(guān)聯(lián)關(guān)聯(lián) (基于

6、規(guī)那么中涉及的數(shù)據(jù)維基于規(guī)那么中涉及的數(shù)據(jù)維)(例子同上例子同上)n單層單層 vs. 多層多層 分析分析(基于規(guī)那么集所涉及的籠統(tǒng)層基于規(guī)那么集所涉及的籠統(tǒng)層)n那個(gè)種類牌子的啤酒與那個(gè)牌子的尿布有關(guān)系那個(gè)種類牌子的啤酒與那個(gè)牌子的尿布有關(guān)系?n各種擴(kuò)展各種擴(kuò)展n相關(guān)性、因果分析相關(guān)性、因果分析n關(guān)聯(lián)并不一定意味著相關(guān)或因果關(guān)聯(lián)并不一定意味著相關(guān)或因果n最大方式和閉合項(xiàng)集最大方式和閉合項(xiàng)集第第6章：從大數(shù)據(jù)庫中發(fā)掘關(guān)聯(lián)章：從大數(shù)據(jù)庫中發(fā)掘關(guān)聯(lián)規(guī)那么規(guī)那么n6.1 關(guān)聯(lián)規(guī)那么發(fā)掘關(guān)聯(lián)規(guī)那么發(fā)掘n6.2由事務(wù)數(shù)據(jù)庫發(fā)掘單維布爾關(guān)聯(lián)規(guī)那么由事務(wù)數(shù)據(jù)庫發(fā)掘單維布爾關(guān)聯(lián)規(guī)那么n6.3由事務(wù)數(shù)據(jù)庫發(fā)掘多層

7、關(guān)聯(lián)規(guī)那么由事務(wù)數(shù)據(jù)庫發(fā)掘多層關(guān)聯(lián)規(guī)那么n6.4由關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫發(fā)掘多維關(guān)聯(lián)規(guī)那由關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫發(fā)掘多維關(guān)聯(lián)規(guī)那么么n6.5由關(guān)聯(lián)發(fā)掘到相關(guān)性分析由關(guān)聯(lián)發(fā)掘到相關(guān)性分析n6.6基于約束的關(guān)聯(lián)發(fā)掘基于約束的關(guān)聯(lián)發(fā)掘n6.7小結(jié)小結(jié)關(guān)聯(lián)規(guī)那么發(fā)掘關(guān)聯(lián)規(guī)那么發(fā)掘一個(gè)例子一個(gè)例子對于對于 A C：support = support(A 、C) = 50%confidence = support(A 、C)/support(A) = 66.6%Apriori的根本思想的根本思想:頻繁項(xiàng)集的任何子集也一定是頻繁的頻繁項(xiàng)集的任何子集也一定是頻繁的交易ID購買商品2000A,B,C1000A,C4

8、000A,D5000B,E,F頻繁項(xiàng)集支持度A75%B50%C50%A,C50%最小值尺度 50%最小可信度 50%關(guān)鍵步驟：發(fā)掘頻繁集關(guān)鍵步驟：發(fā)掘頻繁集n頻繁集頻繁集:是指滿足最小支持度的工程集合是指滿足最小支持度的工程集合n頻繁集的子集也一定是頻繁的頻繁集的子集也一定是頻繁的n如如, 假設(shè)假設(shè)AB 是頻繁集，那么是頻繁集，那么 A B 也一也一定是頻繁集定是頻繁集n從從1到到kk-頻繁集遞歸查找頻繁集頻繁集遞歸查找頻繁集n用得到的頻繁集生成關(guān)聯(lián)規(guī)那么用得到的頻繁集生成關(guān)聯(lián)規(guī)那么Apriori算法算法n銜接銜接: 用用 Lk-1自銜接得到候選自銜接得到候選k-項(xiàng)集項(xiàng)集Ckn修剪修剪: 一個(gè)

9、一個(gè)k-項(xiàng)集，假設(shè)他的一個(gè)項(xiàng)集，假設(shè)他的一個(gè)k-1項(xiàng)集他的子集項(xiàng)集他的子集 不是頻繁的，那他本身也不能夠是頻繁的。不是頻繁的，那他本身也不能夠是頻繁的。n偽代碼偽代碼:nCk: Candidate itemset of size knLk : frequent itemset of size knL1 = frequent items;nfor (k = 2; Lk-1 !=; k+) do beginn Ck = candidates generated from Lk-1;n for each transaction t in database don increment the coun

10、t of all candidates in Ck that are contained in tn Lk = candidates in Ck with min_supportn endnreturn k Lk;Apriori算法算法 例子例子TID Items100 1 3 4200 2 3 5300 1 2 3 5400 2 5數(shù)據(jù)庫 Ditemset sup.1223334153itemset sup.12233353掃描 DC1L1itemset1 21 31 52 32 53 5itemset sup1 211 321 512 322 533 52itemset sup1 322

11、322 533 52L2C2C2掃描 DC3L3itemset2 3 5掃描 Ditemset sup2 3 52如何生成候選集如何生成候選集n假定假定 Lk-1 中的項(xiàng)按順序陳列中的項(xiàng)按順序陳列n第一步第一步: 自銜接自銜接 Lk-1 ninsert into Cknselect p.item1, p.item2, , p.itemk-1, q.itemk-1nfrom Lk-1 p, Lk-1 qnwhere p.item1=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1 q.itemk-1n第二步第二步: 修剪修剪nFor all itemsets c

12、 in Ck donFor all (k-1)-subsets s of c donif (s is not in Lk-1) then delete c from Ckn計(jì)算支持度為什么會成為一個(gè)問題？計(jì)算支持度為什么會成為一個(gè)問題？n候選集的個(gè)數(shù)非常宏大候選集的個(gè)數(shù)非常宏大n 一筆買賣能夠包含多個(gè)候選集一筆買賣能夠包含多個(gè)候選集生成候選集的例子生成候選集的例子nL3=abc, abd, acd, ace, bcdn自銜接自銜接 : L3*L3nabc 和和 abd 得到得到 abcd nacd 和和 ace 得到得到 acden修剪修剪:nade 不在不在 L3中，刪除中，刪除 acden

13、C4=abcd提高提高Apriori效率的方法效率的方法1.基于基于Hash的項(xiàng)集計(jì)數(shù)的項(xiàng)集計(jì)數(shù): 假設(shè)假設(shè) k-項(xiàng)集在項(xiàng)集在hash-tree的途徑上的一個(gè)的途徑上的一個(gè)計(jì)數(shù)值低于閾值，那他本身也不能夠是頻繁的。計(jì)數(shù)值低于閾值，那他本身也不能夠是頻繁的。(157頁圖頁圖6-6)2.減少買賣記錄減少買賣記錄: 不包含任何頻繁不包含任何頻繁k-項(xiàng)集的買賣也不能夠包含任何項(xiàng)集的買賣也不能夠包含任何大于大于k的頻繁集，下一步計(jì)算時(shí)刪除這些記錄。的頻繁集，下一步計(jì)算時(shí)刪除這些記錄。3.劃分劃分: 一個(gè)項(xiàng)集要想在整個(gè)數(shù)據(jù)庫中是頻繁的，那么他至少在數(shù)一個(gè)項(xiàng)集要想在整個(gè)數(shù)據(jù)庫中是頻繁的，那么他至少在數(shù)據(jù)庫的

14、一個(gè)分割上是頻繁的。據(jù)庫的一個(gè)分割上是頻繁的。 兩次掃描數(shù)據(jù)。兩次掃描數(shù)據(jù)。(157頁圖頁圖5-6)4.抽樣抽樣: 運(yùn)用小的支持度運(yùn)用小的支持度+完好性驗(yàn)證方法。在小的抽樣集上找到完好性驗(yàn)證方法。在小的抽樣集上找到部分頻繁項(xiàng)集，然后在全部數(shù)據(jù)集找頻繁項(xiàng)集。部分頻繁項(xiàng)集，然后在全部數(shù)據(jù)集找頻繁項(xiàng)集。5.動態(tài)項(xiàng)集計(jì)數(shù)動態(tài)項(xiàng)集計(jì)數(shù): 在添加一個(gè)新的候選集之前，先估計(jì)一下是不是在添加一個(gè)新的候選集之前，先估計(jì)一下是不是他的一切子集都是頻繁的。他的一切子集都是頻繁的。Apriori 夠快了嗎夠快了嗎? 性能瓶頸性能瓶頸nApriori算法的中心算法的中心:n用頻繁的用頻繁的(k 1)-項(xiàng)集生成候選的頻繁

15、項(xiàng)集生成候選的頻繁 k-項(xiàng)集項(xiàng)集n用數(shù)據(jù)庫掃描和方式匹配計(jì)算候選集的支持度用數(shù)據(jù)庫掃描和方式匹配計(jì)算候選集的支持度nApriori 的瓶頸的瓶頸: 候選集生成候選集生成n宏大的候選集宏大的候選集:n104 個(gè)頻繁個(gè)頻繁1-項(xiàng)集要生成項(xiàng)集要生成 107 個(gè)候選個(gè)候選 2-項(xiàng)集項(xiàng)集n要找尺寸為要找尺寸為100的頻繁方式，如的頻繁方式，如 a1, a2, , a100, 他必需先產(chǎn)生他必需先產(chǎn)生2100 1030 個(gè)候選集個(gè)候選集n多次掃描數(shù)據(jù)庫：多次掃描數(shù)據(jù)庫： n假設(shè)最長的方式是假設(shè)最長的方式是n的話，那么需求的話，那么需求 (n +1 ) 次數(shù)次數(shù)據(jù)庫掃描據(jù)庫掃描發(fā)掘頻繁集發(fā)掘頻繁集 不用生成

16、候選集不用生成候選集n頻繁方式增長頻繁方式增長 (FP-增長增長)用用Frequent-Pattern tree (FP-tree) 構(gòu)造緊縮數(shù)據(jù)庫構(gòu)造緊縮數(shù)據(jù)庫, n高度濃縮，同時(shí)對頻繁集的發(fā)掘又完備的高度濃縮，同時(shí)對頻繁集的發(fā)掘又完備的n防止代價(jià)較高的數(shù)據(jù)庫掃描防止代價(jià)較高的數(shù)據(jù)庫掃描n 開發(fā)一種高效的基于開發(fā)一種高效的基于FP-tree的頻繁集發(fā)掘算法的頻繁集發(fā)掘算法n采用分而治之的方法學(xué)：分解數(shù)據(jù)發(fā)掘義務(wù)為小采用分而治之的方法學(xué)：分解數(shù)據(jù)發(fā)掘義務(wù)為小義務(wù)義務(wù)n防止生成關(guān)聯(lián)規(guī)那么防止生成關(guān)聯(lián)規(guī)那么: 分別發(fā)掘條件數(shù)據(jù)庫分別發(fā)掘條件數(shù)據(jù)庫用用 FP-tree發(fā)掘頻繁集發(fā)掘頻繁集n根本思想根

17、本思想 (分而治之分而治之)n用用FP-tree地歸增長頻繁集地歸增長頻繁集n方法方法 n對每個(gè)項(xiàng)，生成它的對每個(gè)項(xiàng)，生成它的 條件方式庫條件方式庫, 然后是它的然后是它的 條條件件 FP-treen對每個(gè)新生成的條件對每個(gè)新生成的條件FP-tree，反復(fù)這個(gè)步驟，反復(fù)這個(gè)步驟n直到結(jié)果直到結(jié)果FP-tree為空為空, 或只含維一的一個(gè)途徑或只含維一的一個(gè)途徑 (此途徑的每個(gè)子途徑對應(yīng)的相集都是頻繁集此途徑的每個(gè)子途徑對應(yīng)的相集都是頻繁集)發(fā)掘發(fā)掘 FP-tree的主要步驟的主要步驟n為為FP-tree中的每個(gè)節(jié)點(diǎn)生成條件方式庫中的每個(gè)節(jié)點(diǎn)生成條件方式庫n用條件方式庫構(gòu)造對應(yīng)的條件用條件方式庫

18、構(gòu)造對應(yīng)的條件FP-treen遞歸構(gòu)造條件遞歸構(gòu)造條件 FP-trees 同時(shí)增長其包含的頻繁同時(shí)增長其包含的頻繁集集n假設(shè)條件假設(shè)條件FP-tree直包含一個(gè)途徑，那么直接生直包含一個(gè)途徑，那么直接生成所包含的頻繁集。成所包含的頻繁集。步驟步驟1: 1: 建立建立 FP-tree FP-tree 159159頁圖頁圖6-86-8n從從FP-tree的頭表開場的頭表開場n按照每個(gè)頻繁項(xiàng)的銜接遍歷按照每個(gè)頻繁項(xiàng)的銜接遍歷 FP-treen列出可以到達(dá)此項(xiàng)的一切前綴途徑，得到條件方式庫列出可以到達(dá)此項(xiàng)的一切前綴途徑，得到條件方式庫步驟步驟2:2:建立條件建立條件FP-treeFP-tree進(jìn)展發(fā)掘

19、進(jìn)展發(fā)掘159159頁圖頁圖6-96-9n對每個(gè)方式庫對每個(gè)方式庫n計(jì)算庫中每個(gè)項(xiàng)的支持度計(jì)算庫中每個(gè)項(xiàng)的支持度n用方式庫中的頻繁項(xiàng)建立用方式庫中的頻繁項(xiàng)建立FP-tree為什么為什么 頻繁集增長頻繁集增長 速度快？速度快？n我們的性能研討顯示我們的性能研討顯示nFP-growth 比比Apriori快一個(gè)數(shù)量級快一個(gè)數(shù)量級, 同樣也比同樣也比 tree-projection 快?？?。n緣由緣由n不生成候選集，不用候選測試。不生成候選集，不用候選測試。n運(yùn)用緊縮的數(shù)據(jù)構(gòu)造運(yùn)用緊縮的數(shù)據(jù)構(gòu)造n防止反復(fù)數(shù)據(jù)庫掃描防止反復(fù)數(shù)據(jù)庫掃描n根本操作是計(jì)數(shù)和建立根本操作是計(jì)數(shù)和建立 FP-tree 樹樹FP

20、-growth vs. Apriori: 相對于支持度相對于支持度的擴(kuò)展性的擴(kuò)展性010203040506070809010000.511.522.53Support threshold(%)Run time(sec.)D1 FP-grow th runtimeD1 Apriori runtimeData set T25I20D10KFP-growth vs. Tree-Projection:相對于相對于支持度的擴(kuò)展性支持度的擴(kuò)展性02040608010012014000.511.52Support threshold (%)Runtime (sec.)D2 FP-growthD2 TreeP

21、rojectionData set T25I20D100K關(guān)聯(lián)規(guī)那么結(jié)果顯示關(guān)聯(lián)規(guī)那么結(jié)果顯示 (Table Form )關(guān)聯(lián)規(guī)那么可視化關(guān)聯(lián)規(guī)那么可視化Using Plane Graph關(guān)聯(lián)規(guī)那么可視化關(guān)聯(lián)規(guī)那么可視化Using Rule Graph第6章：從大數(shù)據(jù)庫中發(fā)掘關(guān)聯(lián)規(guī)那么n6.1 關(guān)聯(lián)規(guī)那么發(fā)掘關(guān)聯(lián)規(guī)那么發(fā)掘n6.2由事務(wù)數(shù)據(jù)庫發(fā)掘單維布爾關(guān)聯(lián)規(guī)那么由事務(wù)數(shù)據(jù)庫發(fā)掘單維布爾關(guān)聯(lián)規(guī)那么n6.3由事務(wù)數(shù)據(jù)庫發(fā)掘多層關(guān)聯(lián)規(guī)那么由事務(wù)數(shù)據(jù)庫發(fā)掘多層關(guān)聯(lián)規(guī)那么n6.4由關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫發(fā)掘多維關(guān)聯(lián)規(guī)那由關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫發(fā)掘多維關(guān)聯(lián)規(guī)那么么n6.5由關(guān)聯(lián)發(fā)掘到相關(guān)性分析由關(guān)聯(lián)發(fā)掘到相

22、關(guān)性分析n6.6基于約束的關(guān)聯(lián)發(fā)掘基于約束的關(guān)聯(lián)發(fā)掘n6.7小結(jié)小結(jié)多層關(guān)聯(lián)規(guī)那么多層關(guān)聯(lián)規(guī)那么n項(xiàng)通常具有層次項(xiàng)通常具有層次n底層的項(xiàng)通常支持度也低底層的項(xiàng)通常支持度也低n某些特定層的規(guī)那么能夠某些特定層的規(guī)那么能夠更有意義更有意義n買賣數(shù)據(jù)庫可以按照維或買賣數(shù)據(jù)庫可以按照維或?qū)泳幋a層編碼n可以進(jìn)展共享的多維發(fā)掘可以進(jìn)展共享的多維發(fā)掘食品面包牛奶脫脂奶光明一致酸奶白黃TID ItemsT1111, 121, 211, 221T2111, 211, 222, 323T3112, 122, 221, 411T4111, 121T5111, 122, 211, 221, 413發(fā)掘多層關(guān)聯(lián)規(guī)那么發(fā)

23、掘多層關(guān)聯(lián)規(guī)那么n自上而下，深度優(yōu)先的方法：自上而下，深度優(yōu)先的方法：n先找高層的先找高層的“強(qiáng)規(guī)那么：強(qiáng)規(guī)那么：n牛奶牛奶 面包面包 20%, 60%. 20%, 60%.n再找他們底層的再找他們底層的“弱規(guī)那么：弱規(guī)那么：n酸奶酸奶 黃面包黃面包 6%, 50%. 6%, 50%.n多層關(guān)聯(lián)規(guī)那么的變種多層關(guān)聯(lián)規(guī)那么的變種n1 1 支持度不變支持度不變: : 在各層之間運(yùn)用一致的支持度在各層之間運(yùn)用一致的支持度n+ + 一個(gè)最小支持度閾值一個(gè)最小支持度閾值. . 假設(shè)一個(gè)項(xiàng)集的父項(xiàng)集不具有最小支假設(shè)一個(gè)項(xiàng)集的父項(xiàng)集不具有最小支持度，那他本身也不能夠滿足最小支持度。持度，那他本身也不能夠滿足

24、最小支持度。n 底層項(xiàng)不會成為頻繁集，假設(shè)支持度底層項(xiàng)不會成為頻繁集，假設(shè)支持度n太高太高 喪失底層關(guān)聯(lián)規(guī)那么喪失底層關(guān)聯(lián)規(guī)那么n太低太低 生成太多的高層關(guān)聯(lián)規(guī)那么生成太多的高層關(guān)聯(lián)規(guī)那么n2 2 支持度遞減支持度遞減: : 隨著層次的降低支持度遞減隨著層次的降低支持度遞減多層關(guān)聯(lián)規(guī)那么多層關(guān)聯(lián)規(guī)那么: 支持度不變支持度不變 vs. 支支持度遞減持度遞減3層次交叉單項(xiàng)過濾：層次交叉單項(xiàng)過濾： 4層次交叉層次交叉K-項(xiàng)過濾：項(xiàng)過濾：4種搜索戰(zhàn)略：種搜索戰(zhàn)略：層與層獨(dú)立層與層獨(dú)立用用k-項(xiàng)集跨層過濾項(xiàng)集跨層過濾用項(xiàng)跨層過濾用項(xiàng)跨層過濾用項(xiàng)進(jìn)展可控跨層過濾用項(xiàng)進(jìn)展可控跨層過濾支持度不變支持度不變支持

25、度不變多層發(fā)掘支持度不變多層發(fā)掘牛奶牛奶support = 10%酸奶酸奶 support = 6%脫脂奶脫脂奶support = 4%層層 1min_sup = 5%層層 2min_sup = 5%支持度遞減支持度遞減支持度遞減多層發(fā)掘支持度遞減多層發(fā)掘酸奶酸奶 support = 6%脫脂奶脫脂奶 support = 4%層層 1min_sup = 5%層層 2min_sup = 3%牛奶牛奶support = 10%多層關(guān)聯(lián)：冗余過濾n由于由于“祖先關(guān)系的緣由，有些規(guī)那么能夠是多余的。祖先關(guān)系的緣由，有些規(guī)那么能夠是多余的。n例子例子n奶制品奶制品 白面包白面包 support = 8%

26、, confidence = 70%n酸奶酸奶 白面包白面包 support = 2%, confidence = 72%n酸奶占奶制品酸奶占奶制品25%n我們稱第一個(gè)規(guī)那么是第二個(gè)規(guī)那么的祖先我們稱第一個(gè)規(guī)那么是第二個(gè)規(guī)那么的祖先n參考規(guī)那么的祖先，假設(shè)他的支持度與我們參考規(guī)那么的祖先，假設(shè)他的支持度與我們“預(yù)期的支持度預(yù)期的支持度近似的話，我們就說這條規(guī)那么是冗余的。近似的話，我們就說這條規(guī)那么是冗余的。數(shù)據(jù)發(fā)掘查詢的逐漸精化數(shù)據(jù)發(fā)掘查詢的逐漸精化n為什么要逐漸精化為什么要逐漸精化n發(fā)掘操作的代價(jià)能夠高或低，結(jié)果能夠過細(xì)致或粗糙發(fā)掘操作的代價(jià)能夠高或低，結(jié)果能夠過細(xì)致或粗糙n在速度和質(zhì)量之

27、間折衷：逐漸精化在速度和質(zhì)量之間折衷：逐漸精化n超集覆蓋特征：超集覆蓋特征：n預(yù)存儲一切正面答案預(yù)存儲一切正面答案允許進(jìn)一步正確性驗(yàn)證，而不用驗(yàn)證允許進(jìn)一步正確性驗(yàn)證，而不用驗(yàn)證曾經(jīng)錯(cuò)誤的曾經(jīng)錯(cuò)誤的n2或多步發(fā)掘：或多步發(fā)掘：n先執(zhí)行粗糙的、容易的操作先執(zhí)行粗糙的、容易的操作 (超集覆蓋超集覆蓋)n然后在減少后的候選集上進(jìn)展計(jì)算量大的算法然后在減少后的候選集上進(jìn)展計(jì)算量大的算法 (Koperski & Han, SSD95).第6章：從大數(shù)據(jù)庫中發(fā)掘關(guān)聯(lián)規(guī)那么n6.1 關(guān)聯(lián)規(guī)那么發(fā)掘關(guān)聯(lián)規(guī)那么發(fā)掘n6.2由事務(wù)數(shù)據(jù)庫發(fā)掘單維布爾關(guān)聯(lián)規(guī)那么由事務(wù)數(shù)據(jù)庫發(fā)掘單維布爾關(guān)聯(lián)規(guī)那么n6.3由事務(wù)

28、數(shù)據(jù)庫發(fā)掘多層關(guān)聯(lián)規(guī)那么由事務(wù)數(shù)據(jù)庫發(fā)掘多層關(guān)聯(lián)規(guī)那么n6.4由關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫發(fā)掘多維關(guān)聯(lián)規(guī)那由關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫發(fā)掘多維關(guān)聯(lián)規(guī)那么么n6.5由關(guān)聯(lián)發(fā)掘到相關(guān)性分析由關(guān)聯(lián)發(fā)掘到相關(guān)性分析n6.6基于約束的關(guān)聯(lián)發(fā)掘基于約束的關(guān)聯(lián)發(fā)掘n6.7小結(jié)小結(jié)多維關(guān)聯(lián)規(guī)那么：多維關(guān)聯(lián)規(guī)那么： 概念概念n單維規(guī)那么：單維規(guī)那么：nbuys(X, “milk) buys(X, “bread)n多維規(guī)那么：多維規(guī)那么： 2個(gè)以上維個(gè)以上維/謂詞謂詞n維間關(guān)聯(lián)規(guī)那么維間關(guān)聯(lián)規(guī)那么 (維詞不反復(fù)維詞不反復(fù))nage(X,19-25) occupation(X,“student) buys(X,“coke)n混

29、合維關(guān)聯(lián)規(guī)那么混合維關(guān)聯(lián)規(guī)那么 (維詞反復(fù)維詞反復(fù))nage(X,19-25) buys(X, “popcorn) buys(X, “coke)n類別屬性類別屬性n有限個(gè)值有限個(gè)值, 值之間無順序關(guān)系值之間無順序關(guān)系n數(shù)量屬性數(shù)量屬性n數(shù)字的，值之間隱含了順序關(guān)系數(shù)字的，值之間隱含了順序關(guān)系發(fā)掘多維關(guān)聯(lián)的技術(shù)發(fā)掘多維關(guān)聯(lián)的技術(shù)n搜索頻繁搜索頻繁k-維詞集合：維詞集合：n如如: age, occupation, buys 是一個(gè)是一個(gè)3-維詞集合。維詞集合。n按照對按照對 age 處置方式的不同，分為：處置方式的不同，分為：n1. 用靜態(tài)方法把數(shù)值屬性離散化用靜態(tài)方法把數(shù)值屬性離散化n數(shù)值屬性可

30、用預(yù)定義的概念層次加以離散化。數(shù)值屬性可用預(yù)定義的概念層次加以離散化。n2. 帶數(shù)量的關(guān)聯(lián)規(guī)那么帶數(shù)量的關(guān)聯(lián)規(guī)那么n根據(jù)數(shù)據(jù)的分布，動態(tài)的把數(shù)值屬性離散化到不同的根據(jù)數(shù)據(jù)的分布，動態(tài)的把數(shù)值屬性離散化到不同的“箱箱。n3. 基于間隔的關(guān)聯(lián)規(guī)那么基于間隔的關(guān)聯(lián)規(guī)那么n用數(shù)據(jù)點(diǎn)之間的間隔動態(tài)的離散化用數(shù)據(jù)點(diǎn)之間的間隔動態(tài)的離散化數(shù)值屬性的靜態(tài)離散化數(shù)值屬性的靜態(tài)離散化n在發(fā)掘之前用概念層次先離散化在發(fā)掘之前用概念層次先離散化n數(shù)值被交換為區(qū)間范圍數(shù)值被交換為區(qū)間范圍n關(guān)系數(shù)據(jù)庫中，要找到一切頻繁關(guān)系數(shù)據(jù)庫中，要找到一切頻繁k-維詞需求維詞需求k或或k+1次表掃次表掃描。描。n適宜運(yùn)用數(shù)據(jù)立方體適宜

31、運(yùn)用數(shù)據(jù)立方體nN維立方體的每個(gè)單元維立方體的每個(gè)單元 對應(yīng)一個(gè)維詞集合對應(yīng)一個(gè)維詞集合n運(yùn)用數(shù)據(jù)立方體速度更快運(yùn)用數(shù)據(jù)立方體速度更快(income)(age)()(buys)(age, income)(age,buys) (income,buys)(age,income,buys)帶數(shù)量的關(guān)聯(lián)規(guī)那么帶數(shù)量的關(guān)聯(lián)規(guī)那么age(X,30-34) income(X,24K - 48K) buys(X,high resolution TV)n動態(tài)動態(tài) 離散化數(shù)值屬性離散化數(shù)值屬性n使?jié)M足某種發(fā)掘規(guī)范，如最大化發(fā)掘規(guī)那么的置信度緊湊使?jié)M足某種發(fā)掘規(guī)范，如最大化發(fā)掘規(guī)那么的置信度緊湊性性.n2-維數(shù)量關(guān)

32、聯(lián)規(guī)那么：維數(shù)量關(guān)聯(lián)規(guī)那么： Aquan1 Aquan2 Acatn用用2-維表格把維表格把“臨近的臨近的關(guān)聯(lián)規(guī)那么組合起來關(guān)聯(lián)規(guī)那么組合起來n例子例子 ARCS (關(guān)聯(lián)規(guī)那么聚集系統(tǒng)關(guān)聯(lián)規(guī)那么聚集系統(tǒng)) ARCS 流程流程1. 分箱分箱2. 查找頻繁維詞查找頻繁維詞 集合集合3. 關(guān)聯(lián)規(guī)那么聚類關(guān)聯(lián)規(guī)那么聚類4. 優(yōu)化優(yōu)化ARCS的局限性的局限性n數(shù)值屬性只能出如今規(guī)那么的左側(cè)數(shù)值屬性只能出如今規(guī)那么的左側(cè)n左側(cè)只能有兩個(gè)屬性左側(cè)只能有兩個(gè)屬性 (2維維)nARCS 的改良的改良n不用基于柵格的方法不用基于柵格的方法n等深分箱等深分箱n基于部分完好性基于部分完好性 測度的聚集測度的聚集n“M

33、ining Quantitative Association Rules in Large Relational Tables by R. Srikant and R. Agrawal.發(fā)掘基于間隔的關(guān)聯(lián)規(guī)那么發(fā)掘基于間隔的關(guān)聯(lián)規(guī)那么n分箱的方法沒有表達(dá)數(shù)據(jù)間隔的語義分箱的方法沒有表達(dá)數(shù)據(jù)間隔的語義n基于間隔的分割是更有基于間隔的分割是更有“意義的離散化方法，思索：意義的離散化方法，思索：n區(qū)間內(nèi)密度或點(diǎn)的個(gè)數(shù)區(qū)間內(nèi)密度或點(diǎn)的個(gè)數(shù)n區(qū)間內(nèi)點(diǎn)的區(qū)間內(nèi)點(diǎn)的“嚴(yán)密程度嚴(yán)密程度價(jià)格（$）等寬( 寬度$10)等深(深度 2)基于距離70,107,207,72011,2022,5020,222221,30

34、51,5350,535031,405141,505351,60第第6章：從大數(shù)據(jù)庫中發(fā)掘關(guān)聯(lián)章：從大數(shù)據(jù)庫中發(fā)掘關(guān)聯(lián)規(guī)那么規(guī)那么n6.1 關(guān)聯(lián)規(guī)那么發(fā)掘關(guān)聯(lián)規(guī)那么發(fā)掘n6.2由事務(wù)數(shù)據(jù)庫發(fā)掘單維布爾關(guān)聯(lián)規(guī)那么由事務(wù)數(shù)據(jù)庫發(fā)掘單維布爾關(guān)聯(lián)規(guī)那么n6.3由事務(wù)數(shù)據(jù)庫發(fā)掘多層關(guān)聯(lián)規(guī)那么由事務(wù)數(shù)據(jù)庫發(fā)掘多層關(guān)聯(lián)規(guī)那么n6.4由關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫發(fā)掘多維關(guān)聯(lián)規(guī)那由關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫發(fā)掘多維關(guān)聯(lián)規(guī)那么么n6.5由關(guān)聯(lián)發(fā)掘到相關(guān)性分析由關(guān)聯(lián)發(fā)掘到相關(guān)性分析n6.6基于約束的關(guān)聯(lián)發(fā)掘基于約束的關(guān)聯(lián)發(fā)掘n6.7小結(jié)小結(jié)n強(qiáng)關(guān)聯(lián)規(guī)那么不一定是有趣的強(qiáng)關(guān)聯(lián)規(guī)那么不一定是有趣的168頁例頁例5.8n由關(guān)聯(lián)分析到相

35、關(guān)分析由關(guān)聯(lián)分析到相關(guān)分析n 項(xiàng)集項(xiàng)集A與項(xiàng)集與項(xiàng)集B獨(dú)立獨(dú)立 n P(AB)=P(A)P(B)n 項(xiàng)集項(xiàng)集A、B的相關(guān)性的相關(guān)性n corrAB=P(AB)/P(A)P(B)n 第第6章：從大數(shù)據(jù)庫中發(fā)掘關(guān)聯(lián)章：從大數(shù)據(jù)庫中發(fā)掘關(guān)聯(lián)規(guī)那么規(guī)那么n6.1 關(guān)聯(lián)規(guī)那么發(fā)掘關(guān)聯(lián)規(guī)那么發(fā)掘n6.2由事務(wù)數(shù)據(jù)庫發(fā)掘單維布爾關(guān)聯(lián)規(guī)那么由事務(wù)數(shù)據(jù)庫發(fā)掘單維布爾關(guān)聯(lián)規(guī)那么n6.3由事務(wù)數(shù)據(jù)庫發(fā)掘多層關(guān)聯(lián)規(guī)那么由事務(wù)數(shù)據(jù)庫發(fā)掘多層關(guān)聯(lián)規(guī)那么n6.4由關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫發(fā)掘多維關(guān)聯(lián)規(guī)那由關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫發(fā)掘多維關(guān)聯(lián)規(guī)那么么n6.5由關(guān)聯(lián)發(fā)掘到相關(guān)性分析由關(guān)聯(lián)發(fā)掘到相關(guān)性分析n6.6基于約束的關(guān)聯(lián)發(fā)掘基于約

36、束的關(guān)聯(lián)發(fā)掘n6.7小結(jié)小結(jié)6.6.1 基于約束的發(fā)掘基于約束的發(fā)掘n運(yùn)用約束的必要性運(yùn)用約束的必要性n在數(shù)據(jù)發(fā)掘中常運(yùn)用的幾種約束：在數(shù)據(jù)發(fā)掘中常運(yùn)用的幾種約束：n知識類型約束：指定要發(fā)掘的知識類型知識類型約束：指定要發(fā)掘的知識類型n 如關(guān)聯(lián)規(guī)那么如關(guān)聯(lián)規(guī)那么n數(shù)據(jù)約束：數(shù)據(jù)約束： 指定與義務(wù)相關(guān)的數(shù)據(jù)集指定與義務(wù)相關(guān)的數(shù)據(jù)集 nFind product pairs sold together in Vancouver in Dec.98.n維維/層次約束層次約束:指定所用的維或概念構(gòu)造中的層指定所用的維或概念構(gòu)造中的層nin relevance to region, price, brand, customer category.n規(guī)那么約束：指定要發(fā)掘的規(guī)那么方式規(guī)那么