數(shù)據(jù)挖掘概念和技術(shù)Cha

,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,2001-11-6,數(shù)據(jù)挖掘：概念和技術(shù),*,數(shù)據(jù)挖掘:概念和技術(shù),Chapter 6,張曉輝,復(fù)旦大學（國際）數(shù)據(jù)庫研究中心,2001-11-6,1,數(shù)據(jù)挖掘：概念和技術(shù),第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é),2001-11-6,2,數(shù)據(jù)挖掘：概念和技術(shù),什么是關(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,H,ead support,confidence”.,buys(x,“diapers”),buys(x,“beers”)0.5%,60%,major(x,“CS”)takes(x,“DB”),grade(x,“A”)1%,75%,2001-11-6,3,數(shù)據(jù)挖掘：概念和技術(shù),關(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)用,*,護理用品,(商店應(yīng)該怎樣提高護理用品的銷售？,),家用電器,*,(其他商品的庫存有什么影響,?),在產(chǎn)品直銷中使用,附加郵寄,Detecting,“ping-pong”ing of patients,faulty“collisions”,2001-11-6,4,數(shù)據(jù)挖掘：概念和技術(shù),規(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%),買尿布的客戶,二者都買的客戶,買啤酒的客戶,2001-11-6,5,數(shù)據(jù)挖掘：概念和技術(shù),關(guān)聯(lián)規(guī)則挖掘：路線圖,布爾,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.,多層,分析,那個品種牌子的啤酒與那個牌子的尿布有關(guān)系,?,各種擴展,相關(guān)性、因果分析,關(guān)聯(lián)并不一定意味著相關(guān)或因果,最大模式和閉合相集,添加約束,如,哪些“小東西”的銷售促發(fā)了“大家伙”的買賣？,2001-11-6,6,數(shù)據(jù)挖掘：概念和技術(shù),第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é),2001-11-6,7,數(shù)據(jù)挖掘：概念和技術(shù),關(guān)聯(lián)規(guī)則挖掘一個例子,對于,A,C：,support=support(,A,、,C,)=50%,confidence=support(,A,、,C,)/support(,A,)=66.6%,Apriori,的基本思想:,頻繁項集的任何子集也一定是頻繁的,最小值尺度 50%,最小可信度 50%,2001-11-6,8,數(shù)據(jù)挖掘：概念和技術(shù),關(guān)鍵步驟：挖掘頻繁集,頻繁集,:是指滿足最小支持度的項目集合,頻繁集的子集也一定是頻繁的,如,如果,AB,是頻繁集，則,A,B,也一定是頻繁集,從1到,k（k-,頻繁集）遞歸查找頻繁集,用得到的頻繁集生成關(guān)聯(lián)規(guī)則,2001-11-6,9,數(shù)據(jù)挖掘：概念和技術(shù),Apriori,算法,連接,:,用,L,k-1,自連接得到,C,k,修剪,:,一個,k-,項集，如果他的一個,k-1,項集（他的子集）不是頻繁的，那他本身也不可能是頻繁的。,偽代碼,:,C,k,:Candidate itemset of size k,L,k,:frequent itemset of size k,L,1,=frequent items;,for,(,k,=1;,L,k,!=,;,k,+),do begin,C,k+1,=candidates generated from,L,k,;,for each,transaction,t,in database do,increment the count of all candidates in,C,k+1,that are contained in,t,L,k+1,=candidates in,C,k+1,with min_support,end,return,k,L,k,;,2001-11-6,10,數(shù)據(jù)挖掘：概念和技術(shù),Apriori,算法 例子,數(shù)據(jù)庫,D,掃描,D,C,1,L,1,L,2,C,2,C,2,掃描,D,C,3,L,3,掃描,D,2001-11-6,11,數(shù)據(jù)挖掘：概念和技術(shù),如何生成候選集,假定,L,k-1,中的項按順序排列,第一步:自連接,L,k-1,insert into,C,k,select,p.item,1,p.item,2,p.item,k-1,q.item,k-1,from,L,k-1,p,L,k-1,q,where,p.item,1,=q.item,1,p.item,k-2,=q.item,k-2,p.item,k-1,=10,用,Apriori,提高,執(zhí)行,冰山查詢的效率,先計算低維,只有當,所有的,低維都滿足預(yù)制時才計算高維,2001-11-6,36,數(shù)據(jù)挖掘：概念和技術(shù),