數(shù)據(jù)挖掘4關(guān)聯(lián)規(guī)則資料

1、數(shù)據(jù)挖掘發(fā)現(xiàn)(fxin)知識的類型概念描述（廣義知識(zh shi) ）關(guān)聯(lián)知識分類知識預測型知識偏差型知識共四十二頁從數(shù)據(jù)分析角度出發(fā)，數(shù)據(jù)挖掘可以分為(fn wi)兩種類型描述性數(shù)據(jù)挖掘: 以簡潔概述的方式表達數(shù)據(jù)中的存在的一些有意義的性質(zhì)預測性數(shù)據(jù)挖掘: 分析數(shù)據(jù)，建立一個或一組模型，并試圖預測新數(shù)據(jù)集的行為共四十二頁Chapter 4 Association Rule & Rough Set4.1 關(guān)聯(lián)規(guī)則概述4.2 經(jīng)典的關(guān)聯(lián)規(guī)則挖掘(wju)算法4.3 從事物數(shù)據(jù)庫中挖掘多層關(guān)聯(lián)規(guī)則 共四十二頁 What Is Frequent Pattern Analysis?Frequent

2、pattern: a pattern (a set of items, subsequences, substructures, etc.) that occurs frequently in a data set First proposed by Agrawal, Imielinski, and Swami AIS93 in the context of frequent itemsets and association rule miningMotivation: Finding inherent regularities in dataWhat products were often

3、purchased together? Beer and diapers?!What are the subsequent purchases after buying a PC?What kinds of DNA are sensitive to this new drug?Can we automatically classify web documents?ApplicationsBasket data analysis, cross-marketing, catalog design, sale campaign analysis, Web log (click stream) ana

4、lysis, and DNA sequence analysis.共四十二頁關(guān)聯(lián)規(guī)則模式是屬于描述型模式，發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的算法屬于無監(jiān)督學習的方法。關(guān)聯(lián)規(guī)則的意義和度量 關(guān)聯(lián)規(guī)則挖掘的主要對象是事務數(shù)據(jù)庫（transaction DB），針對的應用大多是售貨數(shù)據(jù)，一般情況下，一個事務由如下幾個部分組成：事務處理時間，一組顧客購買的物品(wpn)，物品的數(shù)量及金額，顧客的標識號。 在事務數(shù)據(jù)庫中，考察一些涉及到許多物品（項）的事務：事務1中出現(xiàn)了物品甲，事務2中出現(xiàn)了物品乙，事務3中同時出現(xiàn)了物品甲和乙，then，物品甲和物品乙在事務中的出現(xiàn)相互之間是否有一定的規(guī)律？ 在數(shù)據(jù)庫知識發(fā)現(xiàn)中，關(guān)聯(lián)規(guī)則

5、就是描述這種在一個事務中物品之間同時出現(xiàn)的規(guī)律的知識模式。更確切的說，關(guān)聯(lián)規(guī)則通過量化的數(shù)字描述物品甲的出現(xiàn)對物品乙的出現(xiàn)有多大影響。共四十二頁例如(lr)某超級市場的銷售系統(tǒng)，記錄了5個顧客的購物清單 流水號所購物品清單1球鞋、手套、網(wǎng)球拍2摩托車、手套、頭盔3球鞋、摩托車 、手套、頭盔4頭盔5摩托車、頭盔購買摩托車的人很大可能同時(tngsh)購買頭盔共四十二頁 有些數(shù)據(jù)不像售貨數(shù)據(jù)那樣很容易就能看出一個事務是哪些物品的集合，但稍微轉(zhuǎn)換一下思考角度，仍然可以像售貨數(shù)據(jù)一樣處理。 例如人壽保險，一份保單就是一個事務。保險公司在接受保險前，往往需要(xyo)記錄投保人詳盡的信息，有時還要到醫(yī)院

