【正文】 (I4,1) (I5,1) (I1,2) (I3,2) 前綴路徑 (I2 I1,1) (I2 I1 I3, 1) 條件路徑 (I2 I1, 2) 條件 FPtree (I2 I1 I5, 2), (I2 I5, 2), (I1 I5, 2) null (I2,2) (I1,2) 49 挖掘 FPTree 項(xiàng) 條件模式基 條件 FPtree 生成的頻繁模式 I5 {(I2 I1:1),(I2 I1 I3:1)} I2:2,I1:2 I2 I5:2, I1 I5:2, I2 I1 I5:2 I4 {(I2 I1:1),(I2:1)} I2:2 I2 I4:2 I3 {(I2 I1:2,(I2:2),(I1:2)} I2:4,I1:2, I1:2 I2 I3:4, I1 I3:2, I2 I1 I3:2 I1 {(I2:4)} I2:4 I2 I1:4 50 挖掘 FPTree Procedure FP_growth(Tree,?) (1) If Tree contains a single path P then (2) for each bination (denote as ?) of the nodes in the path P (3) generate pattern ??? with support = minisup of nodes in ?。)//use prior knowledge for each (k1)subset s of c if s? Lk1 then return TRUE。//prune step: remove unfruitful candidate else add c to Ck } return Ck 29 Apriori 算法 Join is generate candidates set of itemsets Ck from 2 itemsets in Lk1 Procedure join(p,q) insert into Ck select , ,..., , from Lk1 p, Lk1 q where =, ..., =, = 30 Apriori 算法 Procedure has_infrequent_subset(c:candidate kitemset。 28 Apriori 算法 Procedure apriori_gen(Lk1: frequent (k1)itemsets。// get the subsets of t that are candidates For each candidate c? Ct ++。 k++) do begin{ Ck = apriori_gen(Lk1 ,min_sup)。 for (k = 2。 su p ( ) su p ( ) /i i kkjjw w w w ww x w x n?? ? ? ?? ?令則27 Apriori 算法 Algorithm: Apriori 輸入 : Database, D, of transactions。39。39。 s u p ( ) ( ) s u p ( )kjjw x w xk ?? ?1239。( sup ( ) )w port w port X Y?12{ , , .... }mI i i i?25 加權(quán)關(guān)聯(lián)規(guī)則的描述 ? 對(duì)于項(xiàng)目集 X、 Y， ， X ∩Y = φ ，如果有 wsup( X ∪Y )≥wminsup ，且 conf(X→Y)≥minconf ，則稱(chēng) X→Y 是一條加權(quán)關(guān)聯(lián)規(guī)則。 ? 形如 X → Y 的關(guān)聯(lián)規(guī)則的加權(quán)支持度為： ? 置 信 度 的 定 義 仍 然 沿 用 Apriori算 法 里 的 定 義 ， 即 ： conf (X →Y) = sup(X ∪Y)/sup(X ) 。事先指定最小加權(quán)支持度閾值為 wminsup和最小置信度閾值 minconf。 24 加權(quán)關(guān)聯(lián)規(guī)則的描述 ? 設(shè) 是項(xiàng)的集合， 每個(gè)項(xiàng)都有一個(gè)權(quán)值與之對(duì)應(yīng)。ve algorithm的分析 ? I 的子集 : O(2m) ? 為每一個(gè)子集掃描 n個(gè)事務(wù) ? 測(cè)試 s為 T的子集 : O(2mn) ? 隨著項(xiàng)的個(gè)數(shù)呈指數(shù)級(jí)增長(zhǎng) ! ? 我們能否做的更好 ? 18 Apriori 性質(zhì) ? 定理 (Apriori 性質(zhì) ): 若 A是一個(gè)頻繁項(xiàng)集 ,則 A的每一個(gè)子集都是一個(gè)頻繁項(xiàng)集 . ? 證明 :設(shè) n為事務(wù)數(shù) .假設(shè) A是 l個(gè)事務(wù)的子集 ,若 A’ ? A , 則 A’ 為 l’ (l’ ? l )個(gè)事務(wù)的子集 .因此 , l/n ≥s( 最小支持度 ), l’/n ≥s 也成立 . 19 Apriori 算法 ? Apriori算法是一種經(jīng)典的生成布爾型關(guān)聯(lián)規(guī)則的頻繁項(xiàng)集挖掘算法 .算法名字是緣于算法使用了頻繁項(xiàng)集的性質(zhì)這一先驗(yàn)知識(shí) . ? 思想 : Apriori 使用了一種稱(chēng)作 levelwise搜索的迭代方法 ,其中 k項(xiàng)集被用作尋找 (k+1)項(xiàng)集 . 首先 ,找出頻繁 1項(xiàng)集 ,以 L1表示 .L1用來(lái)尋找 L2,即頻繁 2項(xiàng)集的集合 .L2用來(lái)尋找 L3,以此類(lèi)推 ,直至沒(méi)有新的頻繁 k項(xiàng)集被發(fā)現(xiàn) .每個(gè) Lk都要求對(duì)數(shù)據(jù)庫(kù)作一次完全掃描 .. 20 生成頻繁項(xiàng)集 ? 中心思想 : 由頻繁 (k1)項(xiàng)集構(gòu)建候選 k項(xiàng)集 ? 方法 ? 找到所有的頻繁 1項(xiàng)集 ? 擴(kuò)展頻繁 (k1)項(xiàng)集得到候選 k項(xiàng)集 ? 剪除不滿足最小支持度的候選項(xiàng)集 21 Apriori: 一種候選項(xiàng)集生成 測(cè)試方法 ? Apriori 剪枝原理 : 若任一項(xiàng)集是不頻繁的 ,則其超集不應(yīng)該被生成 /測(cè)試 ! ? 方法 : ? 由頻繁 k項(xiàng)集生成候選 (k+1)項(xiàng)集 ,并且 ? 在 DB中測(cè)試候選項(xiàng)集 ? 性能研究顯示了 Apriori算法是有效的和可伸縮(scalablility)的 . 22 The Apriori 算法 —一個(gè)示例 Database TDB 1st scan C1 L1 L2 C2 C2 2nd scan C3 L3 3rd scan Tid Items 10 A, C, D 20 B, C, E 30 A, B, C, E 40 B, E Itemset sup {A} 2 {B} 3 {C} 3 {D} 1 {E} 3 Itemset sup {A} 2 {B} 3 {C} 3 {E} 3 Itemset {A, B} {A, C} {A, E} {B, C} {B, E} {C, E} Itemset sup {A, B} 1 {A, C} 2 {A, E} 1 {B, C} 2 {B, E} 3 {C, E} 2 Itemset sup {A, C} 2 {B, C} 2 {B, E} 3 {C, E} 2 Itemset {B, C, E} Itemset sup {B, C, E} 2 23 加權(quán)關(guān)聯(lián)規(guī)則挖掘 ? 傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法通常都認(rèn)為數(shù)據(jù)庫(kù)里每個(gè)項(xiàng)目都有相同的重要性，沒(méi)有主要、次要之分。1 關(guān)聯(lián)規(guī)則 Association Rules 2 內(nèi)容提要 ? 引言 ? Apriori 算法 ? Frequentpattern tree 和 FPgrowth 算法 ? 多維關(guān)聯(lián)規(guī)則挖掘 ? 相關(guān)規(guī)則 ? 基于約束的關(guān)聯(lián)規(guī)則挖掘 ? 總結(jié) 3 關(guān)聯(lián)規(guī)則 ? 關(guān)聯(lián)規(guī)則表示了項(xiàng)之間的關(guān)系 ? 示例 : cereal, milk ? fruit ―買(mǎi)谷類(lèi)食品和牛奶的人也會(huì)買(mǎi)水果 .‖ 商店可以把牛奶和谷類(lèi)食品作特價(jià)品以使人們買(mǎi)更多的水果 . 4 市場(chǎng)購(gòu)物籃分析 ? 分析事務(wù)數(shù)據(jù)庫(kù)表 ? 我們是否可假定 ? ? Chips = Salsa Lettuce = Spinach Person Basket A Chips, Salsa, Cookies, Crackers, Coke, Beer B Lettuce, Spinach, Oranges, Celery, Apples, Grapes C Chips, Salsa, Frozen Pizza, Frozen Cake D Lettuce, Spinach, Milk, Butter 5 基本概念 ? 通常 , 數(shù)據(jù)包含 : TID Basket 事務(wù) ID 項(xiàng)的子集 6 關(guān)聯(lián)規(guī)則挖掘 ?在事務(wù)數(shù)據(jù)庫(kù) ,關(guān)系數(shù)據(jù)庫(kù)和其它信息庫(kù)中的項(xiàng)或?qū)ο蟮募现g ,發(fā)現(xiàn)頻繁模式 ,關(guān)聯(lián) ,相關(guān) ,或因果關(guān)系的結(jié)構(gòu) . ? 頻繁模式 : 數(shù)據(jù)庫(kù)中出現(xiàn)頻繁的模式(項(xiàng)集 ,序列 ,等等 ) 7 基本概念 ? 項(xiàng)集 ? 事務(wù) ? 關(guān)聯(lián)規(guī)則 ? 事務(wù)數(shù)據(jù)集 (例如右圖 ) ? 事務(wù)標(biāo)識(shí) TID： 每一個(gè)事務(wù)關(guān)聯(lián)著一個(gè)標(biāo)識(shí) IT ?}, . . . ,{ 21 miiiI ???????BAIBIABA,DTransactionid Items bought 10 A, B, C 20 A, C 30 A, D 40 B, E, F 8 度量有趣的關(guān)聯(lián)規(guī)則 ? 支持度 s ? D中包含 A和 B 的事務(wù)數(shù)與總的事務(wù)數(shù)的比值 規(guī)則 A?B 在數(shù)據(jù)集 D中的支持度為 s, 其中 s 表示 D中包含 A?B (即同時(shí)包含 A和 B)的事務(wù)的百分率 . ||||||}|{||)(DTBADTBAs ?????9 度量有趣的關(guān)聯(lián)規(guī)則 ? 可信度 c ? D中同時(shí)包含 A和 B的事務(wù)數(shù)與只包含 A的事務(wù)數(shù)的比值 ||}|{|| ||}|{||)( TADT TBADTBAc ?? ?????規(guī)則 A?B 在數(shù)據(jù)集 D中的 可信 度為 c, 其中 c表示 D中包含 A的事務(wù)中也包含 B的百分率 .即可用條件概率P(B|A)表示 . confidence(A ? B )=P(B|A) 條件概率 P(B|A) 表示 A發(fā)生的條件下 B也發(fā)生的概率 . 10 度量有趣的關(guān)聯(lián)規(guī)則 ? 關(guān)聯(lián)規(guī)則根據(jù)以下兩個(gè)標(biāo)準(zhǔn) (包含或排除 ): ? 最小支持度 – 表示規(guī)則中的所有項(xiàng)在事務(wù)中出現(xiàn)的頻度 ? 最小可信度 表示規(guī)則中左邊的項(xiàng) (集 )的出現(xiàn)暗示著右邊的項(xiàng) (集 )出現(xiàn)的頻度 11 市場(chǎng)購(gòu)物籃分析 I是什么 ? 事務(wù) ID B的 T是什么 ? s(Chips=Salsa) 是什么 ? c(Chips=Salsa)是什么 ? 事務(wù) ID 購(gòu)物籃 A Chips, Salsa, Cookies, Crackers, Coke, Beer B Lettuce, Spinach, Oranges, Celery, Apples, Grapes C Chips, Salsa, Frozen Pizza, Frozen Cake D Lettuce, Spinach, Milk, Butter, Chips 12 Step one: 頻繁項(xiàng)集 ? 項(xiàng)集 – 任意項(xiàng)的集合 ? k項(xiàng)集 – 包含 k個(gè)項(xiàng)的項(xiàng)集 ? 頻繁 (或大 )項(xiàng)集 – 滿足最小支持度的項(xiàng)集 ? 若 I包含 m個(gè)項(xiàng) ,那么可以產(chǎn)生多少個(gè)項(xiàng)集 ? 13 Step two:強(qiáng)關(guān)聯(lián)規(guī)則 ? 給定一個(gè)項(xiàng)集 ,容易生成關(guān)聯(lián)規(guī)則 . ? 項(xiàng)集 : {Chips, Salsa, Beer} ? Beer, Chips = Salsa ? Beer, Salsa = Chips ? Chips, Salsa = Beer ? 強(qiáng)規(guī)則是有趣的 ? 強(qiáng)規(guī)則通常定義為那些滿足最小支持度和最小可信度的規(guī)則 . 14 關(guān)聯(lián)規(guī)則挖掘 ? 兩個(gè)基本步驟 ? Step one:找出所有的頻繁項(xiàng)集 ?滿足最小支持度 ? Step two:找出所有的強(qiáng)關(guān)聯(lián)規(guī)則 ?由頻繁項(xiàng)集生成關(guān)聯(lián)規(guī)則 ?保留滿足最小可信度的規(guī)則 15 內(nèi)容提要 ? 引言 ? Apriori 算法 ? Frequentpattern tree