1、1,商業(yè)自動(dòng)化,主講教師：陳冬林,第十四講DM之關(guān)聯(lián)規(guī)則昆明理工大學(xué)計(jì)算機(jī)系周海河2020年8月24日,2,引言 關(guān)聯(lián)規(guī)則挖掘 從交易數(shù)據(jù)庫(kù)中挖掘一維的布爾形關(guān)聯(lián)規(guī)則 練習(xí)題 Frequent-Pattern tree（選講）,目錄,3,引言,關(guān)聯(lián)知識(shí)（Association） 一、定義：它反映一個(gè)事件和其他事件之間依賴(lài)或關(guān)聯(lián)的知識(shí)。 二、實(shí)現(xiàn)技術(shù)有 Apriori算法 第一步是迭代識(shí)別所有的頻繁項(xiàng)目集，要求頻繁項(xiàng)目集的支持率不低于用戶(hù)設(shè)定的最低值； 第二步是從頻繁項(xiàng)目集中構(gòu)造可信度不低于用戶(hù)設(shè)定的最低值的規(guī)則。,4,關(guān)聯(lián)分析：數(shù)據(jù)關(guān)聯(lián)是數(shù)據(jù)庫(kù)中存在的一類(lèi)重要的可被發(fā)現(xiàn)的知識(shí)。若兩個(gè)或多個(gè)變量

2、的取值之間存在某種規(guī)律性，就稱(chēng)為關(guān)聯(lián)。關(guān)聯(lián)可分為簡(jiǎn)單關(guān)聯(lián)、時(shí)序關(guān)聯(lián)、因果關(guān)聯(lián)。關(guān)聯(lián)分析的目的是找出數(shù)據(jù)庫(kù)中隱藏的關(guān)聯(lián)網(wǎng)。有時(shí)并不知道數(shù)據(jù)庫(kù)中數(shù)據(jù)的關(guān)聯(lián)函數(shù)，即使知道也是不確定的，因此關(guān)聯(lián)分析生成的規(guī)則帶有可信度。,5,關(guān)聯(lián)規(guī)則,引言 關(guān)聯(lián)規(guī)則挖掘 從交易數(shù)據(jù)庫(kù)中挖掘一維的布爾形關(guān)聯(lián)規(guī)則 練習(xí)題 Frequent-Pattern tree（選講）,6,什么是關(guān)聯(lián)挖掘?,關(guān)聯(lián)規(guī)則挖掘： 在交易數(shù)據(jù)、關(guān)系數(shù)據(jù)或其他信息載體中，查找存在于項(xiàng)目集合或?qū)ο蠹现g的頻繁模式、關(guān)聯(lián)、相關(guān)性、或因果結(jié)構(gòu)。 應(yīng)用： 購(gòu)物籃分析、交叉銷(xiāo)售、產(chǎn)品目錄設(shè)計(jì)、 loss-leader analysis、聚集、分類(lèi)等。

3、舉例： 規(guī)則形式： “Body Head support, confidence”. buys(x, “diapers”) buys(x, “beers”) 0.5%, 60% major(x, “CS”) takes(x, “DB”) grade(x, “A”) 1%, 75%,7,關(guān)聯(lián)規(guī)則：基本概念,給定: (1)交易數(shù)據(jù)庫(kù) (2)每筆交易是：一個(gè)項(xiàng)目列表 (消費(fèi)者一次購(gòu)買(mǎi)活動(dòng)中購(gòu)買(mǎi)的商品) 查找: 所有描述一個(gè)項(xiàng)目集合與其他項(xiàng)目集合相關(guān)性的規(guī)則 E.g., 98% of people who purchase tires and auto accessories also get aut

4、omotive services done 應(yīng)用 * 護(hù)理用品 (商店應(yīng)該怎樣提高護(hù)理用品的銷(xiāo)售？) 家用電器 * (其他商品的庫(kù)存有什么影響?) 在產(chǎn)品直銷(xiāo)中使用附加郵寄,8,規(guī)則度量：支持度與可信度,查找所有的規(guī)則 X 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

5、+1 with min_support end return k Lk;,stetp1:,14,Apriori算法算例,現(xiàn)有A、B、C、D、E五種商品的交易記錄表，試找出三種商品關(guān)聯(lián)銷(xiāo)售情況(k=3)，最小支持度=50%。,15,算例解答,K=1,支持度50,討論：求k=3,考不考慮A、C、D？為什么？,16,答：confidence = support(A ,B,C,E)/support(B,C,E) = 25%/50%=50%,17,Apriori 夠快了嗎? 性能瓶頸,Apriori算法的核心: 用頻繁的(k 1)-項(xiàng)集生成候選的頻繁 k-項(xiàng)集 用數(shù)據(jù)庫(kù)掃描和模式匹配計(jì)算候選集的支持度

