數(shù)據(jù)挖掘概念和術(shù)Chapter6課件

1、數(shù)據(jù)挖掘: 概念和技術(shù) Chapter 6 張曉輝 復(fù)旦大學(xué) （國際）數(shù)據(jù)庫研究中心第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é)什么是關(guān)聯(lián)挖掘?關(guān)聯(lián)規(guī)則挖掘：在交易數(shù)據(jù)、關(guān)系數(shù)據(jù)或其他信息載體中，查找存在于項目集合或?qū)ο蠹现g的頻繁模式、關(guān)聯(lián)、相關(guān)性、或因果結(jié)構(gòu)。應(yīng)用：購物籃分析、交叉銷售、產(chǎn)品目錄設(shè)計、 loss-leader analysis、聚集、分類等。舉例： 規(guī)則形式： “Body Head sup

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

3、店應(yīng)該怎樣提高護(hù)理用品的銷售？)家用電器 * (其他商品的庫存有什么影響?)在產(chǎn)品直銷中使用附加郵寄Detecting “ping-pong”ing of patients, faulty “collisions”規(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%)買尿布的客戶二者都買的客戶買啤酒的客戶關(guān)聯(lián)規(guī)則挖掘：路線圖布爾 vs. 定量

4、關(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. 多層 分析那個品種牌子的啤酒與那個牌子的尿布有關(guān)系?各種擴展相關(guān)性、因果分析關(guān)聯(lián)并不一定意味著相關(guān)或因果最大模式和閉合相集添加約束如, 哪些“小東西”的銷售促發(fā)了“大家伙”的買賣？第6章：從大數(shù)據(jù)庫中挖掘關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則挖掘從交易數(shù)據(jù)庫中挖掘一維的布爾形關(guān)聯(lián)規(guī)則從交易數(shù)

5、據(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é)關(guān)聯(lián)規(guī)則挖掘一個例子對于 A C：support = support(A 、C) = 50%confidence = support(A 、C)/support(A) = 66.6%Apriori的基本思想:頻繁項集的任何子集也一定是頻繁的最小值尺度 50%最小可信度 50%關(guān)鍵步驟：挖掘頻繁集頻繁集:是指滿足最小支持度的項目集合頻繁集的子集也一定是頻繁的如, 如果AB 是頻繁集，則 A B 也一定是頻繁集從1到k（k-頻繁集）遞歸查找頻繁集用得到的頻繁集生成關(guān)聯(lián)規(guī)則Apriori算法連

6、接: 用 Lk-1自連接得到Ck修剪: 一個k-項集，如果他的一個k-1項集（他的子集 ）不是頻繁的，那他本身也不可能是頻繁的。偽代碼: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 database 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;Apriori算法 例子數(shù)據(jù)庫 D掃描 DC1L1L2C2C2掃描 DC3L3掃描 D如何生成候選集假定 Lk-1 中的項按順序排列第一步: 自連接 Lk-1 insert into Ckselect p.item1, p.item2, , p.itemk-1, q.itemk-1from Lk-1 p, Lk-1