6、做身體檢查。保單上記錄有投保人的年齡、性別、健康狀況、工作單位、工作地址、工資水平等。這些投保人的個人信息就可以看作事務中的物品。通過分析這些數(shù)據(jù)，可以得到類似以下這樣的關(guān)聯(lián)規(guī)則： 年齡在40歲以上，工作在A區(qū)的投保人當中，有45的人曾經(jīng)向保險公司索賠過。在這條規(guī)則中，“年齡在40歲以上”是物品甲，“工作在A區(qū)”是物品乙，“向保險公司索賠過”則是物品丙。 可以看出來，A區(qū)可能污染比較嚴重，環(huán)境比較差，導致工作在該區(qū)的人健康狀況不好，索賠率也相對比較高。 共四十二頁事務(shw)與項集設：R=I1，I2，In是一組項集（項目集，屬性集，item set）W是一組與R相關(guān)的事務集。W中的每個事務T

7、是一組項（屬性）。假設有一個項集A，一個事務T，如果 AT，則稱事務T支持(zhch)項集A。例如： R=I1, I2, I3, I4, I5, I6, I7 事務集W：事務T1I1, I2, I5事務T2I1, I5, I7事務T3I2, I4, I6, I7事務T4I3, I7事務T5I5, I6 假設有項集A=I1, I5，則稱事務T1，事務T2支持項集A。共四十二頁規(guī)則(guz)表示由事務與項集表，最終得到(d do)的關(guān)聯(lián)規(guī)則是如下形式的一種蘊涵式：TIDItem SetT1牛奶，面包，黃油T2牛奶，面包，啤酒T3面包，黃油，啤酒T4黃油，醬油，餐巾紙T5餐巾紙，拖把R牛奶，面包，黃

8、油，啤酒，醬油，餐巾紙，拖把A=面包，B黃油 ？A=面包，B拖把 ？A=餐巾紙，牛奶，B黃油 ？ How to evaluate this rule?共四十二頁描述關(guān)聯(lián)(gunlin)規(guī)則屬性的四個參數(shù)(1)可信度（condifence），設W中支持(zhch)物品集A的事務中，有c的事務同時也支持物品集B，c稱為關(guān)聯(lián)規(guī)則的可信度。是對關(guān)聯(lián)規(guī)則的準確度的衡量。 (2)支持度（support），設W中有s的事務同時支持物品集A和B，s稱為關(guān)聯(lián)規(guī)則的支持度。是對關(guān)聯(lián)規(guī)則重要性（或適用范圍）的衡量。支持度說明了這條規(guī)則在所有事務中有多大代表性，支持度越大，關(guān)聯(lián)規(guī)則越重要，應用越廣泛。 共四十二頁(3

9、)期望(qwng)可信度（expected confidence）,設W中有e的事務支持物品集B，e稱為關(guān)聯(lián)規(guī)則的期望可信度。描述的是在沒有任何條件影響時，物品集B在所有事務中出現(xiàn)的概率?；蛘哒f是在沒有物品集A的作用下，物品集B本身的支持度。(4)作用度（lift），是可信度與期望可信度的比值。描述的是物品集A的出現(xiàn)對物品集B的出現(xiàn)有多大影響。通 過 可 信 度 對 期 望 可 信 度 的 比 值 反 映 了 在 加 入“ 物 品 集A 出 現(xiàn)” 的 這 個 條 件 后， 物 品 集B 的 出 現(xiàn) 概 率 發(fā) 生 了 多 大 的 變 化。作用度越大，說明物品集B受物品集A的影響越大。 共四十二

10、頁四個參數(shù)(cnsh)的計算公式 可信度（condifence） 在物品集A出現(xiàn)的前提下，B出現(xiàn)的概率 P(B|A)支持度（support） 物品集A、B同時出現(xiàn)的概率 P(BA)期望可信度（expected confidence） 物品集B出現(xiàn)的概率 P(B)作用度（lift） 可信度對期望可信度的比值 P(B|A)/P(A)一般情況下，有用(yu yn)的關(guān)聯(lián)規(guī)則的作用度都應該大于1，只有關(guān)聯(lián)規(guī)則的可信度大于期望可信度，才說明A的出現(xiàn)對B的出現(xiàn)有促進作用，也說明了它們之間有某種程度的相關(guān)性。如果作用度不大于1，則此關(guān)聯(lián)規(guī)則就沒意義了。 Back共四十二頁TIDItem SetT1牛奶，面包