6、Apriori 的瓶頸: 候選集生成 巨大的候選集: 104 個(gè)頻繁1-項(xiàng)集要生成 107 個(gè)候選 2-項(xiàng)集 要找尺寸為100的頻繁模式，如 a1, a2, , a100, 你必須先產(chǎn)生2100 1030 個(gè)候選集 多次掃描數(shù)據(jù)庫(kù)： 如果最長(zhǎng)的模式是n的話(huà)，則需要 (n +1 ) 次數(shù)據(jù)庫(kù)掃描,18,2.現(xiàn)有五種商品的交易記錄表，用Apriori算法試找出三種商品關(guān)聯(lián)銷(xiāo)售情況(k=3)，最小支持度=50%。,練習(xí)題,1.正確解釋表達(dá)式的含義：major(x, “CS”) takes(x, “DB”) grade(x, “A”) 1%, 75%。,19,答案,1.正確解釋表達(dá)式的含義：major

7、(x, “CS”) takes(x, “DB”) grade(x, “A”) 1%, 75%。 解釋(1)在成績(jī)登記系統(tǒng)中，專(zhuān)業(yè)為“計(jì)算機(jī)專(zhuān)業(yè)”并且選修“數(shù)據(jù)庫(kù)原理”其得分為“A”等的比例是1%。 (2)計(jì)算機(jī)專(zhuān)業(yè)的學(xué)生選修“數(shù)據(jù)庫(kù)原理”，成績(jī)得“A”的可能性是75%,20,2.解按C1L1C2L2C3L3求解,支持度50,支持度50,支持度50,支持度50,支持度50,支持度50,21,挖掘頻繁集 不用生成候選集,用Frequent-Pattern tree (FP-tree) 結(jié)構(gòu)壓縮數(shù)據(jù)庫(kù), 高度濃縮，同時(shí)對(duì)頻繁集的挖掘又完備的 避免代價(jià)較高的數(shù)據(jù)庫(kù)掃描 開(kāi)發(fā)一種高效的基于FP-tree

8、的頻繁集挖掘算法 采用分而治之的方法學(xué)：分解數(shù)據(jù)挖掘任務(wù)為小任務(wù) 避免生成關(guān)聯(lián)規(guī)則: 只使用部分?jǐn)?shù)據(jù)庫(kù)!,22,用交易數(shù)據(jù)庫(kù)建立 FP-tree,最小支持度 = 0.5,TIDItems bought (ordered) frequent items 100f, a, c, d, g, i, m, pf, c, a, m, p 200a, b, c, f, l, m, of, c, a, b, m 300 b, f, h, j, of, b 400 b, c, k, s, pc, b, p 500 a, f, c, e, l, p, m, nf, c, a, m, p,步驟: 掃描數(shù)據(jù)庫(kù)一次，

9、得到頻繁1-項(xiàng)集 把項(xiàng)按支持度遞減排序 再一次掃描數(shù)據(jù)庫(kù)，建立FP-tree,23,FP-tree 結(jié)構(gòu)的好處,完備: 不會(huì)打破交易中的任何模式 包含了序列模式挖掘所需的全部信息 緊密 去除不相關(guān)信息不包含非頻繁項(xiàng) 支持度降序排列: 支持度高的項(xiàng)在FP-tree中共享的機(jī)會(huì)也高 決不會(huì)比原數(shù)據(jù)庫(kù)大（如果不計(jì)算樹(shù)節(jié)點(diǎn)的額外開(kāi)銷(xiāo)) 例子: 對(duì)于 Connect-4 數(shù)據(jù)庫(kù),壓縮率超過(guò) 100,24,用 FP-tree挖掘頻繁集,基本思想 (分而治之) 用FP-tree地歸增長(zhǎng)頻繁集 方法 對(duì)每個(gè)項(xiàng)，生成它的 條件模式庫(kù), 然后是它的 條件 FP-tree 對(duì)每個(gè)新生成的條件FP-tree，重復(fù)這個(gè)

