【正文】 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 =, ..., =, = 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 27 Apriori 算法 Procedure has_infrequent_subset(c:candidate kitemset。Lk1: frequent (k1)itemsets。)//use prior knowledge for each (k1)subset s of c if s? Lk1 then return TRUE。 return FALSE. 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 28 Apriori 算法 ? 如何生成候選項(xiàng)集 ? ? 步驟 1: 自連接 Lk ? 步驟 2: 剪枝 ? 如何計(jì)算候選項(xiàng)集的支持度 ? ? 候選項(xiàng)庥生成的示例 ? L3={ abc, abd, acd, ace, bcd } ? 自連接 : L3*L3 ? 由 abc 和 abd 連接得到 abcd ? 由 acd 和 ace 連接得到 acde ? 剪枝 : ? 因?yàn)?ade 丌在 L3中 acde 被剪除 ? C4={abcd} 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 29 如何生成候選項(xiàng)集 ? ? 假定 Lk1中的項(xiàng)以一定順序排列 ? 步驟 1: 自連接 Lk1 insert into Ck select , , … , , from Lk1 p, Lk1 q where =, … , =, ? 步驟 2: 剪枝 forall itemsets c in Ck do forall (k1)subsets s of c do if (s is not in Lk1) then delete c from Ck 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 30 如何計(jì)算候選項(xiàng)集的支持度 ? ? 為何候選項(xiàng)集的支持度的計(jì)算是一個(gè)問題 ? ? 候選項(xiàng)集的總數(shù)可能是巨大的 ? 一個(gè)事務(wù)可能包含多個(gè)候選項(xiàng)集 ? 方法 : ? 候選項(xiàng)集被存儲(chǔ)在一個(gè)哈希樹 ? 哈希樹的 葉子結(jié)點(diǎn) 包含一個(gè)項(xiàng)集和計(jì)數(shù)的列表 ? 內(nèi)部結(jié)點(diǎn) 包含一個(gè)哈希表 ? 子集函數(shù) : 找出包含在一個(gè)事務(wù)中的所有候選項(xiàng)集 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 31 頻繁模式挖掘的挑戰(zhàn) ? 挑戰(zhàn) ? 多次掃描事務(wù)數(shù)據(jù)庫 ? 巨大數(shù)量的候選項(xiàng)集 ? 繁重的計(jì)算候選項(xiàng)集的支持度工作 ? 改進(jìn) Apriori: 大體的思路 ? 減少事務(wù)數(shù)據(jù)庫的掃描次數(shù) ? 縮減候選項(xiàng)集的數(shù)量 ? 使候選項(xiàng)集的支持度計(jì)算更加方便 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 32 AprioriTid算法 ? AprioriTid算法由 Apriori算法改進(jìn) ? 優(yōu)點(diǎn)：只和數(shù)據(jù)庫做一次交互，無須頻繁訪問數(shù)據(jù)庫 ? 將 Apirori中的 Ck 擴(kuò)展，內(nèi)容由 {c}變?yōu)?{TID， c}，TID用于唯一標(biāo)識(shí)事務(wù) ? 引入 Bk ， 使得 Bk 對(duì)于事務(wù)的項(xiàng)目組織集合，而不是被動(dòng)的等待 Ck 來匹配 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 33 AprioriTid算法 ? 舉例： minsupp = 2 ? 數(shù)據(jù)庫： TID 項(xiàng)目 100 1 3 4 200 2 3 5 300 1 2 3 5 400 2 5 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 34 AprioriTid算法 示例 TID 項(xiàng)目集 100 {1} {3} {4} 200 {2} {3} {5} 300 {1} {2} {3} {5} 400 {2} {5} 項(xiàng)集 支持度 {1} 2 {2} 3 {3} 3 {5} 3 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 35 ApioriTid算法示例 TID 項(xiàng)目集 100 {{1 3}} 200 {{2 3} {2 5} {3 5} } 300 {{1 2} {1 3} {1 5} {2 3} {2 5} {3 5}} 400 {{2 5}} 項(xiàng)集 支持度 {1 3} 2 {2 3} 2 {2 5} 3 {3 5} 2 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 36 ApioriTid算法示例 TID 項(xiàng)目集 100 空 200 {{2 3 5}} 300 {{2 3 5 }} 400 空 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 37 ApioriTid算法 ? 上面圖中分別為 Bk 和 Lk ， 而 Ck 和 Apriori算法產(chǎn)生的一樣，因此沒有寫出來 ? 可以看到 Bk 由 Bk1 得到，無須由數(shù)據(jù)庫取數(shù)據(jù) ? 缺點(diǎn)：內(nèi)存要求很大，事務(wù)過多的時(shí)候資源難以滿足 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 38 內(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ī)則 39 頻繁模式挖掘的瓶頸 ? 多次掃描數(shù)據(jù)庫是高代價(jià)的 ? 長模式的挖掘需要多次掃描數(shù)據(jù)庫以及生成許多的候選項(xiàng)集 ? 找出頻繁項(xiàng)集 i1i2…i100 ? 掃描次數(shù) : 100 ? 候選項(xiàng)集的數(shù)量 : (1001) + (1002) + … + (110000) = 21001 = *1030 ! ? 瓶頸 :候選項(xiàng)集 生成 測(cè)試 ? 我們能否避免生成候選項(xiàng)集 ? 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 40 不生成候選項(xiàng)集的頻繁模式挖掘 ? 利用局部頻繁的項(xiàng)由短模式增長為長模式 ? “abc” 是一個(gè)頻繁模式 ? 得到所有包含 “ abc” 的事務(wù) : DB|abc ? “d” 是 DB|abc 的一個(gè)局部頻繁的項(xiàng) ? abcd 是一個(gè)頻繁模式 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 41 FP Growth算法 (Han, Pei, Yin 2020) ? Apriori算法的一個(gè)有問題的方面是其候選項(xiàng)集的生成 ? 指數(shù)級(jí)增長的來源 ? 另一種方法是使用分而治乊的策略 (divide and conquer) ? 思想 : 將數(shù)據(jù)庫的信息壓縮成一個(gè)描述頻繁項(xiàng)相關(guān)信息的 頻繁模式樹 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 42 利用 FP樹進(jìn)行頻繁模式挖掘 ? 思想 : 頻繁模式增長 ? 遞歸地增長頻繁模式借助模式和數(shù)據(jù)庫劃分 ? 方法 ? 對(duì)每個(gè)頻繁項(xiàng) ,構(gòu)建它的條件模式基 ,然后構(gòu)建它的條件 FP樹 . ? 對(duì)每個(gè)新創(chuàng)建的條件 FP樹重復(fù)上述過程 ? 直至結(jié)果 FP樹為空 ,戒者它僅包含一個(gè)單一路徑 .該路徑將生成其所有的子路徑的組合 ,每個(gè)組合都是一個(gè)頻繁模式 . 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 43 頻繁 1項(xiàng)集 ? 最小支持度為 20% (計(jì)數(shù)為 2) TID Items 1 I1,I2,I5 2 I2,I4 3 I2,I3,I6 4 I1,I2,I4 5 I1,I3 6 I2,I3 7 I1,I3 8 I1,I2,I3,I5 9 I1,I2,I3 Itemset Support count {I1} 6 {I2} 7 {I3} 6 {I4} 2 {I5} 2 {I6} 1 Itemset Support count {I1} 6 {I2} 7 {I3} 6 {I4} 2 {I5} 2 事務(wù)數(shù)據(jù)庫 支持度計(jì)數(shù) 頻繁 1項(xiàng)集 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 44 FP樹 構(gòu)建 Itemset Support count {I1} 6 {I2} 7 {I3} 6 {I4} 2 {I5} 2 Itemset Support count {I2} 7 {I1} 6 {I3} 6 {I4} 2 {I5} 2 按支持度降序排列 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 45 FP樹 構(gòu)建 創(chuàng)建根結(jié)點(diǎn) null 掃描數(shù)據(jù)庫 事務(wù) 1: I1, I2, I5 排序 : I2, I1, I5 處理事務(wù) 以項(xiàng)的順序增加結(jié)點(diǎn) 標(biāo)注項(xiàng)及其計(jì)數(shù) (I2,1) (I1,1) (I5,1) 1 I5 0 I4 0 I3 1 I1 1 I2 維護(hù)索引表 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 46 FP樹 構(gòu)建 null (I2,2) (I1,1) (I5,1) 0 I5 1 I4 0 I3 0 I1 2 I2 (I4,1) TID Items 1 I1,I2,I5 2 I2,I4 3 I2,I3,I6 4 I1,I2,I4 5 I1,I3 6 I2,I3 7 I1,I3 8 I1,I2,I3,I5 9 I1,I2,I3 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 47 FP樹 構(gòu)建 null (I2,7) (I1,4) (I5,1) 2 I5 2 I4 6 I3 6 I1 7 I2 (I4,1) TID Items 1 I1,I2,I5 2 I2,I4 3 I2,I3,I6 4 I1,I2,I4 5 I1,I3 6 I2,I3 7 I1,I3 8 I1,I2,I3,I5 9 I1,I2,I3 (I3,2) (I3,2) (I1,2) (I3,2) (I4,1) (I5,1) 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 48 FP樹 構(gòu)建 ? 掃描事務(wù)數(shù)據(jù)庫 D一次 ,得到頻繁項(xiàng)的集合 F及它們的支持度 .將 F按支持度降序排列成 L,L是頻繁項(xiàng)的列表 . ? 創(chuàng)建 FP樹的根 , 標(biāo)注其為 D中的每個(gè)事務(wù)進(jìn)行以下操作 : ? 根據(jù) L中的次序?qū)κ聞?wù)中的頻繁項(xiàng)進(jìn)行選擇和排序 . 設(shè)事務(wù)中的已排序的頻繁項(xiàng)列表為 [p|P],其中 p表示第一個(gè)元素 ,P表示剩余的列表 .調(diào)用 insert_Tree([p|P],T). 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 49 FP樹 構(gòu)建 ? Insert_Tree([p|P],T) If T has a child N such that = , then increment N’s count by 1。 else create a new node N, and let its count be 1, its parent link be linked to T, and its node link to the nodes with the same itemname via the nodelink structure. If P is nonempty, call insert_tree(P,N) recursively. 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 50 挖掘 FPtree ? 從索引表中的最后一個(gè)項(xiàng)開始 ? 找到所有包含該項(xiàng)的路徑 ? 沿著結(jié)點(diǎn) 鏈接 (nodelinks) ? 確定條件模式 ? 路徑中符合頻度要求的模式 ? 構(gòu)建 FPtree C ? 添加項(xiàng)至 C中所有路徑 ,生成頻繁模式 ? 遞歸地挖掘 C (添加項(xiàng) ) ? 從索引表和樹中移除項(xiàng) 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 51 挖掘 FPTree null (I2,7) (I1,4) (I5,1) 2 I5 2 I4 6 I3 6 I1 7 I2 (I4,1) (I3,2) (I3,2) (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) 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 52 挖掘 F