11、，黃油T2牛奶，面包，啤酒T3面包，黃油，啤酒T4黃油，醬油，餐巾紙T5餐巾紙，拖把R牛奶(ni ni)，面包，黃油，啤酒，醬油，餐巾紙，拖把 How to evaluate this rule?A=面包，B黃油 支持度：2/5; 可信度：2/3; 期望可信度：3/5; 作用度：10/9規(guī)則: A B (40%, 67% )A=面包，B拖把(tub) 支持度：0; 可信度：0; 期望可信度：1/5; 作用度：0規(guī)則: A B (0%, 0% )A=餐巾紙，牛奶，B黃油 支持度：0; 可信度：0; 期望可信度：3/5; 作用度：0規(guī)則: A B (0%, 0% )共四十二頁Customerbuy

12、s diaperCustomerbuys bothCustomerbuys beer共四十二頁Chapter 4 Association Rule & Rough Set4.1 關(guān)聯(lián)(gunlin)規(guī)則概述4.2 經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法4.3 從事物數(shù)據(jù)庫中挖掘多層關(guān)聯(lián)規(guī)則 共四十二頁4.2 經(jīng)典(jngdin)的關(guān)聯(lián)規(guī)則挖掘算法關(guān)聯(lián)規(guī)則的挖掘就是在事務(shw)數(shù)據(jù)庫D中找出具有用戶給定的最小支持度min-sup和最小可信度min-conf的關(guān)聯(lián)規(guī)則。 共四十二頁1. 關(guān)聯(lián)規(guī)則的挖掘過程:(1) 找出存在于事務數(shù)據(jù)庫中的所有頻繁項集。 項集X的支持(zhch)度不小于用戶給定的最小支持(zh

13、ch)度，則稱x為頻繁項集（frequent item set）或大物品集（large item set）。第二步比較(bjio)容易，目前大多數(shù)研究集中在第一個子問題上。 利用頻繁集生成關(guān)聯(lián)規(guī)則。 對于每個頻繁集A，若 共四十二頁2. 關(guān)聯(lián)規(guī)則(guz)方法的分類（1）一般(ybn)處理的是離散化數(shù)據(jù)，根據(jù)離散化結(jié)果，可分為根據(jù)規(guī)則中涉及的數(shù)據(jù)維數(shù)（項數(shù)，屬性數(shù)） 根據(jù)規(guī)則集所涉及的抽象層 共四十二頁3. 經(jīng)典的關(guān)聯(lián)規(guī)則(guz)挖掘算法 （單維、單層、布爾型的關(guān)聯(lián)規(guī)則挖掘） Aprior算法(sun f)FP_增長樹算法共四十二頁3.1 Aprior算法：尋找頻繁集，用k-1項集（Lk-1

14、）探索k項集（Lk），即頻繁集的子集必須(bx)是頻繁項集，是寬度優(yōu)先算法。先找出所有的1項集（含有一個項的項集），記為C1，找出所有的頻繁1項集，記為L1。然后根據(jù)頻繁1項集確定候選2項集的集合C2 ，從C2中找出所有的頻繁2項集，記為L2。然后再根據(jù)頻繁2項集確定候選3項集的集合，記為C3，從C3中找出所有的頻繁3項集，記為L3。如此下去直到(zhdo)不再有候選項集。 TIDItem SetT1牛奶，面包，黃油T2牛奶，面包，啤酒T3面包，黃油，啤酒T4黃油，醬油，餐巾紙T5餐巾紙，拖把C1：牛奶，面包，黃油，啤酒，醬油，餐巾紙，拖把L1：面包，黃油共四十二頁How to receive

15、 Lk from Lk1？共四十二頁How to receive Lk from Lk1？共四十二頁ExampleTIDItemsT100I1, I2, I5T200I2, I4T300I2, I3T400I1, I2, I4T500I1, I3T600I2, I3T700I1, I3T800I1, I2, I3, I5T900I1, I2, I3Transactional database DItem setSupportI16I27I36I42I52Scan DC1Item setSupport I16I27I36I42I52L1Calculate supportJoinL1*L 1Min