10、步驟 直到結(jié)果FP-tree為空, 或只含維一的一個(gè)路徑 (此路徑的每個(gè)子路徑對(duì)應(yīng)的相集都是頻繁集),25,挖掘 FP-tree的主要步驟,為FP-tree中的每個(gè)節(jié)點(diǎn)生成條件模式庫(kù) 用條件模式庫(kù)構(gòu)造對(duì)應(yīng)的條件FP-tree 遞歸構(gòu)造條件 FP-trees 同時(shí)增長(zhǎng)其包含的頻繁集 如果條件FP-tree直包含一個(gè)路徑，則直接生成所包含的頻繁集。,26,步驟1: 從 FP-tree 到條件模式庫(kù),從FP-tree的頭表開(kāi)始 按照每個(gè)頻繁項(xiàng)的連接遍歷 FP-tree 列出能夠到達(dá)此項(xiàng)的所有前綴路徑，得到條件模式庫(kù),條件模式庫(kù) itemcond. pattern base cf:3 afc:3 bf

11、ca:1, f:1, c:1 mfca:2, fcab:1 pfcam:2, cb:1,27,FP-tree支持條件模式庫(kù)構(gòu)造的屬性,節(jié)點(diǎn)褳接 任何包含ai, 的可能頻繁集，都可以從FP-tree頭表中的ai沿著ai 的節(jié)點(diǎn)鏈接得到 前綴路徑 要計(jì)算路徑P 中包含節(jié)點(diǎn)ai 的頻繁集，只要考察到達(dá)ai 的路徑前綴即可，且其支持度等于節(jié)點(diǎn)ai 的支持度,28,步驟2: 建立條件 FP-tree,對(duì)每個(gè)模式庫(kù) 計(jì)算庫(kù)中每個(gè)項(xiàng)的支持度 用模式庫(kù)中的頻繁項(xiàng)建立FP-tree,m-條件模是庫(kù): fca:2, fcab:1,All frequent patterns concerning m m, fm,

12、cm, am, fcm, fam, cam, fcam,f:4,c:1,b:1,p:1,b:1,c:3,a:3,b:1,m:2,p:2,m:1,頭表 Item frequency head f4 c4 a3 b3 m3 p3,29,通過(guò)建立條件模式庫(kù)得到頻繁集,30,第3步: 遞歸挖掘條件FP-tree,“am”的條件模式庫(kù): (fc:3),“cm”的條件模式: (f:3),f:3,cm-條件 FP-tree,“cam”條件模式庫(kù): (f:3),f:3,cam-條件 FP-tree,31,單FP-tree 路徑生成,假定FP-tree T 只包含路徑 P P的子路徑所有可能組合就是T的包含的所

13、有頻繁集,f:3,c:3,a:3,m-條件 FP-tree,包含 m的所有品感激 m, fm, cm, am, fcm, fam, cam, fcam,32,特例: FP-tree 中的唯一前綴路徑,假定一個(gè) (條件) FP-tree T 又一個(gè)共享唯一前綴路徑 P 挖掘可分解為如下兩個(gè)步驟 用一個(gè)節(jié)點(diǎn)代替此前綴路徑P 分別計(jì)算這兩個(gè)部分的結(jié)果,+,33,頻繁集增長(zhǎng)的原理,模式增長(zhǎng)的特征 令 為DB的一個(gè)頻繁集， B 為 的條件模式庫(kù)， 是 B中的一個(gè)項(xiàng)，要使 是DB中的頻繁集，當(dāng)且僅當(dāng) 是 B 的頻繁項(xiàng). “abcdef ” 是頻繁集,當(dāng)且僅當(dāng) “abcde ” 是頻繁集, 且 “f ” 在

14、包含 “abcde ”的事務(wù)中是頻繁的。,34,為什么 頻繁集增長(zhǎng) 速度快？,我們的性能研究顯示 FP-growth 比Apriori快一個(gè)數(shù)量級(jí), 同樣也比 tree-projection 快。 原因 不生成候選集，不用候選測(cè)試。 使用緊縮的數(shù)據(jù)結(jié)構(gòu) 避免重復(fù)數(shù)據(jù)庫(kù)掃描 基本操作是計(jì)數(shù)和建立 FP-tree 樹(shù),35,FP-growth vs. Apriori: 相對(duì)于支持度的擴(kuò)展性,Data set T25I20D10K,36,FP-growth vs. Tree-Projection:相對(duì)于支持度的擴(kuò)展性,Data set T25I20D100K,37,關(guān)聯(lián)規(guī)則結(jié)果顯示 (Table Form ),38,關(guān)聯(lián)規(guī)則可視化Using Plane Graph,39,關(guān)聯(lián)規(guī)則可視化