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

1、數(shù)據(jù)挖掘發(fā)現(xiàn)(fxin)知識(shí)的類型概念描述（廣義知識(shí)(zh shi) ）關(guān)聯(lián)知識(shí)分類知識(shí)預(yù)測(cè)型知識(shí)偏差型知識(shí)共四十二頁(yè)從數(shù)據(jù)分析角度出發(fā)，數(shù)據(jù)挖掘可以分為(fn wi)兩種類型描述性數(shù)據(jù)挖掘: 以簡(jiǎn)潔概述的方式表達(dá)數(shù)據(jù)中的存在的一些有意義的性質(zhì)預(yù)測(cè)性數(shù)據(jù)挖掘: 分析數(shù)據(jù)，建立一個(gè)或一組模型，并試圖預(yù)測(cè)新數(shù)據(jù)集的行為共四十二頁(yè)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ù)庫(kù)中挖掘多層關(guān)聯(lián)規(guī)則 共四十二頁(yè) 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.共四十二頁(yè)關(guān)聯(lián)規(guī)則模式是屬于描述型模式，發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的算法屬于無(wú)監(jiān)督學(xué)習(xí)的方法。關(guān)聯(lián)規(guī)則的意義和度量 關(guān)聯(lián)規(guī)則挖掘的主要對(duì)象是事務(wù)數(shù)據(jù)庫(kù)（transaction DB），針對(duì)的應(yīng)用大多是售貨數(shù)據(jù)，一般情況下，一個(gè)事務(wù)由如下幾個(gè)部分組成：事務(wù)處理時(shí)間，一組顧客購(gòu)買的物品(wpn)，物品的數(shù)量及金額，顧客的標(biāo)識(shí)號(hào)。 在事務(wù)數(shù)據(jù)庫(kù)中，考察一些涉及到許多物品（項(xiàng)）的事務(wù)：事務(wù)1中出現(xiàn)了物品甲，事務(wù)2中出現(xiàn)了物品乙，事務(wù)3中同時(shí)出現(xiàn)了物品甲和乙，then，物品甲和物品乙在事務(wù)中的出現(xiàn)相互之間是否有一定的規(guī)律？ 在數(shù)據(jù)庫(kù)知識(shí)發(fā)現(xiàn)中，關(guān)聯(lián)規(guī)則

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

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

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

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

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

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

12、s diaperCustomerbuys bothCustomerbuys beer共四十二頁(yè)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ù)庫(kù)中挖掘多層關(guān)聯(lián)規(guī)則 共四十二頁(yè)4.2 經(jīng)典(jngdin)的關(guān)聯(lián)規(guī)則挖掘算法關(guān)聯(lián)規(guī)則的挖掘就是在事務(wù)(shw)數(shù)據(jù)庫(kù)D中找出具有用戶給定的最小支持度min-sup和最小可信度min-conf的關(guān)聯(lián)規(guī)則。 共四十二頁(yè)1. 關(guān)聯(lián)規(guī)則的挖掘過程:(1) 找出存在于事務(wù)數(shù)據(jù)庫(kù)中的所有頻繁項(xiàng)集。 項(xiàng)集X的支持(zhch)度不小于用戶給定的最小支持(zh

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

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

15、 Lk from Lk1？共四十二頁(yè)How to receive Lk from Lk1？共四十二頁(yè)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共四十二頁(yè)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共四十二頁(yè)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共四十二頁(yè)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項(xiàng)集 Ck=apriori_gen(Lk-1,min_sup); /產(chǎn)生候選項(xiàng)集 For each transaction tD /對(duì)所有事物進(jìn)行操作(cozu) Ct=subset(Ck, t); /t中包含的候選 For each candidate cCt c.count+; /計(jì)算每個(gè)項(xiàng)集的支持度 共四十二頁(yè)P(yáng)rocedure apriori_gen(Lk-1, min_sup)/連接(linji)和剪枝(1) (2)(3)(4) c=l1*l2; /鏈接步，生成候選項(xiàng)集 (5) if has_infrequent_subse

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

20、每個(gè)頻繁項(xiàng)集l ，產(chǎn)生所有非空子集s對(duì)于l的每個(gè)非空子集，如果 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共四十二頁(yè)然后(rnhu)得到如下的規(guī)則： 如果(rgu)min_conf70，則可得到并輸出下列的結(jié)果（強(qiáng)關(guān)聯(lián)規(guī)則）：共四十二頁(yè)關(guān)聯(lián)規(guī)則挖掘算法主要(zhyo)考慮的問題有以下兩個(gè)：（1）減少I/O操作。關(guān)聯(lián)規(guī)則挖掘的數(shù)據(jù)集有時(shí)可達(dá)GB甚至TB數(shù)量級(jí)，頻繁的I/O操作必將影響關(guān)聯(lián)規(guī)則的挖掘效率，減少I/O操作的方法主要是減少掃描數(shù)據(jù)集D的次數(shù)。（2）降低需要計(jì)算支持度的項(xiàng)目集（常稱為候選項(xiàng)集）的數(shù)量，使其與頻繁項(xiàng)目集的數(shù)量接近。候選項(xiàng)目數(shù)量的降低可以節(jié)省為處理部分候選項(xiàng)目集所需的計(jì)算時(shí)間和存儲(chǔ)

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

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

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

25、節(jié)點(diǎn)鏈指向它在樹中的出現(xiàn)。（如p240的figure6.8） 共四十二頁(yè)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共四十二頁(yè)Step3. 挖掘(wju)FP-tree (從FP-tree中尋找頻繁項(xiàng)集)從L的最后端項(xiàng)開始，依次對(duì)L中的項(xiàng)

27、做如下操作：（1）尋找該項(xiàng)（記為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）共四十二頁(yè)（2）由條件模式基產(chǎn)生滿足最小支持度的條件FP-tree(刪去(shn q)一些不滿足支持度的項(xiàng)) 如， 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）共四十二頁(yè)（3）由條件FP-tree找頻繁(pnfn)模式（frequent patterns）（由條件FP-tree產(chǎn)生的頻繁模式被處理項(xiàng)）,如 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)生強(qiáng)關(guān)聯(lián)規(guī)則共四十二頁(yè)FP_tree 算法(sun f)總結(jié)條件模式基條件FP-tree頻繁模式I5（I2，I1：1）（I2,I1,I3：1） （I2,I1:2） （