16、_sup2Prune共四十二頁Item setI1, I2I1, I3I1, I4I1, I5I2, I3I2, I4I2, I5I3, I4I3, I5I4, I5Item setSupport CountI1, I24I1, I34I1, I41I1, I52I2, I34I2, I42I2, I52I3, I40I3, I51I4, I50C2Scan D C2Item setSupport CountI1, I24I1, I34I1, I52I2, I34I2, I42I2, I52 Calculate supportL2L2*L2Prune共四十二頁Item setI1, I2, I

17、3I1, I2, I5I1, I3, I5I2, I3, I4I2, I3, I5I2, I4, I5Item setI1，I2，I3I1，I2，I5Item setSupportI1，I2，I32I1，I2，I52C3PruneC3Item setSupportI1，I2，I32I1，I2，I52C3Scan DL3ItemsetI1，I2，I3，I5C4L3*L3Prune共四十二頁Apriori Algorithm Input：DB，min_supOutput：L, frequent itemsets in D and their supportsMethod： L1=find_freq

18、uent_1-itemsets(D);/遍歷DB，產(chǎn)生頻繁1項集 Ck=apriori_gen(Lk-1,min_sup); /產(chǎn)生候選項集 For each transaction tD /對所有事物進行操作(cozu) Ct=subset(Ck, t); /t中包含的候選 For each candidate cCt c.count+; /計算每個項集的支持度 共四十二頁Procedure apriori_gen(Lk-1, min_sup)/連接(linji)和剪枝(1) (2)(3)(4) c=l1*l2; /鏈接步，生成候選項集 (5) if has_infrequent_subse

19、t(c, Lk-1) then delete c; /剪枝 else add c to Ck; return Ck; 共四十二頁Procedure has_infrequent_subset(c: Lk-1) /use prior knowledge for each (k-1)-subset s of c return TRUE; Else return FALSE; 共四十二頁找到的所有頻繁項集 I1，I2；I1，I3；I1，I5；I2，I3；I2，I4；I2，I5； I1，I2，I3；I1，I2，I5。從頻繁集生成(shn chn)強關(guān)聯(lián)規(guī)則（滿足min_sup和min_conf）:對于

20、每個頻繁項集l ，產(chǎn)生所有非空子集s對于l的每個非空子集，如果 count（l）/count（s）min_conf, 則輸出規(guī)則 s(l-s) 如：l=I1,I2,I5, 非空子集：I1, I2, I5, I1,I2, I1,I5, I2,I5s=I1,I2, l-s=I5; count(l)/count(s)=2/4s=I1,I5, l-s=I2; count(l)/count(s)=2/2s=I2,I5, l-s=I1; count(l)/count(s)=2/2s=I1, l-s=I2,I5; count(l)/count(s)=2/6s=I2, l-s=I1,I5; count(l)/

21、count(s)=2/7s=I5, l-s=I1,I2; count(l)/count(s)=2/2共四十二頁然后(rnhu)得到如下的規(guī)則： 如果(rgu)min_conf70，則可得到并輸出下列的結(jié)果（強關(guān)聯(lián)規(guī)則）：共四十二頁關(guān)聯(lián)規(guī)則挖掘算法主要(zhyo)考慮的問題有以下兩個：（1）減少I/O操作。關(guān)聯(lián)規(guī)則挖掘的數(shù)據(jù)集有時可達GB甚至TB數(shù)量級，頻繁的I/O操作必將影響關(guān)聯(lián)規(guī)則的挖掘效率，減少I/O操作的方法主要是減少掃描數(shù)據(jù)集D的次數(shù)。（2）降低需要計算支持度的項目集（常稱為候選項集）的數(shù)量，使其與頻繁項目集的數(shù)量接近。候選項目數(shù)量的降低可以節(jié)省為處理部分候選項目集所需的計算時間和存儲

