【正文】 高級(jí)人工智能 第十二章 史忠植 中國(guó)科學(xué)院計(jì)算技術(shù)研究所 關(guān)聯(lián)規(guī)則 Association Rules 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 2 內(nèi)容提要 ? 引言 ? Apriori 算法 ? FPgrowth 算法 ? 并行關(guān)聯(lián)規(guī)則挖掘 ? 多維關(guān)聯(lián)規(guī)則挖掘 ? 相關(guān)規(guī)則 ? 關(guān)聯(lián)規(guī)則改進(jìn) 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 3 關(guān)聯(lián)規(guī)則 ? 關(guān)聯(lián)規(guī)則反映一個(gè)事物與其他事物之間的相互依存性和關(guān)聯(lián)性。如果兩個(gè)或者多個(gè)事物之間存在一定的關(guān)聯(lián)關(guān)系，那么，其中一個(gè)事物就能夠通過(guò)其他事物預(yù)測(cè)到。 關(guān)聯(lián)規(guī)則表示了項(xiàng)之間的關(guān)系。 ? 示例 : cereal, milk ? fruit “ 買(mǎi)谷類(lèi)食品和牛奶的人也會(huì)買(mǎi)水果 .” 商店可以把牛奶和谷類(lèi)食品作特價(jià)品以使人們買(mǎi)更多的水果 . 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 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 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 5 基本概念 ? 通常 , 數(shù)據(jù)包含 : TID Basket 事務(wù) ID 項(xiàng)的子集 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 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)集 ,序列 ,等等 ) 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 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í) ,稱(chēng)作TID. IT ?}, . . . ,{ 21 miiiI ???????BAIBIABA,DTransactionid Items bought 10 A, B, C 20 A, C 30 A, D 40 B, E, F 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 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 ?????2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 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ā)生的概率 . 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 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)的頻度 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 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 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 12 頻繁項(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)集 ? 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 13 強(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ī)則 . 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 14 關(guān)聯(lián)規(guī)則挖掘 ? 兩個(gè)基本步驟 ? 找出所有的頻繁項(xiàng)集 ? 滿足最小支持度 ? 找出所有的強(qiáng)關(guān)聯(lián)規(guī)則 ? 由頻繁項(xiàng)集生成關(guān)聯(lián)規(guī)則 ? 保留滿足最小可信度的規(guī)則 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 15 內(nèi)容提要 ? 引言 ? Apriori 算法 ? FPgrowth 算法 ? 并行關(guān)聯(lián)規(guī)則挖掘 ? 多維關(guān)聯(lián)規(guī)則挖掘 ? 相關(guān)規(guī)則 ? 關(guān)聯(lián)規(guī)則改進(jìn) ? 總結(jié) 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 16 Apriori算法 ? IBM公司 Almaden研究中心的 等人在 1993年提出的 AIS和 SETM。 ? 在 1994年提出 Apriori和 AprioriTid。 Apriori和 AprioriTid算法利用前次過(guò)程中的數(shù)據(jù)項(xiàng)目集來(lái)生成新的候選數(shù)據(jù)項(xiàng)目集，減少了中間丌必要的數(shù)據(jù)項(xiàng)目集的生成，提高了效率 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 17 生成頻繁項(xiàng)集 ?Na239。ve algorithm n |D| for each subset s of I do l 0 for each transaction T in D do if s is a subset of T then l l + 1 if minimum support = l/n then add s to frequent subsets 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 18 生成頻繁項(xiàng)集 ? na239。ve algorithm的分析 ? I 的子集 : O(2m) ? 為每一個(gè)子集掃描 n個(gè)事務(wù) ? 測(cè)試 s為 T的子集 : O(2mn) ? 隨著項(xiàng)的個(gè)數(shù)呈指數(shù)級(jí)增長(zhǎng) ! ? 我們能否做的更好 ? 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 19 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也成立 . 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 20 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ù)作一次完全掃描 .. 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 21 生成頻繁項(xiàng)集 ? 中心思想 : 由頻繁 (k1)項(xiàng)集構(gòu)建候選 k項(xiàng)集 ? 方法 ? 找到所有的頻繁 1項(xiàng)集 ? 擴(kuò)展頻繁 (k1)項(xiàng)集得到候選 k項(xiàng)集 ? 剪除不滿足最小支持度的候選項(xiàng)集 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 22 Apriori: 一種候選項(xiàng)集生成 測(cè)試方法 ? Apriori 剪枝原理 : 若仸一項(xiàng)集是丌頻繁的 ,則其超集丌應(yīng)該被生成 /測(cè)試 ! ? 方法 : ? 由頻繁 k項(xiàng)集生成候選 (k+1)項(xiàng)集 ,并且 ? 在 DB中測(cè)試候選項(xiàng)集 ? 性能研究顯示了 Apriori算法是有效的和可伸縮(scalablility)的 . 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 23 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 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 24 Apriori 算法 Algorithm: Apriori 輸入 : Database, D, of transactions。 minimum support threshold,min_sup. 輸出 : L, freuqent itemsets in D. 過(guò)程 : Ck: Candidate itemset of size k Lk : frequent itemset of size k L1 = find_frequent_1_itemsets(D)。 for (k = 2。 Lk+1 !=?。 k++) do begin{ Ck = apriori_gen(Lk1 ,min_sup)。 for each transaction t in database D do{//scan D for counts Ct =subset(Ck ,t)。// get the subsets of t that are candidates For each candidate c? Ct ++。 } Lk = candidates in Ck with min_support }end return L=?k Lk。 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 25 Apriori 算法 Procedure apriori_gen(Lk1: frequent (k1)itemsets。 min_sup:minimum support threshold ) for each itemset l1? Lk1 for each itemset l2?Lk1 if(l1[1]=l2[1])? (l1[2]=l2[2]) ? … (l1[k1]=l2[k1]) Then{ c=join(l1,l2)//join step: generate candidates if has_infrequent_subset(c, Lk1 ) then delete c。//prune step: remove unfruitful candidate else add c to Ck } return Ck 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 26