22、空間。共四十二頁 Aprior算法最直觀，最易理解，但 需要產(chǎn)生大量的候選項集，工作量很大。 需要重復地掃描數(shù)據(jù)庫，通過模式(msh)匹配檢查一個很大的候選集合（長模式(msh)時尤其如此）。共四十二頁3.2 FP_tree growth algorithm不產(chǎn)生(chnshng)候選項集的頻繁項集挖掘方法 能提供頻繁(pnfn)項集的數(shù)據(jù)庫壓縮到頻繁(pnfn)模式樹（Frequent Pattern Tree）上，分成一組條件數(shù)據(jù)庫，再由這些條件數(shù)據(jù)庫生成頻繁項集。How does FP_tree growth algorithm to find frequent itemsets?共四十

23、二頁FP-tree growth Algorithm Input：A transaction database D, min-supOutput: the complete set of frequent patternsMethod:Step1.第一次掃描數(shù)據(jù)庫，計數(shù)并導出L1的集合，最后(zuhu)使得L1中的每件事務中的項按count的降序排列，記為LItem setSupport I27I16I36I42I52上例的事務(shw)數(shù)據(jù)庫得到的L共四十二頁Step2. 構(gòu)造(guzo)FP-tree.( 包括Item ID, Support count Node link)Step2.1

24、 創(chuàng)建根節(jié)點，記為nullStep2.2 第二次掃描數(shù)據(jù)庫， 對每一個事務中的項按L中的次序重新排列處理 （如右表） 然后對每個事務創(chuàng)建一個分枝（一棵子樹）：1）分枝的節(jié)點數(shù)事務中的項數(shù)2）按順序，最前面一項鏈接到根節(jié)點，后面一項被鏈接到前面一項，并計數(shù)(j sh)3）對于有共享前綴的，計數(shù)加1并在該前綴基礎上創(chuàng)建一個新節(jié)點TIDItemsT100I2, I1, I5T200I2, I4T300I2, I3T400I2, I1, I4T500I1, I3T600I2, I3T700I1, I3T800I2, I1, I3, I5T900I2, I1, I3 4） 創(chuàng)建項類表，使得每個項通過一個

25、節(jié)點鏈指向它在樹中的出現(xiàn)。（如p240的figure6.8） 共四十二頁Construct FP-tree from a Transaction Databasef: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

26、, o, wf, b400 b, c, k, s, pc, b, p500 a, f, c, e, l, p, m, nf, c, a, m, pScan DB once, find frequent 1-itemset (single item pattern)Sort frequent items in frequency descending order, f-listScan DB again, construct FP-treeF-list=f-c-a-b-m-p共四十二頁Step3. 挖掘(wju)FP-tree (從FP-tree中尋找頻繁項集)從L的最后端項開始，依次對L中的項

27、做如下操作：（1）尋找該項（記為I）的條件(tiojin)模式基(conditional pattern base)【FP-tree中與后綴模式（I）一起出現(xiàn)的前綴路徑集合】，如 I5的條件模式基：（I2，I1：1），（I2，I1，I3：1） I4的條件模式基：（I2，I1：1），（I2：1） I3的條件模式基：（I2，I1：2），（I2：2），（I1：2） I2的條件模式基： I1的條件模式基：（I2：4）共四十二頁（2）由條件模式基產(chǎn)生滿足最小支持度的條件FP-tree(刪去(shn q)一些不滿足支持度的項) 如， I5的條件FP-tree：（I2，I1：2） I4的條件FP-tree：

28、（I2：2） I3的條件FP-tree：(I2，I1：2)，(I2：2)，(I1：2) 也有的寫為（I2：4，I1：2），（I1：2） I1的條件FP-tree：（I2：4）共四十二頁（3）由條件FP-tree找頻繁(pnfn)模式（frequent patterns）（由條件FP-tree產(chǎn)生的頻繁模式被處理項）,如 I5的頻繁模式：(I2，I5：2)，(I1，I5：2)，(I2，I1，I5：2) I4的頻繁模式：（I2，I4：2） I3的頻繁模式：(I2，I1，I3：2)，(I2，I3：4)，(I1，I3：4) I1的頻繁模式：(I2，I1：4) Step4.由頻繁集產(chǎn)生強關(guān)聯(lián)規(guī)則共四十二頁FP_tree 算法(sun f)總結(jié)條件模式基條件FP-tree頻繁模式I5（I2，I1：1）（I2,I1,I3：1） （I2,I1:2） （